論文の概要: Algorithmic warm starts for Hamiltonian Monte Carlo
- arxiv url: http://arxiv.org/abs/2603.22741v1
- Date: Tue, 24 Mar 2026 03:06:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-25 19:53:37.268615
- Title: Algorithmic warm starts for Hamiltonian Monte Carlo
- Title（参考訳）: アルゴリズムによるモンテカルロの温暖化開始
- Authors: Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi,
- Abstract要約: Hamiltonian Monte Carloは、主要なソフトウェアパッケージにまたがるデフォルトのアルゴリズムである。
したがって、温かいスタートを見つけることは、HMCの計算ボトルネックである。
エンフェノンメトロゾル化 HMC は $tildeO(d1/4)$ iterations の温かいスタートを生じることを証明している。
- 参考スコア（独自算出の注目度）: 14.517286437348034
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltonian Monte Carlo (HMC) is the default algorithm across mainstream software packages. However, despite the extensive line of work on HMC and its widespread empirical success, it remains unclear how many iterations of HMC are required as a function of the dimension $d$. On one hand, a variety of results show that Metropolized HMC converges in $O(d^{1/4})$ iterations from a warm start close to stationarity. On the other hand, Metropolized HMC is significantly slower without a warm start, e.g., requiring $Ω(d^{1/2})$ iterations even for simple target distributions such as isotropic Gaussians. Finding a warm start is therefore the computational bottleneck for HMC. We resolve this issue for the well-studied setting of sampling from a probability distribution satisfying strong log-concavity (or isoperimetry) and third-order derivative bounds. We prove that \emph{non-Metropolized} HMC generates a warm start in $\tilde{O}(d^{1/4})$ iterations, after which we can exploit the warm start using Metropolized HMC. Our final complexity of $\tilde{O}(d^{1/4})$ is the fastest algorithm for high-accuracy sampling under these assumptions, improving over the prior best of $\tilde{O}(d^{1/2})$. This closes the long line of work on the dimensional complexity of MHMC for such settings, and also provides a simple warm-start prescription for practical implementations.
- Abstract（参考訳）: 連続確率密度からサンプルを生成することは、統計学、工学、科学にまたがる中心的なアルゴリズム上の問題である。
高次元設定では、Hachian Monte Carlo (HMC) はメインストリームのソフトウェアパッケージにまたがるデフォルトのアルゴリズムである。
しかし、HMCに関する広範な研究と、その広範な経験的成功にもかかわらず、次元$d$の関数として HMC の繰り返しが何回必要かは定かではない。
一方、様々な結果から、Metropolized HMC は温暖化開始から定常に近い$O(d^{1/4})$反復に収束することが示された。
一方、等方的ガウス分布のような単純な対象分布に対しても、例えば$Ω(d^{1/2})$反復を必要とするような温かい開始を伴わずに、メトロポリ化 HMC は著しく遅い。
したがって、温かいスタートを見つけることは、HMCの計算ボトルネックである。
この問題は、強い対数共振器(または等長器)と3階微分境界を満たす確率分布からのサンプリングのよく研究された設定について解決する。
We prove that \emph{non-Metropolized} HMC generated a warm start in $\tilde{O}(d^{1/4})$ iterations, then we can exploit the warm start using Metropolized HMC。
我々の最終的な複雑性である$\tilde{O}(d^{1/4})$は、これらの仮定の下での高精度サンプリングにおける最速のアルゴリズムであり、以前の$\tilde{O}(d^{1/2})$よりも改善されている。
これにより、そのような設定に対するMHMCの次元複雑性に関する長い作業が終了し、実用的な実装のための単純なウォームスタート処方薬も提供されます。
関連論文リスト
- Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
本稿では,Gibs 分布 $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC。
この結果は、$pi*$ が非指数的であり、$Mh$ が負のリッチ曲率を持つような一般的な設定に適用できる。
論文 参考訳（メタデータ） (2024-02-15T22:59:14Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップに対して$Delta$の2次スピードアップが得られる。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$Delta$で$ell$スケールを計算するための量子回路へのクエリ数、$epsilon$で必要な精度$epsilon$、および標準偏差$sigma$$$ $ell$ as $tildeO(sigma/epsilonを演算する。
論文 参考訳（メタデータ） (2023-03-10T01:05:16Z) - 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) - Gaussian process regression and conditional Karhunen-Lo\'{e}ve models
for data assimilation in inverse problems [68.8204255655161]
偏微分方程式モデルにおけるデータ同化とパラメータ推定のためのモデル逆アルゴリズムCKLEMAPを提案する。
CKLEMAP法は標準的なMAP法に比べてスケーラビリティがよい。
論文 参考訳（メタデータ） (2023-01-26T18:14:12Z) - 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) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
ハミルトニアンモンテカルロは、標準およびディープアンサンブルよりも大きな性能向上を達成できることを示す。
また,深部分布は標準SGLDとHMCに類似しており,標準変動推論に近いことが示された。
論文 参考訳（メタデータ） (2021-04-29T15:38:46Z) - Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo [0.0]
HMCベースのアルゴリズムであるReflective Hamiltonian Monte Carlo(ReHMC)を,凸ポリトープに制限されたログ凹分布からサンプリングする。
暖かいスタートから始まり、よく周されたポリトープのステップを$widetilde O(kappa d2 ell2 log (1 / varepsilon))$で混ぜることを証明する。
実験により、ReHMCは独立したサンプルを作成する必要がある時間に関して、Hit-and-RunとCoordinate-and-Runより優れていることが示唆された。
論文 参考訳（メタデータ） (2021-02-25T18:34:45Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。