論文の概要: Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized
Hamiltonian Monte Carlo
- arxiv url: http://arxiv.org/abs/2002.04121v3
- Date: Sun, 14 Jun 2020 02:12:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 08:49:15.475721
- Title: Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized
Hamiltonian Monte Carlo
- Title（参考訳）: メトポライズされたハミルトンモンテカルロの対流勾配濃度とタイターランタイム
- Authors: Yin Tat Lee, Ruoqi Shen, Kevin Tian
- Abstract要約: これは1次関数情報のみを用いたログコンケーブ分布に対する最初の高精度混合時間結果である。
我々は、$kappa$への依存が標準のMetropolized firstorderメソッドであることを示す。
- 参考スコア（独自算出の注目度）: 23.781520510778716
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that the gradient norm $\|\nabla f(x)\|$ for $x \sim \exp(-f(x))$,
where $f$ is strongly convex and smooth, concentrates tightly around its mean.
This removes a barrier in the prior state-of-the-art analysis for the
well-studied Metropolized Hamiltonian Monte Carlo (HMC) algorithm for sampling
from a strongly logconcave distribution. We correspondingly demonstrate that
Metropolized HMC mixes in $\tilde{O}(\kappa d)$ iterations, improving upon the
$\tilde{O}(\kappa^{1.5}\sqrt{d} + \kappa d)$ runtime of (Dwivedi et. al. '18,
Chen et. al. '19) by a factor $(\kappa/d)^{1/2}$ when the condition number
$\kappa$ is large. Our mixing time analysis introduces several techniques which
to our knowledge have not appeared in the literature and may be of independent
interest, including restrictions to a nonconvex set with good conductance
behavior, and a new reduction technique for boosting a constant-accuracy total
variation guarantee under weak warmness assumptions. This is the first
high-accuracy mixing time result for logconcave distributions using only
first-order function information which achieves linear dependence on $\kappa$;
we also give evidence that this dependence is likely to be necessary for
standard Metropolized first-order methods.
- Abstract（参考訳）: 勾配ノルム $\|\nabla f(x)\|$ for $x \sim \exp(-f(x))$ ここで、$f$ は強凸かつ滑らかであり、その平均付近で密集する。
これにより、強い対数凸分布からサンプリングするためのよく研究されたハミルトニアンモンテカルロ(hmc)アルゴリズムの事前の最先端解析の障壁が取り除かれる。
条件数 $\kappa$ が大きければ$(\kappa/d)^{1/2}$ という係数で (dwivedi et. al. '18, chen et. al. '19) の$\tilde{o}(\kappa d)$ のランタイムを改善して、metropolized hmc が$\tilde{o}(\kappa d)$ で混合することを示す。
混合時間解析では,コンダクタンス挙動が良好な非凸集合に対する制限や,弱温和性仮定下での一定精度の全変動を保証できる新たな低減手法など,文献にない,独立した興味を持つ技術がいくつか紹介されている。
これは、$\kappa$に線形依存する1次関数情報のみを用いて、ログ凹分布に対する最初の高精度混合時間結果であり、標準のMetropolized 1次法には、この依存が必須であることを示す。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - 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) - Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for
Log-Concave Sampling [2.9972063833424216]
対数平滑かつ強い対数凹分布からサンプリングするために,メトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。
温暖化開始時に最適なミニマックス混合時間を確立する。
論文 参考訳（メタデータ） (2021-09-27T14:02:27Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2021-02-09T02:44:24Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。