論文の概要: Uniform Race: Parameter-Free Approximate Rejection Sampling

• arxiv url: http://arxiv.org/abs/2609.34639v1
• Date: Mon, 28 Sep 2026 08:53:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 11:39:36.897635
• Title: Uniform Race: Parameter-Free Approximate Rejection Sampling
• Title（参考訳）: 均一レース:パラメータフリーな近似型リジェクションサンプリング
• Abstract要約: 重み付けに基づく一様レースと呼ばれるパラメータフリーサンプリングアルゴリズムを提案する。 全ての予算$N$に対して、その総変動誤差は、固定閾値$M$の全てのRS上限を同時に満たす。 また、その出力分布条件を最大スコアに特徴付け、それが正確にターゲット$$であるかどうかを特定する。
• 参考スコア（独自算出の注目度）: 17.690308598077703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study approximate sampling: given $N$ independent samples from a proposal distribution $μ$, the goal is to select one whose distribution is close to a target $π$ specified only up to a normalizing constant. Block and Polyanskiy (2023) provide finite budget error bounds for approximate rejection sampling (RS) as a function of the acceptance threshold $M$. The threshold $M$ giving the smallest bound, however, depends on properties of $(π,μ)$ that are typically unavailable from the observed sample. This raises a natural question: Can one attain the best RS guarantee without taking $M$ as input? We answer affirmatively by proposing a parameter-free sampling algorithm called uniform race (UR), based on importance weights, which are ratios of target to proposal probabilities (or densities). It divides each observed weight by an independent uniform random variable to form a score and returns the candidate with the largest score. For every budget $N$, its total variation error satisfies the RS upper bound for every fixed threshold $M$ simultaneously, thereby achieving the best such bound in hindsight. We also characterize its output distribution conditional on the largest score, identifying when it is exactly the target $π$. Uniform race has no larger total variation error than a natural budget-calibrated RS derived from Rohatgi et al. (2025) and sampling importance resampling (SIR). In particular, we exhibit instances where UR's error is exponentially smaller in $N$ than that of either baseline. Furthermore, we establish conditions under which attaining this RS guarantee for every $(π,μ)$ uniquely determines the selection probabilities as those of UR. Finally, test-time scaling experiments on LLM math-reasoning tasks corroborate the theoretical comparisons and demonstrate that UR remains competitive in ground-truth accuracy without requiring threshold selection.
• Abstract（参考訳）: 提案分布から$N$独立なサンプルを$μ$とすると、その分布が正規化定数までのみ指定された目標$π$に近いものを選択することが目的である。 Block and Polyanskiy (2023) は、受入閾値$M$の関数として、近似回帰サンプリング(RS)に対する有限予算誤差境界を提供する。 しかし、最小境界を与える閾値$M$は、一般に観察されたサンプルから利用できない$(π,μ)$の性質に依存する。 入力として$M$を取ることなく、最高のRS保証を達成できますか? 提案する確率(密度)に対する目標の比率である重み付けに基づいて,一様レース (UR) と呼ばれるパラメータフリーサンプリングアルゴリズムを提案することにより,肯定的に答える。 観測された各重量を独立した一様ランダム変数で割ってスコアを形成し、最も大きいスコアで候補を返す。 すべての予算$N$に対して、その総変動誤差は、固定しきい値$M$の全てのRS上限を同時に満たし、それによって、後向きの最良の境界を達成する。 また、その出力分布条件を最大スコアに特徴付け、それが正確にターゲットの$π$であるかどうかを特定する。 均一レースは、Rohatgi et al (2025) から派生した自然な予算校正されたRSよりも大きな総変分誤差がなく、サンプリング重要度再サンプリング (SIR) がある。 特に、URの誤差がどちらのベースラインよりも指数関数的に$N$小さい場合を示す。 さらに、この RS を保証する条件を $(π,μ)$ ごとに確立し、UR の選択確率を UR のものと一意に決定する。 最後に、LLM数学推論タスクにおける試験時間スケーリング実験は、理論的比較を相関させ、URがしきい値選択を必要とせず、地道的精度で競争力を維持することを示した。

関連論文リスト

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• Variance Reduction for the Independent Metropolis Sampler [11.074080383657453]
  我々は、$pi$がKL分散の下で別の密度$q$に十分近い場合、$pi$からサンプルを得る独立したサンプリング器は、$pi$からサンプリングするi.d.よりも小さな分散を達成することを証明した。 提案手法は,KLの目標との偏差が低減されるように,提案密度に適応する適応型独立メトロポリスアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-25T16:38:53Z)
• 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)
• The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning [29.44582058149344]
  n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。 次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
  論文  参考訳（メタデータ） (2023-02-09T14:20:14Z)
• 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)

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

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