論文の概要: Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2309.14506v1
- Date: Mon, 25 Sep 2023 20:13:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 18:28:05.114212
- Title: Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms
- Title(参考訳): ゼロ次リーマン平均確率近似アルゴリズム
- Authors: Jiaxiang Li, Krishnakumar Balasubramanian and Shiqian Ma
- Abstract要約: textttZo-RASAは$epsilon$-approximation 1次定常解を生成するのに最適なサンプル複雑性を実現する。
指数写像や並列輸送の代わりに幾何とベクトル輸送を用いることで,アルゴリズムの実用性を向上させる。
- 参考スコア(独自算出の注目度): 19.99781875916751
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present Zeroth-order Riemannian Averaging Stochastic Approximation
(\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian
manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities
for generating $\epsilon$-approximation first-order stationary solutions using
only one-sample or constant-order batches in each iteration. Our approach
employs Riemannian moving-average stochastic gradient estimators, and a novel
Riemannian-Lyapunov analysis technique for convergence analysis. We improve the
algorithm's practicality by using retractions and vector transport, instead of
exponential mappings and parallel transports, thereby reducing per-iteration
complexity. Additionally, we introduce a novel geometric condition, satisfied
by manifolds with bounded second fundamental form, which enables new error
bounds for approximating parallel transport with vector transport.
- Abstract(参考訳): リーマン多様体上の確率最適化のためのゼロ階リーマン平均確率近似 (\texttt{Zo-RASA}) アルゴリズムを提案する。
各イテレーションで1つのサンプルまたは定数のバッチのみを使用して、$\epsilon$-approximation 1-order stationary solutionを生成するための最適なサンプル複素性が得られることを示す。
本手法はリーマン移動平均確率勾配推定器と新しいリーマン-リャプノフ解析手法を用いた収束解析を行う。
指数写像や並列トランスポートの代わりに、引き算とベクトル輸送を用いてアルゴリズムの実用性を向上させることにより、イテレーション毎の複雑性を低減できる。
さらに,ベクトル輸送による並列輸送を近似するための新しい誤差境界を実現するため, 2次基本形式が有界な多様体で満たされる新しい幾何学的条件を導入する。
関連論文リスト
- Convergence and complexity of block majorization-minimization for
constrained block-Riemannian optimization [20.128697661112618]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳(メタデータ) (2023-12-16T05:40:19Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Faster Riemannian Newton-type Optimization by Subsampling and Cubic
Regularization [3.867143522757309]
この研究は、制約集合が多様体構造を意味するような制約付き大規模非制約最適化に関するものである。
本稿では,収束性の向上と計算コストの削減を目的とした2階サドル最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-22T00:37:44Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳(メタデータ) (2022-08-09T07:36:25Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳(メタデータ) (2022-06-04T18:53:44Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳(メタデータ) (2021-09-13T16:13:13Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - New Riemannian preconditioned algorithms for tensor completion via
polyadic decomposition [10.620193291237262]
これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。
提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。
合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
論文 参考訳(メタデータ) (2021-01-26T22:11:06Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。