論文の概要: Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo
- arxiv url: http://arxiv.org/abs/2607.12902v1
- Date: Tue, 14 Jul 2026 15:38:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-15 17:08:30.213846
- Title: Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo
- Title（参考訳）: ランダム化ハミルトンモンテカルロの加速混合時間
- Abstract要約: ランダム化ハミルトニアンモンテカルロアルゴリズムは,対数凹面確率分布からのサンプリングに要する混合時間保証を高速化したことを示す。
また、対象の分布が対数凹である場合、指数関数的に増加する手段で三角分布からランダムな積分時間列を使用すれば、KL分散スケールでの誤差$varepsilon$に到達するための合計積分時間は$O(varepsilon-1/2)$であることを示す。
- 参考スコア（独自算出の注目度）: 10.397013127870162
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $α$-Talagrand inequality (for example, if the target distribution is $α$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $Θ(α^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(α^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.
- Abstract（参考訳）: 我々はRandomized Hamiltonian Monte Carlo (RHMC)アルゴリズムが対数凹面確率分布からサンプリングする混合時間保証を高速化したことを示す。
RHMCは、連続時間ハミルトン力学をいくつかのランダムな積分時間で繰り返しシミュレートし、各シミュレーションの間に独立なガウス確率変数となる速度をリセットする。
対象分布が対数不等式(例えば、対象分布が$α$-strongly log-concave)であるとき、RHMC は KL の発散で指数的に速く収束し、KL の発散で$\varepsilon$ に到達する総積分時間は $O(α^{-1/2} \log(\varepsilon^{-1})$ としてスケールする(例えば、対象分布が$α$-strongly log-concave)。
また、対象分布が対数凹である場合、指数関数的に増加する手段で三角分布からランダムな積分時間列を使用すると、KL分散スケールでの誤差$\varepsilon$を$O(\varepsilon^{-1/2})$とする。
我々の解析は、ハミルトン力学に基づく加速最適化手法の類似した結果から着想を得たハミルトン力学に沿った平均KLの発散に依存する。
関連論文リスト
- Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling [55.388363730120325]
本研究では,CTMC(Continuous-Time Markov Chain)フレームワークにおいて,離散拡散を吸収するための$-leapingアルゴリズムを並列化する。
我々は,$$-leapingアルゴリズムとPicard法の連続時間積分形式を利用して,並列時間サンプリング高速化を実現する。
本研究は, 分子構造や言語生成などの応用において, 効率的な並列推論のための離散拡散モデルの可能性を広げるものである。
論文 参考訳（メタデータ） (2026-07-01T10:59:33Z) - Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion [16.463220658992064]
分布の幅広いクラスに対する最初のサンプリングアルゴリズムを提供する。
我々のアルゴリズムは時間反転拡散過程をシミュレートする。
メタスタビリティを回避し、モード位置に関する事前の知識を必要とせず、よく知られた対数平滑性仮定を緩和する。
論文 参考訳（メタデータ） (2024-12-31T17:51:39Z) - Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler [14.34147140416535]
連続空間における2つの一般的な離散時間マルコフ連鎖の混合時間について検討する。
二つの微分可能な厳密凸函数から生じる任意の$Phi$-divergenceが、これらのマルコフ連鎖に沿って指数的に0$に収束することを示す。
論文 参考訳（メタデータ） (2024-10-14T16:41:45Z) - 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) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - Condition-number-independent Convergence Rate of Riemannian Hamiltonian
Monte Carlo with Numerical Integrators [22.49731518828916]
我々は、$m制約のあるポリトープ上の$e-alphatopx$の形式での分布に対して、一般的に使用される$の族の収束率は、$leftVert alpharightVert$とポリトープの幾何学とは独立であることを示す。
これらの保証は、多様体と積分子のパラメータの項で$e-f(x)$という形の密度の収束率の一般境界に基づいている。
論文 参考訳（メタデータ） (2022-10-13T17:46:51Z) - Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps [0.0]
Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。
HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。
論文 参考訳（メタデータ） (2022-09-26T15:29:29Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。