論文の概要: Concentration of the Langevin Algorithm's Stationary Distribution
- arxiv url: http://arxiv.org/abs/2212.12629v1
- Date: Sat, 24 Dec 2022 01:39:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 14:16:46.278427
- Title: Concentration of the Langevin Algorithm's Stationary Distribution
- Title(参考訳): ランゲヴィンアルゴリズムの定常分布の濃度
- Authors: Jason M. Altschuler and Kunal Talwar
- Abstract要約: 任意の非自明な段数 $eta > 0$ に対して、$pi_eta$ はポテンシャルが凸であるときに部分指数であることを示す。
解析の鍵となるのは、Langevinアルゴリズムの定常力学を研究するために回転不変モーメント生成関数を使用することである。
- 参考スコア(独自算出の注目度): 34.66940399825547
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A canonical algorithm for log-concave sampling is the Langevin Algorithm, aka
the Langevin Diffusion run with some discretization stepsize $\eta > 0$. This
discretization leads the Langevin Algorithm to have a stationary distribution
$\pi_{\eta}$ which differs from the stationary distribution $\pi$ of the
Langevin Diffusion, and it is an important challenge to understand whether the
well-known properties of $\pi$ extend to $\pi_{\eta}$. In particular, while
concentration properties such as isoperimetry and rapidly decaying tails are
classically known for $\pi$, the analogous properties for $\pi_{\eta}$ are open
questions with direct algorithmic implications. This note provides a first step
in this direction by establishing concentration results for $\pi_{\eta}$ that
mirror classical results for $\pi$. Specifically, we show that for any
nontrivial stepsize $\eta > 0$, $\pi_{\eta}$ is sub-exponential (respectively,
sub-Gaussian) when the potential is convex (respectively, strongly convex).
Moreover, the concentration bounds we show are essentially tight.
Key to our analysis is the use of a rotation-invariant moment generating
function (aka Bessel function) to study the stationary dynamics of the Langevin
Algorithm. This technique may be of independent interest because it enables
directly analyzing the discrete-time stationary distribution $\pi_{\eta}$
without going through the continuous-time stationary distribution $\pi$ as an
intermediary.
- Abstract(参考訳): log-concaveサンプリングの標準的なアルゴリズムはlangevinアルゴリズム(別名langevin diffusion run with some discretization stepsize $\eta > 0$)である。
この離散化によりランゲヴィンアルゴリズムは定常分布 $\pi_{\eta}$ を持ち、これはランゲヴィン拡散の定常分布 $\pi$ とは異なるものであり、$\pi$ のよく知られた性質が $\pi_{\eta}$ に拡張するかどうかを理解することは重要な課題である。
特に、イソペリメトリや急速に崩壊するテールのような濃度特性は古典的には$\pi$で知られているが、$\pi_{\eta}$の類似性は直接アルゴリズム的な意味を持つ開問題である。
この注記は、古典的結果を反映する$\pi_{\eta}$を$\pi$とすることで、この方向への第一歩を提供する。
具体的には、任意の非自明なステップサイズ $\eta > 0$, $\pi_{\eta}$ が、ポテンシャルが凸であるとき(つまり、強凸)に部分指数的であることを示す。
さらに、私たちが示す濃度境界は本質的にきつい。
我々の分析の鍵は、ランゲヴィンアルゴリズムの定常力学を研究するために回転不変モーメント生成関数(別名ベッセル関数)を使用することである。
この手法は離散時間定常分布 $\pi_{\eta}$ を直接分析できるので、媒介として連続時間定常分布 $\pi$ を通すことなく、独立した興味を持つことができる。
関連論文リスト
- 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) - Fast parallel sampling under isoperimetry [10.619901778151336]
ログソボレフの不等式を満たすディストリビューション$pi$ over $mathbb Rd$から並列にサンプリングする方法を示す。
提案アルゴリズムは分布$hatpi$からKullback-Leibler分散の$pi$に近いサンプルを出力する。
論文 参考訳(メタデータ) (2024-01-17T07:24:18Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳(メタデータ) (2023-07-02T05:03:38Z) - Stochastic Langevin Monte Carlo for (weakly) log-concave posterior
distributions [0.0]
従来のランゲヴィン拡散にサンプリングステップを組み込んだ,[WT11] で導入されたランゲヴィンモンテカルロ法の連続時間バージョンについて検討する。
この方法は、後部分布をサンプリングする機械学習で人気がある。
論文 参考訳(メタデータ) (2023-01-08T17:08:21Z) - 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) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳(メタデータ) (2022-02-23T16:10:23Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳(メタデータ) (2020-12-21T03:10:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳(メタデータ) (2020-06-12T10:21:40Z) - Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
スペクトル密度作用素 $hatrho(omega)=delta(omega-hatH)$ は線形応答論において中心的な役割を果たす。
スペクトル密度を近似する近似量子アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2020-04-10T03:14:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。