論文の概要: Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators
- arxiv url: http://arxiv.org/abs/2303.10599v2
- Date: Sat, 23 Mar 2024 13:26:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-27 03:58:21.466710
- Title: Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators
- Title（参考訳）: MCMC推定器を用いた確率勾配の収束解析
- Authors: Tianyou Li, Fan Chen, Huajie Chen, Zaiwen Wen,
- Abstract要約: 勾配降下(SGD)とその変種は機械学習に不可欠である。
本稿では,マルコフ連鎖モンテカルロ(MCMC)推定器を用いて勾配を計算するSGDアルゴリズムについて考察する。
MCMC-SGDはサドル点から脱出し、$(epsilon,epsilon1/4)$2次定常点に達することが示されている。
- 参考スコア（独自算出の注目度）: 8.493584276672971
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding stochastic gradient descent (SGD) and its variants is essential for machine learning. However, most of the preceding analyses are conducted under amenable conditions such as unbiased gradient estimator and bounded objective functions, which does not encompass many sophisticated applications, such as variational Monte Carlo, entropy-regularized reinforcement learning and variational inference. In this paper, we consider the SGD algorithm that employ the Markov Chain Monte Carlo (MCMC) estimator to compute the gradient, called MCMC-SGD. Since MCMC reduces the sampling complexity significantly, it is an asymptotically convergent biased estimator in practice. Moreover, by incorporating a general class of unbounded functions, it is much more difficult to analyze the MCMC sampling error. Therefore, we assume that the function is sub-exponential and use the Bernstein inequality for non-stationary Markov chains to derive error bounds of the MCMC estimator. Consequently, MCMC-SGD is proven to have a first order convergence rate $O(\log K/\sqrt{n K})$ with $K$ iterations and a sample size $n$. It partially explains how MCMC influences the behavior of SGD. Furthermore, we verify the correlated negative curvature condition under reasonable assumptions. It is shown that MCMC-SGD escapes from saddle points and reaches $(\epsilon,\epsilon^{1/4})$ approximate second order stationary points or $\epsilon^{1/2}$-variance points at least $O(\epsilon^{-11/2}\log^{2}(1/\epsilon) )$ steps with high probability. Our analysis unveils the convergence pattern of MCMC-SGD across a broad class of stochastic optimization problems, and interprets the convergence phenomena observed in practical applications.
- Abstract（参考訳）: 確率勾配勾配(SGD)とその変種を理解することは、機械学習に不可欠である。
しかし、上記の分析のほとんどは、非バイアス勾配推定器(英語版)や有界対象関数(英語版)のような可換な条件下で行われ、これは変分モンテカルロ(英語版)、エントロピー規則化強化学習(英語版)、変分推論(英語版)など、多くの高度な応用を包含していない。
本稿では,MCMC-SGDと呼ばれる,マルコフ連鎖モンテカルロ(MCMC)推定器を用いて勾配を計算するSGDアルゴリズムについて考察する。
MCMCはサンプリングの複雑さを著しく低減するため、実際には漸近的に収束するバイアス推定器である。
さらに、非有界関数の一般クラスを組み込むことで、MCMCサンプリング誤差を解析することがより困難になる。
したがって、関数は部分指数関数であると仮定し、非定常マルコフ鎖に対してベルンシュタイン不等式を用いてMCMC推定器の誤差境界を導出する。
したがって、MCMC-SGD は 1次収束率 $O(\log K/\sqrt{n K})$ と $K$ の反復とサンプルサイズ $n$ を持つことが証明されている。
MCMCがSGDの挙動にどのように影響するかを部分的に説明している。
さらに、合理的な仮定の下で相関負曲率条件を検証する。
MCMC-SGDはサドル点から脱出し、$(\epsilon,\epsilon^{1/4})$近似2次定常点または$\epsilon^{1/2}$分散点が少なくとも$O(\epsilon^{-11/2}\log^{2}(1/\epsilon))$ステップに達する。
本稿では, MCMC-SGDの収束パターンを, 確率的最適化問題の幅広いクラスにわたって明らかにし, 実用化における収束現象を解釈する。
関連論文リスト
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Stochastic Approximation with Biased MCMC for Expectation Maximization [9.4641739998927]
マルコフ連鎖モンテカルロを用いた近似スキームはMCMC-SAEMと呼ばれるアルゴリズムを作成するのに利用できる。
MCMC-SAEMは、理論上はあまり理解されていないMCMCアルゴリズムによってしばしば実行される。
ULA はランゲヴィンの段階的な選択に関してより安定であり、時としてより高速な収束をもたらすことが示される。
論文 参考訳（メタデータ） (2024-02-27T20:10:03Z) - Sharper Analysis for Minibatch Stochastic Proximal Point Methods:
Stability, Smoothness, and Deviation [41.082982732100696]
我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。
ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。
小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
論文 参考訳（メタデータ） (2023-01-09T00:13:34Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳（メタデータ） (2021-10-13T17:47:39Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Estimation in Tensor Ising Models [5.161531917413708]
N$ノード上の分布から1つのサンプルを与えられた$p$-tensor Isingモデルの自然パラメータを推定する問題を考える。
特に、$sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model。
我々は、$p$-tensor Curie-Weiss モデルの特別な場合における MPL 推定の正確なゆらぎを導出する。
論文 参考訳（メタデータ） (2020-08-29T00:06:58Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。