論文の概要: Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling

• arxiv url: http://arxiv.org/abs/2109.13055v1
• Date: Mon, 27 Sep 2021 14:02:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-28 21:44:40.130956
• Title: Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• Title（参考訳）: ログコンケーブサンプリングのためのメトロポリス調整ランジュバンアルゴリズムのミニマックス混合時間
• Authors: Keru Wu, Scott Schmidler, Yuansi Chen
• Abstract要約: 対数平滑かつ強い対数凹分布からサンプリングするために,メトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。 温暖化開始時に最適なミニマックス混合時間を確立する。
• 参考スコア（独自算出の注目度）: 2.9972063833424216
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the mixing time of the Metropolis-adjusted Langevin algorithm (MALA) for sampling from a log-smooth and strongly log-concave distribution. We establish its optimal minimax mixing time under a warm start. Our main contribution is two-fold. First, for a $d$-dimensional log-concave density with condition number $\kappa$, we show that MALA with a warm start mixes in $\tilde O(\kappa \sqrt{d})$ iterations up to logarithmic factors. This improves upon the previous work on the dependency of either the condition number $\kappa$ or the dimension $d$. Our proof relies on comparing the leapfrog integrator with the continuous Hamiltonian dynamics, where we establish a new concentration bound for the acceptance rate. Second, we prove a spectral gap based mixing time lower bound for reversible MCMC algorithms on general state spaces. We apply this lower bound result to construct a hard distribution for which MALA requires at least $\tilde \Omega (\kappa \sqrt{d})$ steps to mix. The lower bound for MALA matches our upper bound in terms of condition number and dimension. Finally, numerical experiments are included to validate our theoretical results.
• Abstract（参考訳）: 対数平滑かつ強い対数凹分布からサンプリングするために,メトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。 温暖化開始時に最適なミニマックス混合時間を確立する。 私たちの主な貢献は2つです。 まず、条件数$\kappa$を持つ$d$次元の対数凹密度に対して、暖かい開始値を持つMALAが、対数因子まで反復して$\tilde O(\kappa \sqrt{d})$となることを示す。 これにより、条件番号 $\kappa$ または dimension $d$ の依存関係に関する以前の作業が改善される。 我々の証明は、跳躍積分器と連続ハミルトニアン力学を比較することに依存し、そこでは受容率に束縛された新しい濃度を確立する。 第二に、一般状態空間上の可逆mcmcアルゴリズムに対するスペクトルギャップに基づく混合時間下界の証明を行う。 この下界の結果を適用して、MALAが混合するために少なくとも$\tilde \Omega (\kappa \sqrt{d})$ step を必要とするようなハード分布を構築する。 MALAの下位境界は条件数と次元の点で上界と一致する。 最後に,理論結果を検証するために数値実験を行う。

関連論文リスト

• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。 また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
  論文  参考訳（メタデータ） (2023-12-02T13:01:29Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。 連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
  論文  参考訳（メタデータ） (2023-04-10T17:35:57Z)
• A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetry [4.657614491309671]
  MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)right logleft(frac1epsilonright)rightで混合する。 MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)rightで混在している。
  論文  参考訳（メタデータ） (2023-04-08T20:17:29Z)
• Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
  実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。 我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。 我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
  論文  参考訳（メタデータ） (2023-02-20T19:27:21Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。 本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。 総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
  論文  参考訳（メタデータ） (2021-02-09T02:44:24Z)
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm [22.19906823739798]
  ログスムースと強くログ凹分布のクラス上のMALAの混合時間は$O(d)$です。 メトロポリタン調整の投影特性に基づく新しい技術は、ランゲビンSDEのよく研究された離散分析にMALAの研究を減少させる。
  論文  参考訳（メタデータ） (2020-12-23T17:14:06Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• 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)
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo [23.781520510778716]
  これは1次関数情報のみを用いたログコンケーブ分布に対する最初の高精度混合時間結果である。 我々は、$kappa$への依存が標準のMetropolized firstorderメソッドであることを示す。
  論文  参考訳（メタデータ） (2020-02-10T22:44:50Z)

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

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