Technical Summary: LOTTERY

Problem Statement

The paper addresses the challenge of data-adaptive two-sample testing under conditions of severe sample-size asymmetry. In many real-world monitoring scenarios (e.g., dataset shift detection, adversarial detection, model monitoring), practitioners possess an abundant historical reference dataset ($X \sim P$) but receive only a handful of query samples ($Y \sim Q$) to test against the reference.

Existing learning-based two-sample tests typically rely on a train-test split paradigm to decouple representation learning from hypothesis testing, ensuring valid Type I error control. However, in few-shot settings where $|Y|$ is extremely small, splitting the query data is detrimental:

1. Learning Instability: Using a tiny subset of $Y$ for training leads to high-variance, unstable feature extractors.
2. Testing Noise: Allocating the remaining few points for testing results in noisy calibration and low statistical power.
3. Bottleneck: Simply increasing the reference sample size does not mitigate the fundamental scarcity of query points.

The core question posed is: How can one retain the adaptivity of learning-based testing while avoiding learning from scarce query data?

Methodology: LOTTERY

The authors propose LOTTERY (Learning from Reference-Only samples in Two-sample Testing under sizE asymmetRY), a framework that shifts the paradigm from "learning a discrepancy between $X$ and $Y$" to "learning a collection of compatibility signals from $X$ and testing $Y$ against them."

1. Reference-Only Learning (RDR)

Instead of splitting $Y$, LOTTERY learns Reference-Dependent Representations (RDRs) exclusively from the abundant reference data $X$. An RDR is a function $f: \mathcal{X} \to \mathbb{R}$ trained on $X$ such that larger values of $f(y)$ indicate lower compatibility with the reference distribution $P$.
The framework employs a family of complementary RDRs to capture diverse structural aspects of $P$:

• ME-RDR (Mean Embedding): Captures local similarity patterns using characteristic kernels and test locations. Theoretically guaranteed to be consistent for any alternative $P \neq Q$.
• Mahalanobis-RDR: Captures global structure (mean and covariance shifts).
• kNN-RDR: Captures local scale and support geometry via nearest-neighbor distances.
• LOF-RDR: Captures local relative density irregularities.

2. Uncertainty-Guided Aggregation

Since no single RDR is uniformly powerful against all alternatives, LOTTERY aggregates evidence from the entire family. To optimize this aggregation without using query data, the authors introduce an uncertainty-guided weighting scheme:

• Stability: Quantified by the variance of the RDR's batch mean when resampling from the reference calibration set. Unstable RDRs (high variance) are downweighted.
• Sensitivity: Quantified by the response of the RDR to small, controlled perturbations of the reference data.
• Weighting: The final weight for an RDR $f$ is $w_f = \hat{\delta}_f / \hat{\sigma}^2_f$, favoring representations that are both stable under the null and sensitive to deviations.
• Test Statistic: The final statistic is a weighted sum of squared mean standardized shifts: $T_{weight}(Y) = \sum_{f \in \mathcal{F}} w_f T_f(Y)$.

3. Pooled Permutation Testing

To ensure valid Type I error control without splitting the query data, LOTTERY uses a pooled permutation test.

• A held-out reference set $X_{hold}$ is combined with the query batch $Y$ to form a pooled sample $U$.
• Under the null hypothesis ($P=Q$), all points in $U$ are exchangeable.
• The test statistic is computed for the observed $Y$ and compared against a distribution generated by randomly sampling subsets of size $|Y|$ from $U$.
• This yields exact finite-sample Type I error control at level $\alpha$.

Key Contributions

1. Reference-Only Framework: Introduces a novel paradigm for two-sample testing in the few-shot, size-asymmetric regime, eliminating the need to split scarce query data for representation learning.
2. Uncertainty-Guided Aggregation: Proposes a mechanism to adaptively weight multiple reference-dependent representations based on their stability and sensitivity, derived solely from reference data.
3. Theoretical Guarantees:
   • Type I Error Control: Proves that the pooled permutation procedure controls Type I error at level $\alpha$ for finite samples.
   • Consistency: Shows that the test power converges to 1 as sample sizes grow, provided the representation family contains at least one consistent representation (e.g., ME-RDR).
4. Empirical Performance: Demonstrates strong performance across synthetic and real-world benchmarks, particularly outperforming kernel-based and split-based learning methods in extreme few-shot settings.

Experimental Results

The authors evaluate LOTTERY on synthetic data (BLOB) and real-world datasets (Higgs Boson, CIFAR-10 adversarial detection).

• Varying Reference Size ($N$): With a fixed small query size, LOTTERY shows significantly faster power growth as $N$ increases compared to baselines. It outperforms all methods when $N$ is sufficiently large (e.g., $N \ge 300$ on BLOB).
• Varying Query Size ($M$): In extreme few-shot regimes (e.g., $M=2$ to $M=10$), LOTTERY achieves substantially higher power than kernel-based (MMD-FUSE, MMDAgg) and split-based learning baselines (MMD-Deep, RL-TST), which often perform near chance levels.
• Ablation Studies:
  • Removing the uncertainty-guided selection mechanism leads to a consistent drop in power, confirming the value of downweighting unstable RDRs.
  • Aggregating multiple RDR families yields better results than any single RDR, confirming their complementarity across different types of distributional shifts (global mean, variance, local density).
• Type I Error: Empirical checks confirm that the test maintains Type I error close to the significance level $\alpha = 0.05$ across all configurations.

Significance and Claims

The paper claims that LOTTERY provides a principled and effective approach for two-sample testing under extreme class imbalance. Its significance lies in:

• Resolving the Few-Shot Bottleneck: It circumvents the instability inherent in splitting small query batches, a limitation that plagues existing data-adaptive tests.
• Bridging One-Class and Two-Sample Testing: It adapts the success of one-class classification (learning from a single distribution) into a rigorous two-sample testing framework with formal Type I error guarantees, distinguishing it from standard anomaly detection which often lacks level-$\alpha$ testing guarantees.
• Practical Utility: It offers a diagnostic tool for high-stakes applications like adversarial detection and model monitoring, where query data is scarce but reference data is abundant, enabling more reliable detection of distributional shifts and silent failures.

The authors emphasize that the method is statistical in nature and intended as a diagnostic component within a broader pipeline, rather than a standalone decision rule for individuals.