CS Paper Radar

Log-optimal two-sample testing by betting

Aaditya Ramdas

cs.IT math.STstat.MEstat.ML ·submitted 2026-11-14 01:14 UTC · v1

Abstract

For each standard Borel observation space, we construct a single anytime-valid two-sample procedure that is asymptotically log-optimal for every pair of unknown probability laws and every limiting ratio of diverging sample sizes, including zero and infinity. For independent balanced pairs, the optimal log-wealth rate is $2\JS(P,Q)$, where $\JS$ is the Jensen--Shannon divergence. Unequal sizes yield weighted Jensen--Shannon information and the one-sample limit $\log W(n_1,n_2)/n_2\to\KL(Q\|P)$ when $n_1/n_2\to\infty$. Refining finite partitions and logarithmic-loss learning with measurable characteristic kernels provide universal constructions. Our main contribution is the generality of our construction, and its connections to classical batch efficiency notions. Practical implementations allow continuous classifier fine-tuning, as demonstrated on finite alphabets, Gaussian data, and handwritten digits.

Comment
55pgs

Closest papers

Nearest neighbours by meaning across the whole index.

Extreme classification: beating chance with one training example from each class

cs.LG stat.ML ·2026-09-17 ·Kevin Bleakley, Aaditya Ramdas
similarity 0.64
Abstract

We study a minimal classification problem: Given independent labeled observations $X\sim P$ and $Z\sim Q$ from two unknown distributions $P,Q$, and given an independent target $Y$ drawn with equal probability from $P$ or $Q$, can one classify $Y$ strictly better than chance whenever $P\neq Q$? The one-nearest-neighbor rule succeeds for every pair of multivariate Gaussian distributions with distinct means and a common positive-definite covariance matrix but can perform strictly worse than chance even for smooth densities on the real line. We construct a fixed randomized kernel rule whose expected accuracy is exactly $1/2+\operatorname{MMD}_k^2(P,Q)/4$, and obtain characteristic kernels on countably generated measurable spaces from countable families of measurable binary questions. We also prove that a deterministic order rule on $\mathbb R$ beats chance for every pair of distinct Borel probability measures. A measurable encoding then gives a deterministic distribution-free rule which beats chance on every countably generated measurable space, in particular every separable metric space. Finally, we show that no rule works for every distinct pair of distributions and every unknown unbalanced class prior; under adaptive target-class selection, every rule other than a fair coin is strictly worse than chance for some finitely supported pair.

0.30

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

cs.LG ·2026-10-18 ·Guangjian Zhang
theory similarity 0.63
Abstract · 92 pages

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

0.30

Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness

cs.LG stat.ML ·2026-10-18 ·Guangjian Zhang
theoryhot direction similarity 0.62
Abstract · 68 pages

Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity $Θ(((\log M)^2/ρ^2+\log(1/δ))/\varepsilon)$ for classes of cardinality at most $M$, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general $ρ^{-1}$ dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses $O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon)$ samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of $d$ finite threshold chains of length $k$, we determine the exact rate $Θ((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon)$. We also characterize deterministic learning, the very-small-$ρ$ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent $3/2$ independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.

0.30

Randomization Beyond Deterministic Adaptivity in Parallel Sampling

cs.IT ·2026-10-02 ·Da Li, Bo Jin, Xiaopeng Wei
similarity 0.61
Abstract · 20 pages

Parallel samplers, including masked diffusion models, generate several coordinates per round from conditional marginals, and their accuracy depends on which coordinates are revealed together. A schedule can be improved in two natural ways: adaptively, by choosing later batches from the values already generated, or by randomization, by drawing the schedule at random. We show that randomization is strictly more powerful. For every $r \geq 1$ we construct a full-support distribution on $9r$ binary coordinates such that every deterministic three-round sampler, even with value-dependent batches and arbitrary product kernels, has forward Kullback-Leibler divergence at least $γr - \log 4$ with $γ\approx 0.0966$, whereas drawing one of four fixed schedules with two fair bits drives the divergence below $18 r β^r$ with $β\approx 0.966$. Both samplers query conditionals of the same target. The separation holds for every fixed number of rounds $T \geq 2$, a strict advantage survives perturbations of the target and errors in the conditional predictor, and exact rational arithmetic certifies the gap at nine coordinates, where trained neural predictors preserve it. The mechanism is a hidden mixture: each schedule preserves the dependence pattern of one component, while no deterministic first batch can serve them all.

0.47

Two-Sample Testing via Generative Processes

cs.LG stat.ML ·2026-10-06 ·Eshant English, Kenji Fukumizu, Taiji Suzuki
theory similarity 0.60
Abstract

Deciding whether two samples come from the same distribution is a classical problem in statistics, and generative transport offers a new way to approach it. We build a stochastic interpolant directly between the two samples and observe that, for a symmetric schedule, its law is invariant under the time reflection $t \mapsto 1-t$ whenever the two distributions coincide. We therefore test whether the marginals at times t and 1-t agree by computing their Jensen--Shannon divergence. Both marginals are explicit mixtures over all cross-pairs of observations, so nothing is learned, and permutation calibration gives an exact finite-sample level. For Gaussian noise, this divergence equals a time integral that pairs the reflection defects of the velocity field and of the score, so the test compares transport dynamics rather than endpoints alone. With a narrow-plus-broad noise design, the test attains the minimax separation rate n^{-2s/(4s+d)} over bounded, compactly supported densities whose difference has Sobolev smoothness s > 3d/4, with no lower bound on the densities. Fusing a dyadic grid of noise scales through their permutation ranks, without sample splitting, preserves exact level and adapts to unknown s at an iterated-logarithmic cost. Empirically, the test matches or outperforms state-of-the-art kernel two-sample tests.

0.06

From Imbalance to Evidence: Deep Nonparametric Testing for Complex Data under Severe Sample Imbalance

cs.LG stat.MLstat.ME ·2026-10-09 ·Guanhao Zhou, Xiufan Yu
similarity 0.60
Abstract

Comparing distributions under severe sample imbalance requires effectively using abundant majority observations while retaining sensitivity to differences involving the smaller sample. This challenge is particularly relevant for complex, non-Euclidean data, such as graphs, whose structural characteristics call for flexible testing procedures. Classifier two-sample tests (C2STs) provide such flexibility, but existing procedures are primarily designed for balanced or comparably sized samples. In this paper, we study C2STs in a highly imbalanced regime, and show that severe sample imbalance may substantially degrade testing performance. Different from conventional imbalanced learning approaches that treat sample imbalance merely as a nuisance for classifier training, we turn it into a source of repeated testing evidence. Building on this insight, we propose an Enhanced Imbalance-Aware Deep Classifier Two-Sample Test (EIAD-C2ST), a classifier-agnostic framework designed for sample imbalance that accommodates diverse data modalities by tailoring classifiers to data structure. For computationally expensive deep classifiers, we further develop a scalable representation-amortized implementation strategy. Theoretically, we establish rigorous guarantees on asymptotic size and characterize conditions for power consistency, allowing the imbalance ratio to diverge. We demonstrate the empirical gains using simulations and an application to blockchain forensics. The results reveal that the majority-sample surplus, when properly leveraged, can be organized into useful statistical evidence, rather than an obstacle, for distributional comparisons with complex data.

0.31

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

cs.IT ·2026-10-11 ·Yijun Fan, Aaron B. Wagner
similarity 0.60
Abstract

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

0.20

High Probability Streaming Lower Bounds for $F_2$ Estimation

cs.DS ·2026-09-15 ·William Swartworth, David P. Woodruff, Samson Zhou
theory similarity 0.60
Abstract · RANDOM 2026

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

0.35