論文の概要: When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm?
- arxiv url: http://arxiv.org/abs/2304.04724v1
- Date: Mon, 10 Apr 2023 17:35:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 14:15:49.574041
- Title: When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm?
- Title（参考訳）: Metropolized Hamiltonian Monte Carloは、Metropolis-adjusted Langevinアルゴリズムよりも確実に優れていますか?
- Authors: Yuansi Chen and Khashayar Gatmiry
- Abstract要約: 本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
- 参考スコア（独自算出の注目度）: 4.657614491309671
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We analyze the mixing time of Metropolized Hamiltonian Monte Carlo (HMC) with
the leapfrog integrator to sample from a distribution on $\mathbb{R}^d$ whose
log-density is smooth, has Lipschitz Hessian in Frobenius norm and satisfies
isoperimetry. We bound the gradient complexity to reach $\epsilon$ error in
total variation distance from a warm start by $\tilde
O(d^{1/4}\text{polylog}(1/\epsilon))$ and demonstrate the benefit of choosing
the number of leapfrog steps to be larger than 1. To surpass previous analysis
on Metropolis-adjusted Langevin algorithm (MALA) that has
$\tilde{O}(d^{1/2}\text{polylog}(1/\epsilon))$ dimension dependency in Wu et
al. (2022), we reveal a key feature in our proof that the joint distribution of
the location and velocity variables of the discretization of the continuous HMC
dynamics stays approximately invariant. This key feature, when shown via
induction over the number of leapfrog steps, enables us to obtain estimates on
moments of various quantities that appear in the acceptance rate control of
Metropolized HMC. Moreover, to deal with another bottleneck on the HMC proposal
distribution overlap control in the literature, we provide a new approach to
upper bound the Kullback-Leibler divergence between push-forwards of the
Gaussian distribution through HMC dynamics initialized at two different points.
Notably, our analysis does not require log-concavity or independence of the
marginals, and only relies on an isoperimetric inequality. To illustrate the
applicability of our result, several examples of natural functions that fall
into our framework are discussed.
- Abstract（参考訳）: 本研究では,ハミルトニアン・モンテカルロ(hmc)とleapfrog積分器の混合時間を,ログ密度が滑らかな$\mathbb{r}^d$ 上の分布から解析し,フロベニウスノルムにリプシッツ・ヘッシアンをもち,等長度法を満たす。
グラデーションの複雑さを$\epsilon$ に限定し,$\tilde o(d^{1/4}\text{polylog}(1/\epsilon))$ というウォームスタートからの全変動距離で$\epsilon$ に限定し,leapfrog ステップ数を 1 よりも大きく選択するメリットを実証した。
Wu et al. (2022) における$\tilde{O}(d^{1/2}\text{polylog}(1/\epsilon))$ dimension dependency を持つメトロポリス調整ランゲヴィンアルゴリズム (MALA) の以前の解析を上回り、連続 HMC 力学の離散化における位置と速度変数の結合分布がほぼ不変であることを示す。
この鍵となる特徴は、跳躍ステップ数に対する誘導によって示される場合、メトロポリ化HMCの受容率制御に現れる様々な量のモーメントを推定することができることである。
さらに、文献におけるHMC分布重なり制御の別のボトルネックに対処するため、2つの異なる点で初期化されたHMCダイナミクスを介してガウス分布のプッシュフォワード間のクルバック・リーブラー分散を上界化するための新しいアプローチを提案する。
特に,本解析では辺縁の対数凹凸性や独立性は必要とせず,等長不等式にのみ依存する。
結果の適用性を説明するために,本フレームワークに該当する自然関数のいくつかの例について論じる。
関連論文リスト
- 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) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Lower Bounds on Metropolized Sampling Methods for Well-Conditioned
Distributions [29.314919044203926]
我々は、実際に最もポピュラーなサンプリング手法であるランゲヴィンアルゴリズム(MALA)とマルチステップのハミルトンモンテカルロ(HMC)の2つの性能に低い限界を与える。
我々の主な結果は、指数的に暖かい開始からMALAの混合時間における$widetildeOmega(kappa d)$のほぼ28の低い境界である。
論文 参考訳（メタデータ） (2021-06-10T03:47:39Z) - Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo [1.14219428942199]
私たちは、調整されていないハミルトンモンテカルロ(uHMC)アルゴリズムに対応するマルコフ鎖の総変動混合時間に関する定量的な上限を提供します。
2つの一般的なモデルのクラスと固定時間離散化ステップサイズ$h$ に対して、混合時間は次元に対数的にのみ依存することが示される。
UHMCにより,目標分布の精度を$varepsilon$-accurate approximation of the target distribution $mu$ in total variation distanceを実現できることを示す。
論文 参考訳（メタデータ） (2021-05-03T14:13:47Z) - 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) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z) - 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) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。