論文の概要: Entropy contraction of the Gibbs sampler under log-concavity
- arxiv url: http://arxiv.org/abs/2410.00858v1
- Date: Tue, 1 Oct 2024 16:50:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-05 03:46:09.190636
- Title: Entropy contraction of the Gibbs sampler under log-concavity
- Title（参考訳）: 対数共振下におけるギブス試料のエントロピー収縮
- Authors: Filippo Ascolani, Hugo Lavenant, Giacomo Zanella,
- Abstract要約: ランダムスキャンギブスサンプリング器は相対エントロピーで収縮し、関連する収縮率を鋭く評価する。
我々の手法は多用途であり、Metropolis-within-GibbsスキームやHit-and-Runアルゴリズムにまで拡張されている。
- 参考スコア（独自算出の注目度）: 0.16385815610837165
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gibbs sampler (a.k.a. Glauber dynamics and heat-bath algorithm) is a popular Markov Chain Monte Carlo algorithm which iteratively samples from the conditional distributions of a probability measure $\pi$ of interest. Under the assumption that $\pi$ is strongly log-concave, we show that the random scan Gibbs sampler contracts in relative entropy and provide a sharp characterization of the associated contraction rate. Assuming that evaluating conditionals is cheap compared to evaluating the joint density, our results imply that the number of full evaluations of $\pi$ needed for the Gibbs sampler to mix grows linearly with the condition number and is independent of the dimension. If $\pi$ is non-strongly log-concave, the convergence rate in entropy degrades from exponential to polynomial. Our techniques are versatile and extend to Metropolis-within-Gibbs schemes and the Hit-and-Run algorithm. A comparison with gradient-based schemes and the connection with the optimization literature are also discussed.
- Abstract（参考訳）: ギブスサンプリングアルゴリズム(Gibs sampler、別名Glauber dynamics and heat-bath algorithm)はマルコフ・チェイン・モンテカルロアルゴリズムであり、確率測度$\pi$ of interestの条件分布から反復的にサンプリングされる。
例えば、$\pi$ が強い対数凹であるという仮定の下で、ランダムスキャン Gibbs sampler が相対エントロピーで収縮し、関連する収縮率を鋭く評価することを示した。
条件値の評価は, 接合密度の評価よりも安価であるとして, ギブス試料の混合に必要な$$\pi$の完全な評価回数は, 条件数と線形に増加し, 寸法に依存しないことが示唆された。
もし$\pi$が非強対数であるなら、エントロピーの収束速度は指数関数から多項式へと低下する。
我々の手法は多用途であり、Metropolis-within-GibbsスキームやHit-and-Runアルゴリズムにまで拡張されている。
勾配に基づくスキームと最適化文献との関係についても論じる。
関連論文リスト
- 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) - A mixing time bound for Gibbs sampling from log-smooth log-concave distributions [0.8702432681310401]
ログスムースと強いログコンケーブ対象分布のクラスにおけるギブスサンプリング器の挙動について検討した。
Gibbsのサンプルは、少なくとも$Ostarleft(kappa2 n7.5left(maxleft1,sqrtfrac1nlog frac2Mgammarightright2right)$のステップで、条件番号$kappa$の分布から合計で$gamma$以下の誤差を持つサンプルを生成する必要がある。
論文 参考訳（メタデータ） (2024-12-23T19:00:02Z) - Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
データサイズが大きくなるにつれて、イテレーションコストの削減が重要な目標になります。
科学計算における初期値問題の並列シミュレーションの成功に触発されて,タスクをサンプリングするための並列Picard法を提案する。
本研究は,動力学に基づくサンプリング・拡散モデルの科学的計算におけるシミュレーション手法の潜在的利点を強調した。
論文 参考訳（メタデータ） (2024-12-10T11:50:46Z) - Path integral Monte Carlo in a discrete variable representation with Gibbs sampling: dipolar planar rotor chain [0.0]
離散化された連続的な自由度と拒絶のないギブズサンプリングに基づくパス積分モンテカルロ(PIMC)アプローチを提案する。
従来のMetroplolis-Hastings法と比較して,Gibbs法が有効であることを示す。
論文 参考訳（メタデータ） (2024-10-17T15:04:39Z) - Linear Complexity Gibbs Sampling for Generalized Labeled Multi-Bernoulli
Filtering [4.186094981300538]
GLMB(Generalized Labeled Multi-Bernoulli)の密度は、単一対象フィルタリングにおいてガウスに類似した多対象系アプリケーションのホストに現れる。
GLMBフィルタ密度の構造を利用して,$mathcalO(T(P+M))$複雑性を実現する。
この革新により、GLMBフィルタの実装は$mathcalO(TP2M)$複雑さから$mathcalO(T(P+M+log T)+PMに縮小できる。
論文 参考訳（メタデータ） (2022-11-29T09:26:43Z) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳（メタデータ） (2022-06-13T14:57:35Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。