論文の概要: Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
- arxiv url: http://arxiv.org/abs/2007.11612v4
- Date: Thu, 8 Jul 2021 06:45:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 22:19:53.631598
- Title: Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
- Title（参考訳）: Chi-Squared と Renyi Divergence におけるLangevin Monte Carlo の収束
- Authors: Murat A. Erdogdu, Rasa Hosseinzadeh, Matthew S. Zhang
- Abstract要約: 推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
- 参考スコア（独自算出の注目度）: 8.873449722727026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study sampling from a target distribution $\nu_* = e^{-f}$ using the
unadjusted Langevin Monte Carlo (LMC) algorithm when the potential $f$
satisfies a strong dissipativity condition and it is first-order smooth with a
Lipschitz gradient. We prove that, initialized with a Gaussian random vector
that has sufficiently small variance, iterating the LMC algorithm for
$\widetilde{\mathcal{O}}(\lambda^2 d\epsilon^{-1})$ steps is sufficient to
reach $\epsilon$-neighborhood of the target in both Chi-squared and Renyi
divergence, where $\lambda$ is the logarithmic Sobolev constant of $\nu_*$. Our
results do not require warm-start to deal with the exponential dimension
dependency in Chi-squared divergence at initialization. In particular, for
strongly convex and first-order smooth potentials, we show that the LMC
algorithm achieves the rate estimate $\widetilde{\mathcal{O}}(d\epsilon^{-1})$
which improves the previously known rates in both of these metrics, under the
same assumptions. Translating this rate to other metrics, our results also
recover the state-of-the-art rate estimates in KL divergence, total variation
and $2$-Wasserstein distance in the same setup. Finally, as we rely on the
logarithmic Sobolev inequality, our framework covers a range of non-convex
potentials that are first-order smooth and exhibit strong convexity outside of
a compact region.
- Abstract（参考訳）: 目標分布である$\nu_* = e^{-f}$ からのサンプリングを、未調整のlangevin monte carlo (lmc) アルゴリズムを用いて検討した。
十分小さい分散を持つガウス確率ベクトルで初期化され、lmcアルゴリズムで$\widetilde{\mathcal{o}}(\lambda^2 d\epsilon^{-1})を反復すると、chi-squared と renyi の発散において目標値の$\epsilon$-neighborhoodに達するのに十分であることが証明され、ここで $\lambda$ は $\nu_*$ の対数ソボレフ定数である。
その結果,初期化時のchi-squared divergenceの指数的次元依存性に対処するためにウォームスタートは不要である。
特に、強凸および一階の滑らかなポテンシャルに対して、lmcアルゴリズムは、同じ仮定の下で、これらのメトリクスの既知のレートを改善するレート推定値$\widetilde{\mathcal{o}}(d\epsilon^{-1})$を達成する。
このレートを他の測定値に換算すると、我々の結果はKLの発散率、総変量、ワッサーシュタイン距離の2ドルを同じ設定で再現する。
最後に、対数ソボレフ不等式に依存するので、この枠組みは一階滑らかでコンパクトな領域の外で強い凸性を示す非凸ポテンシャルの範囲をカバーする。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Variable Selection in Convex Piecewise Linear Regression [5.366354612549172]
本稿では,凸片方向線形回帰における変数選択の解としてスパース勾配を提案する。
亜ガウス雑音下でのSpGDには非漸近局所収束解析が提供される。
論文 参考訳（メタデータ） (2024-11-04T16:19:09Z) - Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - Forward-backward Gaussian variational inference via JKO in the
Bures-Wasserstein Space [19.19325201882727]
変分推論 (VI) は、ターゲット分布の$pi$を、抽出可能な分布の族の元によって近似しようとする。
本研究では,フォワード・バック・ガウス変分推論(FB-GVI)アルゴリズムを開発し,ガウスVIを解く。
提案アルゴリズムでは,$pi$ が log-smooth かつ log-concave である場合に,最先端の収束保証が得られる。
論文 参考訳（メタデータ） (2023-04-10T19:49:50Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。