CS Paper Radar

Uniform Race: Parameter-Free Approximate Rejection Sampling

Seiyun Shin, Juhyeong Pang, Kwang-Sung Jun

cs.LG stat.ML ·submitted 2026-09-28 08:53 UTC · v2
theory

Abstract

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.

Comment
51 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Online Allocation using Few Samples

cs.DS cs.GT ·2026-09-15 ·Matthew Faw, Sahil Singla, Yifan Wang
similarity 0.63
Abstract

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pmε)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $ε$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

0.23

Optimal Sample Complexity for Max-Cut

cs.DS ·2026-11-02 ·Itamar Bender, Robert Krauthgamer
theory similarity 0.60
Abstract

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.

0.21

Shared Randomness and Parallel Rounds in Permutation Sampling

cs.IT cs.DS ·2026-10-31 ·Haoxiang Huang
similarity 0.60
Abstract

We study the shared randomness needed to sample a uniform permutation in parallel output rounds. Coordinates committed in the same round are independent conditional on the complete history and the current shared choice. Previous outputs are public; local computation and private randomness are free. We charge each shared choice by the logarithm of its conditional support size and sum these costs along the worst execution path. At every fixed round density $ρ\in(0,1)$, the optimal limiting total-variation error under any $o(n)$ shared budget matches the conditional-marginal optimum, even with arbitrary local kernels and adaptive coordination. A fixed improvement requires linear cost. For exact sampling in $R=Θ(n)$ rounds, the optimum is $nΦ(R/n)+O(\log n)$, where $Φ$ linearly interpolates $Φ(1/q)=\log q$. A protocol attaining this rate uses an initial seed and at most one further binary shared choice. When $\lceil n/2\rceil\le R\le n$, the finite optimum is $\log\binom{2(n-R)}{n-R}$, attained by an initial seed alone. The approximate converse uses an entropy inequality for sparse injections to control overlap with the target. The exact construction reuses randomness retained in a shared label partition after the first-stage outputs are exposed.

0.22

Hypothesis Selection via Weighted Medians

cs.DS cs.LG ·2026-10-14 ·Liang-Yu Zou
similarity 0.60
Abstract · fix some typos

Given $n$ distributions (hypotheses) $\mathcal H=\{H_1,\ldots,H_n\}$ and samples from an unknown target distribution $P$, proper hypothesis selection seeks a distribution whose total variation distance to $P$ is close to the best achievable within the known distributions. We give an algorithm that, using $O(\varepsilon^{-2}\log(n/δ))$ target samples, running in $O(n\varepsilon^{-2}\log(n/δ))$ time, with probability at least $1-δ$, returns $H_{\hat i}$ satisfying $d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilon.$ The algorithm achieves the optimal approximation factor and sample complexity. The running time improves the dependence on the failure probability from polynomial to logarithmic in the state-of-the-art bound $\tilde{O}(n\varepsilon^{-2}δ^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.

0.33

Order-selection Prophet Inequality (Almost) Goes I.I.D

cs.DS cs.GT ·2026-10-26 ·Bo Peng, Zhihao Gavin Tang
theory similarity 0.60
Abstract · 75 pages

We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $Γ_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $Γ_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.

0.19

Safety Hacking in Constrained Best-of-$N$ Inference-time Scaling

cs.LG cs.AIcs.CLcs.CR ·2026-08-24 ·Akifumi Wachi, Takumi Tanabe, Youhei Akimoto
similarity 0.58
Abstract

Inference-time pipelines often sample multiple outputs, filter them with a learned safety model, and return the proxy-feasible output with the highest learned reward. We show that this composition creates a two-stage failure: an imperfect safety proxy first contaminates the feasible set with unsafe outputs, and reward maximization can then amplify this residual contamination. We define \emph{safety hacking} as selecting an output that passes the learned constraint but violates the true safety criterion. For constrained Best-of-$N$ sampling, we derive finite-$N$ bounds governed by the joint upper reward tails of safe and unsafe outputs within the proxy-feasible set. If unsafe-but-feasible outputs have the heavier tail, safety hacking becomes asymptotically certain as $N$ grows, even when false-positive mass and average safety- and reward-proxy errors are arbitrarily small. We also show that policies within a bounded $χ^2$ divergence from the proxy-feasible reference distribution admit an $N$-independent safety-hacking bound, and instantiate this general coverage-control principle with constrained pessimistic sampling. Coverage control limits amplification but cannot repair a contaminated feasible set: admitted unsafe outputs may still be favored, and regularized selection is not necessarily safer than constrained Best-of-$N$ for every reward proxy. Toy and language-model experiments characterize both contamination and its reward-tail amplification, which exposes an inherent difficulty in inference-time scaling with learned safety models.

0.37

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

cs.GT cs.DS ·2026-09-26 ·Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni, Ruta Mehta, Parnian Shahkar
similarity 0.58
Abstract · 48 pages

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $ω(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

0.31

Balanced Sampling in Stochastic Multi-objective Bandits

cs.LG stat.ML ·2026-10-26 ·Mengfan Xu
theory similarity 0.58
Abstract

In stochastic multi-objective bandits, Pareto optimal arms may represent different trade-offs among objectives. Balanced sampling across them is important in practical settings such as online advertising. Yet, there seems to be little consensus on how to measure fairness, to our best knowledge. Achieving fairness is also tough as the set of Pareto optimal arms is unknown, and early sampling decisions may create imbalances that are difficult to erase afterwards. We measure unfairness by the KL divergence from the uniform distribution over the true Pareto set to the empirical measure induced by the sampling trajectory. Nicely, this measure admits an exact decomposition that separates the cost of sampling suboptimal arms from the imbalance among Pareto optimal arms. With a recursive form for unfairness, we develop \emph{adaptive top-two sampling}, which combines sampling counts and empirical evidence of Pareto membership to define a gain for each arm and guide sampling without committing to an estimated Pareto set. When the Pareto set is stable under small perturbations, we establish an $O(\log T/T)$ and $O(T^{-1})$ bound on expected unfairness and variance, respectively. Information-theoretic lower bounds show that the $\log T/T$ rate can be unavoidable for uniformly fair policies on stable instances, matching our upper bound. More surprisingly, stability is indeed crucial, as the expected unfairness can be $ω(\log T/T)$ without it. Finally, we create a variant that encourages exploration of undersampled arms to reduce the risk of persistent underallocation. At sufficiently large horizons, it preserves the rate on the expected unfairness while admitting a sharper bound of $O(\log^2 T/T^2)$ on variance. Numerical studies support these findings and suggest practical insights.

0.21