論文の概要: Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps
- arxiv url: http://arxiv.org/abs/2209.12771v1
- Date: Mon, 26 Sep 2022 15:29:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 15:32:07.826803
- Title: Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps
- Title(参考訳): 効率的なガウスサンプリングのためのハミルトンモンテカルロ:長いステップとランダムステップ
- Authors: Simon Apers, Sander Gribling, D\'aniel Szil\'agyi
- Abstract要約: Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。
HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a
high-dimensional distribution with density $e^{-f(x)}$, given access to the
gradient of $f$. A particular case of interest is that of a $d$-dimensional
Gaussian distribution with covariance matrix $\Sigma$, in which case $f(x) =
x^\top \Sigma^{-1} x$. We show that HMC can sample from a distribution that is
$\varepsilon$-close in total variation distance using
$\widetilde{O}(\sqrt{\kappa} d^{1/4} \log(1/\varepsilon))$ gradient queries,
where $\kappa$ is the condition number of $\Sigma$. Our algorithm uses long and
random integration times for the Hamiltonian dynamics. This contrasts with (and
was motivated by) recent results that give an $\widetilde\Omega(\kappa
d^{1/2})$ query lower bound for HMC with fixed integration times, even for the
Gaussian case.
- Abstract(参考訳): ハミルトン・モンテカルロ (hamiltonian monte carlo, hmc) は、密度 $e^{-f(x)}$ の高次元分布からサンプリングするためのマルコフ連鎖アルゴリズムである。
興味のある特別な場合として、共分散行列 $\sigma$ を持つ次元ガウス分布のとき、その場合、$f(x) = x^\top \sigma^{-1} x$ である。
HMCは$\varepsilon$-closeの分布から$\widetilde{O}(\sqrt{\kappa} d^{1/4} \log(1/\varepsilon)$グラデーションクエリをサンプリングすることができ、$\kappa$は$\Sigma$の条件番号である。
我々のアルゴリズムはハミルトン力学に長いランダムな積分時間を用いる。
これは、ガウスの場合でさえ、一定の積分時間を持つ HMC に対して$\widetilde\Omega(\kappa d^{1/2})$クエリローバウンドを与える最近の結果とは対照的である。
関連論文リスト
- Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳(メタデータ) (2023-03-30T02:50:49Z) - 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) - Penalized Langevin and Hamiltonian Monte Carlo Algorithms for
Constrained Sampling [8.333246626497363]
分布(x)prop ef(x)$と$x$が凸体上で制約されるような制約付きサンプリング問題を考える。
我々は,制限されたサンプリング問題をペナルティ関数制約違反を導入して非拘束なものに変換する,ペナルティ付ハミルトンモンテカルロダイナミクス(PLD)とペナルティ付ハミルトンモンテカルロダイナミクス(PHMC)を提案する。
PHMCでは、Hessianが$であるときに $tildemathcalO(sqrtd/varepsilon7)$に改善します。
論文 参考訳(メタデータ) (2022-11-29T18:43:22Z) - 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) - Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time [13.427128424538502]
ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。
そこで我々は,Chebyshevsのルーツに基づく時間変化積分時間スキームを提案する。
論文 参考訳(メタデータ) (2022-07-05T17:42:22Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳(メタデータ) (2020-08-01T19:23:34Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳(メタデータ) (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。