論文の概要: A mixing time bound for Gibbs sampling from log-smooth log-concave distributions

• arxiv url: http://arxiv.org/abs/2412.17899v1
• Date: Mon, 23 Dec 2024 19:00:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-25 15:54:19.673183
• Title: A mixing time bound for Gibbs sampling from log-smooth log-concave distributions
• Title（参考訳）: 対数平滑な対数凹分布からのギブスサンプリングのための混合時間
• Authors: Neha S. Wadia,
• Abstract要約: ログスムースと強いログコンケーブ対象分布のクラスにおけるギブスサンプリング器の挙動について検討した。 Gibbsのサンプルは、少なくとも$Ostarleft(kappa2 n7.5left(maxleft1,sqrtfrac1nlog frac2Mgammarightright2right)$のステップで、条件番号$kappa$の分布から合計で$gamma$以下の誤差を持つサンプルを生成する必要がある。
• 参考スコア（独自算出の注目度）: 0.8702432681310401
• License:
• Abstract: The Gibbs sampler, also known as the coordinate hit-and-run algorithm, is a Markov chain that is widely used to draw samples from probability distributions in arbitrary dimensions. At each iteration of the algorithm, a randomly selected coordinate is resampled from the distribution that results from conditioning on all the other coordinates. We study the behavior of the Gibbs sampler on the class of log-smooth and strongly log-concave target distributions supported on $\mathbb{R}^n$. Assuming the initial distribution is $M$-warm with respect to the target, we show that the Gibbs sampler requires at most $O^{\star}\left(\kappa^2 n^{7.5}\left(\max\left\{1,\sqrt{\frac{1}{n}\log \frac{2M}{\gamma}}\right\}\right)^2\right)$ steps to produce a sample with error no more than $\gamma$ in total variation distance from a distribution with condition number $\kappa$.
• Abstract（参考訳）: ギブス・サンプリング(Gibbs sampler)または座標ヒット・アンド・ランアルゴリズム(英: coordinate hit-and-run algorithm)は、任意の次元の確率分布からサンプルを引き出すのに広く用いられるマルコフ連鎖である。 アルゴリズムの各イテレーションにおいて、ランダムに選択された座標は、他のすべての座標の条件付けの結果生じる分布から再サンプリングされる。 我々は,$\mathbb{R}^n$で支持された対数平滑かつ強対数凹のターゲット分布のクラスにおけるギブスサンプリング器の挙動について検討した。 初期分布がターゲットに対して$M$-warmであると仮定すると、Gibs サンプルは少なくとも$O^{\star}\left(\kappa^2 n^{7.5}\left(\max\left\{1,\sqrt {\frac{1}{n}\log \frac{2M}{\gamma}}\right\right)^2\right)$ 条件番号 $\kappa$ の分布から、誤差が$\gamma$ 以下のサンプルを生成するためのステップが要求される。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Entropy contraction of the Gibbs sampler under log-concavity [0.16385815610837165]
  ランダムスキャンギブスサンプリング器は相対エントロピーで収縮し、関連する収縮率を鋭く評価する。 我々の手法は多用途であり、Metropolis-within-GibbsスキームやHit-and-Runアルゴリズムにまで拡張されている。
  論文  参考訳（メタデータ） (2024-10-01T16:50:36Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Fast parallel sampling under isoperimetry [10.619901778151336]
  ログソボレフの不等式を満たすディストリビューション$pi$ over $mathbb Rd$から並列にサンプリングする方法を示す。 提案アルゴリズムは分布$hatpi$からKullback-Leibler分散の$pi$に近いサンプルを出力する。
  論文  参考訳（メタデータ） (2024-01-17T07:24:18Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Perfect Sampling from Pairwise Comparisons [26.396901523831534]
  分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-23T11:20:30Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• An MCMC Method to Sample from Lattice Distributions [4.4044968357361745]
  我々はMarkov Chain Monte Carloアルゴリズムを導入し、$d$-dimensional lattice $Lambdaでサポートされている確率分布からサンプルを生成する。 提案する分布として$pi$を使用し、適切な目標分布に対するメトロポリス・ハスティングの受け入れ比率を算出する。
  論文  参考訳（メタデータ） (2021-01-16T15:01:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。