論文の概要: Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler
- arxiv url: http://arxiv.org/abs/2410.10699v1
- Date: Mon, 14 Oct 2024 16:41:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-29 20:15:14.952525
- Title: Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler
- Title（参考訳）: 非調整ランゲヴィンアルゴリズムと近距離サンプリングによる$$$-divergenceの高速収束
- Authors: Siddharth Mitra, Andre Wibisono,
- Abstract要約: 連続空間における2つの一般的な離散時間マルコフ連鎖の混合時間について検討する。
二つの微分可能な厳密凸函数から生じる任意の$Phi$-divergenceが、これらのマルコフ連鎖に沿って指数的に0$に収束することを示す。
- 参考スコア（独自算出の注目度）: 14.34147140416535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the mixing time of two popular discrete time Markov chains in continuous space, the unadjusted Langevin algorithm and the proximal sampler, which are discretizations of the Langevin dynamics. We extend mixing time analyses for these Markov chains to hold in $\Phi$-divergence. We show that any $\Phi$-divergence arising from a twice-differentiable strictly convex function $\Phi$ converges to $0$ exponentially fast along these Markov chains, under the assumption that their stationary distributions satisfies the corresponding $\Phi$-Sobolev inequality. Our rates of convergence are tight and include as special cases popular mixing time regimes, namely the mixing in chi-squared divergence under a Poincar\'e inequality, and the mixing in relative entropy under a log-Sobolev inequality. Our results follow by bounding the contraction coefficients arising in the appropriate strong data processing inequalities.
- Abstract（参考訳）: 連続空間における2つの一般的な離散時間マルコフ連鎖の混合時間、調整されていないランゲヴィンアルゴリズムと、ランゲヴィン力学の離散化である近位サンプリング器について検討する。
これらのマルコフ連鎖に対する混合時間解析を$\Phi$-divergenceで保持するように拡張する。
二つの微分可能な厳密凸関数$\Phi$-divergence から生じる任意の$\Phi$-divergence がこれらのマルコフ連鎖に沿って指数関数的に$0$に収束することを示し、それらの定常分布が対応する$\Phi$-Sobolevの不等式を満たすことを仮定する。
我々の収束速度は厳密であり、特に一般的な混合時間体制、すなわちポアンカーの不等式の下でのカイ二乗発散の混合、対数ソボレフ不等式の下での相対エントロピーの混合を含む。
その結果, 適切なデータ処理の不等式に起因した収縮係数の有界化が得られた。
関連論文リスト
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。
本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。
我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
論文 参考訳（メタデータ） (2024-10-03T09:07:13Z) - In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies [7.70133333709347]
高次元凸体を一様にサンプリングするための新しいランダムウォークを提案する。
出力をより強力な保証で、最先端のランタイムの複雑さを実現する。
論文 参考訳（メタデータ） (2024-05-02T16:15:46Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Taming under isoperimetry [0.0]
本稿では,ログの増大に伴う分布のサンプル化を目的としたLangevinベースのスキームであるmathbfsTULA$を提案する。
非漸近KLを導出し、結果としてLog-Sobolevの不等式を満たす。
論文 参考訳（メタデータ） (2023-11-15T14:44:16Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev [25.18241929887685]
離散時間ランゲヴィンモンテカルロアルゴリズムに対する最初の収束保証を提供する。
従来の研究とは異なり、我々の結果は滑らかさの弱さを許容し、凸性や解離性条件を必要としない。
論文 参考訳（メタデータ） (2021-12-23T15:56:33Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Concentration inequality for U-statistics of order two for uniformly
ergodic Markov chains [0.0]
我々は、一様エルゴード型マルコフ鎖に対する位数2のU-統計量に対する濃度不等式を証明した。
独立確率変数と正準核のU統計値の集中結果を示したArconesとGin'eの収束率を復元できることが示される。
論文 参考訳（メタデータ） (2020-11-20T15:14:34Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Finite Time Analysis of Linear Two-timescale Stochastic Approximation
with Markovian Noise [28.891930079358954]
線形2時間スケールSAスキームに対して有限時間解析を行う。
我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。
一致した下界を持つ予測誤差の拡張を示す。
論文 参考訳（メタデータ） (2020-02-04T13:03:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。