論文の概要: 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次的でない滑らかな凸ポテンシャルを持つ分布からのサンプリングにおいても、時間変化積分時間方式を採用する利点を見出した。
関連論文リスト
- Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
固定次元の複雑なサンプリングアルゴリズムを提案する。
我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。
応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
論文 参考訳（メタデータ） (2024-12-31T17:51:39Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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) - Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration [0.0]
非調整ハミルトンモンテカルロ(uHMC)に対するランダム化時間積分器の提案
調整可能な乱数時間も用意されている。
uHMCアルゴリズムとVerlet時間積分の複雑さは一般に$Oleft((d/K)1/2 (L/K)2 varepsilon-1 logである。
論文 参考訳（メタデータ） (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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。