論文の概要: Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information
- arxiv url: http://arxiv.org/abs/2402.17067v2
- Date: Sat, 08 Feb 2025 18:00:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:24:20.248907
- Title: Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information
- Title(参考訳): 約$$-Mutual Informationの縮約によるランゲヴィンダイナミクスとアルゴリズムに沿ったサンプルの依存性のキャラクタリゼーション
- Authors: Jiaming Liang, Siddharth Mitra, Andre Wibisono,
- Abstract要約: 連続空間サンプリングにおいて,サンプルがマルコフ連鎖に沿ってほぼ独立になる速度について検討する。
我々の証明手法は,マルコフ連鎖に沿ったSDPI(Strong Data Processing Inequality)を示すものである。
- 参考スコア(独自算出の注目度): 16.54557731304283
- License:
- Abstract: The mixing time of a Markov chain determines how fast the iterates of the Markov chain converge to the stationary distribution; however, it does not control the dependencies between samples along the Markov chain. In this paper, we study the question of how fast the samples become approximately independent along popular Markov chains for continuous-space sampling: the Langevin dynamics in continuous time, and the Unadjusted Langevin Algorithm and the Proximal Sampler in discrete time. We measure the dependence between samples via $\Phi$-mutual information, which is a broad generalization of the standard mutual information, and which is equal to $0$ if and only if the the samples are independent. We show that along these Markov chains, the $\Phi$-mutual information between the first and the $k$-th iterate decreases to $0$ exponentially fast in $k$ when the target distribution is strongly log-concave. Our proof technique is based on showing the Strong Data Processing Inequalities (SDPIs) hold along the Markov chains. To prove fast mixing of the Markov chains, we only need to show the SDPIs hold for the stationary distribution. In contrast, to prove the contraction of $\Phi$-mutual information, we need to show the SDPIs hold along the entire trajectories of the Markov chains; we prove this when the iterates along the Markov chains satisfy the corresponding $\Phi$-Sobolev inequality, which is implied by the strong log-concavity of the target distribution.
- Abstract(参考訳): マルコフ鎖の混合時間は、マルコフ鎖の反復が定常分布にどれだけ早く収束するかを決定するが、マルコフ鎖に沿ったサンプル間の依存関係を制御しない。
本稿では,連続時間におけるランゲヴィンダイナミクスと,離散時間における非調整ランゲヴィンアルゴリズムと近距離サンプリングという,一般的なマルコフ連鎖に沿って,サンプルがどの程度の速度で独立になるのかを考察する。
サンプル間の依存度を$\Phi$-mutual information, これは標準相互情報の広範な一般化であり、サンプルが独立である場合に限り$0$と等しい。
これらのマルコフ連鎖に沿って、ターゲット分布が強い対数展開の場合、第1次と第1次を繰り返す$k$-番目の繰り返しの間の$\Phi$-mutual情報は、$k$で指数関数的に$0$に減少することを示す。
我々の証明手法は,マルコフ連鎖に沿ったSDPI(Strong Data Processing Inequality)を示すものである。
マルコフ連鎖の高速混合を証明するためには、静止分布に対してSDPIが保持されていることを示す必要がある。
対照的に、$\Phi$-mutual 情報の縮約を証明するためには、SDPIがマルコフ連鎖の全軌道に沿って保持されていることを示す必要がある。
関連論文リスト
- Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。
マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
論文 参考訳(メタデータ) (2024-11-14T01:37:02Z) - Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler [14.34147140416535]
連続空間における2つの一般的な離散時間マルコフ連鎖の混合時間について検討する。
二つの微分可能な厳密凸函数から生じる任意の$Phi$-divergenceが、これらのマルコフ連鎖に沿って指数的に0$に収束することを示す。
論文 参考訳(メタデータ) (2024-10-14T16:41:45Z) - Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。
本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。
我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
論文 参考訳(メタデータ) (2024-10-03T09:07:13Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳(メタデータ) (2023-10-09T18:38:56Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳(メタデータ) (2023-06-27T08:15:28Z) - Enabling Quantum Speedup of Markov Chains using a Multi-level Approach [0.0]
マルコフ連鎖を混合する量子スピードアップは、ゆっくりと変化する$r$マルコフ鎖の構成に基づいて達成できる。
低分解能マルコフ鎖の密度関数を用いてマルコフ鎖を高分解能で温めることができることを示す。
論文 参考訳(メタデータ) (2022-10-25T15:17:52Z) - Score-Based Diffusion meets Annealed Importance Sampling [89.92133671626327]
Annealed Importance Smpling はいまだに限界推定の最も効果的な方法の1つである。
我々は、スコアベース生成モデルにおける最近の進歩を活用し、AIS提案の最適拡張目標分布を近似する。
論文 参考訳(メタデータ) (2022-08-16T12:13:29Z) - A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
我々は、$pi(x)=|langle x|psirangle|2$ からビット文字列 $x$ を考える。
我々の主な結果は、逆スペクトルギャップ$H$と関連する連続時間Markov Chainと定常状態$pi$の混合時間との直接リンクを記述する。
論文 参考訳(メタデータ) (2022-07-14T16:38:42Z) - A Matrix Chernoff Bound for Markov Chains and Its Application to
Co-occurrence Matrices [30.49132891333353]
正則な(周期的かつ既約な)有限マルコフ連鎖を介してサンプリングされた行列値確率変数の和に対するチェルノフ型有界性を証明する。
我々の証明は、[Garg et al. STOC '18] とマルコフ連鎖に対するスカラーチャーノフ-ホーフディング境界の行列展開(正規無向グラフ)に基づいている。
マルコフ連鎖に対する我々の行列チェルノフバウンドは、逐次データに対する共起統計量の挙動を解析するために応用できる。
論文 参考訳(メタデータ) (2020-08-06T05:44:54Z) - 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) - Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
隠れマルコフモデルのためのマルコフ連鎖モンテカルロ (MCMC) アルゴリズムは、しばしば前向きのサンプリング器に依存する。
これにより、時系列の長さが増加するにつれて計算が遅くなり、サブサンプリングベースのアプローチの開発が動機となる。
本稿では,パラメータの勾配を計算する際に,希少な潜伏状態に対応するオーバーサンプリング観測を対象とするサブサンプリング手法を提案する。
論文 参考訳(メタデータ) (2018-10-31T17:44:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。