論文の概要: Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time
- arxiv url: http://arxiv.org/abs/2207.02189v1
- Date: Tue, 5 Jul 2022 17:42:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-06 15:53:27.428346
- Title: Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time
- Title(参考訳): チェビシェフ積分時間によるハミルトニアンモンテカルロの加速
- Authors: Jun-Kun Wang and Andre Wibisono
- Abstract要約: ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。
そこで我々は,Chebyshevsのルーツに基づく時間変化積分時間スキームを提案する。
- 参考スコア(独自算出の注目度): 13.427128424538502
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hamiltonian Monte Carlo (HMC) is a popular method in sampling. While there
are quite a few works of studying this method on various aspects, an
interesting question is how to choose its integration time to achieve
acceleration. In this work, we consider accelerating the process of sampling
from a distribution $\pi(x) \propto \exp(-f(x))$ via HMC via time-varying
integration time. When the potential $f$ is $L$-smooth and $m$-strongly convex,
i.e.\ for sampling from a log-smooth and strongly log-concave target
distribution $\pi$, it is known that under a constant integration time, the
number of iterations that ideal HMC takes to get an $\epsilon$ Wasserstein-2
distance to the target $\pi$ is $O( \kappa \log \frac{1}{\epsilon} )$, where
$\kappa := \frac{L}{m}$ is the condition number. We propose a scheme of
time-varying integration time based on the roots of Chebyshev polynomials. We
show that in the case of quadratic potential $f$, i.e., when the target $\pi$
is a Gaussian distribution, ideal HMC with this choice of integration time only
takes $O( \sqrt{\kappa} \log \frac{1}{\epsilon} )$ number of iterations to
reach Wasserstein-2 distance less than $\epsilon$; this improvement on the
dependence on condition number is akin to acceleration in optimization. The
design and analysis of HMC with the proposed integration time is built on the
tools of Chebyshev polynomials. Experiments find the advantage of adopting our
scheme of time-varying integration time even for sampling from distributions
with smooth strongly convex potentials that are not quadratic.
- Abstract(参考訳): ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。
この手法を様々な面で研究する研究はいくつかあるが、興味深い疑問は、加速を達成するために積分時間をどのように選ぶかである。
本研究では,hmc を経由する分布 $\pi(x) \propto \exp(-f(x))$ からのサンプリングプロセスを時間変動積分時間で高速化することを検討する。
l$-smooth と $m$-strongly convex,すなわち、log-smooth と strong log-concave target distribution $\pi$ からサンプリングすると、一定の積分時間の下で、理想的な hmc が $\epsilon$ wasserstein-2 の距離を目標 $\pi$ に設定するのに要するイテレーションの数は $o( \kappa \log \frac{1}{\epsilon} )$ であり、ここで $\kappa := \frac{l}{m}$ は条件数である。
チェビシェフ多項式の根に基づく時間変化積分時間のスキームを提案する。
二次ポテンシャル $f$ の場合、すなわち、目標 $\pi$ がガウス分布であるとき、この積分時間の選択を持つ理想 hmc は、o ( \sqrt{\kappa} \log \frac{1}{\epsilon} )$ を要し、$\epsilon$ 未満のwaserstein-2 距離に到達する。
チェビシェフ多項式のツールを用いて,提案した積分時間を用いたHMCの設計と解析を行う。
実験では、2次的でない滑らかな凸ポテンシャルを持つ分布からのサンプリングにおいても、時間変化積分時間方式を採用する利点を見出した。
関連論文リスト
- 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) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳(メタデータ) (2023-03-30T02:50:49Z) - Stochastic Langevin Monte Carlo for (weakly) log-concave posterior
distributions [0.0]
従来のランゲヴィン拡散にサンプリングステップを組み込んだ,[WT11] で導入されたランゲヴィンモンテカルロ法の連続時間バージョンについて検討する。
この方法は、後部分布をサンプリングする機械学習で人気がある。
論文 参考訳(メタデータ) (2023-01-08T17:08:21Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration [0.0]
未調整のハミルトンモンテカルロ (uHMC) アルゴリズムが提案されている。
成層モンテカルロ (SMC) 時間積分器を基礎となるハミルトン力学に用いている。
uHMCアルゴリズムとVerlet時間積分の複雑さは、一般に$Oleft((d/K)1/2 (L/K)2 varepsilon-1 log( boldsymbolmathcalW2(mu, nu) / varepsilon-1 log( boldsymbolmathcalW)である。
論文 参考訳(メタデータ) (2022-11-20T15:45:26Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - 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) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。