論文の概要: Concentration of the Langevin Algorithm's Stationary Distribution
- arxiv url: http://arxiv.org/abs/2212.12629v2
- Date: Mon, 21 Oct 2024 05:38:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-22 13:13:58.624232
- Title: Concentration of the Langevin Algorithm's Stationary Distribution
- Title（参考訳）: ランゲヴィンアルゴリズムの定常分布の濃度
- Authors: Jason M. Altschuler, Kunal Talwar,
- Abstract要約: 任意の非自明な段数 $eta > 0$ に対して、$pi_eta$ はポテンシャルが凸であるときに部分指数であることを示す。
また、これらの濃度境界がランゲヴィンアルゴリズムの軌道に沿って全ての反復に広がることを示す。
- 参考スコア（独自算出の注目度）: 29.244631254978597
- License:
- 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 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. We also show that these concentration bounds extend to all iterates along the trajectory of the Langevin Algorithm, and to inexact implementations which use sub-Gaussian estimates of the gradient. 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（参考訳）: ログ・コンケーブサンプリングの標準的なアルゴリズムは、ランゲヴィン・アルゴリズム(Langevin Algorithm)、別名ランゲヴィン・ディフュージョン(Langevin Diffusion)であり、いくつかの離散化ステップサイズが$\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) - Stochastic Langevin Monte Carlo for (weakly) log-concave posterior
distributions [0.0]
従来のランゲヴィン拡散にサンプリングステップを組み込んだ,[WT11] で導入されたランゲヴィンモンテカルロ法の連続時間バージョンについて検討する。
この方法は、後部分布をサンプリングする機械学習で人気がある。
論文 参考訳（メタデータ） (2023-01-08T17:08:21Z) - Resolving the Mixing Time of the Langevin Algorithm to its Stationary
Distribution for Log-Concave Sampling [34.66940399825547]
本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。
本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
論文 参考訳（メタデータ） (2022-10-16T05:11:16Z) - 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) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin
Algorithm [11.80267432402723]
ログ凹型確率分布に対するサンプリングの課題を考察する。
対象の分布は、ワッサーシュタイン空間上で定義されるクルバック・リーバーの発散の最小値と見なすことができる。
ポテンシャルが強い凸であれば、PSGLA の複雑さは 2-ワッサーシュタイン距離の点で$O (1/varepsilon2)$である。
論文 参考訳（メタデータ） (2020-06-16T15:57:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。