Classifier-Based Nonparametric Sequential Hypothesis Testing

1. Problem Formulation

The paper addresses the problem of sequential hypothesis testing in a nonparametric setting where the null and alternative distributions are not known analytically but are specified indirectly through offline (historical) datasets.

• Setup:
  • There are $L+1$ unknown data-generating distributions: $\mathcal{P} = \{P_0, P_1, \dots, P_L\}$.
  • Offline Data: A fixed dataset of $N$ samples is available for each distribution $P_\vartheta$ ($\vartheta \in \{0, \dots, L\}$).
  • Online Stream: A new stream of i.i.d. observations $\{X_t\}_{t \ge 1}$ is generated from an unknown distribution $P_\theta$ where $\theta \in \{0, \dots, L\}$.
  • Goal: Sequentially decide between the null hypothesis $H_0: \theta = 0$ and the alternative $H_1: \theta \in \{1, \dots, L\}$.
• Constraints & Criteria:
  • The method must satisfy the Level-$\alpha$ Power-One criterion:
    1. Type-I Error Control: Under $H_0$, the probability of stopping in finite time is $\le \alpha$.
    2. Power-One: Under any $H_1$, the probability of stopping in finite time is 1 (almost sure termination).
  • The approach must be nonparametric (no strong assumptions on the form of $P_\theta$) and rely on the offline data to learn the structure of the distributions.

2. Methodology

The core innovation is a classifier-based sequential test that bridges offline machine learning with online sequential analysis using e-processes (testing-by-betting).

A. The Separability Condition

The authors define a class of distribution tuples $\mathcal{P}_{sep}$ that are "distinguishable" by a given family of classifiers $\mathcal{G}$. A tuple is separable if there exists a classifier $g \in \mathcal{G}$ such that for any true distribution $P_\theta$, the probability of the classifier predicting the correct label $\theta$ is strictly higher than predicting any other label $m \neq \theta$:
$$P(g(X) = \theta | X \sim P_\theta) > \max_{m \neq \theta} P(g(X) = m | X \sim P_\theta)$$
This gap is quantified by $\Delta_\theta = p_\theta[\theta] - p_\theta[0]$, where $p_\theta[m]$ is the probability of predicting label $m$ given $P_\theta$.

B. The Stopping Rule (e-Process Construction)

The test utilizes a multiplicative betting strategy (e-process) constructed from the sequence of classifier predictions $\{g(X_t)\}_{t \ge 1}$:

1. Training: A multi-class classifier $g$ is trained on the offline data to distinguish between the $L+1$ classes.
2. Online Betting: At each time step $t$, the classifier predicts a label $g(X_t)$.
3. Adaptive Betting: The algorithm tracks the empirical frequency of past predictions to estimate the most likely alternative label $\hat{j}_t$. It constructs a betting wealth process $W_n$ that bets against the null hypothesis ($0$) whenever the prediction deviates from the null or aligns with the estimated alternative.
   • The wealth update involves an integral over betting parameters $\lambda \in (-1, 0]$ to ensure robustness and optimal stopping time bounds.
   • $W_n$ is a non-negative supermartingale under $H_0$.
4. Stopping: The test stops and rejects $H_0$ when $W_n \ge 1/\alpha$.

C. Identification Mechanism

Beyond rejecting the null, the procedure identifies the true underlying distribution index $\theta$. The algorithm tracks the empirical mode of the predictions ($\hat{j}_t$), which converges to the true $\theta$ almost surely as $t \to \infty$.

3. Key Contributions & Theoretical Results

A. Statistical Guarantees

• Level-$\alpha$ Control: By Ville's inequality, since $W_n$ is a non-negative supermartingale under $H_0$, the probability of false rejection is bounded by $\alpha$.
• Power-One: Under $H_1$, the separability condition ensures the wealth process grows exponentially, guaranteeing finite stopping time with probability 1.
• Expected Stopping Time: The paper derives a non-asymptotic upper bound for the expected stopping time under $H_1$:
  $$E_\theta[\tau] = O\left( \frac{\log(1/(\alpha \Delta_\theta))}{\Delta_\theta^2} \right)$$
  This shows that the stopping time depends inversely on the square of the classifier's separability gap ($\Delta_\theta$).

B. Role of Offline Training (Sample Complexity)

The authors analyze how the offline data size ($N$) and classifier family ($\mathcal{G}$) impact the test:

• Sufficient Condition: Using Empirical Risk Minimization (ERM) and VC-dimension arguments, they show that if $N$ is sufficiently large (scaling with $1/\Delta^2$), a separable classifier can be found with high probability.
• Necessary Condition: They establish a lower bound on $N$ required for any test to achieve the power-one criterion uniformly. Closer distributions (smaller KL divergence) require larger $N$.
• Minimax Lower Bound: A lower bound on the Type-II error (tail probability of stopping time) is derived, showing that even with infinite training data, the stopping time is limited by the intrinsic difficulty of the hypothesis test (KL divergence) and the capacity of the classifier family.

C. Extensions

1. Training-Testing Mismatch: The framework is robust to distribution shifts. If the testing distribution $\tilde{P}$ is close to the training distribution $P$ (measured by KL divergence), the classifier remains separable, and the test remains valid, though the stopping time may increase.
2. Sequential Change-Point Detection (SCD): The method is adapted to detect abrupt changes from $P_0$ to $P_\theta$ at an unknown time $T$. The expected detection delay matches the theoretical bounds of the hypothesis testing scenario.

4. Empirical Results

The authors validate their theory using synthetic Gaussian data and real-world CIFAR-10 image data:

• Stopping Time Trend: Experiments confirm that the average stopping time scales quadratically with $1/\Delta_\theta$ and logarithmically with $1/\alpha$, matching the theoretical bound.
• Identification Accuracy: As $\alpha \to 0$ (stricter threshold), the probability of correctly identifying the true alternative index approaches 1.
• Robustness: The test remains valid under controlled distribution shifts, with stopping times increasing as the shift magnitude increases.
• Classifier Mixture: Using a mixture of multiple classifiers (e.g., combining a weak and a strong model) yields a shorter expected stopping time than using a single classifier, suggesting future directions for adaptive weighting.

5. Significance and Impact

• Bridging ML and Statistics: This work provides a rigorous statistical framework for utilizing powerful, pre-trained machine learning classifiers (like CNNs or LLMs) in formal sequential hypothesis testing, moving beyond parametric assumptions.
• Offline-Online Paradigm: It solves the critical problem of testing unknown distributions when only historical data is available, a common scenario in applications like LLM detection (distinguishing human vs. AI text) and anomaly detection.
• Anytime-Valid: The use of e-processes ensures the test is valid at any stopping time, offering flexibility for real-time decision-making without pre-specifying a sample size.
• Theoretical Limits: By establishing necessary and sufficient conditions on training data size and classifier capacity, the paper defines the fundamental limits of what is achievable in nonparametric sequential testing with offline data.