論文の概要: A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm
under Smoothness and Isoperimetry
- arxiv url: http://arxiv.org/abs/2304.04095v2
- Date: Thu, 8 Jun 2023 16:31:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-09 19:10:10.087332
- Title: A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm
under Smoothness and Isoperimetry
- Title（参考訳）: Smoothness と Isoperimetry の下でのメトロポリス調整ランゲヴィンアルゴリズムの混合の簡単な証明
- Authors: Yuansi Chen and Khashayar Gatmiry
- Abstract要約: MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)right logleft(frac1epsilonright)rightで混合する。
MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)rightで混在している。
- 参考スコア（独自算出の注目度）: 4.657614491309671
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the mixing time of Metropolis-Adjusted Langevin algorithm (MALA) for
sampling a target density on $\mathbb{R}^d$. We assume that the target density
satisfies $\psi_\mu$-isoperimetry and that the operator norm and trace of its
Hessian are bounded by $L$ and $\Upsilon$ respectively. Our main result
establishes that, from a warm start, to achieve $\epsilon$-total variation
distance to the target density, MALA mixes in
$O\left(\frac{(L\Upsilon)^{\frac12}}{\psi_\mu^2}
\log\left(\frac{1}{\epsilon}\right)\right)$ iterations. Notably, this result
holds beyond the log-concave sampling setting and the mixing time depends on
only $\Upsilon$ rather than its upper bound $L d$. In the $m$-strongly
logconcave and $L$-log-smooth sampling setting, our bound recovers the previous
minimax mixing bound of MALA~\cite{wu2021minimax}.
- Abstract（参考訳）: 目標密度を$\mathbb{R}^d$でサンプリングするためのメトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。
対象密度が $\psi_\mu$-isoperimetry を満たすと仮定し、Hessian の作用素ノルムとトレースはそれぞれ $L$ と $\Upsilon$ で有界であると仮定する。
我々の主な結果は、温かいスタートから目標密度まで$\epsilon$-totalの変動距離を達成するために、malaは$o\left(\frac{(l\upsilon)^{\frac12}}{\psi_\mu^2} \log\left(\frac{1}{\epsilon}\right)\right)$の反復で混合する。
特に、この結果はlog-concaveサンプリング設定以上のものであり、混合時間は上限の$l d$ではなく$\upsilon$にのみ依存する。
m$-strongly logconcave と $L$-log-smooth sample set では、MALA~\cite{wu2021minimax} の以前のミニマックス混合境界を回復する。
関連論文リスト
- Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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) - A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。
我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文 参考訳（メタデータ） (2022-10-05T17:35:46Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。
SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
論文 参考訳（メタデータ） (2021-01-07T03:14:05Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。