Log-optimal two-sample testing by betting

Aaditya RamdasarXiv 2026 · arXiv

TL;DR

This paper introduces a universal, "anytime-valid" framework for sequential two-sample testing by framing the problem as a game of betting against the null hypothesis. The authors prove that their method achieves the optimal logarithmic growth rate of evidence—characterized by the Jensen–Shannon divergence—across diverse data types and sample size ratios, allowing researchers to stop experiments whenever they see enough evidence without inflating false positive rates.

What Problem Does This Paper Address?

In classical statistics, two-sample testing (deciding if two datasets $P$ and $Q$ come from the same distribution) usually happens in "batches." You collect a fixed number of samples, run a test, and get a p-value. However, in modern data science, we often want to monitor data streams sequentially.

The problem is that "peeking" at data and stopping early (optional stopping) invalidates standard p-values, leading to a high rate of false discoveries. Furthermore, most existing sequential tests are either restricted to simple data (like coins or dice) or lack "log-optimality"—meaning they don't accumulate evidence as fast as theoretically possible. This paper seeks a single, robust procedure that works for any data type (from simple numbers to high-dimensional images) and remains optimal even when one data stream is much larger than the other.

Methods

The authors utilize a "testing by betting" framework. Instead of a p-value, they track a "wealth" process $W_n$. You start with \$1 and bet on the difference between the two streams. If the null hypothesis (that $P=Q$) is true, your expected wealth never exceeds \$1 (a property called a test supermartingale). If $P \neq Q$, your wealth grows exponentially.

Key technical components include:

  • E-processes: A mathematical framework that ensures the test is "anytime-valid." You can stop at any time $\tau$, and the probability that $W_\tau \ge 1/\alpha$ is at most $\alpha$.
  • Logarithmic-Loss Learning: The authors show that maximizing the growth of wealth is equivalent to minimizing logarithmic prediction loss. They use this to adaptively learn the "witness" function that best separates the two distributions.
  • Universal Portfolios: To avoid picking a single "best" kernel or partition, they maintain a "bank" of different experts and mix their bets using a strategy inspired by information theory (Cover’s universal portfolios).
  • Kernel and Neural Implementations: They provide concrete algorithms using Reproducing Kernel Hilbert Spaces (RKHS) and Neural Network fine-tuning. For neural networks, they use a "predict-then-train" protocol: the model makes a bet on a new pair of samples before using those samples to update its weights.

Datasets

The authors evaluate their methods on several benchmarks:

  • Synthetic Data: Bernoulli (binary) trials, univariate Gaussians (testing for mean and scale shifts), and a 10-dimensional sparse Gaussian mean shift.
  • UCI Optical Digits: A dataset of $8 \times 8$ handwritten digit images (resized to $28 \times 28$). They specifically look at challenging scenarios like "noisy 3 vs. 8" and "rotated digits," where the model must learn to distinguish distributions under complex transformations.

Key Insights and Ideas

  • The JS Divergence Connection: The paper establishes that for balanced streams, the optimal rate of evidence accumulation is exactly $2 \cdot \text{JS}(P, Q)$. This provides a beautiful information-theoretic bridge between divergence measures and sequential testing.
  • Handling Imbalance: The framework naturally interpolates between two-sample testing and one-sample testing. If one stream is infinitely larger than the other, the growth rate converges to the Kullback–Leibler (KL) divergence, $D_{KL}(Q\|P)$.
  • Generality via Partitions: By using refining partitions of the observation space, the authors construct a "universal" test that works for any standard Borel space without needing to know the underlying densities.
  • Safety in Adaptation: The "predict-then-train" protocol allows for deep learning to be used in hypothesis testing without "cheating." Because the bet is placed using only past information, the validity of the test is preserved even as the neural network becomes more accurate.

Key Results

  • Superior Power: In Gaussian and Bernoulli simulations, the "Kernel Logistic" betting approach consistently reached rejection thresholds faster (required fewer samples) than existing benchmarks like the MMD (Maximum Mean Discrepancy) OGA-ONS method.
  • Neural Fine-tuning Gains: On the rotated digit task, fine-tuning a pre-trained CNN increased the mean normalized log-wealth from 0.7894 to 1.0293 (a ~30% improvement), demonstrating that representation learning significantly boosts the power of the test.
  • Asymptotic Efficiency: The authors prove that their e-values achieve the optimal "Bahadur slope," meaning they provide the strongest possible evidence in the limit of large samples.

Limitations and Future Work

  • Computational Complexity: The exact kernel-based updates have a $O(n^2)$ time and memory cost. While the authors mention sparse approximations and random features, a full-scale implementation for massive datasets would require more engineering.
  • Hyperparameter Sensitivity: Although the "universal" mixture handles many settings, the initial choice of the "bank" of kernels or the neural network architecture still influences how quickly the test gains power in the early stages (the "learning cost").
  • Future Directions: The authors suggest that exploring more sophisticated data-adaptive allocation (deciding which stream to sample from next to maximize wealth) is a promising area for further research.

Summary updated

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.
BibTeX
@misc{ramdas2026log,
  author = {Aaditya Ramdas},
  title = {{Log-optimal two-sample testing by betting}},
  year = {2026},
  eprint = {2611.19062},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19062},
}
Figure