← 研踪 PaperTrailarXiv:2609.34639 · v2
Uniform Race: Parameter-Free Approximate Rejection Sampling
首次提交 2026-09-28 16:53
版本更新 2026-11-04 13:10
雷达观测 2026-11-05 11:10
摘要
Consider the approximate sampling problem: 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. The seminal work of Block & Polyanskiy (2023) provides a total variation (TV) error bound for approximate rejection sampling (RS) as a function of the algorithm's acceptance threshold $M$. The ideal threshold $M$ that minimizes the 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 the best $M$ as input? We answer this question affirmatively by proposing a parameter-free sampling algorithm called uniform race (UR). UR computes a score for each sample $y$ that is the importance weight $π(y)/μ(y)$ divided by an independent uniform random variable and then returns the one with the highest score. We prove that UR attains the best $M$-tuned TV error bound for RS. That is, UR, without knowing the best $M$, achieves the same performance guarantee as RS that takes the best $M$ as input. We also prove that UR has no larger TV error than the budget-calibrated version of the rejection sampler of Rohatgi et al. (2025) and sampling importance resampling (SIR). In particular, we identify instances where UR's error is exponentially smaller in $N$ than that of these two baselines. 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 reasoning tasks corroborate the theoretical comparisons and demonstrate that UR remains competitive without requiring threshold selection.
作者备注：51 pages, 5 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 13:10 · 最新观测版本
Uniform Race: Parameter-Free Approximate Rejection Sampling
Consider the approximate sampling problem: 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. The seminal work of Block & Polyanskiy (2023) provides a total variation (TV) error bound for approximate rejection sampling (RS) as a function of the algorithm's acceptance threshold $M$. The ideal threshold $M$ that minimizes the 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 the best $M$ as input? We answer this question affirmatively by proposing a parameter-free sampling algorithm called uniform race (UR). UR computes a score for each sample $y$ that is the importance weight $π(y)/μ(y)$ divided by an independent uniform random variable and then returns the one with the highest score. We prove that UR attains the best $M$-tuned TV error bound for RS. That is, UR, without knowing the best $M$, achieves the same performance guarantee as RS that takes the best $M$ as input. We also prove that UR has no larger TV error than the budget-calibrated version of the rejection sampler of Rohatgi et al. (2025) and sampling importance resampling (SIR). In particular, we identify instances where UR's error is exponentially smaller in $N$ than that of these two baselines. 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 reasoning tasks corroborate the theoretical comparisons and demonstrate that UR remains competitive without requiring threshold selection.
查看此版本解读 →查看此版本原文 ↗