論文の概要: 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})$クエリローバウンドを与える最近の結果とは対照的である。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• 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)
• 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)
• Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time [13.427128424538502]
  ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。 そこで我々は,Chebyshevsのルーツに基づく時間変化積分時間スキームを提案する。
  論文  参考訳（メタデータ） (2022-07-05T17:42:22Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。