Nonparametric two-sample testing by betting
Mathematical Methods AIMech:NonparametricTwoSampleTestingByBetting DRAFT
Aliases: Sequential IPM Two-Sample Testing by Betting, ONS-Predicted Witness Two-Sample Betting Test, Sequential Kernel MMD Test by Betting, Operator Invariance Sequential Testing by Betting
A general sequential nonparametric two-sample and operator-invariance hypothesis testing framework (Shekhar & Ramdas 2023, IEEE Transactions on Information Theory 70(2):1178–1203) that tests H_0 : P_X = P_Y against H_1 : P_X != P_Y from paired streaming observations {(X_t, Y_t) : t >= 1} by exploiting the variational representation of an Integral Probability Metric (IPM) d_G(P_X, P_Y) = sup_{g in G} (E_{P_X}[g(X)] - E_{P_Y}[g(Y)]) over a symmetric bounded witness class G subseteq [-1/2, 1/2]^X to construct an iterative betting game with wealth process K_t = prod_{i=1}^t (1 + lambda_i (g_i(X_i) - g_i(Y_i))), decoupling predictable witness selection g_t in G via a no-regret online learner A_pred (such as adaptive Online Gradient Ascent in Euclidean or reproducing-kernel Hilbert spaces, or empirical risk minimization over low-Rademacher-complexity classes) from predictable bet-fraction selection lambda_t in [-1/2, 1/2] via the Online Newton Step strategy A_ONS, so that stopping at tau = inf{t >= 1 : K_t >= 1/alpha} guarantees nonasymptotic Type-I error P_{H_0}(tau < infty) <= alpha via Ville's inequality alongside variance-adaptive exponential wealth growth, power-one consistency, and minimax-optimal expected stopping time E[tau] = O(sigma^2 log(1/(alpha Delta)) / Delta^2) under H_1.
Identity Notes & Concept Scope
No normalized identity match for nonparametric two-sample testing by betting across all 442 pinned AIO records and 579 maintained IDs, names, aliases and scoped synonyms. Fixed-string searches across data, sources, research, history, and reviews returned only lines in Round 184 artifacts where Shekhar & Ramdas (2023, IEEE Transactions on Information Theory 70(2):1178-1203, arXiv:2112.09162) was queued as a pending frontier lead. Distinct from AIMech:BettingConfidenceSequencesForBoundedMeans (Waudby-Smith & Ramdas 2024, JRSS Series B 86(1):1-27, arXiv:2010.09686), which constructs one-sample confidence sequences for scalar bounded means in [0, 1] rather than sequential nonparametric two-sample IPM/kernel-MMD and operator-invariance hypothesis tests over multivariate or general metric spaces via coupled online witness prediction A_pred and ONS betting A_ONS; also distinct from AIMech:UniversalInferenceSplitLikelihoodRatioTest (Wasserman, Ramdas, & Balakrishnan 2020, PNAS 117(29):16880-16890), which requires parametric likelihood evaluation over H_0.
Claims & Grounded Evidence
4 Claims
Mechanism
#ipm-variational-two-sample-betting-game-and-ons-wealth-lower-bound
For any symmetric witness class G subseteq [-1/2, 1/2]^X generating an Integral Probability Metric d_G(P_X, P_Y) = sup_{g in G}(E_{P_X}[g(X)] - E_{P_Y}[g(Y)]) (Assumption 1, Equation 5), the oracle two-sample betting game replaces the unknown optimal witness g* and bet lambda* with a predictable witness prediction strategy A_pred selecting F_{t-1}-measurable g_t in G (with cumulative regret R_n = n d_G(hat{P}_{X,n}, hat{P}_{Y,n}) - sum_{t=1}^n (g_t(X_t) - g_t(Y_t)); Definition 4, Equation 10) and the Online Newton Step betting strategy A_ONS updating lambda_{t+1} = Pi_{[-1/2, 1/2]}(lambda_t - (2 / (2 - log 3)) z_t / a_t) from lambda_1 = 0 with v_t = g_t(X_t) - g_t(Y_t) in [-1, 1], z_t = v_t / (1 - lambda_t v_t), and a_t = 1 + sum_{i=1}^t z_i^2 (Definition 5, Equation 11); by Cutkosky & Orabona's coin-betting bound (Appendix A.3), K_n = prod_{t=1}^n (1 + lambda_t v_t) satisfies pathwise K_n >= (1 / sum_{t=1}^n v_t^2) exp((sum_{t=1}^n v_t)^2 / (4(sum_{t=1}^n v_t^2 + sum_{t=1}^n v_t))) >= exp((n/8)(n^{-1} sum_{t=1}^n v_t)^2 - log n), and Theorem 1 guarantees for tau = inf{t >= 1 : K_t >= 1/alpha} that (i) Type-I error satisfies sup_{P_X = P_Y} P(tau < infty) <= alpha via Ville's inequality (Equation 16), (ii) P_{H_1}(tau < infty) = 1 whenever limsup_{n->infty} R_n/n < d_G(P_X, P_Y) a.s. (Equations 17–18), (iii) empirical-Bernstein variance-adaptive asymptotic log-wealth rate liminf_{n->infty} n^{-1} log K_n >= (Delta/4)(min(Delta / E[(g*(X)-g*(Y))^2], 1)) when n^{-1} sum_{t=1}^n v_t -> Delta = d_G(P_X, P_Y) (Equations 19–20, Appendix C), and (iv) Sanov KL-projection error exponent lim_{n->infty} -(2n)^{-1} log P(tau > n) >= beta (Equation 22).
Mechanism
#bounded-mean-sequential-two-sample-test-via-adaptive-oga-and-minimax-optimality
For bounded Euclidean random vectors X_t, Y_t in {x in R^m : ||x||_2 <= 1} testing H_0 : mu_X = mu_Y against H_1 : mu_X != mu_Y using the linear IPM witness class G = {<u, .> : ||u||_2 <= 1/2} (where d_G(P_X, P_Y) = (1/2) ||mu_X - mu_Y||_2 = Delta), instantiating A_pred as scale-free adaptive Online Gradient Ascent u_{t+1} = Pi_U(u_t + eta_t (X_t - Y_t)) with eta_t = 1 / sqrt(2 M_t) and M_t = sum_{i=1}^t ||X_i - Y_i||_2^2 (Equation 29) achieves cumulative regret R_n <= (3/2) sqrt(M_n) (Appendix A.4 / D), O(m) per-step computation (O(tau m) total time), and expected stopping time E[tau] = O(sigma^2 log(1/(alpha Delta)) / Delta^2) where sigma^2 = E[||X - Y||_2^2] (Definition 7, Proposition 1), matching up to logarithmic factors the information-theoretic minimax lower bound E[tau'] = Omega(sigma^2 log(1/alpha) / Delta^2) established via the generalized Wald identity E_{H_1}[tau'] >= log(1/alpha) / d_KL(P_Y, P_X) (Proposition 2, Appendix F Lemma 4).
Mechanism
#sequential-kernel-mmd-betting-test-and-unbounded-sigmoid-extension
For general metric spaces X equipped with a characteristic reproducing kernel Hilbert space H_K with bounded kernel sup_{x,x'} sqrt{K(x,x')} <= 1 and witness ball G = {g in H_K : ||g||_K <= 1/2} generating the Maximum Mean Discrepancy d_MMD(P_X, P_Y) (Equation 33), adaptive RKHS Online Gradient Ascent g_{t+1} = Pi_G(g_t + eta_t (K(X_t, .) - K(Y_t, .))) with Pi_G(h) = h / (2 ||h||_K) when ||h||_K > 1/2 and eta_t = 1 / sqrt(2 sum_{i=1}^t ||K(X_i, .) - K(Y_i, .)||_K^2) (Equation 35) yields a sequential kernel-MMD test (Definition 8) with O(tau^2) total complexity, expected stopping time E[tau] = O(sigma^2 log(1/(alpha Delta)) / Delta^2) for Delta = d_MMD(P_X, P_Y) and sigma^2 = E[||K(X, .) - K(Y, .)||_K^2] (Proposition 3, near-optimal by Proposition 4), and mid-point KL error exponent beta = inf_{P' in P(X)} (1/2)(d_KL(P', P_X) + d_KL(P', P_Y)); moreover, when G or K is unbounded, composing the raw witness payoff g_t(X_t) - g_t(Y_t) with any odd sigmoid function varrho : R -> [-1, 1] satisfying varrho(-x) = -varrho(x) (such as varrho(x) = tanh(x)) preserves E_{H_0}[varrho(g_t(X_t) - g_t(Y_t)) | F_{t-1}] = 0 by distributional symmetry g_t(X_t) - g_t(Y_t) =^d g_t(Y_t) - g_t(X_t) under H_0 (Section 2.3, Definition 6).
Mechanism
#time-varying-nonexchangeable-streams-and-operator-invariance-testing
Under non-i.i.d. time-varying F_{t-1}-measurable data streams (X_t, Y_t) ~ P_t x Q_t (Definition 9, where temporal marginal drift P_t != P_{t'} violates across-time exchangeability and invalidates batch permutation tests; Remark 10), the sequential betting test tau(A_ONS, A_pred) maintains nonasymptotic Type-I error P(tau < infty) <= alpha under H_0 : P_t = Q_t for all t >= 1 and achieves power 1 under H_1 : d_G(P, Q) := liminf_{n->infty} d_G(bar{P}_n, bar{Q}_n) > 0 whenever limsup_{n->infty} R_n/n < d_G(P, Q) a.s. (Proposition 5, Corollary 1); furthermore, the framework generalizes to testing distributional invariance under an arbitrary operator T : Z -> Z (H_0 : P o T^{-1} = P versus H_1 : P o T^{-1} != P; Definitions 10–13, unifying two-sample testing T(x, y) = (y, x), symmetry testing T(z) = -z, and independence testing T((x, y), (x', y')) = ((x, y'), (x', y)) via the symmetrized witness class tilde{G} = {(1/2)(g - g o T) : g in G}), where the empirical risk minimization (ERM) strategy achieves consistency whenever the Rademacher complexity C_n(tilde{G}, P) -> 0 and finite-sample detection threshold Delta_n^* = Omega(n^{-1} sum_{t=1}^{n-1} C_t(tilde{G}) + sqrt(log(n/alpha)/n) + sqrt(log(n/gamma)/n)) (Theorem 2, Equations 51–53, Remark 11).
⚠️ Curated Limitations & Negative Results
- The exact sequential kernel-MMD betting test using adaptive Online Gradient Ascent in an RKHS (Section 4, Definition 8) requires O(t) kernel evaluations at step t to compute g_t(X_t) - g_t(Y_t), resulting in O(tau^2) cumulative computational complexity up to stopping time tau (or O(n^2) in the fixed-horizon batch setting) unless finite-dimensional random Fourier features or Nystrom approximations are employed (Section 4.1, Remark 9).
- Ensuring nonnegativity of the betting wealth process K_t = prod_{i=1}^t (1 + lambda_i v_i) with lambda_i in [-1/2, 1/2] requires bounded payoffs v_i in [-1, 1]; when the underlying witness class G or kernel K is unbounded (Section 2.3, Definition 6), composing g_t(X_t) - g_t(Y_t) with an odd sigmoid squashing function varrho(x) = tanh(x) preserves exact Type-I error control and asymptotic consistency, but the finite-sample expected stopping time and variance-adaptivity bounds of Theorem 1(iii)-(iv) then apply to the squashed discrepancy rather than directly to the raw IPM d_G(P_X, P_Y).
- The standard formulation assumes paired sequential observations (X_t, Y_t) arriving at a 1:1 sampling ratio; extending to unbalanced or asynchronous arrival streams requires mini-batching or pooling observations into matched blocks before updating the witness predictor and betting fraction.
- All 3,527 lines of Shekhar & Ramdas (2023, arXiv:2112.09162) were read. Constructed numerical checks in research/discovery/nonparametric-two-sample-testing-by-betting-boundaries.py verify the Cutkosky-Orabona ONS wealth lower bounds (Appendix A.3) and Eq. 65 ONS regret bound <= 0.5 log n (max ratio 0.2825), Theorem 1(iii) variance-adaptive log-wealth growth rate (0.0951 >= 0.05 for small variance vs. 0.0271 >= 0.0147 for large variance at identical Delta = 0.20), Section 3 Propositions 1–2 bounded-mean adaptive OGA regret ratio R_t / ((3/2) sqrt(M_t)) <= 0.5219 <= 1.0, Type-I error 0.0 <= 0.05, power 1.0, and stopping time scaling above Lemma 4's Wald-KL lower bound (55.27 > 8.84), Section 4 & 2.3 sequential RBF kernel-MMD detection of zero-mean equal-variance distributions (power 1.0, E[tau]=17.6, null Type-I error 0.0) and odd-sigmoid tanh(x) unbounded test (power 1.0, null Type-I error 0.05), and Section 5.1–5.2 time-varying non-exchangeable streams (power 1.0, null Type-I error 0.0) and operator-invariance symmetry (power 1.0, null Type-I error 0.0333) and independence testing (power 1.0, null Type-I error 0.0).
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:DataDredgingBias
Data Dredging Bias
|
related_match | Sequential two-sample testing by betting constructs a nonnegative test martingale K_t under H_0 whose Ville stopping rule tau = inf{t >= 1 : K_t >= 1/alpha} controls Type-I error under continuous monitoring and optional stopping, preventing false-positive inflation from sequential peeking (AIO:DataDredgingBias). |
AIO:TimeSeriesAnalysis
Time Series Analysis
|
related_match | The two-sample betting test processes streaming paired observations sequentially across filtrations (F_t)_{t>=0}, including non-stationary time-varying distributions (X_t, Y_t) ~ P_t x Q_t (Section 5.1, Definition 9; AIO:TimeSeriesAnalysis). |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
shekhar-ramdas2023-two-sample-betting-ar5iv
|
Shubhanshu Shekhar, Aaditya Ramdas
|
primary paper
full_text
|
ID: https://doi.org/10.1109/TIT.2023.3305867
sha256:69380bbf6cc3…
|
shekhar-ramdas2023-two-sample-betting-crossref
|
Shubhanshu Shekhar, Aaditya Ramdas
|
primary paper
abstract_only
|
ID: https://doi.org/10.1109/TIT.2023.3305867
sha256:bdb4c6323a40…
|
shekhar-ramdas2023-two-sample-betting-abs
|
Shubhanshu Shekhar, Aaditya Ramdas
|
primary paper
abstract_only
|
ID: https://doi.org/10.1109/TIT.2023.3305867
sha256:14021274caaf…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini 3
Created: 2026-10-17T13:20:00Z
Updated: 2026-10-17T13:20:00Z
Source File:
data/curated/NonparametricTwoSampleTestingByBetting.yaml
· Schema:
curated_concept.yaml
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories