論文の概要: From Minimax Optimal Importance Sampling to Uniformly Ergodic Importance-tempered MCMC
- arxiv url: http://arxiv.org/abs/2506.19186v1
- Date: Mon, 23 Jun 2025 23:05:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-25 19:48:23.413368
- Title: From Minimax Optimal Importance Sampling to Uniformly Ergodic Importance-tempered MCMC
- Title（参考訳）: Minimax Optimal Importance Smpling から Uniformly Ergodic Importance-tempered MCMC へ
- Authors: Quan Zhou,
- Abstract要約: 我々は、重要サンプリングスキームの使用に関して、密接に関連する2つの理論的貢献を行う。
まず、目標分布に1/2$以上の確率の原子が存在しない場合に限って、目標値と最小値の試行分布が最適であることを証明する。
第二に、定常分布を保ちながらメトロポリス-ハスティングスアルゴリズムを実行することは、しばしば有利であると主張する。
- 参考スコア（独自算出の注目度）: 4.662958544712181
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We make two closely related theoretical contributions to the use of importance sampling schemes. First, for independent sampling, we prove that the minimax optimal trial distribution coincides with the target if and only if the target distribution has no atom with probability greater than $1/2$, where "minimax" means that the worst-case asymptotic variance of the self-normalized importance sampling estimator is minimized. When a large atom exists, it should be downweighted by the trial distribution. A similar phenomenon holds for a continuous target distribution concentrated on a small set. Second, we argue that it is often advantageous to run the Metropolis--Hastings algorithm with a tempered stationary distribution, $\pi(x)^\beta$, and correct for the bias by importance weighting. The dynamics of this "importance-tempered" sampling scheme can be described by a continuous-time Markov chain. We prove that for one-dimensional targets with polynomial tails, $\pi(x) \propto (1 + |x|)^{-\gamma}$, this chain is uniformly ergodic if and only if $1/\gamma < \beta < (\gamma - 2)/\gamma$. These results suggest that for target distributions with light or polynomial tails of order $\gamma > 3$, importance tempering can improve the precision of time-average estimators and essentially eliminate the need for burn-in.
- Abstract（参考訳）: 我々は、重要サンプリングスキームの使用に関して、密接に関連する2つの理論的貢献を行う。
まず、独立サンプリングにおいて、最小値の最適試行分布が目標値と一致することを証明し、目標分布が1/2$以上の原子を持たない場合に限り、「最小値」は自己正規化重要度サンプリング推定器の最悪の漸近分散を最小化することを意味する。
大きな原子が存在する場合、試薬分布によって重み付けされなければならない。
同様の現象は、小さな集合に集中した連続的な目標分布である。
第二に、しばしばMetropolis-Hastingsアルゴリズムを保温定常分布$\pi(x)^\beta$で実行し、重み付けによってバイアスを補正することが有利である。
この「重要タンペア」サンプリングスキームの力学は、連続時間マルコフ連鎖によって説明できる。
多項式の尾を持つ 1 次元のターゲットに対して、$\pi(x) \propto (1 + |x|)^{-\gamma}$ が一様エルゴード的であることと、$/\gamma < \beta < (\gamma - 2)/\gamma$ が成り立つことを証明する。
これらの結果は, 次数$\gamma > 3$の光あるいは多項式のテールを持つ対象分布に対して, 平均時間推定器の精度を向上し, 本質的にバーンインの必要性を排除できることを示唆している。
関連論文リスト
- Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアンニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - Estimation of entropy-regularized optimal transport maps between
non-compactly supported measures [15.857723276537248]
本稿では,ガウシアン以下の音源と目標測度の間の2乗ユークリッドコストでエントロピー規則化された最適輸送マップを推定する問題に対処する。
論文 参考訳（メタデータ） (2023-11-20T17:18:21Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - 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) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
確率分布が未知な分布の不確実性の下でBQOについて検討する。
標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。
この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
論文 参考訳（メタデータ） (2020-01-19T12:00:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。