arXiv:2609.34639v2 cs.LG

Uniform Race: Parameter-Free Approximate Rejection Sampling

Seiyun Shin, Juhyeong Pang, Kwang-Sung Jun

제출 2026-11-05

원문 초록

Consider the approximate sampling problem: given $N$ independent samples from a proposal distribution $\mu$, the goal is to select one whose distribution is close to a target $\pi$ 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 $(\pi, \mu)$ 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 $\pi(y)/\mu(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 $(\pi, \mu)$ 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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.34639v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.