論文の概要: 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$ を通すことなく、独立した興味を持つことができる。
関連論文リスト
- Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [52.69179872700035]
本稿では,$pi(x)proptoexp(-U(x))$という形のGibbs分布から,潜在的に$U(x)$でサンプリングする方法を提案する。
拡散モデルに着想を得て、ターゲット密度の近似の列 $(pit_k)_k$ を考えることを提案し、そこで$pit_kapprox pi$ for $k$ small に対して $pit_k$ は、$k$のサンプリングに好適な性質を示す。
論文 参考訳（メタデータ） (2025-02-03T13:50:57Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。