論文の概要: Convergence Analysis of Riemannian Stochastic Approximation Schemes

• arxiv url: http://arxiv.org/abs/2005.13284v3
• Date: Wed, 19 May 2021 14:25:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-28 08:29:37.488022
• Title: Convergence Analysis of Riemannian Stochastic Approximation Schemes
• Title（参考訳）: リーマン確率近似スキームの収束解析
• Authors: Alain Durmus, Pablo Jim\'enez, \'Eric Moulines, Salem Said, Hoi-To Wai
• Abstract要約: 本稿では,最適化問題に取り組むための相関近似 (SA) スキームのクラスを解析する。 得られた条件は, 従来よりかなり軽度であることを示す。 第3に、平均場関数を小さなバイアスにしか推定できない場合、および/または、サンプルが鎖から引き出される場合を考える。
• 参考スコア（独自算出の注目度）: 39.32179384256228
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper analyzes the convergence for a large class of Riemannian stochastic approximation (SA) schemes, which aim at tackling stochastic optimization problems. In particular, the recursions we study use either the exponential map of the considered manifold (geodesic schemes) or more general retraction functions (retraction schemes) used as a proxy for the exponential map. Such approximations are of great interest since they are low complexity alternatives to geodesic schemes. Under the assumption that the mean field of the SA is correlated with the gradient of a smooth Lyapunov function (possibly non-convex), we show that the above Riemannian SA schemes find an ${\mathcal{O}}(b_\infty + \log n / \sqrt{n})$-stationary point (in expectation) within ${\mathcal{O}}(n)$ iterations, where $b_\infty \geq 0$ is the asymptotic bias. Compared to previous works, the conditions we derive are considerably milder. First, all our analysis are global as we do not assume iterates to be a-priori bounded. Second, we study biased SA schemes. To be more specific, we consider the case where the mean-field function can only be estimated up to a small bias, and/or the case in which the samples are drawn from a controlled Markov chain. Third, the conditions on retractions required to ensure convergence of the related SA schemes are weak and hold for well-known examples. We illustrate our results on three machine learning problems.
• Abstract（参考訳）: 本稿では、確率最適化問題に取り組むためのリーマン確率近似(sa)スキームの大規模クラスに対する収束解析を行う。 特に、我々が研究する再帰は、検討された多様体(測地スキーム)の指数写像または指数写像の代用として使われるより一般的な退化関数(退化スキーム)を使用する。 このような近似は測地学的なスキームに代わる複雑さの低いものであるので、非常に興味深い。 SA の平均場が滑らかなリャプノフ函数の勾配(おそらくは非凸)と相関しているという仮定の下で、上記のリーマン SA スキームが ${\mathcal{O}}(b_\infty + \log n / \sqrt{n})$-定常点(予想)を${\mathcal{O}}(n)$イテレーション内で見つけることを示し、$b_\infty \geq 0$ は漸近バイアスである。 以前の作品と比較して、私たちが引き起こす条件はかなり緩やかです。 まず、イテレートをa-プリオリ境界と仮定しないので、すべての解析はグローバルです。 次に、偏りのあるSAスキームについて検討する。 より具体的には、平均場関数が小さなバイアスまでしか推定できない場合と、そのサンプルが制御されたマルコフ連鎖から引き出される場合を考える。 第三に、関連するSAスキームの収束を保証するのに必要なリトラクション条件は弱く、よく知られた例では保たれる。 我々は3つの機械学習問題について結果を説明する。

関連論文リスト

• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
  論文  参考訳（メタデータ） (2024-04-19T06:24:22Z)
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。 分析として,勾配の非収束に関連する神話や伝説について考察した。
  論文  参考訳（メタデータ） (2023-10-19T17:58:59Z)
• The Curse of Memory in Stochastic Approximation: Extended Version [1.534667887016089]
  適応制御の初期から、制御システムコミュニティ内で近似の理論と応用が成長してきた。 近年の結果, (十分小さい) ステップサイズ$alpha>0$のSAの顕著な性能が確認されている。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  教師付き学習環境では、計量 0 がアセシアンレート $lambda で収縮している場合、それは一様に$math であることを示す。 結果は、連続および安定な $-time において、勾配と決定論的損失曲面を保っている。 それらは、Descent$凸面や強い凸損失面など、ある種の線形な設定で最適であることを示すことができる。
  論文  参考訳（メタデータ） (2022-01-17T23:08:47Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。