論文の概要: Optimal dimension dependence of the Metropolis-Adjusted Langevin
Algorithm
- arxiv url: http://arxiv.org/abs/2012.12810v1
- Date: Wed, 23 Dec 2020 17:14:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 17:58:55.611268
- Title: Optimal dimension dependence of the Metropolis-Adjusted Langevin
Algorithm
- Title（参考訳）: メトロポリス調整ランジュバンアルゴリズムの最適次元依存性
- Authors: Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic,
Philippe Rigollet
- Abstract要約: ログスムースと強くログ凹分布のクラス上のMALAの混合時間は$O(d)$です。
メトロポリタン調整の投影特性に基づく新しい技術は、ランゲビンSDEのよく研究された離散分析にMALAの研究を減少させる。
- 参考スコア（独自算出の注目度）: 22.19906823739798
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conventional wisdom in the sampling literature, backed by a popular diffusion
scaling limit, suggests that the mixing time of the Metropolis-Adjusted
Langevin Algorithm (MALA) scales as $O(d^{1/3})$, where $d$ is the dimension.
However, the diffusion scaling limit requires stringent assumptions on the
target distribution and is asymptotic in nature. In contrast, the best known
non-asymptotic mixing time bound for MALA on the class of log-smooth and
strongly log-concave distributions is $O(d)$. In this work, we establish that
the mixing time of MALA on this class of target distributions is
$\widetilde\Theta(d^{1/2})$ under a warm start. Our upper bound proof
introduces a new technique based on a projection characterization of the
Metropolis adjustment which reduces the study of MALA to the well-studied
discretization analysis of the Langevin SDE and bypasses direct computation of
the acceptance probability.
- Abstract（参考訳）: 一般的な拡散スケーリングの限界に裏打ちされた標本文献における従来の知見は、メトロポリス調整ランジュバンアルゴリズム(mala)の混合時間は、次元が$d$である場合、$o(d^{1/3})$にスケールすることを示唆している。
しかし、拡散スケーリング限界は対象分布に厳密な仮定を必要とし、本質的に漸近的である。
対照的に、対数平滑かつ強対数凹分布のクラス上でMALAが有する最もよく知られた非漸近混合時間は$O(d)$である。
本研究は, 対象分布のクラスにおけるMALAの混合時間は, 温かい開始条件下で$\widetilde\Theta(d^{1/2})$であることを示す。
上界証明では,MALAの学習をLangevin SDEのよく研究された離散化解析に還元し,受理確率の直接計算を回避し,メトロポリス調整の投影特性に基づく新しい手法を導入する。
関連論文リスト
- Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。
我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
論文 参考訳（メタデータ） (2024-08-25T10:28:31Z) - An Improved Analysis of Langevin Algorithms with Prior Diffusion for
Non-Log-Concave Sampling [27.882407333690267]
本研究では, 先行拡散を用いた改良型ランゲヴィンアルゴリズムが, 強対数対数対象分布に対して独立に次元を収束させることができることを示す。
また、修正したランゲヴィンアルゴリズムは、異なるステップサイズスケジュールを持つKL発散の次元非依存収束も得ることを証明した。
論文 参考訳（メタデータ） (2024-03-10T11:50:34Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳（メタデータ） (2023-06-27T08:15:28Z) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。
近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。
有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
論文 参考訳（メタデータ） (2023-06-12T16:28:11Z) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
離散空間におけるMetropolis-Hastings (M-H) アルゴリズムの効率は、対象分布に依存しない受容率によって特徴づけられることを示す。
最適受容率の知識は、連続空間におけるステップサイズ制御と直接的に類似して、離散空間における提案分布の近傍サイズを自動的に調整することを可能にする。
論文 参考訳（メタデータ） (2022-09-16T22:09:53Z) - Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for
Log-Concave Sampling [2.9972063833424216]
対数平滑かつ強い対数凹分布からサンプリングするために,メトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。
温暖化開始時に最適なミニマックス混合時間を確立する。
論文 参考訳（メタデータ） (2021-09-27T14:02:27Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。