論文の概要: Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
- arxiv url: http://arxiv.org/abs/2211.11003v1
- Date: Sun, 20 Nov 2022 15:45:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 23:21:33.612996
- Title: Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
- Title(参考訳): モンテカルロ時間積分を用いた非調整ハミルトニアンMCMC
- Authors: Nawaf Bou-Rabee, Milo Marsden
- Abstract要約: 未調整のハミルトンモンテカルロ (uHMC) アルゴリズムが提案されている。
成層モンテカルロ (SMC) 時間積分器を基礎となるハミルトン力学に用いている。
uHMCアルゴリズムとVerlet時間積分の複雑さは、一般に$Oleft((d/K)1/2 (L/K)2 varepsilon-1 log( boldsymbolmathcalW2(mu, nu) / varepsilon-1 log( boldsymbolmathcalW)である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A novel unadjusted Hamiltonian Monte Carlo (uHMC) algorithm is suggested that
uses a stratified Monte Carlo (SMC) time integrator for the underlying
Hamiltonian dynamics in place of the usual Verlet time integrator. For target
distributions of the form $\mu(dx) \propto e^{-U(x)} dx$ where $U: \mathbb{R}^d
\to \mathbb{R}_{\ge 0}$ is both $K$-strongly convex and $L$-gradient Lipschitz,
and initial distributions $\nu$ with finite second moment, coupling proofs
reveal that an $\varepsilon$-accurate approximation of the target distribution
$\mu$ in $L^2$-Wasserstein distance $\boldsymbol{\mathcal{W}}^2$ can be
achieved by the uHMC algorithm with SMC time integration using
$O\left((d/K)^{1/3} (L/K)^{5/3} \varepsilon^{-2/3} \log(
\boldsymbol{\mathcal{W}}^2(\mu, \nu) / \varepsilon)^+\right)$ gradient
evaluations; whereas without any additional assumptions the corresponding
complexity of the uHMC algorithm with Verlet time integration is in general
$O\left((d/K)^{1/2} (L/K)^2 \varepsilon^{-1} \log(
\boldsymbol{\mathcal{W}}^2(\mu, \nu) / \varepsilon)^+ \right)$. The SMC time
integrator involves a minor modification to Verlet, and hence, is easy to
implement.
- Abstract(参考訳): uhmc (unadjusted hamiltonian monte carlo) アルゴリズムは、通常のバーレット時間積分器の代わりにハミルトン力学の基礎となる階層化されたモンテカルロ時間積分器(smc)を使用することが提案されている。
For target distributions of the form $\mu(dx) \propto e^{-U(x)} dx$ where $U: \mathbb{R}^d \to \mathbb{R}_{\ge 0}$ is both $K$-strongly convex and $L$-gradient Lipschitz, and initial distributions $\nu$ with finite second moment, coupling proofs reveal that an $\varepsilon$-accurate approximation of the target distribution $\mu$ in $L^2$-Wasserstein distance $\boldsymbol{\mathcal{W}}^2$ can be achieved by the uHMC algorithm with SMC time integration using $O\left((d/K)^{1/3} (L/K)^{5/3} \varepsilon^{-2/3} \log( \boldsymbol{\mathcal{W}}^2(\mu, \nu) / \varepsilon)^+\right)$ gradient evaluations; whereas without any additional assumptions the corresponding complexity of the uHMC algorithm with Verlet time integration is in general $O\left((d/K)^{1/2} (L/K)^2 \varepsilon^{-1} \log( \boldsymbol{\mathcal{W}}^2(\mu, \nu) / \varepsilon)^+ \right)$.
SMCのタイムインテグレータはVerletに小さな修正を加えており、実装が容易である。
関連論文リスト
- 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) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - 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) - Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time [13.427128424538502]
ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。
そこで我々は,Chebyshevsのルーツに基づく時間変化積分時間スキームを提案する。
論文 参考訳(メタデータ) (2022-07-05T17:42:22Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Kernel Thinning [26.25415159542831]
カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。
我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
論文 参考訳(メタデータ) (2021-05-12T17:56:42Z) - 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) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳(メタデータ) (2021-03-17T00:59:33Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。