From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting

From Approachability Residuals to Anytime-Valid Evidence:

The Online Convex Geometry of Testing by Betting

Summary

This paper establishes an exact and quantitative connection between Blackwell approachability and betting-based sequential two-sample testing, unified through a shared support-function residual. The central contribution is a pathwise identity linking the distance of an empirical average to a convex target set with the cumulative scalar payoff produced by an online convex optimization (OCO) learner and the learner's regret.

Core Identity (Proposition 3.1): For a compact convex target S in a separable real Hilbert space, with observations rt, an OCO learner selects a predictable normal wt ∈ B (unit ball) and produces residual qt = ⟨wt, rt⟩ − hS(wt), where hS is the support function of S. The paper proves the exact identity:

dist(r̄T, S) = (1/T) Σt=1 T ⟨wt, rt⟩ − hS(wt) + RegT/T,

where r̄T is the empirical average and RegT is the OCO regret. This identity is exact algebraically for every deterministic sequence and every sequence of normals.

Finite-Time Rate Transfer (Theorem 5.1): Composing this identity with one-sided betting (nonnegative bets λt ∈ [0, 1/2]) yields a finite-time transfer theorem. Under the null hypothesis that the conditional mean of rt lies in S, the wealth process Kt is a nonnegative supermartingale, giving anytime validity via Ville's inequality. The paper defines an evidence radius cT(α) = 2B√((log(1/α) + lT)/T), where lT is the betting log-wealth regret. The theorem states: if the target gap DT = dist(r̄T, S) exceeds aT/T + cT(α), where aT is the OCO regret bound, then rejection occurs by time T. Conversely, non-rejection certifies that DT < aT/T + cT(α). This certificate holds simultaneously for all T with probability at least 1−α under the null.

Wealth Lower Bound (Theorem 3.2): The paper proves the pathwise inequality:

log KT ≥ (T/(4B2)) (dist(r̄T, S) − RegT/T)2+ − LT,

where LT is the betting regret. Under a separated stationary alternative with δ = dist(µ, S) > 0, this gives exponential wealth at rate at least δ2/(4B2), implying power one.

Two-Sample Specializations (Section 4):

• Bounded means: With rt = (Xt − Yt)/2 and S = 0, the residual identity becomes (1/T)Σvt = ∥r̄T∥2 − RT/T, recovering the bounded-mean betting test. The population separation is ∆ = (1/2)∥EX − EY∥2.

• Kernel MMD: With rt = (ϕ(Xt) − ϕ(Yt))/2 in an RKHS, the residual equals gt(Xt) − gt(Yt), recovering the sequential kernel-MMD test. The identity reads (1/T)Σvt = (1/2)MMD(P̂X,T, P̂Y,T) − RT/T.

• General convex nulls: The framework extends beyond S = 0 to moment-inequality nulls, multivariate tolerance regions, and conditional calibration constraints.

Controlled Stochastic Blackwell–Betting Game (Theorem 5.3): The paper formulates a controlled experiment where an action at ∈ A0(wt) is selected after the normal wt, satisfying Blackwell's supporting-halfspace condition for every null mean payoff. Under adaptive nulls, the wealth is an e-process and stochastic approachability holds (dist(r̄T, S) → 0 almost surely). Under alternatives with persistent mean separation δ, the wealth grows exponentially at rate at least δ2/(4B2). Deterministic Blackwell games arise as the noise-free case, and passive tests as the singleton-action case.

Heterogeneous Sources: For M data sources with direct-sum RKHS embedding, the mean separation is exactly (1/4)Σρ2a,T∆2a, where ρa,T are source frequencies and ∆a are source MMDs. An informative source with frequency ρ gives evidence exponent ρ2∆2/16.

Protocol Dictionary (Table 1): The paper provides a dictionary showing the same residual is controlled pathwise (deterministic Blackwell), merely observed (passive betting), or controlled in conditional mean (controlled stochastic reduction). The two online variables have distinct roles: wt is the geometric dual normal, λt is a one-dimensional capital control.

Rates: For OCO regret aT = O(√T) and betting regret lT = O(log T), the evidence boundary is DT = O(√(log(T/α)/T)). The paper notes that the exact identity preserves the OCO radius without hidden factors, avoiding the rate-distortion phenomena of general approachability–regret reductions.

Limitations: The pathwise reduction controls the empirical target gap, but sharp expected stopping times require additional variance and tail analysis, as repaired in the 2025 correction to the betting paper.

Improvement 1: Anytime-Valid Sequential Decision-Making with Explicit Certificates

The improved AI system can perform real-time hypothesis testing and decision-making (e.g., A/B testing, online model selection, or anomaly detection) with rigorous, anytime-valid confidence bounds. It outputs a certificate at every time step: if the target gap exceeds the evidence boundary, it rejects the null; if not, it certifies the gap is below a computable threshold. This eliminates the need for fixed-sample-size designs and allows continuous monitoring without inflating false-positive rates, using the exact pathwise identity to avoid conservative approximations.

Improvement 2: Unified Framework for Convex Constraint Satisfaction in Online Learning

The AI system can now handle online optimization problems where the goal is to keep an empirical average inside a convex set (e.g., fairness constraints, resource allocation, or safety regions). By leveraging the support-function residual and OCO regret bound, it can provably track the distance to the feasible set in real time, with a finite-time guarantee. This enables adaptive controllers that adjust actions (via the normal vector wt) to steer the system toward feasibility, while quantifying the worst-case deviation from the target set.

Improvement 3: Exponential-Power Detection for Separated Alternatives

The system gains a power-one property: under any stationary alternative with a positive mean separation δ from the null set, it accumulates wealth (log-evidence) at a rate at least δ2/(4B2) per sample. This means it can detect even small persistent shifts with high probability in finite time, and the rate is explicitly computable. This is useful for change-point detection, online monitoring of treatment effects, or detecting distributional drift in production ML systems, where the AI can guarantee eventual detection with a known exponential speed.

Improvement 4: Multi-Source Heterogeneous Evidence Aggregation

For systems ingesting data from multiple sources (e.g., sensors, users, or models), the AI can combine evidence optimally. The direct-sum RKHS embedding yields a closed-form decomposition: the total evidence exponent is a weighted sum of per-source MMDs, with weights proportional to source frequencies squared. The system can therefore allocate sampling effort to the most informative sources, maximizing detection power, and provide a principled stopping rule based on the aggregated e-process.

Improvement 5: General Convex Nulls for Complex Hypotheses

The AI can test hypotheses that are not simple point nulls but general convex sets—e.g., moment inequalities, tolerance regions, or conditional calibration constraints. This allows it to validate whether a model’s predictions satisfy fairness (e.g., equalized odds), safety (e.g., bounded error variance), or distributional constraints, all in a sequential, anytime-valid manner. The system outputs a continuous evidence radius that quantifies how far the empirical behavior is from the allowed region, with a simultaneous guarantee across all time points.

Improvement 6: Controlled Stochastic Games for Adaptive Interventions

In settings where the AI can actively influence the data-generating process (e.g., bandit feedback, adaptive experiments, or control systems), the system can use the controlled Blackwell–betting game formulation. It selects actions that satisfy the supporting-halfspace condition, ensuring that under the null, the wealth process is an e-process (valid even under adaptive sampling). Under alternatives, it achieves exponential wealth growth, enabling optimal adaptive designs that stop early when evidence is strong, while maintaining strict Type-I error control.

Improved AI System Capabilities (Concrete)

• Real-time A/B testing platform that continuously monitors conversion rates, automatically stops when significance is reached, and provides a simultaneous confidence certificate for all interim looks.

• Online fairness monitor for deployed ML models, checking whether the model’s predictions satisfy a convex fairness constraint (e.g., equalized odds) on streaming data, with a hard anytime-valid guarantee.

• Adaptive clinical trial design that allocates patients to arms based on accumulating evidence, with a provable exponential detection rate for any effective treatment, and a strict control of false positives under the null.

• Multi-sensor anomaly detection that fuses heterogeneous data streams, weighting each source by its informativeness, and raises alarms only when the combined evidence crosses a threshold, with a known false-alarm rate.

• Safe reinforcement learning where the agent’s policy is constrained to keep state-action averages inside a convex safety set, with real-time verification of constraint satisfaction and a finite-time bound on violations.