論文の概要: Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling

• arxiv url: http://arxiv.org/abs/2210.08448v1
• Date: Sun, 16 Oct 2022 05:11:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-18 21:23:56.516184
• Title: Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
• Title（参考訳）: ログコンケーブサンプリングのためのランジュバン法と定常分布の混合時間の解法
• Authors: Jason M. Altschuler and Kunal Talwar
• Abstract要約: 本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。 本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
• 参考スコア（独自算出の注目度）: 34.66940399825547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A particularly canonical approach is the Langevin Algorithm, i.e., the Markov chain for the discretized Langevin Diffusion. This is the sampling analog of Gradient Descent. Despite being studied for several decades in multiple communities, tight mixing bounds for this algorithm remain unresolved even in the seemingly simple setting of log-concave distributions over a bounded domain. This paper completely characterizes the mixing time of the Langevin Algorithm to its stationary distribution in this setting (and others). This mixing result can be combined with any bound on the discretization bias in order to sample from the stationary distribution of the continuous Langevin Diffusion. In this way, we disentangle the study of the mixing and bias of the Langevin Algorithm. Our key insight is to introduce a technique from the differential privacy literature to the sampling literature. This technique, called Privacy Amplification by Iteration, uses as a potential a variant of R\'enyi divergence that is made geometrically aware via Optimal Transport smoothing. This gives a short, simple proof of optimal mixing bounds and has several additional appealing properties. First, our approach removes all unnecessary assumptions required by other sampling analyses. Second, our approach unifies many settings: it extends unchanged if the Langevin Algorithm uses projections, stochastic mini-batch gradients, or strongly convex potentials (whereby our mixing time improves exponentially). Third, our approach exploits convexity only through the contractivity of a gradient step -- reminiscent of how convexity is used in textbook proofs of Gradient Descent. In this way, we offer a new approach towards further unifying the analyses of optimization and sampling algorithms.
• Abstract（参考訳）: 高次元分布からのサンプリングは統計学、工学、科学の基本的な課題である。 特に標準的なアプローチはランゲヴィンアルゴリズム、すなわち離散化ランゲヴィン拡散のマルコフ連鎖である。 これはGradient Descentのサンプリングアナログです。 複数のコミュニティで何十年も研究されてきたにもかかわらず、このアルゴリズムの密混合境界は、有界領域上の対数凹分布の一見単純な設定においても未解決のままである。 本稿では,Langevinアルゴリズムの混合時間と,この設定(および他の設定)の定常分布を完全に特徴付ける。 この混合結果は、連続ランジュバン拡散の定常分布からサンプリングするために、離散バイアス上の任意の境界と結合することができる。 このようにして、Langevinアルゴリズムの混合と偏りの研究を混乱させる。 我々の重要な洞察は、差分プライバシー文学からサンプリング文献へのテクニックの導入である。 この手法はPrivacy Amplification by Iterationと呼ばれ、最適輸送平滑化によって幾何学的に認識されるR'enyiの発散の可能性を秘めている。 これは、最適混合境界の短く簡単な証明を与え、さらにいくつかの魅力的な性質を持つ。 まず,本手法は他のサンプリング分析で要求される不要な仮定をすべて取り除く。 第二に、ランジュバンアルゴリズムが射影、確率的ミニバッチ勾配、または強い凸ポテンシャル(混合時間が指数関数的に改善する)を使用する場合、それは変化しない。 第三に、我々のアプローチは、勾配降下の教科書の証明で凸性がどのように使われているかを思い出して、勾配ステップの契約性を通してのみ凸性を利用する。 このようにして、最適化とサンプリングアルゴリズムの分析をさらに統一する新しいアプローチを提案する。

関連論文リスト

• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• An Improved Analysis of Langevin Algorithms with Prior Diffusion for Non-Log-Concave Sampling [27.882407333690267]
  本研究では, 先行拡散を用いた改良型ランゲヴィンアルゴリズムが, 強対数対数対象分布に対して独立に次元を収束させることができることを示す。 また、修正したランゲヴィンアルゴリズムは、異なるステップサイズスケジュールを持つKL発散の次元非依存収束も得ることを証明した。
  論文  参考訳（メタデータ） (2024-03-10T11:50:34Z)
• Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm [12.405427902037971]
  本稿では,コンパクトかつ凸集合を持つ分布からの近似サンプリング法を提案する。 このアルゴリズムは、ミラーランゲヴィンの単一ステップによって誘導されるマルコフ連鎖にアセプション-リジェクションフィルタを追加する。 近似的制約サンプリングの誤差耐性に対する指数関数的に優れた依存性が得られる。
  論文  参考訳（メタデータ） (2023-12-14T11:11:58Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。 また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
  論文  参考訳（メタデータ） (2023-12-02T13:01:29Z)
• Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling [4.848683707039751]
  本稿では, 画像逆問題におけるベイズ推定を行うために, マルコフ近位連鎖モンテカルロ法を提案する。 モロー・ヨシダの滑らか化によって滑らかにあるいは正規化されるモデルに対しては、中間点は過度に損傷されたランゲヴィン拡散の暗黙の離散化と等価である。 kappa$-strongly log-concaveのターゲットに対しては、提供された非漸近収束解析も最適な時間ステップを特定する。
  論文  参考訳（メタデータ） (2023-08-18T10:55:49Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  本稿では, 拡散サンプリング法とクリロフ部分空間法を相乗的に組み合わせた, 新規で効率的な拡散サンプリング手法を提案する。 具体的には、ツイーディの公式による分母化標本における接空間がクリロフ部分空間を成すならば、その分母化データによるCGは、接空間におけるデータの整合性更新を確実に維持する。 提案手法は,従来の最先端手法よりも80倍以上高速な推論時間を実現する。
  論文  参考訳（メタデータ） (2023-03-10T07:42:49Z)
• Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
  計量$g$の多様体上の自然測度に関して、密度$nu$の分布からサンプリングする問題を研究する。 対数障壁によって定義されるポリトープに制限された等尺的密度をサンプリングする手法が,本手法の特例である。
  論文  参考訳（メタデータ） (2022-04-22T16:56:00Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。