論文の概要: Improved Discretization Analysis for Underdamped Langevin Monte Carlo
- arxiv url: http://arxiv.org/abs/2302.08049v1
- Date: Thu, 16 Feb 2023 03:09:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 15:10:26.809502
- Title: Improved Discretization Analysis for Underdamped Langevin Monte Carlo
- Title（参考訳）: アンダーダム型Langevin Monte Carloの離散化解析の改善
- Authors: Matthew Zhang, Sinho Chewi, Mufan Bill Li, Krishnakumar
Balasubramanian, Murat A. Erdogdu
- Abstract要約: アンダーダムド・ランゲヴィン・モンテカルロ (Underdamped Langevin Monte Carlo, ULMC) は、ポテンシャル井戸内を移動する粒子の運動量を利用して非正規化密度からサンプリングするために用いられるアルゴリズムである。
2つの中心的な質問に動機づけられたULMCの新しい分析法を提案する。
強い対数共振域を超えたサンプリング保証の改善は可能か?
- 参考スコア（独自算出の注目度）: 15.87191223426522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Underdamped Langevin Monte Carlo (ULMC) is an algorithm used to sample from
unnormalized densities by leveraging the momentum of a particle moving in a
potential well. We provide a novel analysis of ULMC, motivated by two central
questions: (1) Can we obtain improved sampling guarantees beyond strong
log-concavity? (2) Can we achieve acceleration for sampling?
For (1), prior results for ULMC only hold under a log-Sobolev inequality
together with a restrictive Hessian smoothness condition. Here, we relax these
assumptions by removing the Hessian smoothness condition and by considering
distributions satisfying a Poincar\'e inequality. Our analysis achieves the
state of art dimension dependence, and is also flexible enough to handle weakly
smooth potentials. As a byproduct, we also obtain the first KL divergence
guarantees for ULMC without Hessian smoothness under strong log-concavity,
which is based on a new result on the log-Sobolev constant along the
underdamped Langevin diffusion.
For (2), the recent breakthrough of Cao, Lu, and Wang (2020) established the
first accelerated result for sampling in continuous time via PDE methods. Our
discretization analysis translates their result into an algorithmic guarantee,
which indeed enjoys better condition number dependence than prior works on
ULMC, although we leave open the question of full acceleration in discrete
time.
Both (1) and (2) necessitate R\'enyi discretization bounds, which are more
challenging than the typically used Wasserstein coupling arguments. We address
this using a flexible discretization analysis based on Girsanov's theorem that
easily extends to more general settings.
- Abstract（参考訳）: underdamped langevin monte carlo (ulmc) は、ポテンシャル井戸内を移動する粒子の運動量を利用して非正規化密度からサンプリングするアルゴリズムである。
我々は,(1)強い対数連結性以上のサンプリング保証が得られるか,という2つの中心的疑問に動機づけられたulmcの新しい解析法を提案する。
(2)サンプリングの高速化は可能か?
1) ULMCの先行結果は対数ソボレフの不等式と制限的ヘッセンスな滑らかさ条件でのみ保持される。
ここでは、ヘッセンの滑らかさ条件を取り除き、ポアンカーの不等式を満たす分布を考えることでこれらの仮定を緩和する。
解析は,芸術次元依存の状態を実現し,弱滑らかなポテンシャルを扱うのに十分な柔軟性を有する。
副生成物として, 強対連結性下でのヘッセン滑らか性のないulmcに対する最初のkl発散保証を得るとともに, 沈殿したランジュバン拡散に沿った対数ソボレフ定数の新たな結果に基づく。
2) に対し、最近の Cao, Lu, and Wang (2020) のブレークスルーにより、PDE 法による連続時間サンプリングのための最初の加速結果が確立された。
我々の離散化分析は、それらの結果をアルゴリズム的な保証に変換し、従来のULMCよりも条件数依存が優れているが、離散時間で完全な加速の問題を解き放ったままである。
1) と (2) のどちらも R\'enyi の離散化境界を必要とし、これは典型的なワッサーシュタイン結合の議論よりも難しい。
我々は、より一般的な設定に容易に拡張できるジルサノフの定理に基づくフレキシブルな離散化解析を用いてこの問題に対処する。
関連論文リスト
- Non-Reversible Langevin Algorithms for Constrained Sampling [13.472207533177151]
本研究では,制約領域上の対象分布から標本化することを目的とする制約サンプリング問題を考察する。
SRNLD(skew-reflected non-reversible Langevin dynamics)を提案する。
我々は,SRNLDの非漸近収束速度を,全変量と1-ワッサーシュタイン距離の両方の目標分布に求める。
論文 参考訳（メタデータ） (2025-01-20T21:04:29Z) - Shifted Composition III: Local Error Framework for KL Divergence [12.93725028754563]
引数の結合は、2つのプロセス間の偏差を境界付ける中心的なツールである。
カップリングの議論をKL(Kulback-Leibler)の発散に適用する。
論文 参考訳（メタデータ） (2024-12-23T21:40:01Z) - A Unified Analysis for Finite Weight Averaging [50.75116992029417]
Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。
本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
論文 参考訳（メタデータ） (2024-11-20T10:08:22Z) - Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
本研究では,新しいDDPMサンプリング器が,これまで考慮されていなかった3種類の分散クラスに対して高速化性能を実現することを示す。
この結果から, DDPM型加速サンプリング器におけるデータ次元$d$への依存性が改善された。
論文 参考訳（メタデータ） (2024-02-21T16:11:47Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Langevin Monte Carlo for strongly log-concave distributions: Randomized
midpoint revisited [4.551456632596834]
我々は,バニラ・ランゲヴィン過程の中間点の離散化を解析する。
この分析は根底にある原則を明確にし、貴重な洞察を提供するのに役立つ。
我々は、オイラー離散化を伴うランゲヴィン過程の新たな保証を確立する。
論文 参考訳（メタデータ） (2023-06-14T13:18:09Z) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - Unadjusted Langevin algorithm for sampling a mixture of weakly smooth
potentials [0.0]
我々は,ポアンカーの不等式や球体の外側の非強凸の下での収束保証を証明した。
また、滑らかなポテンシャルに対する$L_beta$-Wasserstein 計量の収束も提供する。
論文 参考訳（メタデータ） (2021-12-17T04:10:09Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。
平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。
任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
論文 参考訳（メタデータ） (2020-06-16T20:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。