論文の概要: Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling
- arxiv url: http://arxiv.org/abs/2010.09597v2
- Date: Tue, 23 Feb 2021 07:15:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 21:21:42.417939
- Title: Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling
- Title（参考訳）: 非対数サンプリングのための確率勾配ランジュバンダイナミクスの高速収束
- Authors: Difan Zou and Pan Xu and Quanquan Gu
- Abstract要約: 我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
- 参考スコア（独自算出の注目度）: 110.88857917726276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a new convergence analysis of stochastic gradient Langevin
dynamics (SGLD) for sampling from a class of distributions that can be
non-log-concave. At the core of our approach is a novel conductance analysis of
SGLD using an auxiliary time-reversible Markov Chain. Under certain conditions
on the target distribution, we prove that $\tilde O(d^4\epsilon^{-2})$
stochastic gradient evaluations suffice to guarantee $\epsilon$-sampling error
in terms of the total variation distance, where $d$ is the problem dimension.
This improves existing results on the convergence rate of SGLD (Raginsky et
al., 2017; Xu et al., 2018). We further show that provided an additional
Hessian Lipschitz condition on the log-density function, SGLD is guaranteed to
achieve $\epsilon$-sampling error within $\tilde O(d^{15/4}\epsilon^{-3/2})$
stochastic gradient evaluations. Our proof technique provides a new way to
study the convergence of Langevin-based algorithms and sheds some light on the
design of fast stochastic gradient-based sampling algorithms.
- Abstract（参考訳）: 確率勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行い、非log-concaveとなる分布のクラスからサンプリングする。
我々のアプローチの核心は、時間反転可能なマルコフ連鎖を用いたSGLDの新しいコンダクタンス解析である。
対象分布の特定の条件下では、$\tilde O(d^4\epsilon^{-2})$ stochastic gradient evaluations は、$d$が問題次元であるような全変動距離の点で$\epsilon$-sampling誤差を保証するのに十分である。
これにより、SGLD(Raginsky et al., 2017; Xu et al., 2018)の収束率に関する既存の結果が改善される。
さらに、ログ密度関数にヘッセン・リプシッツ条件を付加すると、SGLDは$\tilde O(d^{15/4}\epsilon^{-3/2})$確率勾配評価において$\epsilon$-sampling誤差を達成することが保証される。
本手法は,ランジュバンに基づくアルゴリズムの収束を研究する新しい方法を提供し,高速確率的勾配に基づくサンプリングアルゴリズムの設計に光を当てる。
関連論文リスト
- Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - A sharp uniform-in-time error estimate for Stochastic Gradient Langevin
Dynamics [11.437892757715877]
グラディエント・ランゲヴィン・ダイナミクス(SGLD)の急激な一様誤差推定法を確立する。
我々は、SGLD反復とランゲヴィン拡散の間のKL分割に対する一様時間$O(eta2)$バウンドを得る。
論文 参考訳（メタデータ） (2022-07-19T14:38:52Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Wasserstein distance estimates for the distributions of numerical
approximations to ergodic stochastic differential equations [0.3553493344868413]
エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。
これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
論文 参考訳（メタデータ） (2021-04-26T07:50:04Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。