cs.LGAug 10, 2026

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

Authors: Jinze Zhao

Organizations: University of California, San Diego

Abstract

Betting-based sequential tests and Blackwell approachability are linked by a rate-explicit reduction through support-function residuals. For a compact convex target SS and vector observations rtr_t, an OCO learner selects a predictable normal wtw_t and produces qt=⟨wt,rt⟩−hS(wt)q_t=\langle w_t,r_t\rangle-h_S(w_t). We prove the exact pathwise identity \dist(rˉT,S)=1T∑t=1Tqt+\RegTT.\dist(\bar r_T,S) =\frac1T\sum_{t=1}^Tq_t+\frac{\Reg_T}{T}. When ∣qt∣≤B|q_t|\leq B, composing this identity with one-sided betting yields a finite-time transfer: if the OCO and log-wealth regrets are at most aTa_T and ℓT\ell_T, respectively, then a target gap exceeding

aTT+2Blog⁡(1/α)+ℓTT\frac{a_T}{T} +2B\sqrt{\frac{\log(1/α)+\ell_T}{T}}

forces rejection by time TT, while non-rejection certifies the converse radius. We then formulate a controlled stochastic experiment in which an action selected after wtw_t satisfies Blackwell's supporting-halfspace condition for every null mean payoff. The resulting wealth is an e-process under adaptive nulls; sublinear OCO regret gives stochastic approachability, whereas persistent mean separation under an alternative gives exponential wealth at rate at least δ2/(4B2)δ^2/(4B^2). Deterministic Blackwell games and passive tests are, respectively, the noise-free and singleton-action cases of this protocol. Bounded two-sample means, kernel MMD, and active heterogeneous data sources instantiate the reduction. The resulting connection is exact algebraically, quantitative at finite time, and operational when experiments are controlled.

Explore similar work

CardsList
Jun 25, 2026cs.LG

Blackwell Approachability and Gradient Equilibrium are Equivalent

Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. While GEQ has curious similarities with known online learning frameworks, namely regret minimization, prior work has shown that GEQ error and regret are incomparable objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape. In this work, we show that GEQ is equivalent to Blackwell approachability in the algorithmic sense. That is, a Blackwell approachability problem can always be solved using queries to a black-box GEQ oracle, with no asymptotic loss in the oracle's error rate, and vice versa. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply that GEQ is equivalent to these frameworks, as well. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Along the way, we also identify necessary and sufficient conditions for GEQ, and establish reductions between different notions of GEQ with unconstrained and constrained decision sets.
Brian W. Lee, Nika Haghtalab, Michael I. Jordan +1
EquilibriumOnline
AskPDF
Jun 17, 2026stat.ML

Sequential Kernel-based Conditional Independence Testing via Adaptive Betting

Testing conditional independence is fundamental yet intrinsically difficult: without additional assumptions, Type I error control is impossible in general. The "Model-X'' paradigm addresses this difficulty by assuming exact knowledge of a relevant conditional distribution. While small deviations from this assumption can sometimes be tolerated in classical one-shot testing, existing sequential conditional independence tests typically require the Model-X conditional to be known exactly, making them fragile when it must instead be estimated. We propose a new approach that is substantially more robust to such estimation error. Our method applies testing-by-betting to an adaptively optimized Kernel Conditional Independence statistic, together with a normalization scheme and a truncate-and-shift calibration strategy. These modifications greatly reduce Type I error inflation while preserving high power across high-dimensional synthetic benchmarks and real-world fairness tasks, outperforming existing sequential Model-X approaches. Code is available at https://github.com/he-zh/SKCI.
Zheng He, Danica J. Sutherland
Conditional IndependenceSeparabilityBettingSequential
AskPDF
Apr 22, 2026cs.LG

Cover meets Robbins while Betting on Bounded Data: \ln n Regret and Almost Sure \ln\ln n Regret

Consider betting against a sequence of data in [0,1][0,1], where one is allowed to make any bet that is fair if the data have a conditional mean m0∈(0,1)m_0 \in (0,1). Cover's universal portfolio algorithm delivers a worst-case regret of O(ln⁡n)O(\ln n) compared to the best constant bet in hindsight, and this bound is unimprovable against adversarially generated data. In this work, we present a novel mixture betting strategy that combines insights from Robbins and Cover, and exhibits a different behavior: it eventually produces a regret of O(ln⁡ln⁡n)O(\ln \ln n) on almost all paths (a measure-one set of paths if each conditional mean equals m0m_0 and intrinsic variance increases to ∞\infty), but has an O(log⁡n)O(\log n) regret on the complement (a measure zero set of paths). Our paper appears to be the first to point out the value in hedging two very different strategies to achieve a best-of-both-worlds adaptivity to stochastic data and protection against adversarial data. We contrast our results to those in Agrawal and Ramdas [2026] for a sub-Gaussian mixture on unbounded data: their worst-case regret has to be unbounded, but a similar hedging delivers both an optimal betting growth-rate and an almost sure ln⁡ln⁡n\ln\ln n regret on stochastic data. Finally, our strategy witnesses a sharp game-theoretic upper law of the iterated logarithm, analogous to Shafer and Vovk [2005].
Shubhada Agrawal, Aaditya Ramdas
O(T^Β)$ Simultaneous RegretRegretBettingPortfolio OptimizationGame-Theoretic FrameworkFinite
AskPDF