論文の概要: 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アルゴリズムにまで拡張されている。
勾配に基づくスキームと最適化文献との関係についても論じる。
関連論文リスト
- 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) - Closed-form Filtering for Non-linear Systems [83.91296397912218]
我々は密度近似と計算効率の面でいくつかの利点を提供するガウスPSDモデルに基づく新しいフィルタのクラスを提案する。
本研究では,遷移や観測がガウスPSDモデルである場合,フィルタリングを効率的にクローズド形式で行うことができることを示す。
提案する推定器は, 近似の精度に依存し, 遷移確率の正則性に適応する推定誤差を伴って, 高い理論的保証を享受する。
論文 参考訳（メタデータ） (2024-02-15T08:51:49Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - 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) - Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms [39.746670539407084]
我々は、$bbRd$の強い対数凹密度からサンプリングする問題を考察する。
必要なログ密度の勾配クエリ数に基づいて,情報理論の下界を証明した。
論文 参考訳（メタデータ） (2020-02-01T23:46:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。