Sequential Predictive Two-Sample and Independence Testing
Authors: Aleksandr Podkopaev
Aaditya Ramdas
Venue: NeurIPS 2023 poster (2023)
Keywords: two-sample testing
independence testing
testing by betting
sequential testing
TL;DR: Sequential nonparametric two-sample and independence testing by betting

Abstract: We study the problems of sequential nonparametric two-sample and independence testing. Sequential tests process data online and allow using observed data to decide whether to stop and reject the null hypothesis or to collect more data, while maintaining type I error control. We build upon the principle of (nonparametric) testing by betting, where a gambler places bets on future observations and their wealth measures evidence against the null hypothesis. While recently developed kernel-based betting strategies often work well on simple distributions, selecting a suitable kernel for high-dimensional or structured data, such as images, is often nontrivial. To address this drawback, we design prediction-based betting strategies that rely on the following fact: if a sequentially updated predictor starts to consistently determine (a) which distribution an instance is drawn from, or (b) whether an instance is drawn from the joint distribution or the product of the marginal distributions (the latter produced by external randomization), it provides evidence against the two-sample or independence nulls respectively. We empirically demonstrate the superiority of our tests over kernel-based approaches under structured settings. Our tests can be applied beyond the case of independent and identically distributed data, remaining valid and powerful even when the data distribution drifts over time.

Sequential Predictive Two-Sample and Independence Testing
Aleksandr Podkopaev Walmart Global Tech sasha. sasha. pokkpparootaaeeeelaaaart........ com
Aaditya Ramdas Carnegie Mellon University
aramdas@cm cmu, edu
Abstract
We study the problems of sequential nonparametric two-sample and independence testing. Sequential tests process data online and allow using observed data decide whether to stop and reject the null hypothesis or to collect more data, while maintaining type error control. We build upon the principle of (nonparametric) testing by betting, where a gambler places bets on future observations and their wealth measures evidence against the null hypothesis. While recently developed dernel-based betting strategies often work well on simple distributions, selecting a suitable kernel for high-dimensional structured data, such images, is often nontrivial. To address this drawback, we design prediction-basee betting strategies that rely on the following fact: if sequentially updated predictor starts to consis- tently determine (a) which distribution an instance is drawn from, or (b) whether an instance is drawn from the joint distribution the product of the marginal distribu- tions (the latter produced by external randomization), it provides evidence against the two-sample independence nulls respectively. We empirically demonstrate the superiority of our tests over kernel-based approaches under structured settings. Our tests can be applied beyond the case independent and identically distributed data, remaining valid and powerful even when the data distribution drifts over time.
Introduction
We consider two closely-related problems of nonparametric two-sample and independence testing. In the former, given observations from two distributions and Q, the goal is to test the null hypothesis that the distributions are the same: Ho P Q, against the alternative that they the latter, given observations from some joint distribution Pxy. the goal is to test the null hypothesis that the random variables are independent: Ho Pxy Px x Py, against the alternative that they are not: H1 Pxx * Px x Py. Kernel tests, such as kernel-MMD [Gretton et al. 2012] for two-sample and HSIC [Gretton et al. 2005) for independence testing, amongst the most popular methods for solving these tasks which work well on data from simple distributions. However, their performance is sensitive the choice of kernel and respective parameters, like bandwidth, and applying such tests requires additional effort. Further, selecting kernels for structured data, like images, a nontrivial task. Lastly, kernel tests suffer from decaying power in high dimensions [Ramdas al. 2015).
not: H. P / Q.
Predictive two-sample and independence tests (2STs and ITss respectively) aim to address such limitations of kernelized approaches. The idea of using classifiers for two-sample testing dates back to Friedman (2004) who proposed using the output scores as a dimension reduction method. More recent works focused the direct evaluation of learned model for testing. In initial arXiv 2016 preprint, Kim et al. [2021] proposed and analyzed predictive 2STs based on samplc-spliting, namely testing whether the accuracy of model trained the first split of data and estimated on the second split is significantly better than chance. The authors established the consistency of asymptotic and exact tests in high-dimensional settings and provided rates for the case of Gaussian
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distributions. Inspired by this work, Lopez- Paz and Oquab] (017] soon after demonstrated that empirically predictive 2STss often outperform state-of-the of-the-art 2STs, such as kemnl--MMD. Recently, Hediger et al. [022) proposed a related test that utilizes out-of- -fg predictions for beaging-haseds classifiers, such as random forests. To incorporate measures of model confidence, many authors have also explored using test statistics that are based on the output scores instead of the binary class predictions [im et al. 2019 Liu et al., 2020 Cheng and Cloninger 2022 Kübler et al. [022].
The focus of the above works is on batch tests which are calibrated to have fixed false positive rate (say, 5%) if the sample size specified in advance. In contrast, we focus on the setting of sequentially released data. Our tests allow on- on-the-fly fly decision-makinn whether to stop and reject the null or collect more data, without inflating the false alarm rate.
an analyst can use observed data to decide
Problem Setup. First, we define the problems of sequential two-sample and independence testing. Definition (Sequential wo-sample testing). Suppose that we observe a stream of i.i.d. observations ((Z,, W₂) )c21, where We- ~ Rademacher (1/2)) the distribution of Ze W, = +1 is denoted P. and that of Ze W₂- = is denoted Q. The goal to design a sequential test for
Ho : P= Q
(Ia)
H1 : P Q.
(Ib)
Definition 2 (Sequential independence testing). Suppose that we observe that stream of observations: ((X,,)))) 12)) where (X,, (2) ~ Pxx for t 2 1. The goal is to design a sequential test for
Ho (X,, Yi) Pxy and Pxy Px x Py,
(2a)
H1 : (Xi, Y,) ~ Pxy and Pxy + Px x Py.
(2b)
We operate in the framework of "power-one tests" (Darling and Robbins 1968 and define level-o sequential test as mapping $ - 2' - {0, 1 that satisfies: IHo 3. 2 (Z Z,) = 1) S a. We refer to such notion of type error control time- time-uniform. Here, 0 stands for "do not reject the null yet" and stands for "reject the null and stop". Defining the stopping time as the first time that the test outputs 1: == inf 1 (Z ...,, Z,) = 1). sequential test must satisfy
Pho (T < 00) S a.
We aim to design consistent tests which are guaranteed to stop if the alternative happens to be true:
PH. (T 20)= =
Related Works. Our construction follows the principle of testing by betting [Shafer] 202 1 The most closely related work is that of "nopparametrie 2ST by betting" of Sheekar and Ramdas [2023), ) which later inspired several follow-up works, including sequential (marginal) kernelized independence tests oodooppe et al. [2023], and the sequential conditional independence tests under the model-X assumption of Grünwald et al. [2023] and Shaee et al. (2023). We extend the line of work of Shekhar
and Ramdas [2023 and of Podkopaev et al. 2023] studying predictive approaches in detail.
Sequential predictive 2ST's were studied by Lhéritier and Cazals [2018] 2019), but in practice, those tests were found to be inferior to the ones developed by (Shekhar and Ramdas (2023). Recently, Pandeva et al. [2022] proposed a predictive 2ST that handles unknown class proportions using ideas
from [Wasserman al. 2020]. In Section 2 we show that our tests are closely related to [Lhériiter
and Cazals 2018 2019 Pandeva et al. 2022). but are consistent under much milder assumptions.
Sequential Nonparametric Two-Sample and Independence Testing by Betting. Suppose that
one observes a sequence of random variables (Ze)221. where Z, E 2. The principle of testing by betting [Shafer and Vovk 2019 Shafer 2021] can be described follows. A player starts the game with initial capital K = 1. At round f. she selects a payoff function f. Z - [-1, oo) that
satisfies Ez-rz (Z) F. = 0 for all Pz E Ho. where F, a aZ 7T-1) denotes the
sigma-field generated by ,,,.., Z-1 with Fo being the trivial sigma-field, and bets a fraction of her wealth X,K₁-1 for an F, measuuaale X, E [0, 1]. Once Z, is revealed, her wealth is updated
K, = KG-1 + X,C, = KG-1 (1+ fef(
(5)
The wealth is used to measure the evidence against Hg: if player can make money in such game, the null is rejected. Formally, for testing Ho at level a E (0, 1). we use the stopping rule:
inf (t > 1 K, 2 1/a).
(6)

---

The validity of the test follows from Ville's inequality [iilee 1939,, a time-uniform generalization of Markov's 's inequality, since (K2) is a nonnegative martingale starting 1 under any Pz E Hy. To ensure high power, one has to choose (fz)x21 and (Ax)221 to guarantee the growth of the wealth if the alternative true. the context of two-sample and independence testing, [Shekhar and Ramdas [2023] and Pndkoopae et al. [2033 recently proposed effective betting strategies based on kernelized measures of statistical distance and dependence respectively which admit a variational representation. In nutshell, datapoints observed prior to a given round are used to estimate the witness function one that best highlights the discrepancy between P and Q for two-sample (or between Pxy and Px x Py for independence) testing- and bet is formed of distance (or dependence). In contrast, our bets are based on evaluating the performance of a sequentially learned predictor that distinguishes between instances from distributions of interest.
estimator of chosen measure
Remark 1. In practical settings, an analyst may not be able to continue collecting data forever and may adaptively stop the experiment before the wealth exceeds 1/a. In such case, one may use a different threshold for rejecting the null at a stopping time т, namely U/a, where U is (stochastically larger than) uniform random variable on [0, 1] drawn independently from (Fi). This choice strictly improves the power of the test without violating the validity; see [Ramdas and Manole, 2023].
Contributions. In Section 2 we develop sequential predictive two-sample and independence tests. We establish sufficient conditions for consistency of our tests and relate those to evaluation metrics of the underlying models. Section we conduct an extensive empirical study on synthetic and real data, justifying the superiority of our tests over the kernelized ones on structured data.
3
2 Classification-basee Two-Sample Testing
We begin with the two-sample testing setting outlined in Definition 5 Let G : 2 [-1,1]] denote a class of predictors used to distinguish between instances from P (Tabeled as +1) and Q (labeled as We assume that: (a) if g E G. then -y E G. (b) if E G and s E [0, 1J. then 8g E G. and (c) predictions are based on sign(g())], and if g(z) = O, then is assigned to the positive class. Two natural evaluation metrics of a predictor E G include the misclassification and the squared risks:
Rm (g) P (W. sign [g (Z) < 0)
Rg( E [(9( (2) -W)
which give rise to the following measures of distance between 1' and Q. namely
dm (P, Q) = sup (1 Rm(()),, da(PQQ == sup (1 Ra(g)). geg
(8)
gEg
It is easy check that dm, (P, Q) E [o, 1/2] and dm (), E [0. 1). The upper bounds hold due the non non-negativity of the risks and the lower bounds follow by considering that the misclassification risk is invariant squared risk is not, and rescaling any g to optimize the squared risk provides better contrast between P and Q. In the next result, whose proof is deferred to Appendix [D.] we present an important relationship between the squared risk of rescaled predictor and its expected margin: E [W (()).
g(z) = 0, 02 E Z. Note R'm (9). Vs (0, 1)), whereas the
rescaling (Rm (sg)
Proposition 1. Fix an arbitrary predictor g E G. The following claims hold
1. For the misclassification risk, we have that:
sup (1 - Rm()))) = ( Rm (g) VO- = (t LE [ sign [a(2]]] vo.
(9)
#E[U.1]
2. For the squared risk, we have that:
E g(2)
sup (1 - (s())) 2 (E [W (E[W.g(Z)]vo)
E [ (Z)] A1
(10)
eE(0.1]
Further, dP(P Q) > 0 if and only if there exists E G such that E [
g()) > 0.
Similar argument can be applied to general scoring-based classifiers: y Z -> R. e.g. SVMs, by considering g (ā ő(z) = tanh(s tan)(s-g(=)), g E 9, & > 0}, where the constant > 0 corrects the scale of the scores. V and A denote maximum and minimum respectively: V b max/a, b), A b min(a,b).
3

---

Consider an arbitrary predictor g G. Note that under the null Ho in Iaa. the misclassificatiin risk (g) does not depend on g, being equal to 1/2. whereas the squared risk (g) does. In contrast, the lower bound (TO) no longer depends on under the null Ho. being equal to 0.
Oracle Test. It is a known fact that the minimizer of either the misclassification the squared risk is B (2) = 2z) 1, where rπ(z) IP (W = +1 Z = 2). Since g gByess may not belong to G, we consider g. E G. which minimizes either the misclassification the squared risk over predictors in G, and omit superscripts for brevity. To design payoff functions, we follow Proposition and consider
f.h (Z,, Wi) = W sign [g. (Z)) (-1,1),
(11a)
(Z, W:) = W, g, (2x) E [-1,
(11b)
Let the oracle wealth processes based on misclassification and squared risks (Kc ) and be defined by using the payoff functions (Laa) and (TIb) respectively, along with a predictable
sequence of betting fractions (Ae)c21 selected via online Newton step (ONS) strategy (Hazan et al.
2007] (Algorithm D. which has been studied in the context of coin-betting by Cutkkoky and Orabona 2018
If constant betting fraction is used throughout: X = X, Vt, then
log x
[oog(1 + (Z W))] i {m,s}.
(12)
To illustrate the tightness of our results, consider the optimal constant betting fractions which maximize the log-wealth (12) and are constrained to lie in [-0.5, 0.5], like ONS bets:
arg max E [log(1 + Xf w))], , i e {m,s}. XE( 0.5.0.5.0
(13)
Algorithm 1 Online Newton step (ONS) strategy for selecting betting fractions
Input: sequence of payoff' (ft) ApNS = 0, ag =
for t = 1, 2, do Observe ft E [-1, 1];
Set 2; == ft/(1 + A ONS fe):
Set 02 = d:-1 2/;
Set AONS : 1/44 A
AONS + 2-1og3 ;1 :)):
Assuming that the 2ST null is false and a predictor with non-trivial prediction risk is used, it is easy to see that the optimal constant betting fraction has be positive, which is why in Algorithm D we truncate X at O instead of - 1/2 (the latter option is used in [Cutkosky and Orabona 2018). We note that this is allowed and does not affect any theoretical claims of the paper. In early simulations, we also did not observe any major differences between the two truncating options. We conclude with the following result for the oracle tests, whose proof deferred to Appendix D.3
Theorem 1. The following claims hold:
1. Suppose that Ho in (Tab is true. Then the oracle sequential test based on either (KCT ")(20 (K)))r20 ever stops with probability at most ac IP Ho (T < 00) S a.
2. Suppose that H₃
(b is true. Then:
(a) The growth rate of the oracle wealth process (K,m )ez0
Je20 satisfies:
lim inf (2 log K!Th+)) 1-000
(2 Ruu (9.))²
(14)
If Rm (g.) <1/2. then the test based on (KeT""))>0 is consistent: PH, (T < 00) Further, the optimal growth rate achieved by Am in (3) satisfies:
=
E [oog(1 +
<
16 (3
(1
Rm (I+))) A ( Run ( (15)
(b) The growth rate of the oracle wealth process (KC"")) satisfies:
lim inf (t log ko+)
E [W- (z)). a.s.
2
(16)
10000

---

I IW 9.(Z)) > O, then the test based on (K()) )120 is consistent: PH, (T < 00) =
Further, the optimal growth rate achieved by X 13 satisfies:
E [lg((1 + x. - 2 IW 9 (z)).
(17)
Theorem T precisely characterizes the properties of the oracle wealth processes and relates those to interpretable metrics of predictive performance. Further, the proof of Theorem Thighlights a direct impact of the variance of the payoffs the wealth growth rate, and hence the power of the resulting sequential tests (as the null is rejected once the wealth exceeds 1/a)..
The second moment of the payoff's based on the misclassification risk (1a) is equal to one, resulting in a slow growth: the bound (14) proportional to squared deviation of the misclassification risk from one half. The bound (5) shows that the growth rate with the ONS strategy matches, up to constants, that of the oracle betting fraction. Note that the second term in (15) characterizes the growth rate if Rm (g.) < 5/16 (low Bayes risk). In this regime, the growth rate of our test is at least (3/16) (1/2- - Rm (9+)) which is close to the optimal rate. The second moment of the payoffs based on the squared risk is more insightful. First, present result for the case when the oracle predictor 9. in (Tib) is replaced by an arbitrary E G. The proof is deferred to Appendix D.3
Corollary 1. Consider an arbitrary g E 9 with nonnegative expected margin: E [W g(Z)) 2 Then the growth rate of the corresponding wealth process (KC))22 satisfies:
lim inf (t log (c)) 2 { sup (1- Rs (sg)) A EE IW 2((I)) =E[0,1]
(18a)
+20
1/4 (B [W g(2)))²
(18b)
and the optimal growth rate achieved by X; in 13 satisfies:
E [log(1 + (z <
sup (0
(1 Rs (8g)) A (5 E [W 9(Z)])
(19)
Corollary I states that for an arbitrary E G. the growth rate is lower bounded by the minimum of the expected margin and the (optimized) squared risk of such predictor. While the latter term is always smaller for the optimal g.. this may not hold for an arbitrary E G. The lower bound (I8b), which follows from []oposition[]] is always worse than that for 9+ (the expected margin is squared). The upper bound (9) shows that the growth rate with the ONS strategy matches, up to constants, that of the optimal constant betting fraction. Before presenting a practical sequential 2ST, we provide two important remarks that further contextualize the current work in the literature.
Remark 2. In practice, we learn predictor sequentially and have to choose a learning algorithm. Note that (8a) suggests that direct margin maximization may hurt the power the resulting 2ST: the squared risk is sensitive to miscalibrated and overconfident predictors. Kübler et al. (2022) made a similar conjecture in the context of batch two-sample testing. To optimize the power, the authors suggested minimizing the cross-entropy or the squared loss and related such approach to maximizing the signal-to-noiss ratio, a hcuristic approach that was proposed earlier by Sutherland et al. (2017
Remark 3. Suppose that g Bayes E G and consider the payoff' function based on the squared risk (1b). At round t, the wealth of a player K is multiplied by
1 Ae We Bayes (Zx) = (1- Av) + A (1+ We Bayes (Ze)
= (1 - A.) 1+ (v))))) 1[W;=1} (1 -1-1/ ()=) 2(W:=)
(20)
(W:--1)
and hence, the betting fractions interpolate between the regimes of not betting and betting using likelihood ratio. From this standpoint, 2STs of Lhéritier and Cazals [2018] 2019). Pandeva et al. 2022) set X 1, Vt, and use only the second term for updating the wealth despite the fact that the true likelihood ratio is unknown. An argument about the consistency of such test hence requires imposing strong assumptions about sequence of predictors (gt) [Lhéritier and Cazals 2018 2019]. Our test differs a critical way: we use a sequence of betting fractions, (Ad)e21, which adapts to the quality of the underlying predictors, yielding consistent test under much weaker assumptions.
Standard CLT does not apply directly when the conditioning set grows; see
Kim and Ramdas 2020
5

---

Example 1. Consider P= NO, 1) and Q (6 1) for 20 values of ó, equally spaced in [0, 0.5].
For given ö, the Bayes-optimal predictor
Bayes (z) (0 1)
((;; -(( E 11,,,1}
(21)
(02;0 6(2;;,1)
where (2;;; μt, o²) denotes the density of WM,, o²) evaluated at In Figure la we compare tests that use (a) the Bayes-optimal predictor, (b) a predictor constructed with the plug-in estimates of the means and variances. While in the former case betting using likelihood ratio (A, = 1, Vt) is indeed optimal, our test with an adaptive sequence (Ae) is superior when predictor learned. The difference becomes even more drastic in Figure lb where (regularized) k-NN predictor is used.
1.0
1.0
Rejecton Rate Time 7 5000
Cracia predictior:
Rejection Rate Time 7- 2009
1,12
0.00
Learned predictor:
0.5
3.W
0.
0.2
0.3
(a) Parametric model.
(b) Nonparametric model (k-NN).
Figure 1: Comparison between 2ST with adaptive betting fractions and the likelihood ratio test for Example [ While the likelihood ratio test is better if the Bayes-optimal predictor is used, our test superior if predictor is learned. The results aggregated over 500 runs for each value of 8.
Sequential Classffication-based 2ST (Seq-C-2ST), Let A.
+1) x
denote learning algorithm which maps training dataset of any size and previously used classifier, to an updated predictor. For example, As may apply a single gradient descent step using the most recent observation to update model. We start with D/ and 91 :: (2) 0, for any Z. At round i, we use one of the payoffs:
(Z, W.) = W. sign (Z)) E (-1,1), [e, (Z,, W.) W. (Z,) [-1,1].
(22a)
(22b)
After (Ze, Wi) is used for betting, update training dataset: D, Di-1 {(Z,, Wo). and an existing predictor: 9++1 = Ac(r,.))) We summarize our sequential classification based 2ST (Seq- C-2ST) in Algorithm 2 We note that using pre-trained models (e.g., for image data) as initialization
may definitely improve the performance during the early stages of testing in practice.
Algorithm 2 Sequential glassification-basse 2ST C-2ST)
Input: level (0, 1), data stream ((z, Wi)) 91(2) = 0, Ac. Do 0, NONS 0.
for t = 1,2.... do
Evaluate payoff fi(2,, W.) as 22a
Using XONS update the wealth process K.; as per 5
KC 2 1/a then
Reject Hg and stop;
else
Update the training dataset: D, = D,-1 U ((Z,, Wo);;
Update predictor: 9t+1 = (D, 9t); Compute X ONS (Algorithm) using f (Z,, Wi): x++1
While we do not need any assumptions to confirm the type error control, we place some mild assumptions the learning algorithm Ag argue about the consistency.

---

Assumption 1 (Rm -earnabilit) Suppose that H1 in (lb) is true. An algorithm A. is such that the
resulting sequence (g))21 satisfies: sup, 1 E/=
==1 [W; ; sign [9,( <0 a.s.
1/2.
Assumption (Rg-laaraaiiltt)) Suppose that H1 in (1b is true. An algorithm A. is such that the resulting sequence (gt (g))121 satisfies: lim supt-<>
2 (o:(Z.) w:) <
In words, the above assumptions state that sequence of predictors (gt):21 is better than chance predictor on average. We conclude with the following result, whose proof is deferred to Appendix D.3
Theorem 2. The following claims hold for Seq-C-2ST (Algorithm 2
1. If Ho in la is true, the test ever stops with probability at most a: Pho (r 00) S a.
2. Suppose that H1 in (Ib) is true. Then:
(a) Under Assumption I the test with the payoff (22a) is consistent: PH, (T < 20)
(b) Under Assumption
2
the test with the payoff (2bb is consistent: Pr, (T < 000 =.
Remark 4. Suppose that we perform two-sample testing for d-dimensional data. At time T, the total accumulated computation for the kernelized test of Shekhar and Ramdas 2023 is Odd7²). For our test, the answer depends on the chosen classifier and learning algorithm. Using logistic regression in combination with gradient descent for updating model parameters results in cheap updates and payoff evaluation (both are (dd) at each round, and hence the total accumulated computation at time '' is O(d("). For N-NN classifier, no parameters have be updated, yet evaluating payoff's becomes more expensive with growing sample size, resulting in the total accumulated computation of O O(kTT² time T. For more complex models like neural nets, runtime depends on the chosen architecture: the total accumulated computation at time T is O([cB + F)T), where F and B are the costs of horward-propagee and back- propaaatoonnnnnn steps respectively and e the number prop-propagttion steps applied after processing the next point (the exact cost depends on the architecture).
Sequential Classification- Independence Test (Seq-C- C-IT-C- Under the setting of Definition 2 a single point from Pxy revealed each round. Following [Podkopaev et al. 2023], we bet on two points from Pxy (labeled as +1) and utilize external randomization to produce instances from Px x Py (labeled as -1). Let A (U121 ((X' x )) x {-1,+1))') x g - G denote a learning algorithm which maps training dataset of any size and previously used classifier, to updated
predictor. We start with Do = @ and 91 91 (x. y) = 0, v(I y) E X' x V. We use derandomized
versions of the payoffs 22 e.g., instead of (22h)
17((22-11 Yu- (X26, Y20)) = (ge (x Y2-1) + De (e(X20x Y2()) - 4 (X2-111 Y2.) + ge (X2,, Y2:
(23)
After (X2--1, Y21 (X2r, Y21) have been used for betting, update training dataset:
D. D:-1 U (((xx=11, Y2. 1), +1), ((X2r, Y2,), ((X2-1, Y2.), -1), ((X2,, Y2. 1), 1))}
and an existing predictor: -t-1 A!T (De, Seq-C-IT inherits the time-uniform type error control and the consistency guarantees of Theorem 2 and we omit details for brevity.
Experiments
Synthetic Experiments. In our evaluation, we first consider synthetic datasets where the complexity of the independence testing setup is characterized by single univariate parameter. We the monitoring horizon to T = 5000 points from Pxy, and for each parameter value, we aggregate the results over 200 runs. In particular, we use the following synthetic settings:
1. Spherical model. Let (Ut)21 be sequence of random vectors a unit sphere in Rd:
U, iid Unif( and let u() denote the i-th coordinate of u. For t 2 1, we take
(X,, Y2) = ((U))))) (U)))))
We consider d E (3...., 10}. where larger d defines a harder setup.
7

---

We use the HSIC-based sequential kernelized independence test (SKIT) [Podkopacv al. 2023 as a reference test and defer details, such as MLP training scheme and SKIT hyperparameters to observe that SKIT outperforms Seq-C-IT's under the spherical model (with no localized dependence structure), whereas, under the structured HTDD model, Seq-C-IT's, is superior. Further, inspecting Figure the reader to Appendix [E.2 for additional experiments on synthetic data with localized dependence where Seq-C-IT's are superior. In Appendix [.2] we also provide the results for the average stopping times of our tests: we empirically confirm that our tests are adaptive to the complexity of a problem 2. Hard-to rro-detect-dependdee (HTDD) model. We sample ((X,, Y2))21 from
p(r, v) - (1 sin(wx) sin(wy)) (1, v) [-
(24)
We consider w E {O...., 6). where Ho true (random variables are independent) if and only if O. For w > 0, Corr (X, Y s 1/w", and the setup is harder for larger w.
For the comparison, we use two predictive models to construct Seq-C-ITs:
1. (i()) == (2, ke) define the set of kt closest points in D;-1 query point
2 = (z, We consider regularized k-NN predictor: (x(z) k E 2 (Z.W))N W.
1
We select the number of neighbors using the square-root rule: k = v DD = / 1).
2. We use multilayer perceptron (MIP) with three hidden layers and 128, 64 and 32 neurons respectively and the parameters learned using an incremental training scheme.
Appendix E.T In Figure
0 confirms that all tests control the type I error. We refer
hand: they stop earlier on easy tasks and later harder ones.
Rejectóo Rate at Time T- 5000
910
0.5
S-I.CIT (MLF):
0.5
SKIT
C-I
Power Time p=
S. [[-M0):
0.0
0.0
5
10
0
(a) Spherical model.
(b) HTDD model.
Figure 2: Power of different sequential independence tests on synthetic data from Section 3 Under the spherical model (no localized dependence), SKIT is better than Seq-C-IT'. Under the (structured) HTDD model, SKIT is inferior to sequential predictive independence tests.
Real Data Experiments. First, we compare sequential classification based and kernelized 2STs using Karolinska Directed Emotional Faces dataset (KDEF) [Lundqvist et al.) 1998) which contains images of actors and actresses expressing different emotions: afraid (AF), angry (AN), disgusted (DI), happy (HA), neutral (HE), sad (SA), and surprised (SU). Following earlier works [Lopez-Paz and Oquab] 2017 7 Fitkrittum et al. 2016), we focus on straight profile only and assign HA, NE, SU emotions to the positive class (instances from P), and AF, AN, DI emotions to the negative class (instances from Q); see Figure Bal We remove corrupted images and obtain a dataset containing 802 images with six different emotions. The original images (562 762 pixels) are cropped to exclude the background, resized to 64 64 pixels and converted to grayscale.
For Seq-C-2ST, we use small CNN as an underlying model and defer details about the architecture and training Appendix E..1 As reference kernel-based 2ST, we use the sequential MMD test
of Shekhar and Ramdas (2033 and adapt it to the setting where at each round either an observation from P or that from Q is revealed: see Appendix E. I for details. We omit the comparison to [héritier
and Cazals [209]] since their test has been shown to be inferior to the one developed by Shekhar
and Ramdas [2233 In Figure (3b we illustrate that while both tests achieve perfect power after processing sufficiently many observations, our Ceq-C-2ST requires fewer observations to do

---

1.0
Seq C 25T
Kemel
Rejetton Rate
0.5
0.2
Sample
(a)
(b)
Figure 3: (a) Examples of instances from P (top row) and Q (bottom row) for KDEF dataset. (b) Rejection rates for our test (Seq-C-2ST) and the sequential kernelized 2ST. While both tests achieve perfect power with enough data, our test is superior to the kernelized approach, requiring fewer observations to do so. The results are averaged over 200 random orderings the data.
Next, we compare two independence tests using MNIST image dataset [LeCun et al. 1998]. To simulate the null setting, we sample pairs of random images from the entire dataset, and simulate the alternative, we sample pairs of random images depicting the same digit (Figure 4ab. For Seq-C-IT, MLP with the same architecture as for simulations synthetic data. For SKIT, median heuristic with 20 points from Pxy to compute kernel hyperparameters. In Figure 4b] we show that while both tests control the type I error under Ho. SKIT is inferior to Seq-C-IT under H1. requiring twice as much data to achieve perfect power.
the
3
3
Seq (T:
H. true
SKIT:
0.6
Rejectin
3
0.2
Pairs
(a)
(b)
Figure 4: (a) Instances from the Pxy (top row) and Px x Py (bottom row) for MNIST dataset. (b) While both independence tests control the type error under Hn. Seq-C-IT outperforms SKIT under H1, rejecting the null much sooner. The results are aggregated over 200 runs.
4 Conclusion
While kernel methods are state-of-the-art for nonparametrie two-sample and independence testing, their performance often deteriorates on complex data, e.g., high-dimensional data with localized dependence. In such settings, prediction-basee tests are often much more effective. In this work. we developed sequential predictive two-sample and independence tests following the principle of testing by betting. Our tests control the type I error despite continuously monitoring the data and are consistent under weak and tractable assumptions. Further, our tests provably adapt to the complexity of a problem at hand: they stop earlier on easy tasks and later on harder ones. An additional advantage of our tests is that an analyst may modify the design choices, e.g., model architecture, on-the-fly. Through experiments on synthetic and real data, we confirm that our tests are competitive to kernel-based ones overall and outperform those under structured settings.

---

We refer the reader to the Appendix for additional results that were not included in the main paper:
1. In Appendix A we complement classification- based ITss with regression- based approach. Regression-basee based IT's represent an alternative to the classification approach in settings where data stream ((X,, Y2))21 may be processed directly reature-response pairs.
2. In Section 2
considered the case of balanced classes, meaning that at each round, an instance from either P or Q is observed with equal chance. In Appendix B we extend the methodology to more general case of two-sample testing with unknown class proportions.
3. Batch two-sample and independence tests rely on either a cutoff computed using the asymp- totic null distribution of chosen test statistic (when and if the distribution drifts, both approaches fail to provide the type error control. In contrast, Seq-C-2ST and Seq-C-IT remain valid beyond the i.i.d. setting by construction (analogous to tests developed by Shekhar and Ramdas [2023] Podkopaev et al. [2023) ), and we refer the reader to Appendix C for more details.
tractable) or a permutation p-value,
The authors thank Ian Waudby-Smine and Tudor Manole for fruitful discus- sions. AR acknowledges support from NSF grants USS-2229881 and DMS-2310718.
Acknowledgements.
References
Thomas B. Berrett and Richard J. Samworth. Nonparametric independence testing via mutual information. Biometrika, 2019.
Xiuyuan Cheng and Alexander Cloninger. Classification logit two-sample testing by neural networks for differentiating near manifold densities. IEEE Transactions on Information Theory, 2022.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-fres online learning in banach spaces. In Conference on Learning Theory, 2018.
Donald A. Darling and Herbert E. Robbins. Some nonparametric sequential tests with power one.
Proceedings of the National Academy of Sciences, 1968.
Jerome H. Friedman. On multivariate goodness-of-ff fit and two-sample testing. Technical report, Stanford University, 2004.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with Kilbeer-SShhiie norms. In Algorithmic Learning Theory, 2005.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 2012.
Peter Grünwald, Alexander Henzi, and Tyron Lardy. Anytime-valid tests of conditional independence under model-X. Journal of the American Statistical Associatio, 2023.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 2007.
Simon Hediger, Loris Michel, and Jeffrey Näf. On the use of random forest for two-sample testing. Computational Statistics Data Analysis, 2022.
Wittawat Jitkrittum, Zoltán Szabó, Kacper P Chwialkowski, and Arthur Gretton. Interpretable distribution features with maximum testing power. In Advances in Neural Information P Processing Systems, 2016.
Imuu Kim and Aaditya Ramdas. Dimension-agnootic inference using cross U-statistics. Bernoulli, 2020.
Immn Kim, Ann B. Lee, and Jing Lei. Global and local two-sample tests via regression. Electronic Journal of Statistics, 2019.
Immn Kim, Aaditya Ramdas, Aarti Singh, and Larry Wasserman. Classification accuracy as proxy for sample testing. The Annals of Statistics, 2021.
10

---

Jonas M. Kübler, Vincent Stimper, Simon Buchholz, Krikamol Muandet, and Bernhard Schölkopf. AutoML two-sample test. In Advances in Neural Information Processing Systems, 2022.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Alix Lhéritier and Frédéric Cazals. A sequential non-parametric multivariate two-sample test. IEEE Transactions on Information Theory, 2018.
Alix Lhéritier and Frédéric Cazals. universal guarantees. In Advances in Neural Information Processing Systems, 2019.
Low-complexity nonparametric bayesian online prediction with
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica Sutherland. Learning deep kernels for paraametettic two-sample tests. In International Conference on Machine Learning, 2020.
David Lopez-Paz and Maxime Oquab. Revisiting classifier two-sample tests.
International
Conference Learning Representations, 2017.
Daniel Lundqvist, Anders Flykt, and Arn Öhman. The Karolinska Directed Emotional Faces KDEF. Technical report, Karolinska Institutet, 1998.
Teodora Pandeva, Tim Bakker, Christian A Naesseth, and Patrick Forré. E-valuating classifier two-sample tests. arXiv preprint: 2210.13027, 2022.
Aleksandr Podkopaev, Patrick Blöbaum. Shiva Prasad Kasiviswanathan, and Aaditya Ramdas. Se- quential kernelized independence testing. In International Conference on Machine Learning, 2023.
Aaditya Ramdas and Tudor Manole. Randomized and exchangeable improvements of Markov's, Chebyshev's 's and Chernoff's inequalities. arXiv preprint: 2304.02611, 2023.
Aaditya Ramdas, Sashank Jakkam Reddi, Barnabas Poczos, Aarti Singh, and Larry Wasserman. On the decreasing power of kernel and distance based nonparametrie hypothesis tests in high dimensions. AAAI Conference on Artificial Intelligence, 2015.
Aaditya Ramdas, Johannes Ruf, Martin Larsson, and Wouter Koolen. Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv preprint: 2009.03167 2020.
Shalev Shaer, Gal Maman, and Yaniv Romano. Model-free sequential testing for conditional independence via testing by betting. Conference on Artificial Intelligence and Statistics, 2023.
Glenn Shafer. Testing by betting: a strategy for statistical and scientific communication. Journal of the Royal Statistical Society: Series A (Statistics in Society), 2021.
Glenn Shafer and Vladimir Vovk. Game-Theoretic Foundations for Probability and Finance. Wiley Series in Probability and Statistics. Wiley, 2019.
Shubhanshu Shekhar and Aaditya Ramdas. Nonparametric two-sample testing by betting. IEEE
Transactions on Information Theory, 2023.
Danica J. Sutherland, Hsiao-Yo Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representatiinss 2017.
Jean Ville. Étude critique de la notion de collectif. Thèses de d'entre-deux-guerrss Gauthier- Villars, 1939.
Larry Wasserman, Aaditya Ramdas, and Sivaraman Balakrishnan. Universal inference. Proceedings of the National Academy of Sciences, 2020.
11

---

Appendix
A Regression-based Independence Testing
Regression-based independence tests represent an alternative to classification- based approaches in settings where data stream ((X,, Y())21 may be processed directly as feature- feature- response pairs. Suppose that one selects functional class G X' - y for performing such prediction task, and let denote loss function that evaluates the quality of predictions. For example, if (Yt) is
sequence of univariate random variables, one can use the squared loss: E(g(z), v) (g(x) - y)², or the absolute loss: {g((),,) 19(x) yy--
Such tests rely on the following idea: if the alternative H1 in 2b is true and sequence of sequentially updated predictors 201 has nontrivial predictive power, then the losses on random instances drawn from the joint distribution Pxy expected be less on average than the losses on random instances from Px x Py. For the 1-th pair of points from PXy, we can label the losses of ge on all possible (X, -)-piirs
-2:= = T-2 (9: Y2)). T2e 2 ( Y21-1)
- (1)
(25)
One can view this problem sequential two-sample testing under distribution drift (due incremental learning of (g:)s>) 1). Hence, one may use either Seq-C-2ST from Section Orr sequential kernelized 2ST of Shekhar and Ramdas [023) the resulting sequence of the losses on observations from Pxx and Px x Py. In what follows, we analyze direct approach where testing is performed by comparing the losses on instances drawn from the two distributions. A critical difference with construction of Seq-C-2ST is that to design valid betting strategy one has to ensure that the payoff functions are lower bounded by negative one.
A.1 Proxy Regression- Independence Test
To avoid cases when some expected values are not well-defined, we assume for simplicity that X' is a
bounded subset of Rd for som d 2 1: X' f E Rd ||ا||| I B₁ } for some B₁ > 0. Similarly, assume that ) is a bounded subset of I: y = (u R ly < B2 for some B₂ >> 0. We note that
the construction the regression-based IT will not require explicit knowledge of constants B, and
Bg. First, we consider setting where an instance either from the joint distribution from the product of the marginal distributions is observed at each round.
instance
stream of i..d. observations ((,,, Y,, We))c21, where W2 ~ Rademacher(1/2)) the distribution of (X,, Yi) | W, = +1 is Px x Py, and that of (X,, Y)) W, is PxY. The goal is to design test for the following pair of hypotheses:
Definition 3 (Proxy Setting). Suppose that we observe
Ho Pxx = = x x
(26a)
H1 PxY Px
(26b)
Oracle Proxy Sequential Regression-based IT. To construct an oracle test, we assume having access to the oracle predictor 9. X' > V/ e.g., the minimizer of the squared risk is g- (x)
E. [ X = zr). Formalizing the above intuition, we use E [[(g,(X), Y)] as natural way for
measuring dependence between X and Y. To enforce boundedness of the payoff functions, we use
ideas of the tests for symmetry from [Ramdas et al., 2020 Shekhar and Ramdas 2023 Podkopaey
ct al. 2023 Shaer et al. 2023], namely we use a composition with an odd function:
(X, Y., W;) = tanh (s. W. E(g. (X.), X)) E [-1,
(27)
where s, > O is an appropriately selected scaling factor Fl Since under Ho in (26). 8, W. C(g. (X,), Y2) is random variable that is symmetric around zero, it follows that E[ (X,, Y,, W,)]
WWe note that rescaling is important for arguing about consistency and not the type error control.
12

---

O, and, using the argument analogous to the proof of Theorem I we can easily deduce that sequential IT based on f- controls the type I error control. The scaling factor 8, selected in way that guarantees that, if H, in (26b) is true and if I (())((), Y)] > O, then E (X, Y, WW] > O. which is sufficient condition for consistency the oracle test. In particular, we show that it suffices to consider:
2p
V
(28a)
where
P. (X), Y),,
(28b)
2, [11 W) (e(g,
(28c)
Without loss of generality, we assume that v, is bounded away from zero (which is a very mild assumption since V/ essentially corresponds to a cubic risk of g. on data drawn from the product of the marginal distributions Px Py). Let the oracle regression -aased wealth process (XC) 120 be defined
by using the payoff function 27 with a scaling factor defined in (88)), along with a predictable
sequence of betting fractions (d4)221 selected via the ONS strategy (Algorithm Ip. We have the
following result about the oracle regression- IT, whose proof is deferred to Appendix D.4
Theorem 3. The following claims hold for the oracle sequential regression- based IT based on (KC)") '220'
1. Suppose that Ho in (26a) is true. Then the test ever stops with probability at most a: HH (T 00)= S
2. Suppose that H1 in 26bb true. Further, suppose that: E (X), 0. Then the test is consistent: PH, 00)= =
Practical Proxy Sequential Regression- IT. To construct a practical test, we use a sequence of predictors (g))(21 that are updated sequentially as more data are observed. We write A, (U:21 x )) x G - G to denote a chosen regressor learning algorithm which maps training updated predictor. We start with Do- 0 and some initial guess 91 E G. At round t, we use the payoff function:
dataset of any size and previously used predictor,
(X,, Y, W;) tanh (st W, E(ge (X.), Yi))
(29)
where a sequence of predictable scaling factors (8t)621 defined as follows: we set 8p and define:
8t 2/4
(30a)
1-1
where
Ht =
Wr ((g((X))) vo.
(30b)
t
Vt
Σ
(1+ W.) (I),
(30c)
After (X,, Y2, W.) has been used for betting, update training dataset: D. Dz-1 U {(X,, Y,, Wo), and an existing predictor: g1+1 = A.,,,.g)). We summarize this practical se- quential 2ST in Algorithm
For simplicity, we consider a class of functions g == (go : + v, E O) for some parameter set θ which we assume to be subset of metric space. In this case, sequence of predictors (0t) associated with the corresponding sequence parameters (0:)r21: for 2 1, g:(-) = g( 0.) for some 0, E O. To argue about the consistency of the resulting test, we make two assumptions.
Assumption 3 (Smoothness). We assume that:
Predictors in & are Lipschit smooth:
sup 1g(;; 0) - g(2; 0') s In 110 0'11, 40, e. x
(31)
13

---

Algorithm 3 Proxy Sequential Regression-based IT
Input: significance level (0, 1), data stream ((X,, Y,, W.)) g1(=) = O, Ar. Do = 0.
x $1 0. for f = .... do Evaluate the payoff (X,, Y,. Wi) as in 22 Using X update the wealth process K; as in 5);
K; 2 1/a then
Reject Ho and stop;
else
Update the training dataset: D, = D ((X,, Y));
Update predictor: 9t+1 A, (Dr,
Compute $14-1 as in (30a;
Compute ONS
(Algorithm using (X,, Y2, Wt);
The loss function l is L Li-ships smooth:
[[(g(2; 0). E(g(x; 0') $ Le sup (g(=;0) ,(x;0)), V0, e.. vEY
sup
(32)
#E
=EX'
In words, Assumption states that the outputs of predictors, whose parameters are close, will also be close. Assumption (32 states that that the losses of two predictors, whose outputs are close, will also be close. For example, if G is class of linear predictors: (0(x) A x, Assumption will
X, then will be trivially satisfied for the squared and the absolute losses if X' and y are bounded.
Note that we do need explicit knowledge of Lı L2 for designing a test. Second, make learnability assumption about algorithm Ar.
Assumption 4 (Learnability)) Suppose that H1 in (6bb) is true. We assume that the regressor learning algorithm A, is such that for the resulting sequence parameters (0z)121. holds that a.s.
0, - 0., where 0, is random variable taking values in O and E (Wt(g(X;0.); 0.) > where (X) 1l. 0-.
We conclude with the following result for the practical proxy sequential regression- IT, whose proof is deferred to Appendix D.4
Theorem 4. The following claims hold for the proxy sequential regression-based IT' (Algorithmm
1. Suppose that Ho in (6a) is true. Then the test ever stops with probability at most a:
I Ho (T < 00) S a.
2. Suppose that Hı in 26bb is true. Further, suppose that Assumptions' 3 and are satisfied. Then the test is consistent: PH, (7 < <0)
Sequential Regression- Independence Test (Seq-R-IT). Next, instantiate this test for the sequential independence testing setting (as per Definition 2 where we observe sequence
((,,, Y2))c21. where (X,, Yt) two observations drawn from the joint distribution Pxy. To proceed, derandomize the payoff function (29p and consider
jid Pxy, 2 Analogous to Section 2 we bet on the outcome of
1
(((( Y2-1)), (X2r, Y2.)) 4
(lanh (st - Y2)) + tanh (#t (g((Xz))) Y2e-1)))
1 (Lanh (st l (g) (X2x), Yz.)) tanh (st (g. (X 21- Y )))
(33)
After betting on the outcome of the t-th pair of observations from Pxy. we update a training dataset:
D. = D,-1 U (X 12.-1), (Xee, Y2.))
and predictive model: 9:+1 A,
14

---

A.2 Synthetic Experiments
To evaluate the performance of Req-R-IT, we consider the Gaussian linear model. Let (Xt)121 and (Et) denote two independent sequences of i..dd standard Gaussian random variables. For t 2 1, we take
(X Y2) (X,, X, + ex),
where 3 + 0 implies nonzero linear correlation (hence dependence). We consider 20 values of B equally spaced [0, 1/2. For the comparison, we use:
1. Req-R-IT with ridge regression. We use ridge regression as underlying model: (x:)) 3 + 2 where
2(t-1)
(06 ((0) arg min 8o,8s
Σ
-
-Bo)² 2 A39.
2. Seq-C-IT with QDA. Note that Pxx (N,, and Px x Py =N(,E where
0 ) Σ
B
Σ (: B
B
11
For this problem, oracle predictor which minimizes the misclassification risk is
u): -
9" (1z, v) (0 y): Σー (((,,, Σ+)
E [-1,
(34)
where (0 v); n, Σ) denotes the density of the Gaussian distribution (Nu, Σ) evaluated at
(x. 8). Recall that Dz-1 = {Z,, +1))isa((-1) U -1))s((-)) denotes the training dataset that available
round for training a predictor Ôr X' y - [-1, We deploy Seq-C-IT with an estimator d. of (34). obtained by using plug-in estimates of et, + 1 DT computed from D,-1:
At 2(t - 1)
Σ Z,
Σ
1
Σ ZED
ZZ ((())R2)
2(t - 1)
ZED
and (7, En computed similarly from DT-
In addition, we also include HSIC-based SKIT to the comparison and defer the details regarding kernel hyperparameters Appendix E.I We set the monitoring horizon to T 5000 points from Pxy and aggregate the results over 200 sequences of observations for each value of 3. We illustrate the result in Figure while Req-R-IT has high power for large values of B, observe its inferior performance against Seq-C-IT (and SKIT) under the harder settings. Improving regression-ban betting strategies, e.g., designing better scaling factors that still yield provably consistent test, open question for future research.
B Two-sample Testing with Unbalanced Classes
In Section 2 we developed a sequential 2ST under the assumption at each round, an instance from either P is revealed with equal probability. Such assumption was reasonable for designing Seq-C-IT, where external randomization produced two instances from Pxy and Px x Py at each round. Next, we generalize our sequential 2ST more general setting of unbalanced classes.
Definition 4 (Sequential two-sample testing with unbalanced classes), Let (0, 1). Suppose that we observe a stream of i.idd. observations ((Z,, W,))2.. where W, ~ Rademacher the distribution of Z, W, +1 is denoted P, and that of Z, W. -1 is denoted Q. We set the goal of designing a sequential test for the following pair of hypotheses:
Ho : P Q
(35a)
H1 P Q
(35b)
15

---

5300
Rijerion Rate at Time 7- (000
Sea CTT
C-1T Raq-RAIT
SKIT
SKIT
11:0
6.6
Srppinn
2300
1000
(a)
(b)
Figure 5: Comparison between Seq-R-IT, Seq-C-IT and HSIC-based SKIT under the Gaussian linear model. Inspecting Figure Sa at 3 = 0 confirms that all tests control the type error. Non-surprisingly, kernel-based SKIT performs better than predictive tests under this model (no localized dependence).
We also observe that Seq-C-IT performs better than Seq-R-IT.
For what follows, will focus on the payoff based on the squared risk due its relationship the likelihood-ratio based test (Remark() 3). In particular, after correcting the likelihood under the null 20 to account for a general positive class proportion x, we can deduce that (see Appendix D
(1- A.) 1 do- (no(2))) (WW=l) (1 7h (2t)) (W)=))
W, (Zx( (2T - 1)) W2 - 1)
1+
(36)
(TT) ((W=1) (1 π) WWW==
where (2) = (9c(2) + 1)/2, and hence, a natural payoff function for the case with unbalanced classes is
We (Ze (2m 10--1]] 1)) 1 W2
ZZ Wi)
(37)
Note that the payoff for the balanced case (2b) is recovered by setting 1/2. It is easy to check that (see Appendix D (a) (z, w) 2 for any (z, w) x {-1, and (b) if Ho in (35a) is true, then HH, [f Ze W,) Fi-1l O, where F = a (Z W;) Wi)) This in turn implies that wealth process that relies on the payoff function f in 37 is nonnegative martingale, and hence, the corresponding sequential 2ST valid. However, the positive class proportion æ,, needed to the payoff function (37. is generally unknown beforehand. First, let us consider the case when A = 1, In this case, the wealth of gambler that uses the payoff function (37 after round t
K2 IT (Z.) (W-=) (1 m((Z)) (W--))
(38)
I1 ([W-=1) m)
(1,5) (W,
Note that:
[ (W: (1 (1-x)
1 [W, 1) arg max T
E=1
the MLE for æ computed from (Weleer In particular, if we consider a process (K))120 where
Ii (Z)) (1 7) (1.)) I (+t) (W; (1 - # (W,
c
t21,
follows that R. KG, VL 2 meaning that (AC) is process that is upper bounded by nonnegative martingale with initial value one. This turn implies that test based on (fz))ze is valid level-a sequential 2ST for the case of unknown class proportions. This idea underlies the running MLE sequential likelihood ratio test of Wasserman al. [2020) and has been recently considered in the context of two-sample testing by Pandeva et al. 2022] In case of nontrivial betting fractions: (Xx 1221, representation of the wealth process (38) no longer holds, and to proceed, we modify the rules of the game and use minibatching. A bet is placed every (say, 5 or 10) observations, meaning
16

---

that for given minibatch size 2 1, at round t we bet on {(Zb(- Whçe- (it The MLE of computed from the f-th minibatch is
tt
Σ
(tt1))+11
We consider a payoff function of the following form:
be
11 (ig( (
ft (((Z Wo(c sE (epp.) = II
T+ 1+W,,(25) 17) - 1. (39)
bb(-11)+
In words, the above payoff essentially compares the performance of a predictor It, trained on f(Z,, Williga(--) and evaluated on the t-th minibatch, that of trivial baseline predictor to form a bet. In particular, setting b 1 yields a valid, yet powerless test. Indeed, we have n. (We = = (W, + 1)/2. In this case, the payoff (39 reduces to W, (g. (Z.) (2#, - 1)) W.g. (Z.) - a.a. 1 + Wi (2 - 1)
2 E [-1,0],
implying that the wealth can not grow even if the null is false. Define a wealth processes (XC)) )220
based on the payoff functions (39) along with predictable sequence of betting fractions (Ae)
selected via ONS strategy (Algorithm TT. Let F, = (((Z,, Wi))isw) for t 2 1, with Fo denoting trivial sigma-algebra. We conclude with the following result, whose proof deferred Appendix DD5
Theorem 5. Suppose that Ho in (35a) is true. Then (KF) is nonnegative supermartingale adapted to (Fi)z2o Hence, the sequential 2ST based on (KT )0200 satisfies: Pho (T < 00) S a.
C Testing under Distribution Drift
First, we define the problem of two-sample testing when at each round instances from both distribu- tions observed.
Definition (Sequential two-sample testing). Suppose that we observe that a stream of observations:
Px x Py for 2 1. The goal to design a sequential test for ((,,, Y2)) where (X,, Y2) äd
Ho: (X,, Y.) ~ Px x Py and Px = Py,
(40a)
H1 (X,, Y)) Px x Py and Px # Py.
(40b)
Under the two-sample testing setting (Definition 5). label observations from Py positive (+1) and observations from Px as negative (-1). We write AASST (Utz1 (X' x +1)) x G - G to denote chosen learning algorithm which maps training dataset of any size and previously used predictor, to an updated predictor. We start with Dn = and 91 91 (z) = 0, Vr E X. At round t, bet using derandomized versions of the payoffs 22). namely
(X,, Y2) = (sign [9. (Yr) sign [ (X,))) (X,, = (g.(X) (X.)).
(41a)
(41b)
After (X2, Yr) has been used for betting, we update a training dataset and an existing predictor:
D. = D +1), -1)], g++1 A gt).
Testing under Distribution Drift. Batch two-sample and independence tests generally rely on either cutoff computed using the asymptotic null distribution of chosen test statistic (if tractable) or a permutation p-value. Both approaches require imposing i.i.d. (or exchangeability. for the latter option) assumption about the data distribution, and if the distribution drifts, both approaches fail to guarantee the type error control. contrast, Seq-C-2ST and Seq-C-IT remain valid beyond the i.i.d. setting by construction (analogous to tests developed in (Shekhar and Ramdas 2023 (Podkopaey al. (023)). First, we define the problems of sequential two-sample and independence testing under distribution drift.
17

---

Definition 6 (Sequential two-sample testing under distribution drift), Suppose that we observe that stream of independent observations: ((X,, 12) where (X,, Y:) ple p()) is to design sequential test for the following pair of hypotheses:
1. The goal
Ho : p PV Vt,
(42a)
H1 33 P p
(42b)
Definition (Sequential independence testing under distribution drift). Suppose that we observe that stream of independent observations from the joint distribution which drifts over time: ((X,, 12))
where (Xe, Yi) Pxy. The goal is design sequential test for the following pair of hypotheses:
Ho P( = P( x p(() Vt,
(43a)
H, 3t PKP p( x p(()
(43b)
The superscripts highlight that, in contrast to the standard i.i.d. setting (Definitions S and 2). the underlying distributions may drift over time. For independence testing, we need to impose an additional assumption that enables reasoning about the type error control of Seq-C-IT.
Assumption 5. Consider the setting of independence testing under distribution drift (Definition 7 We assume that for each t 1, it holds that either P p(t-1) 1) p( or P Pf" meaning that at each step either the distribution of X changes that of Y changes, but not both simultancouslyJ
We have the following result about the type error control of our tests under distribution drift.
Corollary 2. The following claims hold:
1. Suppose that Ho (42a) is true. Then Seq-C- satisfies: PH, (r < c0) S a.
2. Suppose that Ho in (3a) is true. Further, suppose that Assumption is satisfied. Then Seq-C-I1 satisfies: PHo
00) 5
The above result follows from the fact the payoff functions underlying Seq-C-2ST (1) and Seq-C- IT (23) are valid under the more general null hypotheses (42a) and (43a) respectively. The rest of the proof of Corollary follows the same steps as that of Theorem and we omit the details. We conclude with an example which shows that Assumption 5 is necessary for the type error control.
Example Consider the following case when the null Hg (43a) is true, but Assumption is not satisfied. We show that Seq-C-IT fails to control type error (at any prespecified level a E (0. 1)). and for simplicity, focus on the payoff function based on the squared risk (23). Suppose that we observe a sequence of observations: ((x,, (2)) where (X,, Yi) (.,,, V+) and W., V iid suffices to show that there exists a sequence of predictors (9t) for which
Bern(1/2).
lim inf t-000
7.
Σ 18(((X=-1, Y2--1), (X2r, Y2:)) 0. i=1
(44)
If 44
holds, then using the same argument as in the proof of Theorem 2 one can then deduce that T 20) = Consider the following sequence of predictors (g:)
9t ge v) ((x- (2t })) (v (21 1)) A 1) V-1.
We have:
ge Y2x) = ((W2r + 1) (V2r + } A v
9e 0x 12--1) = (W2-1 - 1)) (V2-1 - 2)
90 (X2r, 121-1) (Wzr + 2)) (V2-1 2)
(x Y20) (W2r-1 1)) (V2r 1
Simple calculation shows that:
E [9x (X2r, Y2.)] = 11/16, E (x 1) = E [g (Xze, Yu-1)l = E (X2-11 (22) = 0 and hence, for all t 2 1, it holds that E [f7((2x211 Yz- 1), (Xze. Y2+)) 11/64 0. This in turn implies (44). and hence, we conclude that Seq-C-IT fails to control the type I error.
'Technically, a slightly weaker condition suffices - at odd f, the distribution can change arbitrarily, but at even f. either the distribution of X changes or that of Y changes but not both; however, this weaker condition is slightly less intuitive than the stated condition.
18

---

C.1
Synthetic Experiments
Under the alternative, the power of our test depends on the performance of classifier according to misclasiffiatioonssuuae risk. If the distribution drifts over time, then models updated via online gradient descent may retain predictive power. despite the present distribution drift. Of course, if the distribution shifts adversarially. the method will not have power, but neither will any other method. So the implicit goal to maintain type-1 error control under the null despite shifting distributions (beyond the i.i.d. assumption typically made the literature) while retaining power against reasonable (but not all) distribution drifts. To put this into context, we consider four settings:
such cases, our test will still have high power
1. Q (0, 1), i.e., the 2ST null is true;
2. P -V 1) and Q =V(00.5 1), i.e., the 2ST null is false;
3. Up to time 250, p()) ( (0, 1), but for > 251, we have p(t) N/ 1) and
((+) (0,5,, i.e., there is a distribution shift and the 2ST null is false;
4. Up to time = 250, p(t) = Q = (o 1), but for 251, p(t) = Q = NO.5, 1),
i.e., there is change in distribution yet the 2ST null is still true.
We use standard logistic regression model as an underlying predictor with weights updated via online gradient descent and monitor the tests until T 2000 observations. In Figure observe that our test controls the type-1 error whenever the 2ST null is true even there a shift distribution, and retains high power if the alternative is true.
Hn true, no shift
Hy false, shift
0.8
true, changepoint
Ho false, changepoint
Rejection Rate
0.6
0.05
0.4
0.2
8.0
1250
2000
Sample size
Figure 6: Average rejection rates for four settings: solid lines correspond to the standard i.i.d. setting and dashed lines correspond to the settings that involve distribution shift. Despite there being a shift distribution, our test that utilizes logistic regression learned via online gradient descent controls the type-1 I error under more general 2ST null hypothesis and has power under the alternative. Results are aggregated over 500 random sequences from the corresponding distributions.
D Proofs
D.I Auxiliary Results
Proposition (Ville's inequality [Ville 1939 ). Suppose that (Mi)zo a nonnegative supermartin-
gale process adapted to filtration (F,) ):200- Then, for any >> 0 it holds that:
E [Mo
1 M. 2 a) <
D.2 Supporting Lemmas
Lemma 6. Consider sequential two-sample testing setting (Definition Suppose that a predictor g E G satisfies E (Z, W)] 0, where f(z, w) wg(2).
19

---

(a) Consider the wealth process (22) based on f along with the ONS strategy for selecting betting fractions (Algorithm 7). Then we have the following lower bound on the growth rate of the wealth process:
log K.
1 (]]
lim inf
2
A ABIF(2
(45)
8-000
4
E (2, W)
(b) For Xa = arg (aggxxx----05003
E [log(1 1 + (2, W)),, it holds that:
(I [][2
E [[J(Z,W)
E
log(1 + x.f(2, - 3 E (F(Z,
(46)
2
Analogous result holds when the payoff functionn f(z, w)
sign [g(2)] is used instead.
Proof.
(a) Under the ONS betting strategy, for any sequence of outcomes (fe) ft E [-1,1].
it holds that (see the proof of Theorem in [Cutkosky and Orabona 2018 E
loAo) - log KG O log ΣS f
(ER)
(47)
where (Ao) is the wealth of any constant betting strategy Ao E 1-1/2, 1/2] and K, is the wealth corresponding to the ONS betting strategy. Hence, it follows that
log Kr log (e(\1a) C log
(48)
for some absolute constant > 0. Next, consider
E1 1i Si
1 vo
An
Ei=1 f?
We obtain:
log (Xo)
1
Σ
log(1 + +oJec
(a)
7 (Dofi \8.33
(49)
+ Si vo)
+ Si
A1
11)
i Σ .3
where in (a) we used that log(1 + x) 2 x - x² for x E 1-1/ From 48 it then follows that:
log
E [f(, W)] vo)
[[J(Z,
lim inf 1-000
2
E[S ^1)
4
(E [F]F(Z.)]]
E W)) ABIS(Z
=
which completes the proof of the first assertion of the lemma.
(b) Since log(1 + x) S x 3xx2/ /8 for any x E [-0.5, 0.5), we know that:
E [log (1 + X. E ).](Z,
(A.[(Z, w))²
8
max
(X-E(5(Z,W) W))
3X²
-B
Xel 0
20

---

The optimizer of the above is
41 [f(2, W)]
3E
[f(2
2
Hence, as long as E [f (3/8) (f(Z,w)) we have:
2 (B [f(2 W)1) -
E log (1 + x.f(Z,
(50)
3 IB (((Z))))²
If however, []] (3/8) W)) then we know that:
R [[(,WW)
E log (1 + A. (())
2
To bring it to convenient form, we multiply the upper bound in (50) by two and get the bound (46). which completes the proof of the second assertion the lemma.
D.3 Proofs for Section
2
Proposition 1.
Fix an arbitrary predictor g E G. The following claims hold m
For the misclassification risk, we have that:
sup
( Rmm()))) ( Rm(g)) VO (1 E [W sign [x(2]]] vo.
(9)
*E(0,1]
2. For the squared risk, we have that:
sup (1 - Rg(sg)) 2 E W. ( .E[0,1]
E Eg (g) (Z) ^1)
E g(
(10)
Further, d&(P, Q) if and only if there exists E G such that E [W g(Z) > 0.
Proof.
1. The first equality in (9) follows from two facts: (a) for any g E g and any E (0, 1). it holds that Rm (sg) Rm (g) (b) R. (0) 1/2. The second equality easily follows from the following fact: sign [a] 2 1/2 (a < 0}.
2. Consider an arbitrary predictor g E Let us consider all possible scenarios:
(a) E [W g(Z)) S O, then the RHS (10) is zero. For the LHS of 10 we have that:
sup (1 Rg (sg)) *E(0.1]
(2) 0,
so the bound 1T) holds. (b) Next, assume that E [W o(Z) 0, then it is easy to derive that:
84 arg max (1 (sg)) E I g(Z)
g (2) A1
(51)
<E[0.1]
A simple calculation shows that:
E W g(Z)]
- R=(9)))) 2 EEW. o(Z))
E [Z) ^1).
and hence, we conclude that the bound (10) holds.
V and A denote maximum and minimum respectively: b max(a, b), A min(a,b).
21

---

To establish the second part of the statement, note that (P. > 0 iff there is predictor g such that (g) For the squared risk. we have:
Rg(9) = 2I [W ( E [ (Z)]
(52)
and hence, (g) < 1 trivially implies that E (Wg((Z) > 0. The converse implication trivially follows from (TO). Hence, the result follows.
Theorem 1. The following claims hold:
1. Suppose that Ho in (1a) is true. Then the oracle sequential test based on either )r20
or (K1 )220 ever stops with probability at most o: Ho (T < 00) S a.
2. Suppose that H1 in 1b is true. Then:
(a) The growth rate of the oracle wealth process (Krr")e2 "e20 satisfies:
lim (7 log K?T 2 ( Rm (g.))² 1-300
(14)
If Rm (9+) < 1/2, then the test based on (KC,,.))) is consistent: Ph, (T < <00) =1 Further, the optimal growth rate achieved by XT in (33) satisfies:
E [Iog(1 + fZ
15 ( R (2.))² ( Ru (g.))) (15)
(b) The growth rate of the oracle wealth process (KT"")20 122 satisfies:
lim inf ( log K,)"") " E E[ (z)) 8-000
(16)
E I g. (2)) > O, then the test based on )(20 consistent: PH, (7 00)
1. Further, the optimal growth rate achieved by X3 in (13) satisfies:
E [log(1 fz W))] S 1 [W (x(2)
(17)
Proof.
1. We trivially have that the payoff functions 11a) and 11b are bounded: V(z, w) E
Zxf-1 1. }. it holds that fT w) E [-1, 1, 1] and f2 w) E -1, 1]. Further, under the null
Ho in [Ia). it trivially holds that EH, [ W.) F. = ER, [fe W,) [i 0,
where Fi-1 = o(( Wilhss--) Since ONS betting fractions (AONS) (21 are pre-
dictable, we conclude that the resulting wealth process is nonnegative martingale. The assertion the Theorem then follows directly from Ville's inequality (Proposition) 2 when
= 1/a.
2. Suppose that H1 in (1 is true. First, we prove the results for the lower bounds:
(a) Consider the wealth process based on the misclassification risk (KCT)))10- Note that for all 1:
E (Z, W.)] = - R.n (o+)) (Z,,)) =
Since IE I (Z,, Wil [0. we also have (LE [fTH Wo))) S EL Wo)l From the first part of Lemma it follows that:
log K
[ (Z. WoI) = (1 Rm (o.)
lim inf
4
From the second part of Lemma and (46) in particular, follows that:
16
( Ri((o.) )) ) 2
E oog 1 1. (Z.W))
3
The first term the above smaller or equal than the second one whenever Rm (ga) 2 5/ 16. We conclude that the assertion of the theorem is true.
22

---

(b) Next, we consider the wealth process based on the squared error: (KT)))20 )220 Note that:
E [ Wi] E [W 9, (2)),
E (J5 wo)) E [2)(
and hence from Lemma 6 it follows that:
lim inf 6-000
log K.; a.s.
1
(E [W (Z)))
A E IW g. g.
(53)
4
E [Z)
In the above, we assume that the following case not possible: g. gz(Z) 3.3. (for such I+. the corresponding expected margin and the growth rate of the resulting wealth process are clearly zero, and will still be highlighted in our resulting bound), Next, note that since D. E arg min geg Rg (g), we have that:
1 Rs (g.)
sup (1 -1-6 Rs (sg.)),
.E(0.]]
meaning that g- can not be improved by scaling with 8 < 1. From Proposition and 5T in particular, it follows that:
E [W (2)]
1,
(54)
E [2)(2)
and hence, the bound 55 reduces
log K
E W (z)
lim inf
1-000
4
From the second part of Lemma it follows that:
4 (E W g- (Z))) E log (1 + X,f((z, W))]
E [ (z)]
A
(55)
3 E (Z))
2
Next, we use that Js satisfies (54). which implies that the second term in is smaller, and hence,
E E (Z)]
log + x.f.(z, W))] S
2
which concludes the proof of the second part of the theorem.
Corollary 1. Consider an arbitrary g E 9 with nonnegative expected margin: E [W Then the growth rate of the corresponding wealth process (KC)) satisfies:
g(Z)] 2
lim inf (t log log 600
8.6. 2
4 sup (1 R. (8g)) IW o(2))))
(18a)
=E(0.1]
> (B =(Z)))²
(18b)
and the optimal growth rate achieved by X; 13
satisfies:
E [log(1 1 + X (Z, W))] <
sup
(1 Rs (sg)) (1 E [W g(Z)))
(19)
xE(o.1]
Proof. Following the same argument as that of the proof of Theorem I we can deduce that:
lim
log KC
a.s.
(E [W g(Z)))
E [g2) AE IW 9(Z))
(56)
Hence, it suffices argue that the lower bound (56) is equivalent to (8a). Without loss of generality, we can assume that E [ g{))] 2 0, and further, the two lower bounds are equal if E W g(
Hence, consider the when E [W o( [2) > 0. First, let consider the case when
W (())
(57)
E [Z)]
23

---

Using 51. we get that:
[E I o())))
sup sE[0,]]
Rg (sg))
(58)
E. [Z)]
and hence, two bounds coincide. For the upper bound (19). we use Lemma and the upper bound (46) in particular. Note that the first term in 46) is less than the second term whenever
E W g(Z)
3
<1
[0(2))
8
However, in this regime we also know that 58) holds, and hence the two bounds coincide. This completes the proof.
Theorem 2. The following claims hold for Seq-C-2ST (Algorithm 2
1. If Ho in Ia is true, the test stops with probability at most Pho (T < <00) S
2. Suppose that H1
(Tb is true. Then:
(a) Under Assumption 7
the test with the payoff 22a consistent: Pnt, (T x0)
(b) Under Assumption
2
the test with the payoff 22b is consistent: PH, (T < 00) 1.
Proof.
1. We trivially have that the payoff functions 22a and (22b) are bounded: Vt and V(2, w) Z x {-1,1}, it holds that (2, w) [-1, and fi w) E 1-1.]] Further, under the null Ho in (Ta), it trivially holds that En, [/T Zz, We) F--1] EH (Z, Wt) [.-1]
where Fi-1 (((Zi, Wo)lgg-1). Since ONS betting fractions (AONs) 121 are predictable, we conclude that the resulting wealth process is nonnegative martingale. The assertion of the Theorem then follows directly from Ville's inequality (Proposition when 1/a.
2. Note that if ONS strategy for selecting betting fractions deployed, then (49 implies that the tests will be consistent as long as
lim inf Σ 1=1
a.s. fx
> 0,
(59)
800
W;) and f, = (Z, W:) for the payoffs based on the where for 2 1, (2, misclassification and the squared risks respectively.
(a) Recall that
fTh (Z, W,) = W; sign (Z,)),
and Assumption T states that:
lim sup
Σ 1 ( sign 19. (2+) < <
1 2
t-100
i=1
Since <0= sign (zt) /2, we get that:
1 Σ
(
W sign [gs 7+))
a.s. 1
lim sup t-+00
2
i=1
which, after rearranging and multiplying by two, implies that:
lim inf 1-000
7
Σ
W, - sign [g: (2.) a.s. > 0.
1=1
Hence, a sufficient condition for consistency true.
(59 holds, and we conclude that the result
24

---

(b) Recall that
fZ W;) W. ...)).
and Assumption 2
states that:
lim sup 1-000
(g:) W.) <
which is equivalent to
lim sup
(Z,) 2W, ge (Z)))) < 0.
t-5000
is easy to see that the above, in turn, implies that:
lim inf (-400
Σ W, (V,)) 8.5 > 0.
1=1
Hence, sufficient condition for consistency true.
(59) holds, and conclude that the result
D.4 Proofs for Appendix
Theorem 3. The following claims hold for the oracle sequential regression-based based IT based on (KT"") 120'
Suppose that Ho in (26 true. Then the test ever stops with probability at most a: PH, (T < oo) S
2. Suppose that H1 in 26bb is true. Further, suppose that: E (X), 0. Then the test consistent: PH, (T 00) =
Proof.
1. We trivially have that the payoff function 27 is bounded: V(I, w) E x (-1, 1}. it holds that fx y. w) [-1, Further, under the null Hg in (26a). trivially holds that En, (X, Y,,WW, W)) Fi-1l = 0, where F a(((X, Y, W;) W.)hssr-) Since
ONS betting fractions (AONS) (21 are predictable, we conclude that the resulting wealth process is nonnegative martingale. The assertion of the Theorem then follows directly from Ville's inequality (Proposition
2
when 1/a.
2. Note that if ONS strategy for selecting betting fractions is deployed, then (49 implies that the tests will consistent as long as
lim inf " f.(x,, Y,, W.) as 0. t1000
(60)
Note that:
f( W.)
tanh W.llg.(X.)) Y.) 3 E [tanh (s. W (X), Y))].
Note that for any x E R tanh(r)) 2 x 1/4 max 3 03. Hence, for any > 0, it holds that:
E [aanh (s WX(g,(X), 2 sE (V)(,,()),x
[max (sa WX)(,, 0)]
3
sIE [WE (X)),
E (I),, max (W. 03]
sIE (V((
E [1 + W) (X),
(61)
25

---

where we used that max { 0] (W + 1)/2 since W E {-1,1). Maximizing the RHS of (61) over s yields s, defined in (8a Hence,
E [tanh (s. (Ve(g, s. (x)
[1 W) ())((e),(x)))))))))
2
(X), -
(1 W) (e(x,
s. (X), -
28 E (X),
X)
3
Hence, we conclude that the oracle regression-basee IT is consistent since the sufficient condition 62 holds.
Theorem 4. The following claims hold for the proxy sequential regression-based IT' (Algorithm
1. Suppose that Hg in (26a)
true. Then the test ever stops with probability at most a::
P (T < 00) S
2. Suppose that H1 in 26bb is true, Further, suppose that Assumptions and are satisfied. Then the test is consistent: PH, (7 < <0) 1.
Proof.
1. We trivially have that the payoff function (29) is bounded: V(r, y. w) E x V x
[1,, it holds that ff y, w) E [-,,1]. Further, under the null Hg in (26a). trivially holds that En, (X,, Yi, W) Fi-1]= = 0, where Fi-1 o{ Y, W;) W))s)--)) Since ONS betting fractions (AONS),22 1>1 are predictable, we conclude that the resulting wealth process is nonnegative martingale. The assertion of the Theorem then follows directly from Ville's inequality (Proposition
2
with 1/a.
2. Note that if ONS strategy for selecting betting fractions is deployed, then 449 implies that the tests will be consistent as long as
1-000 7 Σ Yi W.) &.8 0.
lim inminn
(62)
(a) Step 1. Consider a predictable sequence of scaling factors (st)121, defined in (30a).
and the corresponding sequences (#1)21 and (M))211 defined in (30b) and (30c) respectively. For t 2 let F, == o o{((,, Y,, W.)),,)). Since the losses are bounded,
we have that:
(W; - - (.),
[W ((g(Xx; YJ) FF-11)
is bounded martingale difference sequence (BMDS). By the Strong Law of Large Numbers for BMDS, it follows that:
(W, - ((g(Xxgg)),,,,)X)))) -[W+)(((Xx00) F--I) $ 0.
Since ((Xe, Yr, W2))r21 is sequence of i.i.d. observations, we can write
E B ((g((
|
F B[w-
26

---

where (X,Y,W) 1T (01) 0.. Using Assumption
3 we get that:
E [ (()(X; 0,] w ()(( 0-]
<
sup zEd vey
[[]]((; 0.). -
(63)
Le sup sEx
19(2; 0.) g(z: 0.)l
La Li 110, 0-11 # 0,
since |10, 10,-00 -+11 - 0 by Assumption E [ 0)), 0.]. Similar argument can be used to show that n.g. (1 + W) (e(g(X;;,) 0.), 8))² 0z]. and hence,
particular, this implies that it =
2E [W 0.1
E W) (e(((X;))) Y))3 0.]
8x-
(64)
Note that 8, is a random variable which positive (almost surely) by Assumption 4
(b) Step 2. Recall that for any x E R tanh(x)) 2 x max { (=²,0) and that max {W, 0} = (W + 1)/2 since W E 11. We have:
fI,,, Y. W.)
tanh (s: (.)()(X(:88),333))
8: W. (()((.;))))) 6 (L+ (L()(X;;)),, 0,,, x3)33
Note that 0; and s; are -masuuuurrab (see Step I for the definition of F; Under minor technical assumption that (st)121 is sequence of bounded scaling factors (the lower bound is trivially zero and the upper bound also holds if 1 are bounded away from almost surely which is reasonable given the definition of vt), analogous argument regarding a BMDS in Step to deduce that:
use
lim inf
Y.
lim inf t-x00
Σ
8; E [W l(o
52 [ (
(((((x;))) 10:]
(65)
Using argument analogous to 63
we can show that:
+ W) (L(g(X; 0,), 3 0.] " ())(((((X))))) e.]
(66)
Combining 63
64)
and (66) we deduce that
8: E [W ((((X; 0,]
E
[1 W) (((((()));0) 0.]
a 8, E WW ((g([: Y) 0.)
[1 W) (f(g(X;; YY)² e.]
6
27

---

28.
E W. (x)) 0.].
3
Hence, from
655 it follows that:
Σ
Y, WT) 2 28.
lim imminf (-20
E E ((g(X;0,), 1 0,],
3
where the RHS is a random variable which is positive almost surely. Hence, a sufficient condition for consistency (62) holds which concludes the proof.
D.5 Proofs for Appendix B
Two-Sample Testing with Unbalanced Classes. Note that (g(z) 2n(2) 1):
(1- (1) 1 (n(2,) (W/=1) (1 ((2))) (WW=] -1(
(T) [[W==) (1 π)) 1-1 1-1(
[+olZe)
I[W,=1}
1-n(Ze)
1-1(W;=1)
2
(1-A)) -- 1+
(T) 1-)
(1+ g(()(()) (1)) (W]=1)
(1 g( (1) 1-W=11
= (1-1)) 1+
2
(T) ([/=1) (1 TT) [W,
d
1+ (zg(Z))
(1-A) 1+
(T) (W] (1 (1-T) -T) 1- [Wi=]]
2
= (1 - (1-A) .
1+
1 W2TT 1) (1 + Wzg(2,)
2
d
(1 (1- 1+
(1+ + Wig(Z.)
1 W2(2T 1) -(2T 1))
W, (g(Z,)
1
1 W (2T - 1)
Payoff for the Case of Unbalanced Classes (known T). To see that the payoff function 37 is lower bounded by negative one, note that:
(z, 1) 9c(2) (2iT 2
-1 (2T - 1) -1,
2T
2T
fl -1) -9((2) + (2TT - 1)
-1 (2T - 11
-1
2(1 - Tt)
2(1 - π)
To see that such payoff is fair, note that:
EHo (5, Wx) Fr-1l = Ep ge(Zi) - (2iT 1))
9r(2,) - -2x -1)
- EQQ (1 (1-
2(1 m Fe_ = 0,
2T
where F ((Zz,
Theorem 5. Suppose that Ho in (35a) is true. Then (KF) is a nonnegative supermartingale adapted to (Fi)ezo- Hence, the sequential 2ST based on (Kt))zo satisfies: PHo (7 < oo) S a.
Proof. First, we show that (ACH) )22 is a nonnegative supermartingale. For any I. 2 1, the wealth K,-1 is multiplied at round t by
I T (1 + W.g. (Zt)) Ih (1 + W2 1))
1+ Aeft (((Zo(- WoG- WatDD (e.))s = (1- 1+
28

---

Since A E 10, 0.5), we conclude that the process (KC)) is nonnegative. Next, note that since कe is the MLE of x computed from a t-th minibatch, it follows that:
be I=M--D+ (1 Waye(
1 1 dele (1(20(-11+1 Waa-1)+1) (e (E.1.....)) )
s S 11 A
Th= 1)+1 (1 + W2(2T 1))
1 Wage(Zi)
= -1 Xo) 1+
II
1+ W2(T -
b=(111))+1
Recall that Fi-1 =0 (12,, Wi W) It suffices show that if Ho true, then
( 1
( W.o. Fi-1 1+ W2 - -1)
Eho
II
=1
(=1+11))+1
Note that the individual terms in the above product are independent conditional on Ft-1. Hence,
bt
( [1+ 1+
1 Waye (zi)
bi II
+ (Z.)
EH
II
Fr
EHo 1+ W2(2 -1)
Ft-1
1 W2(2 -
b= 1)+1
b=
For any
E (b(l 1)+1) 11 11...,,,1y holds that:
1 Wige(Zi)
1 1 9e
- (z(
E Ho
|i--1
EHO
-T)
1 (2x - Fi-1
1 + W2(2T 1)
1 (2T - -1
1 + (Z,)
+ 1 - 91 (Zi)
EHo
Fi-1
1.
Hence, we conclude that (KC)) 120 a nonnegative supermartingale adapted to (Fe) The time- uniform type error control of the resulting test then follows from Ville's inequality (Proposition 2
E
Additional Experiments and Details
E.1
Modeling Details
CNN Architecture and Training. We use CNN with 4 convolutional layers (kernel size is taken
be and 16. 32, 32, 64 filters respectively. Further, each convolutional layer is followed by max-pooling layer (2 x 2). After flattening, those layers are followed by I fully connected layer with 128 neurons. Dropout (p 0.5) and early stopping (with patience equal to ten epochs and 20% of data used in the validation set) is used for regularization. ReLU activation functions are used in each layer. Adam optimizer used for training the network. We start training after processing twenty observations, and update the model parameters after processing every next ten observations. Maximum number of epochs set to 25 for each training iteration. The batch size set to 32.
Single-stream Sequential Kernelized 2ST. The construction of this test is the extension of 2ST Shekhar and Ramdas 2023 to the case when each round an observation only from a single distribution (P or Q) is revealed. Let G denote an RKHS with positive-definit kernel i and canonical feature map (p()) defined on Z. Recall that instances from P as labeled as +1 and instances from Q are labeled as -1 (characterized by W). The mean embeddings of P and Q are then defined as
Σ
((Z)) ( = 1 +1},
(t)
1=1
1
Σ
((Z,) 1 1 -1).
N_(t)
1=1
29

---

where N+ function is
| S :: W; = +1| and N-(t)= = list: W = -1/. The corresponding payoff
fi W2+1)= We+1 (c(Z++1),
9: = Pp (1) (1) where
P4
up PQ (1) l1a
To make the test computationally efficient, is critical update the normalization constant efficiently, Suppose that at round t + 1, an instance from P is observed. In this case, uQ (f+1) = PQ Note that:
t+1
((+1) up
Σ
(Z,) 1(,,=
(1++1)
(2,) 1 = =11
(+()) + 1=1
N+()) + (0((++1)
(t) + Σ ((z)) 1 (W,, = +1)
1=
(t) (1)
(t) +1 (f((++1)
(t) +1 1
Hence, we have:
(1+1) ((+1) 2 pp
(1) 1
110 9
pip
| /
2 pp (
/g + |
9
In particular,
pp 1 = (+) +1 ((2+1)) + (+ + up .Ha
(1+1)
N_(1)
N+(1) +1 (p(Zet1)) (1)) + N4(1)+1 +1 (p (1p:Po)1
N+
Note that:
(x (p(Z)+1) 1 N- (t)
Σ k(Z+1, Z,) 1 (W; -1).
;=1
Next, we assume for simplicity that k( x)) 1, Var which holds RBF kernel. Observe that:
1++1
(1+1) ((+1))
up PP
9
9
(t) (1) + (t) + 1)² (p(Ze+1). (1)
(1)) (N+ + 1)²
By caching intermediate results, we can compute the normalization constant using linear in number of kernel evaluations. We start betting once at least one instance is observed from both P and Q. For simulations, we use RBF kernel and the median heuristic with first 20 instances compute the kernel hyperparameter.
MLP Training Scheme We begin training after processing twenty datapoints from Pxy which gives a training dataset with 40 datapoints (due to randomization). When updating a model, we use previous parameters as initialization. We use the following update scheme: we start after next YAn 10 datapoints from Pxy are observed. Once nn becomes less than 1 % of the size of the existing training dataset, we increase it by ten, that is, n, = n + 10. When we fit the model, we set the maximum number of epochs be 25 and use early stopping with patience of epochs.
30

---

Kernel Hyperparameters for Synthetic Experiments. For SKIT, we use RBF kemels::
k(I, exp (-xx |z 22'1) (y,,3") exp (-Ay 11 - v'1l.)
For simulations on synthetic data, we take kernel hyperparameters be inversely proportional the second moment of the underlying variables (the median heuristic yields similar results):
xx
Xy
2B
|
x
2B I
Y
1. Spherical model. By symmetry, we have: Px
Pr, and hence we take Ax = xy. We have
- -() = 2E x d
2. HTDD model. By symmetry, we have: Px = Py, and hence we take Xx = xy. We have
2T
E [ = 21E [x]]
3
3. Sparse signal model. We have
E || x'
[
21E
| 4d,
d
E || Y'
[/]
21
2tr( + + = 2(d Σ 89).
/=1
4. Gaussian model. We have
(X x11 2E
x2| 2,
E [Y - Y0 = 2E Y? = 2(1+
Ridge Regression. We use ridge regression as an underlying predictive model: 9r (x) = 3/ +
where the coefficients are obtained by solving:
2(t-1)
(00 ((0)) arg min
Σ
(Y: X,8 - B0)² XB8.
30.3h
Let I' diag(0, 1). Let X,-1 1)x1 be such that (Xę-1); (1, [1,2(t 1)]. Finally, let Y--1 vector of responses:
(Yt-1); Y,, i [1,2(t -1)] Then:
8(0) arg min Y - X + 1 (X AT) (XTIY.-1).
E.2 Additional Experiments for Seq-C-IT
we present average stopping times for ITs under the synthetic settings from Section 3 We confirm that all tests adapt to the complexity of a problem at hand, stopping earlier on easy tasks and later on harder ones. We also consider two additional synthetic examples where Seq-C-IT' outperforms kernelized approach:
In Figure 7
1. Sparse signal model. Let (Xt)e21 and (E1)121 be two independent sequences of standard Gaussian random vectors Rd: Xt, ltd (O, L,), t 2 We take
(X, Y2) = (X,, B,X, + =t),
where B, diag(B),... 3a) and only of (8, are nonzero being sampled from Uni,([-0.5, 0.5]). We consider d E ( 50).
31

---

0300
(HI-P)
4000
4000
Average Stopping Time
JP
SKIT
2000
(BSL-))
1000
1300
(2-20))
17.
10
(a) Spherical model.
(b) HTDD model.
Figure Stopping times of ITs synthetic data from Section Subplot (a) shows that SKIT is only marginally better than Seq-C-IT (MLP) due to slightly better sample efficiency under the spherical model (no localized dependence). Under the structured HTDD model, SKIT is inferior Seq-C-ITs.
)221, (e( )12) denote sequences of ran- 2. Nested circles model. Let (I4))21, (Or) (e(")))),
dom variables where L jid Unif(1..... for prespecified I N, O iid Unif([0, 2m)). and et ,8g (O, (1/4)9). For 2 1, we take
(1) (2) iid
(X,, Y2) = (Le cos(O)) + +e(") L. + +((
(67)
We consider (1,...,10)) 10).
In Figure 8 we show that Seq-C Scq-C-ITs significantly outperform SKIT under these models. We note that the degrading performance of kernel-bass tests under the nested circles model (67) has been also observed in earlier works [Berrett and Samworth 2019 Podkopaev et al. 2023
E.3 Sequential vs Batch 2STs
The role sequential tests to complement existing batch tests and not replace those. Generally, one is ready to commit to a particular sample size, it is better to refer to batch tests. To understand the loss power, we conducted an experiment where we take / = (O, 1). Q = _V, 1) and use k-NN predictor underlying predictor. As point out in Remark [ if an analyst stops the experiment early, i.c., before the wealth exceeds 1/a,, there is one modification that allows using non-exhausted type-I error budget to strictly improve power [Ramdas and Manole 2023): may different threshold for rejecting the null, namely U/a, where U is an independently drawn (stochastically larger than) uniform random variable on [0, 1).
We set the sample size to 1500 and compared three tests: batch (with half of the data used for training and half for inference). Seq-C-2SS C-2TT (our sequential test), and Seq-C-2ST Randomization (as per Remark [T.. Figure 9 we observe that the batch test has only slightly higher power than our sequential one when the sample size is specified beforehand. Yet in cases where the power is less than one using sequential test allows collecting more data to improve it, but with batch test, nothing can be done since the type-1 emor budget is fully exhausted.
32

---

SKIT (MLPy:
SKIT Sep-C-1 (MLP))
Power Time -0000
17
Average Stopping Time
17
12
2000
2000
1000
0.0
(a) Sparse signal model.
(b) Sparse signal model.
S-y-E-IT (MI P3
Power at Time I 5000
0.5
SKIT See-C-IT (MLP):
0.6
Stopping
ff
Sou.
f:
11
2
10
(c) Nested circles model.
(d) Nested circles model.
Figure 8: Rejection rates (left column) and average stopping times (right column) of sequential IT's for synthetic datasets from Appendix E.2
In both cases, SKIT is inferior to Seq-C-ITs..
Seq C:25T Randemization
Seq-C-25T
0.8
Batch
(UUS
Rejection Rate
8.6
0.4
0.2
8.
Figure 9: Comparison between the batch and sequential 2STs on Gaussian data when the sample size is set beforehand to 1500. First, invoking randomization improves the power of our sequential test across all settings. Second, batch 2ST has only slightly higher power across many settings. Note that the power of Ceq-C-2ST can be easily improved after collecting bit more data, yet this is not allowed for the batch test.
33


Reviews:
[{"review_id": "kCIrcmcWen", "reviewer": "Reviewer_ryYs", "summary": "Kernel-based nonparametric two sample and independence tests performance can break down in the cases of complex data like images. The paper proposes sequential two sample and independence tests based on the misclassification rate. \n\nCompared to kernel-based tests, the proposed tests, which use CNNs, reject the null hypothesis faster than sequential kernel-based two sample and independence tests on image data while still controlling the type I error rate. The power comparison between the two approaches is somewhat inconclusive. ", "questions": "Optimizing the bandwidths is one drawback of kernel tests - how much hyperparameter tuning was required to achieve the performance reported?\n\nHave the authors compared the approach to kernel-based tests on simpler data?\n\nHow do the runtimes compare to kernel-based tests?", "limitations": "Could be expanded", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The proposed approach is quite general and well suited to complex data like images that can be modeled with DNNs. \n\nThe work is well supported theoretically.\n\nThe empirical results argue favorably for the approach. \n\nThe paper is well written.", "weaknesses": "Some discussion of the practical computational complexity of the approach compared to kernel based tests would improve the paper.\n\nAn empirical comparison to kernel-based tests on simpler data would highlight the advantages/disadvantages of each approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback on the paper. Below, we address in detail issues that have been raised in the review.\n\n> Some discussion of the practical computational complexity of the approach compared to kernel-based tests would improve the paper. How do the runtimes compare?\n\nBelow, we assume that the tests are deployed for $d$-dimensional data. At time $T$, the total accumulated computation for the kernelized test is $O(dT^2)$. For our test, the answer depends on the chosen classifier and learning algorithm. For example, using logistic regression in combination with gradient descent for updating model parameters results in cheap updates and payoff evaluation (both are $O(d)$ at each round, and hence the total accumulated computation at time $T$ is $O(dT)$). For $k$-NN classifier, no parameters have to be updated, yet evaluating payoffs becomes more expensive with a growing sample size, resulting in the total accumulated computation of $O(k dT^2)$ at time $T$. For more complex models like neural nets, runtime depends on the chosen architecture: the total accumulated computation at time $T$ is $O((cB+F)T)$, where $F$ and $B$ are the costs of forward-propagation and back-propagation steps respectively and $c$ is the number of back-propagation steps applied after processing the next point (the exact cost depends on the architecture). We have added a paragraph about the runtime comparison to the paper. \n    \n> Empirical comparison to kernel tests on simpler data would highlight the advantages/disadvantages of each approach.\n\nOverall, our empirical findings illustrate that neither of the approaches (kernel-based vs predictive) dominates the other and that our new approaches are surprisingly versatile across settings. To elaborate, some additional simulations that highlight the advantages/disadvantages of kernel approaches versus our new methods are already in Appendix E. While it may seem a natural guess that kernel methods would perform better for ``simpler'' unstructured data, our results in Appendix E suggest that this is not always the case. If there is any particular data distribution you would like us to add, we would be happy to do so. \n\n    \n> Optimizing the bandwidths is one drawback of kernel tests - how much hyperparameter tuning was required to achieve the performance reported?\n\nFor simulations on synthetic data, we utilized the knowledge of the underlying distributions to estimate kernel hyperparameters, taking those to be inversely proportional to the second moment of the random variables (details are provided in Appendix E). For simulations on real data, we utilized the median heuristic (standard practice) to estimate these hyperparameters. For our method, we applied minimal hyperparameter tuning: (a) for MLPs and CNNs, we committed to a single architecture throughout the experiments and used early stopping for regularization, (b) for experiments with $k$-NN classifier, there are no hyperparameters to be tuned except for the number of neighbors, and we used the square root rule (standard practice). In fact, one important advantage of our sequential test is that various design choices (increasing/decreasing regularization, changing neural network architecture) can also be updated on-the-fly."}, {"review_id": "IulrkKomRE", "reviewer": "Reviewer_ssj4", "summary": "The work considered the problems of sequential nonparametric two-sample and independence\ntesting. The researchers propose a novel approach, which overcomes the issues of kernel-based testing, such as finding an appropriate kernel for high-dimensional or structured data like text and images. The authors empirically demonstrate the superiority of their tests over\nkernel-based methods in structured settings. Furthermore, the tests remain valid and powerful even when the data distribution drifts over time.", "questions": "1. Does the proposed method have any potential limitations on data-dependency due to the use of nonparametric techniques?\n\n2. Could the authors clarify how your method can retain its power when data distribution drifts over time?\n\n3. It is not clear how the proposed techniques can be scalable to larger datasets?", "limitations": "The authors do not mention the limitations of this work.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The authors propose a prediction-based betting strategies to help alleviate problems associated with kernel selection and adaptability with high-dimensional or structured data.\n\n2. The authors provide compelling empirical evidence that their method outperforms existing kernel-based tests, especially in the context of structured settings.\n\n3. The author provides the theoretical analysis about the properties of the proposed method.", "weaknesses": "1. The authors should provide more technical details about the principle of testing by betting strategies. This is the key concepts in the paper but the author does not elaborate it too much in the paper.\n\n2. The paper provides a high-level overview of the research making it challenging for general readers to comprehend.\n\n3. The presentation is poor is a way mixed with methodology, theory, and numerical study in a single section (e.g. Section 2).\n\n4. It is uncommon that one paper focused on two testings: the two-sample test and the independence test. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback on the paper. Below, we address in detail issues that have been raised in the review.\n\n> ...more technical details about the principle of testing by betting strategies...key concept in the paper but the author does not elaborate it too much in the paper...\n\nWe have added more technical details (e.g., clarifying that under the null hypothesis, the resulting wealth process is a nonnegative martingale starting at 1, which is the key to invoking Ville's inequality to justify the type-1 error control) as well as a more intuitive explanation regarding the principle of testing by betting to the revision.\n\n> A high-level overview of the research makes it challenging for general readers to comprehend the paper.\n\nTo improve the comprehension for general readers, we made the following updates in the revision: (a) a more detailed explanation of the principle of testing by betting (improving on both technical and intuitive sides), (b) a more comprehensive review of the most closely related works (making it easier to disseminate the contributions of our work).\n\n> The presentation is poor...mixed methodology, theory, and numerical study in a single section (e.g. Section 2).\n\nTo improve the presentation of the paper, we have separated experiments from the methods and theory in the revision.\n\n> Uncommon that one paper focuses on two-sample and independence testing\n\nWe kindly disagree with the reviewer that this point represents a weakness of our paper. While it is less common for a single paper to consider both problems, the two are closely related: an algorithm for one can be used for the other and vice versa (i.e., each problem reduces to the other, but this reduction may not be the optimal way to solve the problems). In our paper, we use the connection between the two problems explicitly: we design and evaluate sequential predictive tests for both settings.\n\n> Any potential limitations of the method on data dependency due to the use of nonparametric techniques?\n\nWe do not see any limitations due to the nonparametric aspect currently, but perhaps we have not fully understood what the reviewer may be hinting at.\n\n> Clarify how the method can retain its power when data distribution drifts over time?\n\nUnder the alternative, the power of our test depends on the performance of a classifier according to misclassification/squared risk. If the distribution drifts over time, then models updated via online gradient descent may retain their predictive power. In such cases, our test will still have high power despite the present distribution drift. Of course, if the distribution shifts adversarially, the method will not have power, but neither will any other method. So the implicit goal is to maintain type-1 error control under the null despite shifting distributions (beyond the iid assumption typically made in the literature) while retaining power against reasonable (but not all) distribution drifts.\n\nTo put this into context, we conducted the following experiment (the results have also been added to the revision) where we consider four settings: \n\n(a) $P=Q= \\mathcal{N}(0,1)$, i.e., the 2ST null is true,\n\n(b) $P= \\mathcal{N}(0,1)$ and $Q= \\mathcal{N}(0.5,1)$, i.e., the 2ST null is false,\n\n(c) up to time $t=250$, $P^{(t)}=Q^{(t)}= \\mathcal{N}(0,1)$, but for $t > 251$, we have $P^{(t)}= \\mathcal{N}(0,1)$ and $Q^{(t)}= \\mathcal{N}(0.5,1)$, i.e., there is a distribution shift and the 2ST null is false,\n\n(d) up to time $t=250$, $P^{(t)}=Q^{(t)}= \\mathcal{N}(0,1)$,  but for $t > 251$, $P^{(t)}=Q^{(t)}= \\mathcal{N}(0.5,1)$, i.e., there is a change in distribution yet the 2ST null is still true.\n\nIn all settings, we monitor the tests until $T=2000$ observations. We use a standard logistic regression model as an underlying predictor with weights updated via online gradient descent. We have uploaded the figure with the respective rejection rates to the allowed PDF file. In a nutshell, our test controls the type-1 error whenever the 2ST null is true even if there is a shift in distribution, and retains high power if the alternative is true.\n\n> It is not clear how the proposed techniques can be scalable to larger datasets.\n\nThe main computational burden of our test lies on a selected classifier and learning algorithm. The data are processed one at a time in a sequential fashion, so it is only the per-point update cost that is critical. Hence, for many models trained online, using versions of stochastic gradient descent, like neural nets, our test will scale perfectly well to larger datasets. In fact, one of the advantages of our test over the batch tests (which would require thinking about the sample size in advance) is that our test adapts to the complexity of a problem at hand. Hence, if the null is false, our test may stop after processing a few hundred observations, whereas its batch counterpart will require training using an unnecessarily large sample.\n"}, {"review_id": "RcTnxGwudV", "reviewer": "Reviewer_FPjp", "summary": "This paper proposes two sequential predictive two-sample tests based on betting, one is constructed by the payoff function $W\\cdot \\mathrm{sign}[g(Z)]$ for the misclassification risk, and the other is by the payoff function  $W\\cdot g(Z)$ for the squared risk.  The limiting growth rate and the expected growth rate of both tests for an optimal $g^*\\in G$ are given, and additionally, the same quantities of the squared-risk based test for an arbitrary $g\\in G$ are given. ", "questions": "1. Why $\\lambda$ is restricted to $[0, 1]$ instead of $[-1, 1]$. I can imagine a case where the payoff is negative, then using negative $\\lambda$ would help increase the wealth in betting. \n\n2. Is fitting the betting framework into the coin flip case the reason why the payoff functions are restricted to $[-1,1]$?\n\n3. Why the ONS in algorithm 1 is different from the one in  (Cutkosky and Orabona, 2018) work and  (Shubhanshu Shekhar and Aaditya Ramdas, 2021), e.g., the update of $z_t$ and $\\lambda_{t+1}^{ONS}$.", "limitations": "Please see the weakness section.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality\\\nThe paper proposes and thoroughly analyzes the sequential predictive two-sample tests; to the best of my knowledge, the proposed tests and the theoretical results are new.   \n\nQuality\\\nThe theoretical result is decent, which gives a growth rate comparison for the test based on the misclassification and the test based on the squared risk. \n\nClarity\\\nThe paper overall presents well.\n\nSignificance\\\nThe paper fills the blank that there is no formal construction of a classifier two-sample test using the betting framework.", "weaknesses": "1. The variance of the growth rate is not given and it is actually also important in the derivation of the testing power. \n\n2. The expected growth rate is a result of optimal $\\lambda$ instead of an arbitrary one. \n\n3. The comparison with the likelihood ratio test (Alix Lhéritier, 2018) is missing in the real-data experiment. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback on the paper. Below, we address in detail issues that have been raised in the review.\n\n> Variance of the growth rate is not given ... it is actually important in the derivation of the testing power.\n\nWe kindly disagree with the reviewer regarding this claim. To establish consistency of our test, it suffices to show that the growth rate of the wealth process (expected log wealth) is positive which we do: we show that the growth rate is lower bounded by a term proportional to the deviation of the risk of the limiting predictor from that of a naive predictor. Hence, as long as it is possible to learn a predictor with non-trivial prediction risk, our test is guaranteed to be consistent.\n\n> Expected growth rate is a result of optimal $\\lambda$ instead of an arbitrary one.\n\nWe kindly disagree with the reviewer regarding this claim. The lower bounds on the growth rate in Theorem 1 correspond to the case when the betting fractions are selected via the ONS strategy. The upper bounds indeed correspond to the optimal/oracle betting fraction $\\lambda_\\star$, and those are meant to quantify the best possible growth rate, and thus also show that the growth rate of ONS matches that of the oracle test. In summary, an arbitrary $\\lambda$ would not work with our test: instead, we smartly set $\\lambda_t$ online using ONS and the growth rate that this strategy achieves is at least (i.e. lower bounded by) that of the oracle $\\lambda^*$ (which is unknown to us).\n\n> Comparison with the LR test (Alix Lhéritier, 2018) is missing in the real-data experiment.\n\nAs we show through experiments, our predictive test (with CNNs) outperforms the one developed in [1] on image data. We omitted the comparison to the test of Lhéritier and Cazals [2019] since it has already been shown to be much inferior to the test developed in [1], specifically on multivariate data with localized differences between two distributions of interest (similar to the differences in our real data experiments). We have clarified that point in the revision.\n\n[1] ``Nonparametric Two-Sample Testing by Betting'', Shekhar and Ramdas, IEEE Transactions on Information Theory (to appear), 2023.\n\n> Why $\\lambda$ is restricted to $[0,1]$ instead of $[-1,1]$. I can imagine a case where the payoff is negative, then using negative $\\lambda$ would help increase the wealth in betting.\n\nThanks for the great question! Technically, using the range $[-1,1]$ instead of $[0,1]$ is allowed, and none of the theoretical statements in our paper get affected. When ONS is used for selecting betting fractions, this translates into truncating $\\lambda_t$ at -1/2 instead of 0. We tried both in our early experiments and did not observe any major differences in power, but truncating at 0 resulted in a bit more stable wealth processes, and hence, we used this option. If the alternative is true and a good classifier is learned online, then both of our payoffs will be positive on average, in which case it makes sense for $\\lambda_t$ to be positive. We have added a short remark about this.\n  \n> Is fitting the betting framework into the coin flip case the reason why the payoff functions are restricted to $[-1,1]$?\n\nNonnegative (super)martingales starting at 1 are central in the testing by betting framework (in particular, it allows to instantiate Ville's inequality to guarantee ``time-uniform'' type-1 error control under the null hypothesis). At round $t$, the wealth is updated as $\\mathcal{K}\\_t = \\mathcal{K}\\_{t-1} \\cdot (1+\\lambda_t f_t(Z_t,W_t))$, and hence, restricting the payoff functions and betting fractions to $[-1,1]$ suffices to guarantee that the resulting process $(\\mathcal{K}\\_t)_{t\\geq 0}$ is nonnegative. If the payoff is bounded in any other range, it can be transformed into $[-1,1]$, and we do not know how to design unbounded (on one side) bets that still result in nonnegative (super)martingales for our problem.\n\n> Why the ONS in algorithm 1 is different from the one in Cutkosky and Orabona ... e.g., the update of $z_t$ and $\\lambda_{t+1}$.\n\nWe thank the reviewer for reflecting upon that part. In the definition of $z_t$, there was indeed a typo: $z_t:=f_t/(1-\\lambda_t f_t)$, which we have now fixed. Regarding the update rule for $\\lambda_{t+1}$, there is a small change: instead of truncating at -1/2, we truncate at 0 (which is allowed and does not affect any theoretical claims of the paper). The reason behind this is the following: to maximize the power of the test, we aim to maximize the growth rate of the underlying wealth process, which corresponds to choosing $\\lambda\\_\\star = \\text{argmax}\\_{\\lambda\\in [-1,1]}\\mathbb{E}\\log (1+\\lambda f(Z_t,W_t))$. For a given predictor $g$, consider the payoff corresponding to the squared risk: $f(Z_t, W_t) = W_t\\cdot g(Z_t)$, where $W_t\\in\\\\{-1,+1\\\\}$ and $g_t\\in [-1,1]$. Assuming the 2ST null is false and $g$ is a predictor with non-trivial prediction risk, we have that: $\\mathbb{E}f(Z_t,W_t)>0$, in which case it is easy to see that $\\lambda_\\star$ has to be positive. In early simulations, we also did not observe any major differences between the two truncating options. We have clarified that part in the revision."}, {"review_id": "TL49j29TZw", "reviewer": "Reviewer_VGT6", "summary": "The authors propose methods of two-sample and independence tests in the setting of sequentially released data. Theoretical and empirical evaluations of the proposed methods are included.", "questions": "- In the paper, the initial values of $\\lambda_t^{ONS}$ and $g_t$ are set as 0. Are there any strategies to set better initial values, or are there any empirical observations about that?\n\n- What is $\\sigma(Z_1,\\ldots,Z_{t-1})$ in line 75? Does it mean the $\\sigma$-algebra?\n\n- In line 121, can we guarantee the existence of the minimizer $g_{\\star}$? or is it just an assumption?", "limitations": "In the proposed algorithm, the computation is the same for all $t$. Thus, the estimated $\\lambda_t^{ONS}$ and $g_t$ for small $t$ seem to perform worse than those for large $t$. It cannot be helped to a certain extent, but in the sequential setting, I think investigating some strategies to improve the performance for small $t$ would be important.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors propose algorithms for sequential two-sample and independence tests. The setting is interesting and important for practical applications. They provide theoretical results regarding the stop of the algorithm and the growth rate of the wealth. They also study the proposed methods numerically with synthetic and real-world data.", "weaknesses": "The readability can be improved. The introduction part is so long that I understand the contributions of the paper. I think the authors should split Section 1 into 2 sections: one is for explaining the motivation and the contribution, the other is for the problem setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback on the paper. Below, we address in detail issues that have been raised in the review.\n\n> Readability can be improved. The introduction part is so long that I understand the contributions of the paper. I think the authors should split Section 1 into 2 sections (motivation + contribution and problem setting).\n\nWe thank the reviewer for suggestions about improving the readability of the paper. We have added more structure in the revised paper, specifically, we have added more subsections to Sections 1 and 2.\n    \n> Initial values of $\\lambda_t$ and $g_t$ are set as 0. Are there any better strategies / any empirical observations about that?\n\nInitializing $\\lambda_t$ with 0 is not major since the online Newton step is used to update the betting fractions, and we simply used the default value specified in the earlier works. Initializing the predictor with a constant predictor is a bit more subtle: in our experiments, we trained all the models from scratch, but one can definitely use pre-trained models (e.g., weights of an image classifier trained on some other data) as initialization. We have added a remark about that point to the paper.\n\n> What is $\\sigma (Z_1,\\dots, Z_{t-1})$ in line 75? Does it mean the $\\sigma$-algebra?\n\nThis is correct. For $t\\geq 1$, $\\mathcal{F}\\_{t}=\\sigma (Z_1,\\dots, Z_{t})$ stands for the sigma-field generated by $Z_1,\\dots,Z_t$, and $\\mathcal{F}_0$ stands for the trivial sigma-field. We have now clarified this part in the paper.\n\n> In line 121, can we guarantee the existence of the minimizer $g_\\star$? or is it just an assumption?\n\nThis part of the paper aims to build intuition. To define the oracle test, we only care about the risk of $g_\\star$ (the optimal classifier in our class), and if the risk minimizer is not unique, $g_\\star$ is chosen as any of the predictors that minimize the risk. When a classifier is trained online, then we do not need to assume convergence to $g_\\star$, but the power will depend on the risk of the limiting classifier (whatever it is).\n\n> In the proposed algorithm, the computation is the same for all $t$. The estimated $\\lambda_t$ and $g_t$ for small $t$ seem to perform worse than those for large $t$. It cannot be helped to a certain extent, but in the sequential setting, I think investigating some strategies to improve the performance for small $t$ would be important.\n\nGood point! The rule for updating $\\lambda_t$ is indeed the same for all $t$. When the null hypothesis is false, the performance of a classifier $g_t$ clearly improves as more data are observed, and inferior performance in the beginning (when only a few points have been observed) is indeed expected. In practice, using pre-trained models (e.g., for image data) as initialization may definitely improve the performance during the early stages of testing. Another idea could be to bet slightly more conservatively for the first 20-30 (say) rounds, which is a heuristic that will affect the final regret guarantee or achieved growth rate."}, {"review_id": "KBk7ft7Nfc", "reviewer": "Reviewer_qWK6", "summary": "[Update: After reading the other reviews and the rebuttal, I have increased my score from 7 to 8]\n\nThe paper provides an algorithm for sequential testing of the homogeneity (two-sample) and independence hypothesis. \nThe core idea is that one learns a classifier to distinguish $P$ from $Q$ (in case of two-sample testing) or $P_{XY}$ from $P_X \\times P_Y$ (in case of Independence testing) from the previously seen data. This learned algorithm is used to place a bet on a new observation (how likely it is that it is from one class or the other). If it matches one updates the betting budget (starting from 1). There is also a parameter that trades-off how much of the existing budget is used at a step. If the betting budget ever exceeds $1/\\alpha$, with $\\alpha$ the significance level, then one rejects the test.\n\nThe authors show that the test controls type-I error and is consistent under the alternative if a non-trivial classifier can be learned. Furthermore they provide a strategy to select betting fractions which improves performance, especially if the classifier during the first iterations has poor quality.\n\n", "questions": "- Please see my remark above regarding Pandeva et al.\n\nBelow are curiosities that could further improve the paper, but are not absolutely critical.\n- In Batch C2ST, where the sample size is fixed upfront, usually half the data is used for learning/testing. However, I am not aware that this is a principled choice. What if you used your approach even in batch testing to circumvent the need of selecting the splitting ratio. Can we get better power? I think it would be nice to have an experiment with exactly the same algorithm  / architecture and compare the two approaches.\n- You prove that the type-I error is controlled even if the test is run indefinitely. I am curious: Does the test eventually exhaust the significance level? Do you have any theoretical or empirical insights?\n- you apply your test to every new datapoint. Panderas et al only update after a small batch of new data is presented. Have you considered this? It might be computationally a bit more convenient, and I am curious how it would affect test power.", "limitations": "I do not see much limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper nicely combines recent work on sequential testing with the power of general classification algorithms. It does not require any specific learning algorithms but can use any existing learning framework. \n- The theory is presented at an adequate level. \n- The experiments nicely underline the theoretical statements of the work and show good empirical performance.\n", "weaknesses": "- If I understand correctly, the main innovation over Pandeva et al [2022] is that the present work uses adaptive betting fractions? Is this a correct interpretation? I struggle a bit to clearly see the parallels and differences to Pandeva et al. They formulate their test in terms of E-values. Can your tests also be rephrased in terms of E-values to make a comparison simpler?\n\n\n\n**Minor**: \n- It took me a bit to understand the notation in some places:\n  - l. 75. What does $\\sigma$ stand for?\n  - After l. 104. Say that probability and expectations are wrt 1/2 (P+Q) (at least that's what I figured)\n  - Introduce $\\vee \\wedge$ notation for min/max\n  - l. 127 what is the expectation taken over?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback on the paper. Below, we address in detail issues that have been raised in the review.\n\n> The main innovation over Pandeva et al [2022] is that the present work uses adaptive betting fractions?...hard to clearly see the parallels and differences to Pandeva et al. They formulate their test in terms of E-values. Can your tests also be rephrased in terms of E-values to make the comparison simpler?\n\nOur works are indeed closely related as we pointed out in the paper. However, our focus is on the sequential setting, whereas Pandeva et al. focus on the batch case. Our construction results in a nonnegative martingale starting at 1 under the null hypothesis (test martingale). Test martingales are essentially a dynamic version of (conditional) e-values (see [1] for more context). The critical difference is indeed in using adaptive betting fractions which results in (a) substantial empirical improvements in terms of power as we illustrate in Example 1 in the paper, (b) much milder conditions for consistency (Pandeva et al. do not actually even discuss consistency, but the conditions should essentially the same as for the test of Lhéritier and Cazals, whereas our test is consistent as long as the squared errors (or misclassification error for the second test) are better on average than that of a naive predictor).\n\n[1] ``Game-Theoretic Statistics and Safe Anytime-Valid Inference'', Ramdas et al., 2023\n\n> Line 75: what does $\\sigma$ stand for?\n\n$\\mathcal{F}_t = \\sigma(Z_1,\\dots,Z_t)$ stands for the sigma-field generated by $Z_1,\\dots,Z_t$, with $\\mathcal{F}_0$ standing for the trivial sigma-field.\n\n> After line 104. Say that probability and expectations are wrt 1/2 (P+Q) (at least that's what I figured)\n\nSection 2 indeed corresponds to the setting of Definition 1. We have clarified that point in the revision.\n\n> Introduce $\\wedge, \\vee$ notation for min/max\n\nDone, thanks.\n\n> Line 127 what is the expectation taken over?\n\nSection 2 corresponds to the setting of Definition 1, i.e., $(Z_1, W_1),(Z_2, W_2),\\dots$ (and $(Z,W)$) are i.i.d. draws from $\\frac{1}{2}(P+Q)$, and those are the only sources of randomness over which expectations are taken over. We have clarified that point in the revision.\n\n> You prove that the type-1 error is controlled even if the test is run indefinitely. I am curious: Does the test eventually exhaust the significance level? Do you have any theoretical or empirical insights?\n\nYes, the test \"essentially\" exhausts the significance level (Ville's inequality holds with equality for continuous time martingales if the limiting cumulative variance is infinite, which it will be if we never stop betting; in discrete time, there is a slight looseness due to ``overshoot\" but it is a second order effect).\n\nIn practice, it is indeed the case that the tests can not be run indefinitely. As we point out in Remark 1, if an analyst stops the experiment early, i.e., before the wealth exceeds $1/\\alpha$, there is one modification that allows using non-exhausted type-I error budget to strictly improve power: one may use a different threshold for rejecting the null, namely $U/\\alpha$, where $U$ is an independently drawn (stochastically larger than) uniform random variable on [0, 1]; see [2] for more details.\n\n[2] ``Randomized and exchangeable improvements of Markov’s, Chebyshev’s and Chernoff’s inequalities'', Ramdas and Manole, 2023.\n\n> In Batch C2ST, where the sample size is fixed upfront, usually half the data is used for learning/testing. However, I am not aware that this is a principled choice. What if you used your approach even in batch testing to circumvent the need of selecting the splitting ratio. Can we get better power? I think it would be nice to have an experiment with exactly the same algorithm/architecture and compare the two approaches.\n\nThe role of sequential tests is to complement existing batch tests and not replace those. Generally, if one is ready to commit to a particular sample size, it is better to refer to batch tests. To understand the loss of power, we conducted an experiment, and the results are added to the allowed separate PDF. We take $P=\\mathcal{N}(0,1)$, $Q=\\mathcal{N}(\\delta,1)$, and use $k$-NN predictor. We set the sample size to 1500 and compared three tests: batch (with half of the data used for training and half for inference), Seq-C-2ST (our sequential test), and Seq-C-2ST + Randomization (as per Remark 1). The batch test has (slightly) higher power than our sequential one if the sample size is specified beforehand. Yet in cases where the power is less than one using a sequential test allows collecting more data to improve it, but with the batch test, nothing can be done since the type-1 error budget is fully utilized. We have added this experiment to the Appendix and included the figure in the rebuttal.\n\n> You apply your test to every new datapoint. Pandeva et al only update after a small batch of new data is presented. Have you considered this? It might be computationally a bit more convenient, and I am curious how it would affect test power.\n\nIn Appendix B, we discuss a minibatched version of our test where wealth updates are performed each time a batch of data is observed. It is a great question whether minibatches could improve power (i.e., be translated into the results about the growth rate of the underlying wealth process), and we plan to investigate this question in future work."}]

Author rebuttal:
Dear Reviewers,

We wanted to thank you for your time and for your valuable feedback! We hope that our responses address many/most of the existing concerns. We also attach a PDF file that contains the results of several additional experiments you asked for. If you have any additional questions, we would love to hear those from you and engage in a discussion. Looking forward.

Sincerely, 
The authors.

Meta-review: The focus of the submission is sequential two-sample and independence testing. Using the principle of testing by betting, the authors present a novel sequentially learnt predictor-based hypothesis testing framework (Algorithm 2) which is shown to be level-alpha and consistent (Theorem 2), alongside with the characterization of the growth of the underlying oracle wealth process (Theorem 1). The practicality of the method is showcased on the KDEF and MNIST datasets.

Sequential hypothesis testing is a key problem in data science. Constructing new, flexible, principled, and practically-efficient techniques in the domain, complementing existing kernel-based approaches is without doubt relevant to the community. The submission nicely achieves this goal, as it was detailed by the reviewers.
Decision: Accept (poster)