論文の概要: Approximating Metric Magnitude of Point Sets
- arxiv url: http://arxiv.org/abs/2409.04411v1
- Date: Fri, 6 Sep 2024 17:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-09 15:05:01.234121
- Title: Approximating Metric Magnitude of Point Sets
- Title(参考訳): 点集合の計量マグニチュードの近似
- Authors: Rayna Andreeva, James Ward, Primoz Skraba, Jie Gao, Rik Sarkar,
- Abstract要約: 計量等級は、多くの望ましい幾何学的性質を持つ点雲の「大きさ」の尺度である。
様々な数学的文脈に適応しており、最近の研究は機械学習と最適化アルゴリズムを強化することを示唆している。
本稿では, 等級問題について検討し, 効率よく近似する方法を示し, 凸最適化問題として扱うことができるが, 部分モジュラ最適化としては適用できないことを示す。
本稿では,高速に収束し精度の高い反復近似アルゴリズムと,計算をより高速に行うサブセット選択法という,2つの新しいアルゴリズムについて述べる。
- 参考スコア(独自算出の注目度): 4.522729058300309
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Metric magnitude is a measure of the "size" of point clouds with many desirable geometric properties. It has been adapted to various mathematical contexts and recent work suggests that it can enhance machine learning and optimization algorithms. But its usability is limited due to the computational cost when the dataset is large or when the computation must be carried out repeatedly (e.g. in model training). In this paper, we study the magnitude computation problem, and show efficient ways of approximating it. We show that it can be cast as a convex optimization problem, but not as a submodular optimization. The paper describes two new algorithms - an iterative approximation algorithm that converges fast and is accurate, and a subset selection method that makes the computation even faster. It has been previously proposed that magnitude of model sequences generated during stochastic gradient descent is correlated to generalization gap. Extension of this result using our more scalable algorithms shows that longer sequences in fact bear higher correlations. We also describe new applications of magnitude in machine learning - as an effective regularizer for neural network training, and as a novel clustering criterion.
- Abstract(参考訳): 計量等級は、多くの望ましい幾何学的性質を持つ点雲の「大きさ」の尺度である。
様々な数学的文脈に適応しており、最近の研究は機械学習と最適化アルゴリズムを強化することを示唆している。
しかし、データセットが大きい場合や、繰り返し計算を行わなければならない場合(例えば、モデルトレーニング)には計算コストが制限される。
本稿では, 等級計算問題について検討し, 効率よく近似する方法を示す。
凸最適化問題としてキャストできるが、部分モジュラ最適化としては適用できないことを示す。
本稿では,高速に収束し精度の高い反復近似アルゴリズムと,計算をより高速に行うサブセット選択法という,2つの新しいアルゴリズムについて述べる。
確率勾配降下時に生じるモデル列の規模は一般化ギャップと相関することが従来提案されてきた。
よりスケーラブルなアルゴリズムを用いてこの結果を拡張することで、より長いシーケンスが実際に高い相関関係を持つことが示される。
また、ニューラルネットワークトレーニングの効果的な正規化ツールとして、また、新しいクラスタリング基準として、機械学習における新たなスケールの応用について説明する。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳(メタデータ) (2023-06-28T00:46:58Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳(メタデータ) (2023-03-30T15:48:26Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳(メタデータ) (2023-02-14T22:12:16Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳(メタデータ) (2022-04-12T16:27:49Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳(メタデータ) (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。