Active Sequential Two-Sample Testing
Authors: Weizhi Li
Prad Kadambi
Pouria Saidi
Karthikeyan Natesan Ramamurthy
Gautam Dasarathy
Visar Berisha
Venue: Accepted by TMLR ()

Abstract: A two-sample hypothesis test is a statistical procedure used to determine whether the distributions generating two samples are identical. We consider the two-sample testing problem in a new scenario where the sample measurements (or sample features) are inexpensive to access, but their group memberships (or labels) are costly. To address the problem, we devise the first \emph{active sequential two-sample testing framework} that not only sequentially but also \emph{actively queries}. Our test statistic is a likelihood ratio where one likelihood is found by maximization over all class priors, and the other is provided by a probabilistic classification model. The classification model is adaptively updated and used to predict where the (unlabelled) features have a high dependency on labels; labeling the ``high-dependency'' features leads to the increased power of the proposed testing framework. In theory, we provide the proof that our framework produces an \emph{anytime-valid}  $p$-value. In addition, we characterize the proposed framework's gain in testing power by analyzing the mutual information between the feature and label variables in asymptotic and finite-sample scenarios. In practice, we introduce an instantiation of our framework and evaluate it using several experiments; the experiments on the synthetic, MNIST, and application-specific datasets demonstrate that the testing power of the instantiated active sequential test significantly increases while the Type I error is under control.

Published in Transactions on Machine Learning Research (lune/2024)
Active Sequential Two-Sample Testing
Weizhi Li
weizhili edu
Arizona State University
Los Alamos National Laboratory
Prad Kadambi
pladambi@asu. edu
Arizona State University
Pouria Saidi
psaidiBasu. edu
Arizona State University
Karthikeyan Natesan Ramamurthy
knatesa@us. ibm. com
IBM Reseorch
Gautam Dasarathy
goutamd@asu.co edu
Arizona State University
Visar Berisha Arizona State University
visar edu
Reviewed on OpenReview: https:
// openreview. net/ forum? id= ExPRgIq2Tk
Abstract
A two-sample hypothesis lest is a statistical procedure used to delermine whether the distri- butions generating two samples are identical. We consider the two-sample testing problem in a new scenario where the sample measurements (or sample features) are incxpensive to access, but their group memberships (or labels) are costly. To address the problem, we de- vise the first active sequential two-sample testing framework that not only sequentially but also actively queries. Our test statistic maximization all class priors, and the other is provided by probabilistic classification model. The classification model is adaptively updated and used to predict where the (unla- belled) features have high dependency on labels; labeling the "high-dependeney" features leads to the increased power of the proposed testing framework. In theory, we provide the proof that our framework produces an onytime-valid p-value. addition, we characterize the proposed framework's gain in testing power by analyzing the mutual information bo- tween the feature and label variables in asymptotic and finite-sample scenarios. In practice, introduce instantiation of our framework and evaluate it using several experiments; the synthetic, MNIST, and application-specife datasets demonstrate
likelihood ratio where one likelihood is found by
the experiments that the testing power of the instantiated active sequential test significantly increases while the Type I error under control.
1 Introduction
The two-sample test statistical hypothesis test applied to data samples (or measurements) from two distributions. The goal is to test if the data supports the hypothesis that the distributions different. If we consider each data point then the two-sample test is equivalent to the problem of testing the dependence between the features and the labels. Viewed with this lens, the null hypothesis for the two-sample test states that the feature and
feature and label (which tells us which distribution the data is from) pair,
Work done when the author Arizona State University.

---

Published in Transactions on Machine Learning Research (June/ 22044)
label variables are independent, and the alternate hypothesis states the opposite. The analyst performing the two-sample test needs to decide between the null and the alternative hypotheses with data from the two distributions.
The analyst typically knows little about the difficulty of a two-sample testing problem before running the test. Fixing the sample size a priori may result in test that needs to collect additional evidence arrive final decision (if the problem is hard) or in an inefficient test with over-collected data (if the problem is simple). To address this dichotomy, the rescarch community has proposed sequential two-sample tests [Wald]
1992 Lhéritier & Cazals 2018 Hajnal 1961 Shekhar & Ramdas 2021 Balsubramani & Ramdas, 2015 that
allow the analyst to sequentially collect data and monitor statistical evidence, i.c., statistic is computed from the data. The test can stop anytime when sufficient evidence has been accumulated to make a decision.
Existing sequential two-sample tests [Wald 1992 Lhéritier & Cazals 2018 Hajnal 1961 Shekhar & Ramdas, 2021 Balsubramani & Ramdas 2015) are devised to collect both sample features and sample labels simul- laneously. In this paper, we consider the problem of sequential two-sample testing in novel and practical setting where the cost of obtaining sample labels is high, but accessing sample features is inexpensive. As result, the analyst can obtain large collection of sample features without labels; she will need to sequentially query the label of the sample features in the collection to perform the two-sample testing while ensuring the query complexity (i.e., the number of queried labels) doesn't 't exceed a label budget. A motivation for this formulation comes from the field of digital health: Physicians seek inexpensive digital measurements (e.g,, gait, speech, typing speed measured using a patient's 's smarttphone) to replace traditional biomarkers (e.g., the amyloid buildup that indicates Alzheimer's progression) which are often costly to access; hence they need to validate the dependency between the digital measurements (feature variables) and traditional biomarkers (label variables). While validation studies access large registries to collect digital measurements remotely at scale, there is a fixed label budget for the expensive biomarker measures. An efficient sequential design would reveal the dependency between the features and the labels using only a reasonable label budget.
In this paper, we propose the active sequential testing framework shown in Figure The framework initializes a classifier model probabilities of sample labels given features using an initial random sample; next, depending the classificr's outputs, the framework queries the labels of features predicted to have high dependency with the labels and constructs test statistic w. The framework rejects the null if w is smaller than pre-defined significance level a; otherwise, the framework stops and retains the null if the label budget runs out or re-enters the label query and decision-making, enabling a sequential testing process.
w w> a and the label buns out
Fail to reject the null hypothesis
Initialize the class- probability predictor (zz(s)
Query the labels features predicted by Q(2)s) to have high-deeendency on labels
Update the testing statistic
WSa
Reject the null hypothesis
w > a and the label budget hasn'trun out
Update the predictor (
Figure 1: The active sequential two-sample testing framework.
The test statistic w in the framework based on the likelihood ratio between the likelihood constructed under the null that feature and label variables are independent and the likelihood constructed under the alternative
2

---

Published in Transactions on Machine Learning Research (June/ 20244)
that the dependency between the feature and label variables exists. Such likelihood ratio two-sample test statistic has been first proposed in (Lhéritier & Cazals 2018) to develop a non-active sequential two-sample test capable of controlling the Type I error (i.e., the probability of a decision made on the alternative when the mull is truc). We adapt the original test statistic by replacing the pro-defined label probability prior with a maximum likelihood estimate to satisly our considered selting that the label prior is unknown. More importantly, our framework actively labels the features that are predicted to have a high dependency on labels. We will characterize the benefits of the active query over the random query by the change of mutual information between feature and label variables in the asymptotic and finite-sample scenarios. In practice, we suggest using an active query scheme called bimodal query proposed in (Li et al. 2022), in which the scheme labels samples with the highest class one or zero probabilities.
We summarize the main contributions of our work as follows:
We introduce the first active sequential two-sample testing framework. We prove that the proposed framework produces an anytime-valid p-value to achieve Type I error control. Furthermore, we provide an information-theoredt interpretation of the proposed framework. We prove that, asymptotically, the framework is capable of generating the largest mutual information (MI) between feature and label variables under standard conditions (Györfi et al. 2002]; and we also analyze the gain of the testing power for the proposed framework over its passive query parallel in the finite-sample scenario through MI.
We instantiate the framework using the bimodal query Li et al. 2022) (i.e., queries the labels of the samples that, have the highest class one or zero probabilities) as the label query scheme. We perform Alzheimer's disease dataset
extensive experiments on synthetic data, MNIST, and an application-speciis to demonstrate the effectiveness of the instantiated framework. Our proposed test exhibits significant reduction of the Type II error using fewer labeled samples compared with a non-active sequential testing baseline.
2 Related Works
The author of (Student 1908) compares the mean difference of two samples of uni-variate data. Since then, the research community has expanded the two-sample test to many other forms, e.g., the hotelling test (Hotelling) 1992), the Friedman- Rafsky test (Friedman & Rafsky 1979), the kernel two-sample test. (Gretton et al. 2012) and the classifier two-sample test (Lopez-Paz & Oquab 2016) for the multi-variate case. These tests are constructed with various statistics, including the Mahalanobis distance, the measurement over graph, kernel embedding, or classifier accuracy, all in service of increasing testing power while controlling the Type I error. In partic- ular, (Friedman & Rafsky, 1979 Gretton et al. 2012: Lopez-Paz & Oquab 2016) test if the data from two samples is distributionally different, which is a generalization of the hotelling and (-lest (Student 1908) Hotelling 1992) that only detect the mean difference of two samples. These two-sample tests are batch tests that have been extensively used subject to a fixed-sample size: When the collection of experimental data ends, an analyst performs the two-sample tests the data and makes decision; she is not allowed to continue to collect and incorporate more data into the testing after decision made, as that will inflate the Type I error.
developed the t-test, probably the simplest form of a two-sample test that
In contrast to the batch two-sample tests, the research community has developed a class of sequential two- sample tests (Lhéritier & Cavals 2018 Shekhar & Ramdas 2021 Pandeva et al., (022) that allow the analyst to sequentially collect data and perform the two-sample test, enabling sequential dccision-making. These sequential tests rectify the inflated Type that will happen in the batch test with different statistical techniques such as Bonferroni correction (Dunn 1961) and Ville's maximal inequality (Doob) 1939).
There are also several works that consider the active sctting in two-sample testing. The authors of LLi et al. 2022) proposed a batch two-sample Lest combined with active learning when curated labeled data is unavailable and querying the data labels is expensive. Several studies have also considered sequential testing
for developing active soquential hypothesis tests (Naghshvar & Javidi 2013 Chernoff
1959 Bessler 1960)
Blot & Meeter 1973 Keener 1984 Kiefer & Sacks 1963). However, these tests require a clear parametric description of the statistical models of the hypotheses. The authors of (Duan et al. 2022) developed an
3

---

Published in Transactions on Machine Learning Research (June/ /2044)
interactive rank test, which is distribution-free and can similarly perform the sequential two-sample testing in the active learning setting.
The work proposed herein uses the label query scheme in Li et al. 2022) to develop the first multivariate non- parameametricc sequential test for the active learning setting with a novel test statistic and theoretical results. We demonstrate that the test. controls the Type error via Ville's maximal inequality (See Theorem 5.1 Ville's maximal inequality results in higher testing power than the Bonferroni correction for sequential testing (Shekhar & Ramdas
2021 Ramdas et al. 2022).
While our framework in Figure
employs the label query scheme introduced in distinct advantages over [L et al. 2022):
Li et al. 2022 it offers
Our proposed framework follows a sequential design. Upon accumulating sufficient evidence to reject the null hypothesis, our design automatically stops label collection before exhausting the label budget. In contrast, the batch design in (Li et al. 2022) invariably exhausts the label budget.
Utilizing a different test statistic, our framework enables finite-sample analysis, which not provided in (Li et al. 2022).
3 Problem Statement and Preliminaries
3.1 Notations
We use pair of random variables (S. denote feature and its label variables whose realization is 2s) E Rd x 1). The variable pair (S, Z) admits joint distribution Psz z). Furthermore, we write S to denote the support of ps()). Formally, two-sample testing problem consists of null hypothesis Ho that states Ps))=o(s) psiz=1(s) and alternative hypothesis Hi that stales Ps])=0(s) & ps)z=1(s). An analyst collects a sequence x)s.:);) of N realizations of (S, Z) to test Ho against Hi. The problem is equivalent testing the independency between S and Z. Therefore, we equivalently restate the hypothesis test follows:
Ho : H1 :
E E
(1)
Moving forward, we omit the subscripts in psz(s, Pz(=) and (s(s) and write them as p(s, 2), P(z) and p(s). In addition, we use sN, N and 2) to denote sequences of samples (s;) (2:) and (ss respectively. We use similar notation throughout the paper.
3.2
The problem
In the typical setting of sequential two-sample test, an analyst does not have prior knowledge of sample features. The analyst sequentially collects both sample features and their labels simultaneously with the corresponding random variable pair (S, Z) i..d. generated from data-generating process, i.e., p(s, We consider variant of the setting in which accessing sample features is free free/inexpensive. Consequently, the analyst collects large set S, of sample features before performing scquential test. However, accessing the label of a feature in S,, is costly. We assume the following fact throughout the paper: The clready-collected S, is the result
sample feature collection process where all s; E S, are realizations of random variables S, i.i.d. generated from p(s). There exists an oracle to return label 2 of s, E S, with the corresponding random variable Z, and S, admitting the posterior probability P(z]ss). We consider the following new sequential two-sample testing problem:
4

---

Published in Transactions on Machine Learning Research (June/ (2044)
An active sequential two-sample testing problem: Suppose S, is an unlabeled feature set, there exists an oracle to return label of s Suy and Ng is limit on the number of times the oracle can be queried (e-g., the label budget). An analyst sequentially queries the oracle for the of s E S., After querying a new 2n of Sn, for 1 I S Ng. the analyst needs to decide whether to terminate the label querying process and make decision (i.e., whether to reject Ho) or continue with the querying process if n < Ng.
An analyst actively labeling Sn S, may result in non-ii.d pairs of (S. Z); hence the distribution of (S, Z) is shifted away from 2). In contrast, an analyst passively (or randomly) labeling Sp. E S, maintains (S, Z) 2).
3.3 Evaluation metrics for the problem
In the following, we introduce the evaluation metrics used throughout the paper.
Type I error Po: The probability of rejecting Ho when Ho is true.
Type II error Pf: The probability of rejecting H1 when Hi true.
Testing power: The probability of rejecting Ho when HJ true. In other words, Testing power = 1 1-P,. P1-
Testing power and Type II error interchangeably used in the mothodology and experiment sections (Section 5 and
3.4 Attributes of an active tam-sa test
As already generalized many two-sample testing literature such as (Johari et al., 2022 Wald 1992:
Lhéritier Cazals, 2018: Shekhar Ramdas 2021: Welch 1990), a conventional procodure for soquential two-sample lesting is to compule p-value from sequentially observed samples and compare it pre- defined significance level E [0, anytime. The analyst rejects Hg and stops the testing if p S For more details, see (Wasserstein & Lazar 2016). In addition, as the test proposed in what follows is endowed with active querying to reduce the number of label queries, the active sequential test is anticipated to spend fewer labels than a passive (random-query) test to reject Hı when H1 true. In summary, an active sequential two-sample test has the following four attributes:
The test generates anytime-valid p-value such that Po(p I a:) holds anytime of the soquential testing process. Po is exactly the Type I error and that implies the Type is upper- bounded by
upper-bounded
The test has high testing power Pi(p S a)).
The test is consistent such that Pi(p S a))= = under H, when the test sample size goes to infinity.
The test has higher P1 than the passive test given the same label budgets.
4 A Sequential Two-Sample Testing Statistic
We follow the well-known likelihood ratio test Wilks 1938) Lo construct a sequential testing statistic. We use the statistical models that characterize the label generation processes conditional on the observed sample features under Ho and Hi More preciscly, under Ho, have P(zls) P(z), Vs E that is, when S and Z are independent, the posterior probability P (z|s) is the same for any in the support S of p(s). In contrast, under H1, we have the following statistical model: Es E S, P(z|s) * P(z). We sequentially collect sample data (s, 2), and when a new observation (Sn, zn) arrives, we construct a likelihood ratio w.: With wo = 1, P(zn) Wy, -1 P(a.)
II
P(a.) n 2 1 to assess Ho against H1. P(a, B:)
5

---

Published in Transactions on Machine Learning Research (June/ /2044)
The statistical models P(z) and P(zls) are unknown. To formulate our two-sample test, will use likelihood estimate P(=") that is maximized over all the class priors to replace P(=")-the product of the class prior. In addition, we build a class- bass-probability predictor Qn(z s) with the past observed sample sequence (s, =5.2)==1 to model P(an she posterior probability of 2n given newly observed Sn: any probabilistic classifier, such as a neural network and logistic function, can be used to build Qn(= s). Additionally, Q1(2 s) indicates an initialized class-probability predicto We formally present our sequential testing statistic in the following:
A sequential two-sample testing statistic: Considering (s, 2) is sequentially observed, and as a new (Sn: 2n) arrives, then, for 1,2, an analyst constructs
P(=") W/ = Q(2 sn)
P(z.)
(2)
Qi(z 8;)
1=1
En
where P(z 1) class-probabilityy predictor built by the past observed sequence 2s
a is class prior chosen to maximize P(=") and Qi(z: s;) is the output of
We accordingly Wn. to indicate random variable of which wn is realization. Our test statistic in equation 2 is generalization of the test statistic proposed in (Lhériticr & Cazals 2018). In contrast to that work, our test statistic does not require the prior class to be known. The analyst compares wa with a at every step n starting from n = 1, stopping the test once encountering a step with wn s a. As a result, a small Wn favored under H1 to reject Ho for increasing testing power.
A Algorithm Bimodal Query Based Active Sequential Two-Sample Testing (BQ-AST)
1: Input: Su, A, No, Ny
2: Output: Reject or fail to reject Ho
Initialization: Initialize Q1(2 s) using A with No features uniformly sampled from Sn without re- placement and then labeled.
Active Sequential testing:
5: for n = 1 to N₂ No do
6: Sample a feature Sn = Sgo or Sy, with fair chance where Sqo arg max, [Qn(2 = =[[s]], Vs E S, and Sq: arg max, (Qn(Z = 1|s)] vs E. S.,
7:
Query the label 2n of sn
Update wn, in equation 3 with (Sn, 2n) and Q (2n sn)
if w. I a then Return Reject Ho
10:
11: else
12:
Update Qn(2 s) with newly queried (sn, 2n) and past training examples.
13:
end if
14:
end for
15: Return Retain Ho
5 Active Sequential Two-Sample Testing
This section introduces the active sequential two-sample testing framework and its instantiation. We demon- strate that the framework produces an anytime-us valid p-value regardless of the selected query scheme. We also provide the asymptotic and finite-sample performance of the framework with the testing power gain measured by the change of the mutual information between feature and label variables.
It possible to set Q1 (z|s) random guess plass-probaillity prodictor, and then sequentially gather (s, for training; however, this would hurt the testing power. As suggested by Duan al. 2022 Lhéritier Cazals 2018 we initialize (2(1)) with small of samples randomly labeled and start sequential testing that.

---

Published in Transactions on Machine Learning Research (June/2024)
5.1 An active sequential two-sample testing framework
A flow chart of the proposed framework shown Figure Our framework starts by initializing the class-probbbility predictor Qn s) at
with small of sample features randomly selected from S, and then labeled. Then, the framework enters the sequential testing stage that iteratively performs the following: selects features in S, predicted by On to have high dependency on their labels, update the statistic Wn: decide whether we can reject Ho and update Qn if the test has not stopped. We formally introduce our active sequential two-sample testing framework as follows,
An active sequential two-sample testing framework: Suppose N₂ is label budget and is significance level. An analyst uses the proposed framework to sequentially and actively query the label En of S, from unlabelled feature set S, based on the predictions of Qn (= s). As a new on of 8n is queried, the analyst constructs the following statistic
n
P(2))
Wy
(3)
Qi (z 8.)
The analyst evaluates wn and makes one of the following decisions: (1) rejects Ho if wn, S o; (2) retains Ho the label budget Ng is exhausted and (1) is not satisfied; and (3) continues the test and updates Qn to Qu+1 if (1) and (2) are not satisfied.
Framework instantiation: We provide a framework instantiation called bimodal query based active sequential two-sample testing (BQ-AST) described in Algorithm| I The algorithm takes the following input: an unlabelled feature set S,, a probabilistic classification algorithm A, the size No of an initialization set used for A, label budget Ng and a significance level a. Then, the algorithm initializes class-probability predictor Q using A with small set of randomly labeled samples. In the sequential testing stage, the algorithm uses bimodal query from Li et al. (2022) to sample s, with samples having the highest posteriors from either class (e.g. a fair chance to select the highest Qn (Z 0 s) or Qn (Z = s)) from Su, queries its label 2n and updates the statistic wn- Next, the algorithm compares wn with a, and if Hu is not rejected,
update Qn with zn) and then re-enter the query labeling. The algorithm rejects Ho wn S a or fails
to reject Ho if the label budget is exhausted.
The label budget N₂ Algorithm contains the labels for both initializing QI(2 s) and constructing the statistic w. In what follows in this section, we simply Ng to denote the "label budget" allowed to be used after the initialization.
5.2 The proposed framework results an anytime-valid p-value
Our framework rejects Ho if the statistic wn S a. The following theorem states that under Ho, wn is an anytime- valid p-valuc.
Theorem 5.1. If an analyst uses the proposed framework sequentially query the oracle for with S, resulting in (S, Zyn, then have the following under Hu,
P(Zi) Q (2 S.)
Po 3n E [N,), W.
II
S
Sa
(4)
where Ng is label budget and a is the pre-specified significance level.
Theorem 5.1 implies the probability Po (or Type I error) that our framework mistakenly rejects Hg is upper- bounded by a. Briefly, we prove this by observing that the sequence W.
upper-bounded by a
W.
martingale, and hence we use Ville's maximal incquality Durrett (0019 Doob (1939) to develop Theorem 5.1 See the Appendix for the complete proof.
Durrett

---

Published in Transactions on Machine Learning Research (June/ /2044)
5.3 Asymptotic properties of the proposed framework
This section provides the theorelical conditions under which the proposed framework asymplotically gener- ates the smallest normalized statistic (normalization of the statistic in equation 3 or equivalently, maximally increases the mutual information between S and Z. Before that, we first define the consistent bimodal query as follows,
Desinition 5.2. (Consistent bimodal query) Let S be the support of p(s) that sample features are collected from and added to an unlabeled set Su, and let P( s) denote the posterior probability of 2 given S. An analyst adopts label query scheme, for every E [Ng). to query the label Zn of S, E S,, such that S, admits a probability density function (PDF) (s). The label query scheme is a consistent bimodal query if a (n = (s() where
p (s) = 0, VS E S\ (5 US and p p'(s) > 0, VS E So US
(5)
S 90
P(Z = 01 (/))))))) = max P P(Z = 01s)
(6)
#E8
S
8tz1
| P(Z =1 8qy) )
max
= 1
(7)
sES
Remark 5.3. Def 5.2 considers a label query scheme that only queries the labels of s with the highest p pZ = 0 and p (Z 1
|||s) ()) when n goes to infinily. As p= [s) not directly available, to construet the consistent bimodal guery, one can use nonparametric regressors to construct class- blass-probbbilityy predictor {= as nonparametric estimates of (( s). Vs E S and implements the bimodal query to label s with highest Q = s) or highest Q = 1 s) after Q( s) converges to P (z [). The authors of Györfi et al. 2002) prove that when Q (z 8) is a kernel, KNN or partition estimates with proper smoothing parameters (e.g., bandwidth for the kernel) and labels are sufficiently revealed in the proximity of s, Vs E S,
then Q (z s) converges to ((2 s).
To this end, we introduce the asymptotic property of our framework. We consider normalizing the test statistic in equation as follows,
P(Z,) Q (Z, S.) (S,, 2,) ~ (s. =p(z ss (s)
W
n log
(8)
where (S,, 7 denotes a feature-label pair returned by a label query scheme when querying the i-th label. Next, we state the following theorem.
Theorem 5.4. Let S be the support of that sample features are collected from and added to on unlabeled set Su, and let P (z s) denote the posterior probability of given S. There crists consistent bimodal query scheme; when analyst uses such scheme in the proposed aclive sequential frumework, then, under H1, Wn converges to the negation of mutual information (MT), and the converged negated MT lower-bounds the negated MI generated by any (s) subject to P (z (s, Vs Precisely, there exists a consistent bimodal query leading to the following
lim W. = - (H' - 11 (6 (S) = 1 (S:2) < -1 +00
(9)
I' (S: Z) is the MI constructed with Z, ~ p² (s. = P (= S) p" (s) (See equation 5 for p' (s)); I Z) is MI constructed with (S, 2) ~ (s, P (= (s).
Recalling the mull Ho is rejected when the test statistic wn in equation 3 is smaller than a; hence, the proposed framework, when used with consistent bimodal query to asymptotically minimize the normalized wr in equation 3 favorably increases the testing power when |S,] is large and Q(= s) is close to P(s s). In Section 5.4 we will analyze the finite-sample performance of the proposed framework considering the approximation error of Q(2 | s). Additionally, by characterizing the difficulty of a two-sample testing problem with MI, Theorem 5.4 alludes that the proposed framework asymptotically turns the original hard two-sample testing problem with low dependency between S and (low MI), a simple one by increasing the dependency between S and Z (high MT).
8

---

Published in Transactions on Machine Learning Research (June/ 2004))
Remark 5.5. Our testing framework is also consistent under H1 and the same conditions of Theorem 5.4 P(Z,)
as 1om Pi [I Q.2.187 S a = lim P (W,, S log(a)) Pi(-1" (8, 2) - 0) = 1. The last
equality holds due to 1" (S, 2) > under H1.
5.4 Finite-sample analysis for the proposed framework
This section analyzes the testing power of the proposed framework in the finite-sample case. Section 5.4. and Scction 5.4.2 offer metrics that assess the approximation error of Q(= s) and an irreducible Type II error. These metrics logether determine the finite-sample lesting power. Furthermore, Section 5.4.3) presents an illustrative example of using our framework. In Section 5.4.4 we conduct a inite-sample analysis for the example, incorporating both the metrics that characterize the approximation error and the irreducible Type II error.
5.4.1 Characterizing the approximation error of Q(= [8)
As our framework constructs the lest statistic in equation with the approximation Q(= s), there arises need establish a metric for assessing the approximation error of Q(z s) for our finite-sample analysis. To this end, we introduce KL*-divergence,
Definition 5.6. (KLe-divergence) Let po and to be two probability density functions on the same support X. Let f(t) = log (t). Then, the -iverreeee between Po and go
( (X) (
90 log²
PX ]
DKL2 (gollpo) Ex-po(x)
Ex~po(x)
(10)
D (ga Po) is the second moment of the log-likelihood ratio and has been used (see, e.g., (3.1.14) in (Koga
et al. 2002)) to understand the behavior of the distribution of log (poxx) ). We use DKL (go llo)) to evaluate
[oo())
the distance between p (s, 2) = P (z (s) and q(s. 2) = Q (z ss (s), which yields the following
DKLA (q(s,)))lpf 2)) ((s.z)>p(s.)) log² ( 2) (p(s.2) )))
(Q () ( ( }
E Es
log*
(11)
Remarkably, DKLA (4(s,))llpss, 2)),sss in equation 11 also characterizes the discrepancy between P s) and
Q [z s) by averaging their log square distance over S; in our main result, we will see that the testing power of the proposed framework depends on DKL. (g(s, =)]lp(s, 2)). Additionally, DKL.² (g(s,2)llpd) z)]lp(s, 2)) is closely
related to the typical KL divergence DKL (P s) ||Q (z s)) = (Es. log P(2(S)
Q(Z[8) This can be seen 11 using the formula Var [X] = [x2] - E² [X] resulting in,
by expanding equation
Q(Z 8) } + [KLL
P(Z S)
DKL (g(s, ( p)ssss 2)) = Var (s)
log
[s)]] |x))]]]
(12)
equation 12 implies that DRL.² (q (s, =) lp (s. =)) not only measures the expected distance between P (z and Q (z s) over but also the variance of that distance. Similarly, we write
( DKLa (s,)2) (s, 2)) E ((s,z)~((s.A) log" (Q S
(13)
to measure the discrepancy between p(s, 2) and 2(8,2) but with reverse direction opposed to DELA (q (s, =))
DKL2 (q (s, 2) lpp (s, 2)) and DKLa (p (s, 2) ||g 2)) both characterize the approximation error of Q(2 s), and we will also see they jointly determine the testing power of the proposed framework in Section 5.4.4

---

Published in Transactions on Machine Learning Research (June/ /2044)
5.4.2 Characterizing the factor that leads to the irreducible Type II error in finite-sane sample case
We also introduce another factor inftuencing testing power, which persists even in the absence of approxi- mation error, L.., Q(= 5) P(z s). see this, we recall the information spectrum introduced in (Han Verdú 1993
Definition 5.7. (Information spectrum (Han & Verdú 1993 Let (X,Y) Y) be pair of random variables over the support X' x. Let pxy denote the joint distribution of (X, Y), and let px and py denote the marginal distributions of X and Y. Suppose {(X, Y) is a sequence of i.id random variables for (X, Y) ~ >xxy(x,)). Then, the information spectrum is the probability distribution of the following random variable,
12
PXY (X;, Y,) (X, pxx(xx))
I(x"; Y
log
(14)
71 px (X:)px((Y.)
It is easy to see the expectation of I(X"; Y") is the mutual information I(X;Y for (X. ~ PxY y). Substituting (X ~ pxy y) in equation 14 with the feature-label variable pair (S, 7) ~ p (s, ) in our two-sample testing problem recovers the (negated) normalizing test statistic in equation with P(z) and P( [8) inserted, i.e, the absence of approximation error.
Han 2000 leverages the dispersion of the information spectrum (the distribution of [(": Y")) for (X, Y) to quantify the rate that Type II crror goes zero with increasing Their underlying rationale is that, for a larger variance of T(X"; Y"), the probability of T(X"; Y") falling outside the acceplance region for an alternative hypothesis also increases, thereby resulting in slower convergence rate for the Type II error. In our work, we will make use of the variance the log-likelihood ratio between p(s, 2) and p(s)p(z)
P(Z)
(8) T(S, = - 1 z") = Var - loog
(15)
P(Z (S)
Scaling (ar(ss))pp(s.;))) Z) down by n is the variance of (S": Z"), characterizing the the dispersion the (s)pps)))) [S; Z) is also known as the relative entropy variance (See e.g., (2.29) in (Tan et al. 2014)). It remains present even in the absence of approximation error (i.c., Q(z s) = (( s)). As we will see in Section 5.4.4, the persistent Var [(S Z) leads to non-zero Type II error in the finite-sample case.
information spectrum for {(S, Z)} given
I
5.4.3 An example of using the proposed framework
We first. introduce the notation that will be used in the ensuing sections. We write P = (Ai,...,A Am} to denote a partition of the support other words, U A, S. We compare an example of our proposed framework with the bascline, where features are randomly sampled from S, and labeled. We quantitatively analyze the testing power of both cases. Both the example and the baseline detained as follows:
p(s) from which unlabeled sample features in S, are generated; in
10

---

Published in Transactions on Machine Learning Research (June/ (2044)
(An example of using the proposed framework) Given a label budget Ng. a, an unlabeled set
Su, a partition p '. "mm.:..,mm..: and class priors {P(Z 0 At),... P(Z = 0 Am)) an analyst initializes Q (= [) with a set of labeled features randomly sampled from Su, then, she estimates I (S; Z A.) by
(S: Z A,)
= =H A,) (Z S,).)
-- Σ P( = A.) log PZZ = = A.) A:)+ Exer E:=o Q log (Z (16)
1
|A; Su
selects A" arg MAX i (s: 2 A); and soquentially constructs the statistic wn Ih P(a.)
Q(4 s:)
by labelling features randomly sampled from A S The analyst rejects Ho whenever wn a retains Hn if the label budget runs out. (Baseline lest) Given label budget Ng, a, an unlabeled set S, and the class prior P(Z 0), an analyst initializes Q(2 s) with a set of labeled features randomly sampled from Sa, then, she P(z.)_ by labelling features randomly sampled from S.- The analyst rejects Ho whenever w, S or retains Ho if the label budget runs out.
sequentially constructs the statistic wn = [I Q[[[]]]
In the example of using the proposed framework, the class priors {P (a analytical results; however, one can estimate these priors with labels in each A; and use the prior estimates to replace (P(z A,)), and that will not change the main argument of our theorem. In addition, the analyst chooses the partition A predicted by ( s) to have the highest dependency between S and Z and only conducts sequential testing with the labeled points in A", In contrast, the baseline conducts the sequential test entirely the same, except that the analyst queries the labels of features that are randomly generated from S,,. Both the proposed framework and the baseline assert the use of a stable Q |s) with no updates in the sequential testing: that sufficient for our analysis as will see the testing power for the above cases depend on DKL2 (g(s, =)llp(s, z)) in equation I1 DKL (p(s, 2)l[g(s z)) in equation 12 and Var ())sss)) I(S, Z) in equation 15
A,) are given to simplify our
5.4.4 Finite-sample analysis for the example
We use = maxAşp DRL (s) |p (s, ture the maximum approximation error of Q(2 s) over the partition P = {A,,'.. ,m and use o² = max (maxAee Var(s.2)-=tssaa4)][[5 2). T( Z)} to capture the maximum irroducible Type II error over the same parlition P.
A) and = maX DKL2 (p (s, 11 (s,2) |A) to cap-
We will need make the following assumptions before presenting our results.
Assumption 5.8. (Maximum mutual information gain) max I (S; A) I(::)) = A
Assumption 5.8 characterizes the largest MI gain of the proposed framework in the example over the baseline; that is the direct reason for the increased testing power of the proposed framework.
Assumption 5.9. (Sufficient. number of unlabeled samples) ExEAns, DKL. (Q 5) (2 s) A) P.
B2 log
QiZis) Pizis)
AnSS.
Even though we typically have access to only a finite number of unlabeled samples in real-world scenarios. this number is usually quite large and affordable for many applications. Hence, similar to (Hanneke & Yang 2015), Assumption 5.9 assumes a sufficient supply of unlabeled samples to simplify the analysis and concentrate solely on the number of labels needed for the proposed framework the example.
Now, we present our theorem to address the testing power the framework in the example and the bascline test in the finite-sample case.
11

---

Published in Transactions on Machine Learning Research (June/ (2044)
Theorem 5.10. Under Assumption 5.85.9 the proposed fromework in the ezample with label budget Ng and ar has a testing power of approzimalely at least.
loga + VN,
VN, (1 -2/E, Ve2)
(17)
(c1 + 02 22 1/2
and the baseline test with features randomby sampled from Su and labeled has testing power of approcimately at least
log VN, + VN₂ (1 VEa)
(18)
1/2
20
equation 17 and equation state approximate testing power's lower bounds for the proposed framework in the example and the baseline test. We can observe that
Given a, then, a large budget Ng, and small approximation errors characterized by e1, increase the two testing power's lower-bounds of the proposed framework and the bascline, structured similarly in equation 17 and equalion 18
Comparing equation 17 for the proposed framework to the equation 18 for the baseline, the extra A is ascribed to the maximum power gain, and v V accounts for the diminishing of the maximum power gain in selecting A E P that does not have the highest MI over A P.
When the approximation errors e 0 and/or e2 0, both testing power's lower-bounds are decreased by factor of a, resulting in the irreducible Type II error.
When the maximum MI gain A can compensate the approximation error of Q (2 [s) being larger than vei + /22, our framework in the example has higher testing power's lower bound than the baseline test given the same label budget Ng and a.
6 Experimental Results
We have proposed practical instantiation of the framework, and its algorithmic description BQ-AST is presented in Algorithm[] D In this section, we compare the BQ-AST with sequential testing baseline Lhéri-- tier & Cazals 2018) that uses the same statistic in equation 2 but the bascline labels fcatures randomly sampled from the unlabeled set S,. In addition, we build Q (= s) for the test statistic in equation 2 using logistic regression, SVM, or KNN classifiers; we set No = 10 for the number label queries used to initialize Q (z s), and set significance level a = 0.05.
6.1 Experiments on Synthetic Datasets
Our first suite of experiment results is generated from synthetic data. We create synthetic datasets that comprise two samples data to simulate cases under the null hypothesis Ho and the alternative hypothesis Hi; the data for the first sample (Z = 0) is generated from (s == 0) = N ((-6, 0) and the data for the second sample (Z = 1) is generated from ( Z 1) 1) = A ()). In addition, we set P(Z = 0) from 0.5 to 0.8 to vary the ratio of the data sizes for two samples. For the simulations of the data under Ho. set 8 = implying there is difference between the distributions that generate the two samples; for the simulations of the data under H4, we vary d from 0.2 to 0.5 to simulate two samples from small to high discrepancy under Hi. Having constructed the data-generating process, we simulate 200 cases of data for each pair of P(Z 0) and å under H1, and simulate 500 cases of data for each pair of P(Z 0) and å = 0 under Hg. Each case of data is size 2000 with labols maskod, resulting in an unlaboled set S, with |S.| = 2000. The proposed test actively and sequentially labels feature in S,, to test. the difference between the two samples.
12

---

Published in Transactions on Machine Learning Research (June/ (2044)
Figure presents the empirical Type errors: when Hg is true, the probability of the proposed test mistakenly predicting the two samples is generated under H1. As observed, the empirical Type I crrors are all smaller than a = 0.05 for using various classifiers and label budgets in the experiments; this provides empirical evidence for Theorem 5.1 which states that the Type error is controlled to be smaller than the significance level a.
0.20
n2-01-0.30
21-0010060
912:01:0:70
0.15
21--01-4.0
0.0.09
0.10
Table presents the empirical Type II errors: when H1 is true, the probability of the proposed test and the baseline test mis- takenly predicting the two samples are generated under Ho. Table 2 presents the average label queried spent to reject Ho when H is true. We can observe from Table that the pro- posed test produces lower Type II errors than that of the baso- line under different. classifiers and label budgets; furthermore, in Table 2 observe the proposed test spends smaller num- ber of label queries than the bascline test. Additionally, we run two-sample t-test to assess the mean difference of label query numbers generated by 200 runs using both methods. The resul- tant p-values, truncated to the last 6 decimal places, all equate zero, indicating that the label spent by our framework is statisticalyy smaller than the baseline test. All these observations demonstrate that, under H1, the proposed test labels the features that have high dependency labels to effectively decrcase the Type II error and reduce the number of label queries needed to reject Ho.
0.05
0.00
250
500
750
1000 1250 1500 1750 2000
Figure 2: Under Ho in which 8 = 0, em- pirical Type I errors of the proposed test for different P(Z = 0) when using the lo- gistic regression to build Q(z s). All Type errors are smaller than 0.05, which agrees with Theorem 5.1
Table 1: Under H1, Type II crrors conducting the proposed/bass /bacllasccnneee with various classifiers and label budgets for the synthetic data generated by setting å = 0.2 and different class priors P(Z = 0). Due to the active query, our test produces lower Type II errors than the baseline for various label budgets.
P(Z = 0)
Logistic
KNNN
Label budget
200
400
600
800
1000
200
400
600
800
1000
0.5
Baseline
0.82
0.53
0.29
0.11
0.04
0.95
0.77
0.50
0.28
0.14
Proposed
0.16
0.02
0.00
0.00
0.00
0.49
0.17
0.06
0.03
0.01
Baseline
0.80
0.50
0.23
0.12
0.06
0.95
0.77
0.48
0.29
0.14
0.6
Proposed
0.26
0.06
0.01
0.01
0.01
0.59
0.26
0.09
0.03
0.01
Baseline
0.81
0.56
0.34
0.22
0.10
0.96
0.81
0.58
0.36
0.28
0.7
Proposed 0.26
0.04
0.01
0.01
0.01
0.71
0.33
0.14
0.04
0.02
Baseline
0.88
0.73
0.56
0.35
0.21
0.98
0.90
0.77
0.59
0.48
0.8
Proposed 0.38
0.10
0.04
0.03
0.02
0.80
0.50
0.28
0.16
0.10
Table 2: Under H1, average number of label queries needed to reject Hg for the proposed bepoosedbbaslineeee test using various classifiers and label budgets in the synthetic data generated by setting 6 = 0.2 and different class priors P(Z = 0). Due to the active query, our test spends fewer label queries to reject Ho than the baseline for various label budgets.
PIZ 03
Lagistic
KNN
Label budgee
200
400
800
1000
2001
100
600
800
1000
0.5
Buseline
183-5+41
319.7-113
359 1+188
439.1-233
451 4-4277
198. 1++10
374.4-61
500.++132
578. 1-201
619.5-2254
Proposed
95.3+66
108.1492
108.6=00
108.6+93
108.6=03
162.1=X0
223.1=116
240.8+140
249.7=177
252.8+184
Baselie
162.5141
312.4=116
066.01184
119.7-251
139.01266
196.7116
$75.7166
499.31194
578.91206
619.71256
0.6
Proposed
107.9:700
134.24114
142.8=136
145.74142
144.7=147
166.3:48
246.8=123
282.2:175
294.3:1200
296.61227
0.7
Baseline
1840014
523.32113
415.51188
472.2-252
506.01299
198.3111
378.5158
520.0.127
613. 41:19
678.11268
Proposed
120.4:077
143.41100
147.6=117
149.0:122
150.0=128
178.0=43
282.2:1117
827.
345. 9:2701207
351.71222
0.8
Baseline
190.81:31
351.7196
479 67:
571.1=245
628 008.013006
199.0118
386.61:47
555. 155.0.1106
669. 159.51175
798. 288.411533
Proposed 134.7:664
174.84118
189.5
195.64:170
199.7=196
184.4=33
310.2:1111
387.7+188
434.7+247
462.64-250
13

---

Published in Transactions on Machine Learning Research (June/ 20044)
We present the average number of label queries spent for two samples with small to big discrepancies under H1 in Table 3 A small discrepancy between two samples indicates more difficult. two-sample testing problem than one with a large discrepancy between the two samples, as a two-sample test requires more data to test the existence of the small discrepancy. Table X shows that the proposed active sequential test spends fewer labels to reject Hg when increasing the mean discrepancy 8 belween two samples, which demonstrates the proposed sequential test automatically adapts the number of label queries the problem's complexity.
Table 3: Under H1 and label budget N₂ 1000, the average number of label queries needed to reject Ho for different 8. When the mean difference ò increases between two samples, both our active sequential test and the baseline test reject Ho with a reduced mumber of label queries spent, exhibiting the sequential test's benefit that the tests adapt the label queries to the problem's complexity, Due to the active query, our test spends fewer label queries to reject H2 than the bascline for various 6.
P(Z 0) 0)
Logistic
KNN
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.5
0.5
Baseline
451.4+257
178.3+105
101.0=588
63.9+332
619.5+224
187.8+119
167.4+70
116.8+443
Proposed
108.6+933
37.3++22
24.3+10
19.7=5
252.8+184
109.5+64
72.2+333
54.9++20
Haseline
439.0+-266
175.3+118
96.9+65
65.5+-40
619.7+256
289.8+ 139.8+130
170.2+72
116.2+44
0.6
Proposed 144.7+147
40.5++30
24.9+11
20.1+7
296.6+200
134.3+88
84.3+-43
58.3+25
Bascline
505.01200
223,61145
115.7170
75.71:47
678.11 16:268
349.311778
108.2:99 21:93
133.3156
0.7
Proposed 150.0+128
57.1++42
32.3+21
22.2+88
351.7+-222
160.2+107
94.0++54
67.0++30
Bascline
628. 306
278.11177
149.3:15
94.8:55
798. 45:
470.311223
268.71122
176.3181
0.8
Proposed
199.71186
66.7141
40.0122
29.4:15
462. 462.612003
198.81143
115.7465
83.81466
6.2
Experiments on MNIST
In addition to the syuthetic datasets, We simulate the cases of Ho and H1 with MNIST (LeCun 1998). To create case for Ho, we randomly pick one digit category from 0-9, then randomly sample images from the selected digit category, and lastly divide the images to sample zero (Z- = 0) and one (2 = 1) based on a pro-defined class prior P(Z = 0); for each case, the two samples contain data from the same digit, but the digit categories could be different over cases. To create case for Hi, we randomly pick two different digit categories from 0- 9, then sample images from one digit category and place the images to sample zero (Z= = 0); to create sample one (Z = 1), we sample images from the two digits, mix the sampled images, and place them to sample one. We set the mixture ratio 0.7, meaning there are roughly 30% data in sample one generated from distribution different from sample zero. We also adjust P(Z 0) to create cases with different ratios for the size of sample zero over sample one for H1 We produce 500 cases for Ho and 200 cases for H, with the stated procedure for each P(Z = 0) that ranges from 0.5 to 0.8; each case comprises an unlabeled set S, with a size of 2000 and its corresponding labels that are unknown to an analyst. Instead of using the raw data the created cases, we projected the MNIST data to a 28-dimensional space by a convolutional autoencoder before conducting the two-sample testing.
0.20
PIZ-01-6
P1-0016660
PZ-001-077
0.15
NZ-0110080
0.0.05
0.10
0.05
0.00
250
500
750
1000
1250
1500 1750 2000
Figure 3: Empirical Type I errors of the proposed test for different P(Z = 0) in the MNIST experiment. SVM is used to build Q(z s). All Type errors are smaller than a 0.05, which agrees with Theorem 5.1
We first present the empirical Type I errors in Figure 3 We use the support vector machine (SVM) to build Q(= s) lo generate the results. As observed, all the Type I errors are smaller than a = 0.05, which agrees with Theorem [5.]] In addition, we present the Type errors, as shown in Table [ The proposed test generates smaller Type II crrors than the bascline sequential test for various classifiers, label budgets, and P(Z- = 0), implying the proposed sequential testing combined with the active query is effective. This is further corroborated by Table 5 that exhibits the average number of label queries needed to reject Ho:
14

---

Published in Transactions on Machine Learning Research (June/ /2044)
the proposed test spent fewer label queries than the baseline test to reject Ho. We additionally run a two- sample t-test to statistically compare the mean difference between the label query numbers generated by both methods. The resultant p-values, truncated to the last 6 decimal places, all equate to zero, indicating that the label spent by our framework is statistically smaller than the baseline test in the MNIST experiment.
Table 4: Under H1. Type II errors of conducting the proposed/baselingg with various classifiers and label budgets for MNIST and different class priors P(Z = 0). Due to the active query, our test produces lower Type II errors than the baseline for various label budgets.
P(Z 0)
Logistic
SVM
KNN
Label budget
200
400
600
500
1000
200
400
600
800
1000
200
400
600
800
1000
0.5
Baseline
0.65
0.21
0.02
0.01
0.01
0.59
0.07
0.00
0.00
0.00
0.84
0.43
0.15
0.07
0.03
Proposed
0.12
0.01
0.01
0.00
0.00
0.12
0.03
0.01
0.01
0.00
0.10
0.01
0.01
0.00
0.00
Baseline
0.59
0.16
0.02
0.01
0.01
0.55
0.01
0.00
0.00
0.00
0.89
0.43
0.15
0.06
0.03
0.6
Proposed
0.01
0.00
0.00
0.00
0.00
0.06
0.01
0.00
0.00
0.00
0.06
0.02
0.01
0.01
0.00
Roseline
0.58
0.21
0.04
0.01
0.00
0.67
0.15
0.01
0.00
0.00
0.91
0.58
0.29
0.10
0.04
0.7
Proposed
0.00
0.00
0.00
0.00
0.00
0.10
0.01
0.00
0.00
0.00
0.12
0.03
0.01
0.00
0.00
0.8
Baseline
0.66
0.24
0.04
0.01
0.01
0.77
0.32
0.10
0.01
0.01
0.95
0.71
0.47
0.27
0.12
Proposed
0.00
0.00
0.00
0.00
0.00
0.06
0.01
0.00
0.00
0.00
0.14
0.03
0.01
0.01
0.00
Table 5: Under H1, average number of label queries needed to reject Ho for the proposed/ proposed/baselinee baseline test using various classifiers and label budgets for MNIST and different class priors P(Z = 0). Due to the active query, our test spends fewer label queries to reject Hy than the baseline for various label budgets.
112 19
Logie
8984
KSN
20
2017
100
370
1100
335
100
500
Hundiac
MAc3ate
201
35S02209
35502220
355
3570
$33.32255
Hootin
101N116
203111
2013 176
251
15121101
1151130
3ESTIT1
30511175
Propeoal
01.7
61.7541
81.754
01.7
41.7=43
78.45
58.2=600
58.4552
58.4-13
S9.4
$5.0249
50.0=35
04.0255
05.0250
50.62.05
07
Propeoal
Hasilta
19131156
06.3156
25:81138
40.2-25
40-2-25
40.2-20
25.1 155
46.2 28
747150
25212316
59.0-76
3515130
68.0431
38123335
68.0-5)
355-11303
$9,0-511
50.3-54
101.8555
336.259
104.6:55
106-1:101
105. 1:101
0SE11225
26135128
38312:33
2713:375
10:8:10
367.1:75
3T2.7205
17228:85
582.5:25
383.1276
473.92190
546.7:220
575, 375-412233
Pripeea
6.3 Experiments on An Alzheimer's Disease Dataset
Table 6: Under H,, Type II errors of conducting the proposed/basseling baseline with various classifiers and label budgets for ADNI and different class priors P(Z = -). Due to the active query, our test produces lower Type II errors than the baseline for various label budgets.
PIZ= 0)
Logistic
SVM
KNN
Label budget
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
0.5
Baseline
0.32
0.06
0.01
0.00
0.00
0.67
0.17
0.02
0.00
0.00
0.72
0.49
0.25
0.13
0.04
Proposed
0.10
0.01
0.00
0.00
0.00
0.24
0.03
0.01
0.00
0.00
0.21
0.04
0.00
0.00
0.00
Baseline
0.35
0.04
0.00
0.00
0.00
0.62
0.15
0.01
0.00
0.00
0.73
0.25
0.06
0.01
0.00
0.6
Propased
0.07
0.00
0.00
0.00
0.00
0.18
0.04
0.03
0.00
0.00
0.10
0.01
0.00
0.00
0.00
Baseline
0..0
0.10
0.01
0.00
0.00
0.65
0.21
0.06
0.00
0.00
0.81
0.36
0.12
0..44
0.02
0.7
Proposed
0.11
0.03
0.00
0.00
0.00
0.32
0.07
0.02
0.01
0.01
0.25
0.04
0.01
0.00
0.00
Baseline
0.52
0.23
0.07
0.01
0.00
0.89
0.53
0.27
0.07
0.02
0.90
0.59
0.25
0.16
0.07
0.8
Propased
0.28
0.01
0.00
0.00
0.00
0.49
0.15
0.06
0.08
0.01
0.38
0.10
0.03
0.01
0.01
We demonstrate the utility of the proposed test in a clinical application using data from the Alzheimr's Disease Neuroimaging Initiative (ADNI) database (Jack Jr al. 2008). The ADNI study protocol was approved by local institutional review boards (IRB). All the personal information in the data provided to researchers has been removed. The motivation for applying the proposed test to Alzheimer's disease research is as follows. Amyloid has been linked to the development of Alzhcimer's 's discasc; identifying the amount of amyloid in the human brain is an important step in predicting the progression of Alzheimer's disease. To measure the amyloid level, an expensive CT scan is required used to assess the amyloid deposition in the brain. A useful replacement would be an casy-to-measure and inexpensive replacement for the amyloid to indicate the progression of Alzheimer's discase. In the following experiments, we considered using digital test results that include five cognition measurement scores of participants as a replacement. To verify if the
15

---

Published in Transactions on Machine Learning Research (June/ (2044)
digital test results are suitable replacements, clinicians are seeking approach to test the independence between the digital test results and the amyloid amount with a limited number of expensive CT scans to measure the amyloid levels. We use a binary version of the amyloid level where Z = 0 and Z = 1 suggest low and high amyloid depositions in the brain respectively; we can now formulate a two-sample test and use the proposed scheme. As the results show, our proposed test is endowed with sequential decision-making and active label query, resulting in fewer CT scans needed compared with the conventional sequential test.
Table 7:
Under H1, average number of label queries needed to reject Ho for the proposed/ hoposed/basseine baseline test
using various classifiers and label budgets for ADNT and different class priors P(Z = 0). Due to the active query, our test spends fewer label queries to reject Ho than the baseline for various label budgets.
Legotic
SVM
KNN
Leael Iragen
199
201
100
100
200
309)
320
100
2001
1991
49)
0.5
Esveliie
207-51
120-1105
136-1-20 20
10011150
11581105
1515: 103
195-5-101
Propored
43.8
47.1 133
47.1137
07.1.25
47.1.37
61.0
75.1 47
70.5.31
76.6.10 52
76.0.55
89.31-22
76.8.13
77.8.111
77.8
77.81:1
Exeline
800051
1011377
16.155
2533123
12101.35
12733.81
122.3157
9273.15
100:31.1
18301.80
19631:77
Propened
43.0-20
45.0=13
46.9422
45.3430
45.9-13
01.3-36
70.0-14
72.0=74
74.3-0
74.040
60.8=30
64.4=10
04:4-10
64.4+100
01:1200
Propored
63,0=12
72.0=4
72.0645
78.2045
72.2-40
90.1=30
108.0.37
108.1575
191.9:80
194.0:38
102.4:57
108.0553
104,0568
The obtained ADNI data contains both digital test results and the amyloid amount of participants. We use the cut-off value suggested by ADNT and binarize the amyloid amount to create two-sample cases where s denote a vector of cognition measurement scores and z denotes low or high amyloid amount for the participants. We create 200 data cases for each P(Z = 0) that ranges from 0.5 to 0.8; these cases are simulations for H1, and each case comprises an unlabeled set S, with a size of 1000 and its corresponding labels that are unknown to analyst.
Table 6 and Table 7 present the results of empirical Type IT errors and the average number of label queries needed to reject Ho- Our proposed test has Type 1l errors decreased by 58% and saves on label queries by 62% at most compared with the bascline test with the same label budgets. Additionally, we run a two-sample t-lest to statistically compare the mean difference between the label query numbers generated by both methods. The resultant p-values, truncated to the last decimal places, all equate to zero; this indicates that the label savings are statistically significant.
7 Conclusion
We propose an active sequential two-sample testing frumework that sequentially and actively labels the data to increase the testing power and adapt the number of label queries to the problem's complexity. We provide both finito-sample and asymptotic analysis of the proposed framework; the framework's benefit is characterized by the change of the mutual information between feature and label variables over a random labeling scheme in both finite-sample and asymptotic cases. Morcover, suggest instantiation of the framework, in which we adopt the bimodal query that labels the features predicted by classifier to have the highest class one or zero probabilities. Our experiments on synthetic data, MNIST, and an Alzheimer's Disease dataset demonstrate the effectiveness of the suggested instantiation of the proposed framework.
Acknowledgement
This work was funded in part by Office of Naval Research grant N00014-21-1-2615 and by the National Science Foundation (NSF) under grants CNS-2003111, and CCF- 224-222.
References
Aaditya Ramdas. Martingales, ville and doob, 2018.
https://www.stat cmu, cmm.eeuu/aaaadda
Akshay Balsubramani and Aaditya Ramdas. Sequential nonparametric testing with the law of the iterated logarithm. Xixiv preprint ar 1506 2015.
16

---

Published in Transactions on Machine Learning Research (June/ (2044)
Stuart A Bessler. Theory and applications of the sequential design of experiments, k-actions and infinitely many experiments. part i. theory. Technical report, Stanford Univ CA Applied Mathematics and Statistics Labs, 1960.
William J Blot and Duane A Meeter. Sequential experimental design procedures. Journal of the American Statistical Association, 68(343):586-333 1973.
Herman Chernoff Sequential design of experiments. The Annals of Mathematical Stafistics, 30(3):755 770, 1959.
JL. Doob. Jean ville, étude critique de la notion de collectif. Bulletin of the American mathematical society, ::(11):824 824, 1939.
Boyan Duan, Aaditya Ramdas, and Larry Wasserman. Interactive rank testing by betting. In Conference on Causal Learning and Reasoning, pp. 201-235. PMLR, 2022.
Olive Jean Dunn. Multiple comparisons among means. Journal of the American stalistical associalion, 56 (293):52 64, 1961.
Rick Durrett. Probability: theory and ezamples, volume 49. Cambridge university press, 2019.
Jerome H Friedman and Lawrence C Rafsky. Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests. The Annals of Statistics, pp. 197-717, 1979.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-7735 2012.
László Györfi, Michael Köhler, Adam Krzyžak, and Harro Walk. A distribution-fre theory of nomporametric regression, volume 1. Springer, 2002.
J Hajnal. A two-sample sequential t-test. Biometrika, 48(1/2):65-75, 1961.
Te Sun Han. Hypothesis testing with the general source. arXiv preprint math/0004121, 2000.
Te Sun Han and Sergio Verdú, Approximation theory of output statistics. IEEE Transactions Information Theory, 39(3):752-772, 1993.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1):3487 3602, 2015.
Harold Hotelling. The generalization of student's ratio. In Breakthroughs in statistics, pp. 54-65. Springer, 1992.
Clifford R Jack Jr, Matt A Bernstein, Nick C Fox, Paul Thompson, Gene Alexander, Danielle Harvey, Bret Borowski, Paula J Britson, Jennifer L. Whitwell, Chadwick Ward, et al. The Alzheimer's disease neuroimaging initiative (ADNT): MRI methods. Journal of Magnetic Resonance Imaging: An Official Journal of the International Society for Magnetic Resonance in Medicine, 27(4):685 691, 2008
Ramesh Johari, Pete Koomen, Leonid Pekelis, and David Walsh. Always valid inference: Continuous moni-
toring of a/b tests. Operations Research, 1006)11806-1821, 2022.
Robert Keener. Second order efficiency in the sequential design of experiments. The Annals of Statistics, pp. 510-532, 1984.
Kiefer and J Sacks. Asymptotically optimum sequential inference and design. The Annals of Mathematical Statisties, pp- 705-750, 1963.
H Koga et al. Information-spectrum methods in information theory, volume 50. Springer Science & Business Media, 2002.
Yann LeCun. The mnist database of handwritten digits. hltp://yarmn lecun. com/erdb (erdb/mmist// 1998.
17

---

Published in Transactions on Machine Learning Research (June/ /2044)
Alix Lhéritier and Frédéric Cazals. A sequential non non-parametric multivariate two-sample test. IEEE Trans- actions on Information Theory, 64(5):3361-333) 2018.
Weizhi Li, Gautam Dasarathy, Karthikeyan Natesan Ramamurthy, and Visar Berisha. two-sample test. In Uncertainty in Artificial Intelligence, pp. 1168 1177. PMLR, 2022.
A label efficient
David Lopez-Paz and Maxime Oquab. arXi::1610.008: 661.0665,, 2016.
Revisiting classifier Iwo-sample
tests.
arv preprinl
Steven J Miller. An introduction linear programming. lecture notes, 2007.
Mohammad Naghshvar and Tara Javidi. Active sequential hypothesis testing. The Annals of Statistics, 41 (6):2703 2738, 2013.
Teodora Pandeva, Tim Bakker, Christian A Naesseth, and Patrick Forré. E-valuating classifier two-sample tests. arXiv preprint arXiv:2210. 13027, 2022.
Aaditya Ramdas, Peter Grünwald, Vladimir Vovk, and Glenn Shafer. Game-theoretic statistics and safe anytime-valid inference. arXiv preprint orXi::2210.01948, 2022.
Shubhanshu Shekhar and Aaditya Ramdas. Game-theoretic formulations of sequential nonparametric one- and two-sample tests. arXiv preprint arXiv:2112.09162 2021.
Student. The probable error of mean. Biometrika, 6(1):1 25, 1908.
Vincent YF Tan al. Asymptotic estimates in information theory with non-vanishing error probabilities. Foundations and Trends@ in Communications and Information Theory, 11(1-2):1-184, 2014.
Jean Ville. Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):824, 1939.
Abraham Wald. Sequential tests of statistical hypotheses. In Breakthroughs in Statistics, pp. 256-298.
Springer, 1992.
Ronald L Wasserstein and Nicole Lazar The ASA statement on p-values: context, process, and purpose, 2016.
William J Welch. Construction of permutation tests. Journal of the American Statistical Association, 85 (411):693-66) 698, 1990.
Samuel S Wilks. The largo-sample distribution of the likelihood ratio for testing composite hypotheses. The annals of mathematical statistics, 9(1):60 62, 1938.
A Proof of Theorem 5.1 and Its Preliminaries
A.1 Some statistical preliminaries
In probability theory, sequence (.o.... Xn of random variables is called martingale if at particular time, the expectation of the next random variable is equivalent to the present observation; this is formally defined as follows,
Definition A.1. (Martingale) sequence of random variables (No, Xn} a martingale if, for any n 2 0,
E [|x,|]] $
(19)
[Xn Xn] X
(20)
We refer interested readers to (Aaditya Ramdas related propertics.
2018 for a complete introduction to the martingale and
Next, state Ville's maximal ieequllity Ville 1939
which will be applied to prove Theorem 5.1
18

---

Published in Transactions on Machine Learning Research JJune/0224
Theorem A.2. (Ville's Marimal Inequality Ville 1939)) ): any O, we have
If {X,} is nonnegative martingale, then for
R Xo
P sup > 0
(21)
R20
Ville's maximal incquality gives a probability upper bound for the event that the martingale crosses a threshold e; it is sequential exlension of Markov's inequality.
A.2 Proof of Theorem 5.1
Proof. Our proof comprises proving the following two ordered parts:
(1) The first part is to demonstrate that, under the null hypothesis Ho, the independence between unqueried label random variables and the corresponding foature random variables still holds following the adaptive label query. In particular, Under Ho, the feature and label variables S; and Zi used to construct the test statistic in equation in the proposed framework are independent e E [Ng]]
(2) In the second part, we consider W,, II== P(Z.) Q.(2,15,)) which is the test statistic in equation 2 with true
class prior P(z) plugged in. Moving forward, the second part is to demonstrate the following inqqualiiiss under Hu
P(Z,) S a s Po 3n E [Ng,, Wn II ==1 Qi [.)
P(Z.) Q:(Z:
Po 3E (N,,
II
Sa a
(22)
==1
equation 22 immediately implies that the Type I error of our proposed framework is upper-bounded by a.
Proof for the first part
We write S, and Z, to denote the sets of original unlabeled feature variables on analyst's hand and unrevealed label variables provided by an oracle. We write S and z to denote the sets of the labeled feature and the corresponding label variables after including the i-th (S,, Z,) to construct the statistic in equation 3 We use S.¹ = S, ) S and 2," Z, \ Z to denote their complements that comprise unlabeled feature and unrevealed label variables. In particular, we use S and Z to denote the feature and label variable sets used initialize Q1 (z s) in the first place; Sjj S. SS) and Zii Zu \ Z/j are their complements that comprise unlabeled feature and unrevcaled label variables. Ho being true implics Su 1 Zu. In our setting, an analyst randomly samples features and labels them to build Sy and Z/-. implying S II 2/ and Sø 1. zø when Ho is true. In the following, we employ the induction method to prove S, and Z; are independent Vi E [Ny]-
Base case (i (i= 1): Under Ho, we have S/ IL 2/ and Sp 1L 2g. The analyst first initializes Q1(2 s) with St IL z before starting the sequential testing. Subsequently, the analyst makes a query on a label based on the prediction of Q1 s) and includes the first variable pair (S,, Z1) to construct the test statistic. That immediately implies S 1 Z1, S 1 z and ST 1 Z
Induction step: Suppose ST T z and 8 1 Z(, the analyst updates Qi-1 (z s) to Qi (z s)) with Sy 1 Z and S 1 2/ makes a query ou a label based on the prediction of Qi(= s) and includes the (i+1)-th variable pair (S.+1, Z++1) to update the statistic. That immediately implies S,+1 1 Z 8h,, 1 2 and 8/41 1 2/41-
Combining the base step and the induction step leads to S. Z, vi [N₂] under Ho-
Proof for the second part Suppose ((s, (())) a sequence of realizations of ((S, 2) collected under Ho and the proposed framework. We use & denote a class-one prior probability parameter, and hence P (22...., 2n Ø) is a likelihood function of é. Maximizing P P(z), =n Φ) over the prior parameter & leads to the solution
6" Dis In other words, P (2),-.. zn 1 10) = =II. P(zi) is a maximized likelihood obtained from (#))L where o² P(Z 1). We use P(Z 1) to denote the true prior-one probability under Ho.
19

---

Published in Transactions on Machine Learning Research (June/ 22044)
and plugging P(Z =) to & leads to the true likelihood IT. P(z+) for (2))-1 under Hg. It is easy to see Ih P(a)) IT, P(z,) thus I P(a)) IT;=1 (:(=;)8;)
P(a.)
for any realization (zi) of (Z:) under Ho.
As result, we have Po 3n E [N,), W II Q1-1(2.13.)
P(Z.)
P(Z.) S a S Po A,, Wa = I[ Q.-1(2.(5.) S $a)
Lastly, we prove Po 3n, Wn Ih= (2-1(2.)s,) S 5a) S a. We let W = W. Therefore, W
P(Z,)
Wh11 1.11..1.... with W 1 for n E [Ny]. The sequence (W))== a non-negative martingale
P(Z,) under Ho given
Qu( Sp))
E W"' W1, W Wh E
W n-1
W Wi.". W R--1
(23)
P(Zn)
Qn(Zn s.n)
W
n-1
P(Zm)
W W n-1
(24)
Qn- 17,, S.))
W
Σ
P(Zn
(25)
P(Zn = 2)
W
(26)
Using Ville's maximal inequality in Theorem
A.2
leads to the following: For any 0, we have
P
sup W nE[Na]
= a
(27)
W
1
=
sup
>
<
= a
(28)
W
nE[N)]
E
Wo
P
inf
Wn S
aa
(29)
nC(N.)
Therefore, we have Po (3n [N₂], Wn, II P(Z.)
sa) Po
3 [N₂) Wr =I[=_
P(Z.) (222.8)
S a
(2,
B Proof of Theorem 5.4
Proof. In the following, formulate optimization problem that seeks arbitrary marginal distribution g(s) to maximize the mutual information (MI) between S and Z, where (S, Z) ~ g(s)) (z s). Solving this
optimization problem leads to a consistent bimodal query (see Definition 5.2 asymptotically minimizing the test statistic in equation
Constructing an optimization problem that maximizes MI
We write (s) to denote an arbitrary probability distribution of s. Recall P(2 s) and p(s) that indicate the class probability given and a marginal probability distribution of s for the two-sample testing problem on the analyst's hand; we write g (s, z) = P(= |s) and G(z) = f (s, 2) ds to denote the joint probability distribution and the class prior for new two-sample testing problem with the original p(s) replaced by g()). The mutual information (MT) that characterizes the new two-sample testing problem is as follows
MI MI= Σ (G(z)) log (G(=))+ / (Σrte P(z 1( lo log (P s)) g(s)ds
(30)
2=0
We expand equation 30 and consider the following optimization problem,
(ʃ p( s)g(s)ds)
log (fDle (
/
max g(s)
Σ
Σ P(z s) log (P(z s)) g(s)ds
(31)
20

---

Published in Transactions on Machine Learning Research (June/ 20044)
In other words, equation 31 is secking an g(s) to maximize the MI of new two-sample testing problem with p(= s) provided by the original two-sample testing problem. In what follows, we will see that solving 31 leads to a probability distribution in which & consistent bimodal query (see Definition 5.2)
results, proving the asymptotic property in Theorem 5.4 Instead of directly solving equation 31 we fix G(Z 0) = f = 6)g(s)ds = u, and resort finding the solution of the following,
- /
[
Σ P(z 1)) log (P (z (s)
min ((
g(s)ds
(32)
/ P(Z s)g(s)ds u,
s.t.
(33)
/ ((s)ds= =
(34)
g(s) 2 2
(35)
Then, we approximate equation 32 with a discrete version of the same by partitioning the sample space S into balls {B (s,, !i in addition, L 2. Each B (s.r) {B (s;, r)) has radius r centering at leading lo an approximation P(z = 0/s) = f P(Z 0|s)p (s B(s, r)) ds, and a probability mass function
G(s) Ba. ds) Hence, we approximate equation 32 by the following linear programming (LP):
min G(s)
Σ H((Z)G(s:)
(36)
s.t.
Σ
P(z 01 s:)G(s:) = u,
(37)
Σ G(s.) =
(38)
1=1
G(s;) 2 vi E [T].
(39)
where H2(Z) E' P(2 (() log (P(2 si)) vi [L] indicates constant coefficients in the LP in equa- tion 36
Solving the optimization problem The constraints in equation 37 and equation lutions to the considered LP in equation s non-negative and s satisfies equation more definition of one kind of solution to the system of lincar equations, which is well-known lincar algebra.
38 construct a region of feasible so-
36
we
write this region U {s In addition, we need to make one
37 and equation
3$
Definition B.1. (Basic solutions) Let Ax be a system of linear equations. Let {x x be positive and other entries be zero in x. Then, if the corresponding columns A AA, are linearly independent, then is basic solution to the system.
Moreover, we will need to apply the following Theorems to derive the optimal feasible solution for the LP.
Theorem B.2. If the feasible region of an LP is bounded, then at least one optimal solution occurs at verter of the corresponding polytope (or the feasible region).
Theorem B.3. Let U be the feasible region of linear progrum. Then, x E U is basic feasible solution if and only if x is a vertex of U.
Theorem B.2 and Theorem B.3 are well-known in LP; we refer interested readers to MMiller 2007 for the elaboration their proofs. Theorem B.2 and B.3 suggests one optimal solution of equation 36 is vector
21

---

Published in Transactions on Machine Learning Research (June/ /2044)
(G() ((s)),))...Gss))) with at most two non-zero entries. Herein, write G( and G((s)) to denote the two non-zero entries. That reduces the LPP in equation 36 to the following:
((Σ
max 80:91
(= Sno) log ((z / (m))
G GS ) +
Σ
P
Set log P(= 2 son)
(8m1)
(40)
2=0
s.t. PZ = 01 Sqn G (8go)
P Sqz G (Sg.) u,
(41)
(0 + G(sm) = 1,
(42)
((S 2 0, ((.))) 2 0.
(43)
For the sake of simplifying the expressions in what follows, we write
Tu P (Z Sgo log P Syo
(1- pZ Syp) log
P(Z / 0 S
(44)
T P (Z /ug log P (Z 8up
+
(1- 8 ))
log
P(Z = 0 1.48)
(45)
T- = P (Z = Sq log P (Z = 540 +
(1- P1-P(Z= = 5q.))
log
1- P- = 0 8
(46)
T3 = P (Z = gq log P IZ = Sqy) +
(1 p( = $gp))
log
P(Z = 0 8gg
(47)
Then, equation 40 is re-expressed by the following.
To u1 P (Z = P 8q4))
Ti (f(z =0 8yp =0(8.g)
max
(48)
90.41 P (Z= 0 8 P(Z = 18
P 8.))) P(2 = 0 1
S.I.
( 0 8%)) P (z 0 8m 0,
(49)
p = 0 Sqp S u,
(50)
P (Z O 8go ) 2
(51)
an optimization problem that finds P((z s,o),, (nnn c (P(() s))R maximize the objective function. Herein, we write
equation
48
To
== Pz = 0 S.y)
(52)
P Smy)
B P -0 0
(53)
Ti
C = P(Z = 0 (.. - P (Z 0 Sq,)
(54)
D = P(Z 0 8pp
(55)
22

---

Published in Transactions on Machine Learning Research (uuee/2024
Now, we analyze the derivatives of equation 48 by checking the partial derivatives of A, B, C and D with respect to P(Z= = 0 8oo) and P (Z = 0 )
0A
-T2
2 > 0,
(56)
AP (Z 0 $qp)
(2 8gp - p =0 18111
0A
To
2 < 0,
(57)
aP (Z =0 Sqy))
(P(2=0) (0 8g0) - P P(. =0 0 8
0B
=-1,
(58)
OP (Z =0 0 8q:))
aC
T
2 >0,
(59)
OP (Z = 0 (no)
(P 8y0) - P (z = 0| 882)))
ac
T3
<0,
(60)
OP (3 =0 8qy))
(? = 0 (0o) 000))))))))))))))))))))))))))0 P(z 01 sun 1)2
0D
1.
(61)
OP (Z- 0 Snp)
Therefore, equation
48 is a function that monotonically increases with increasing p - 0 sgo) and
decreasing Pz = 0 mass function G
8qp ). implying that the optimal solution to equation 36 has the following probability
- PZ = 0 (gg)
G (8gg)
8yo arg max P = 0
(62)
P(Z = 0 80p) - P( = 00 Sm)
p(Z = 0 80)
G* (5 Pz =0 8np) ) - P (2 = 0 8.)
Sq. arg max (Z = 1 11 s)
(63)
(*)ss = 0, Vss E (s {s Sqn }.
(64)
Recall that LP in equation 36 approximates the continuous optimization problem in equation 32 by partitioning the sample space S to (B(s,, / Hence, by shrinking the radius r infinitely close to zcro, we get the optimal solution p" (s) of equation 32 as follows,
D" (5))) PZ = 0 Sq))
S.o = arg max P P(Z = =)ss), Sn = arg max P = =||s),
(65)
p" (5q) P(Z 00 8go) - u
8
(s() = 0, Vs E S (5ppp:
(66)
Varying u leads to the optimal solution with the same form that ps(s) = 0, Vs E S \ {s 8qs }
and p" (8)o) > 0,p" (8t) > 0, but different ratio z' p'(w)))
(*())) Furthermore, there could exist set Sgo (0 (Z = 0 my)) = max P p(z 0 {}} with identical P(z ssp); and so does Sn, (sg, PZ sq.) ) = m P (Z 1 s)} for the case of Sqi- Hence, the optimal solution to the original optimization problem in equation 31 has the following form
p² (s) = 0, SA E \ (S USm) and p" (s) > 20 E US.:
(67)
S. = SIo
P(Z = =0| (yo) max
P = 0 0 SES
(68)
Sn = Sq P 2 = 1|s = max P = 1 s)
(69)
8ES
Therefore, there exists a consistent bimodal query resulting in an asymptotic distribution of the labeled feature variables admitting p" (s) (equation 67 to equation 69 to maximize MI and hence minimize the negated MI with P (= s) provided by the original two-sample testing problem.
23

---

Published in Transactions on Machine Learning Research (June/ 2204))
C Proof of Theorem 5.10
Proof. Testing power of the baseline case: As the baseline case randomly samples features from S, and queries their labels, then the resulting variable pair (S,, Zn) collected by the analyst admits p (s, 2), Vn e [Ng], in which p (s, 2) is the joint distribution that characterizes the original two-sample testing problem. In addition, Q (= s) is initialized and stable, and the class-prior P(Z = 0) is provided the case study. Given the label budget N₂ and the significance level a, we have the following inequalities for the testing power the case study:
N₂
P(Z.) (Z S.)
P(Z.)
Pi 3n (N₂), W II
Sa PI
WN, II
S (S... Zn) (s, (70) QZ S.)
The inequality in equation 70 is derived from sequentially comparing with a, Vn E [Ng]] leading to higher testing power than only comparing wn with a at n = Ng- We subsequently convert. RHS of equation 70 as follows,
N
P(Z.) Qo (Z: S
log (WN.) Ng
Σ log
P(Z.) Q(2,(;))
log (a) Ng
P WN, II
Sa Pi
(71)
Ng
Since {(S,, = is an iid. sequence, we skip in (S,, Z:) and analyze E (S, Z) ~ (s, 2) in the following,
P(Z) [(([)))
and Var
P(Z)
for
Q(2(S)
P(Z)
E log P(Z)
P (Z SS)
E log Q S)]
log
(72)
( S)
Q S)
=1 (S; Z) + DKL (P 8) ||Q (z s))
(73)
< (S; + VEIi
(74)
P(Z)
P(Z)
P(Z S)
Var
Var log
log
(75)
SZ)
PZ S)
Q (Z S)
P(Z)
Var log ( S)
P(Z)
P S)
< Var
log
+ 2
Var log P(Z [S)
Var log
P(Z) ()
Q S)
Q S)
(76)
2 + + 2a /e1-
(77)
The inequalities in equation
74 and equation
77 results of the following facts: é1
Max DKL2 (q (s, [|p (s, =) A) and o² max { (maxAep Var(s,2) T(; Z), Var(s.z)~p(e..)) 7(S
over the partition P (A..... A.).
Ng log 2i
PiZ.) ((9118))
It is observed that, in equation 71
log WN,)
is a sample mean of { Oog ((2.8))
PiZ.)
i=1'
hence we use the central limit theorem to approximate the distribution of log(W (o(W,,,) leading to the following,
N₂
Pi ( an [Ng] W,
P(Zz)
N₂
P(Z.)
II
QZ, S)) <a
2 Pi
WN, = II
1=1 QZ, S Sa
(78)
logo
/N, (I Z) Vei)
VN₂
(79)
(a2 + ve + +2 2//00)
24

---

Published in Transactions on Machine Learning Research (June/ 2004))
Testing power of the proposed framework in the case study: The analyst selects region A from partition p = {A:)= in which A" is predicted to have highest 7 (S; Z A*); then the analyst conducts
the sequential testing with (S., Zx) i..d. generated from p (s, A*). We first quantify / (S; Z A*) Recall
that the approximated MI { (S; Z
] used to find A E p is provided in equation 16 in the case
study; given Assumption 5.9 the discrepancy between true and approximate MI for any A E P 1s as follows
(S; 2 A) i (S; Z A) = ES-a(s|A) [Ez-Q(His) [log Q (Z S)] Ez~P(=[S)) (log (Z S)]]
(80)
Furthermore, given é2 = max AcP DKT,² (p (8, =) |1 (s.=) A) over the partition p = {AI,'-. :. Amh. we eval- uate the upper bound of equation 80 for any A E P in the following,
S~p((AA [E=((( [log Q [Z] S)] Ez-P(= llog P (Z S)]]
(81)
< Es ()p((A) [z~((=1)) [log Q (Z S)] [ZzQ(=(S)) (log P (Z S)]
(82)
= DKL (Q (=
s) P( s) A)
(83)
SVE2.
(84)
Similarly, we evaluate the lower bound of equation
80 for any A E P in the following,
E Es-n(s/A) A) [z~O(=[)) [log Q (Z S)] Ez Dlog P (Z |S)]]
(85)
[log P (Z S)]] > Es Eksup(s A) Ez~P(=Is) [log Q (Z S)] (zz
(86)
DKL (P(= s) [] s) A)
(87)
2 - VEI.
(88)
Assumption 5.8
suggests that the maximum MI over P is [(; + A. Combining equation 84 and equa- we get the lower bound of (S; A*) as follows,
tion 88
(S: 2 A 2 / (S: 2) + + (VEi VE2).
(89)
The analyst conducts the sequential testing in the selected A with sample features randomly sampled from A" SS and labeled, leading to the following lesting power lower bound
P(Z) Pi En N2J W. II QZ S,)
P(Z) sa 5a) (Sn, Zn) ~ ps, (s. AA). Q S2)
Sa
P WN, II
(90)
The quantification of the RHS in equation 30 is identical the one in the baseline case, except the sample space constrained to A". Hence, skip the derivation process and obtain the following result,
N₂ WN, II ==1
P. nm (N,),
P(Z:)
P(Z.)
II (Z: S,) Sa 2 P
S
(91)
Q S.)
loga
VN, (I (S: 2) A -2/T-- VE2)
VN.
$
(92)
(a2 - vai + 2/E1o)²
25


Reviews:
[{"review_id": "cXPO1QYzfO", "reviewer": "Reviewer_KN7Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe main strengths of the paper are:\n- The paper extends the typical sequential hypothesis testing framework to include active querying, addressing a real-world problem where labels are expensive to collect. This novel approach not only improves efficiency in label usage but also increases the power of the testing framework under label constraints.\n- The writing in the main paper is exceptionally clear and concise. The authors articulate the motivations, the theoretical advancements, and the introduction is very clear at highlighting the goal of the paper.\n- The experimental results highlight the efficacy of the proposed framework across multiple datasets, including synthetic data and real-world applications like MNIST and Alzheimer's disease datasets.\n- The paper provides substantial theoretical contributions, including the development of an anytime-valid p-value.\n\n## Weaknesses\n\nThe main weaknesses of the paper are:\n\n- While the paper cites relevant literature, it could better delineate its algorithmic  contributions relative to these works. Specifically, a more detailed discussion on how this framework advances beyond [Li et al (2022)].\n- The proofs provided in the appendix are somewhat terse and difficult to follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces an Active Sequential Two-Sample Testing framework, addressing two-sample tests where sample features are inexpensive to collect, but their associated labels are costly. At a high level, the goal is to determine whether the distributions generating two samples are identical.  The algorithm has access to a fixed dataset of unlabeled covariates, and can sequentially query their label over time in an adaptive manner.  The test statistic uses a combination of $(i)$ the likelihood ratio, and $(ii)$ probabilistic classification model.  The classification model is adaptively updated and used to predict features and determine the new data to query the oracle for its label.  The hypothesis test procedure produces an anytime-valid $p$ value.  Additionally the authors investigate the algorithm's power through studying the mutual information between features and labels as well as accuracy of the classification procedure.\n\nAt a high level, the primary contributions for the paper can be summarized as follows:\n- Extends the sequential hypothesis testing literature for two sample tests to consider the setting where the data labels need to be queried.  The authors additionally show that asymptotically the framework generates the largest mutual information between feature and label variables to help highlight its power.\n- The authors conduct extensive experiments across synthetic, MNIST, and Alzheimer’s disease datasets to demonstrate the practical benefits of the framework. Results indicate significant reductions in Type II errors and more efficient use of label queries compared to traditional methods.\n\n**Model:** There is a distribution $(S,Z)$ over feature label pairs.  The two sample testing problem consists of a null hypothesis $H_0$ that states that $p_{S | Z = 0} = p_{S | Z = 1}$ (i.e. the data label is independent of the features).  The algorithm is given a large set $S_0$ of sample features before performing the sequential test.  The statistician then sequentially queries a labelling oracle for the $z$ of each $s_u \\in S_u$ subject to a maximum number of queries $N_q$.  After querying a new $z_n$, the analyst needs to decide whether to terminate the querying process and make a decision (i.e. accept or reject the null), or continue with the querying process.\n\nThe test statistic is then:\n$$W_n = \\prod_{i=1}^n \\frac{\\hat{P}(Z_i)}{Q_i(Z_i | S_i)}$$\nand the procedure rejects the null whenever $w_n \\leq \\alpha$.  Note here that $\\hat{P}(Z_i)$ is just the empirical distribution over the labels and $Q_i$ is the fit classification model.  When picking the next datapoint to query with a fair chance either pick the point which maximizes $Q(Z = 0 | s)$ or $Q(Z = 1 | s)$ where $s$ enumerates over the remaining unlabelled points in the dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Clarifying Proofs**: While I am not confident in this literature, I found several of the proofs difficult to follow and introduce notation that is not properly defined elsewhere in the paper.  For example, in Equation 19 on page 16, $\\tilde{W}_n$ is introduced in the proof with no formal definition.", "broader_impact_concerns": "No broader impact statement is necessary since the authors provide a theoretical statistical testing technique.\n\n## Minor Comments\n- Bolded statement on page one is great, really helps highlight the high level goal and contributions\n- Figure 1 helps highlight the testing procedure, but would be helpful to introduce some of the notation (i.e. $z$ and $s$) earlier in the introduction to appreciate it more\n- Problem statement box in 3.2 is really helpful\n- Should define $P_0$ and $P_1$ formally at the bottom of page 4\n- Would be useful to introduce potential classification methods $Q$ after they are first introduced in page 5 instead of postponing until later in the paper\n- Some minor issues with capitalizing algorithm / equation throughout the paper\n- Missing space after $w_n \\leq \\alpha$ on bottom of page 6\n- Figure 2 vs Table 2 on top of page 11\n- Bolded results in table 2 / 3 when the confidence intervals are overlapping feels a bit disingenuous, should modify them to only bold if there is statistical significance \n- Issues with $=$ in the proofs\n\n## Questions\n- Surprised that Theorem 5.1 does not depend on the instantiation for the classification method $Q$.  Can you comment on why this is not directly needed to show the fact that the sequential hypothesis test is valid?", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UrpnV3dd44", "reviewer": "Reviewer_ZaZG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n-  The test procedure is simple and intuitive and works well in practice.\n-  Theoretically, it is shown to have control over the false alarm probability, and the improvement over the testing power is justified via both asymptotic and finite sample analysis.\n\nWeakness:\n- The finite sample analysis has too many assumptions that are hard to verify in practice. I feel that given these conditions, it should be straightforward to prove the claim, but the challenging part is to verify the conditions. I feel that the formulation of this analysis is a bit contrived.\n- The asymptotic analysis provides an intuitive way to understand the benefits of the proposed test in terms of the error exponent (i.e., the KL divergence between the null and alternative hypotheses), but it requires the labeled samples to go to infinite, which somehow contradicts to the idea of active learning to improve performance in finite sample regime.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new active sequential procedure to perform a two-sample test, where sample features are inexpensive, but their group labels are costly. The proposed test is based on the likelihood ratio between the estimated marginal distribution and a probabilistic model trained using currently available data. Theoretically, it is shown that the false alarm probability can be controlled by providing a valid p-value for all time steps. As for the testing power, asymptotic and finite-sample analyses are provided to demonstrate the gain in the information compared to the baseline method. Empirically, experiments on synthetic, MNIST, and application-specific datasets validate those theoretical claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am curious about one thing. When you run out of the labeling budget, instead of only using the labeled samples to compute the likelihood ratio, can we use the well-trained model $Q_{z|S}$ to generate pseudo-labels for the remaining unlabeled data and compute the test statistics? Can you provide either theoretical or empirical evidence to show it will be better or worse? In general, will there be any benefit of using this model to generate pseudo-labels for the two-sample test?\n\nIn Table 3, it is not clear to me why the average number of label queries as a function of $\\delta$ is not monotone. The maximum is achieved at $\\delta =0.3$. Are there any possible explanations?\n\n\nIt should be Figure 2 instead of Table 2 on the first line on Page 11.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i6JAA7oZFC", "reviewer": "Reviewer_n3Ux", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n-The authors introduce a new, natural, and interesting setting combining ideas in active learning and statistics. \n\n-The introduced method is \"robust\" in the sense that it remains statistically valid despite the dependence introduced by adaptivity and even if the initial $Q$ `belief’ function is wrong.\n\n-Mutual information is a natural quantity to characterize the gain of an active learning problem in this setting. Both this and the above require some non-trivial work to show.\n\n-While I am not qualified to review the experimental part of the paper, the methodology seems very successful in the simulated circumstances (beating baseline methods), including even on real medical data.\n\n**Weaknesses** \n\n-My only real complaint is that the `case study’ in section 5.4 where finite sample bounds are given (which is a bit more typical a setting for the machine learning literature) is not well motivated. In particular, it is very unclear what is going on with the partition of the unlabeled data set. Why is this here? Where is it coming from? Is the $m=1$ setting just the same as the prior setup, and this is a generalization? Please add some discussion on this.\n\n-I was initially somewhat confused about the assumption that $Q$ is already a good estimator of the joint distribution. If this is the case, then naively one would think you could simply look at $Q$ and determine whether the distribution is independent. The authors could be more clear about the benefits of their framework even when the estimator is already good (namely, if I understand correctly, this gives a way of statistically verifying the correlation).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce active sequential two-sample hypothesis testing. In this setting, a learner has sample access to a distribution over unlabeled features and corresponding labels, and wishes to test whether the feature and label spaces are correlated. In other words given a joint distribution **S** over data and **Z** over labels, distinguish between:\n\n$\\forall s,z: P(z|s)=p(s)p(z)$ and $\\exists s: P(z|s) \\neq p(s)p(z)$\n\nThe authors study a natural pool-based active variant of this model in which the learner is assumed to have \"pre-drawn\" a large database of unlabeled samples $S_u \\sim$ **S**, and may adaptively query for labels of points $s_u \\in S_u$ drawn from $p(z|s_u)$. This is a natural setting for applications in e.g. digital health, where a practitioner might want to use `cheap’ indicators (raw data like speech, gait, age…) rather than costly bio-markers/imaging (labels). An active test in this setting allows for practitioners to test such a correlation using many fewer expensive label queries.\n\nThe authors introduce a natural sequential testing algorithm in which the practitioner always queries the sample $s_u \\in S_u$ which she \"believes\" should maximize the conditional label probability $\\Pr(Z=1|s)$ or $\\Pr(Z=0|s)$, since these points contain the most information regarding correlation in the distribution. The practitioner’s `beliefs’ about such points are captured by a separate function $Q(z|s)$, which is pre-trained algorithm on a small initial sub-sample of data. The authors then track the statistic:\n\n$$W_n = \\prod \\frac{P(z_i)}{Q_i(z_i|s_i)}$$\n\nWhere $(z_i,s_i)$ are the adaptively observed labeled samples and $Q_i$ is the belief function run on the prior data to this point.\nThe authors prove that regardless of choice of $Q$ and the dependencies introduced by active sampling, $W_n$ is still an “anytime-valid p-value”, that is it satisfies:\n\n$$\\Pr( \\exists n: W_n \\leq \\alpha) \\leq \\alpha$$\n\nThus the practitioner can sequentially continue their test until they hit $W_n \\leq \\alpha$ while maintaining statistical guarantees.\nThe authors then show how the power of their framework is captured by the metal information between **Z** and **S**. In particular, in the asymptotic regime a normalized variant of their restriction converges to the mutual information. In the finite sample regime, the authors study a variant of their framework in which the practitioner has a partition of the unlabeled data, tests which subset of the partition has the highest mutual information, then performs the above sequential test. They show that if $Q$ is a good approximation for the true joint distribution, then the testing power of their active algorithm outperforms a standard `passive’ (non-adaptive) test by a factor of the mutual information.\n\nFinally, the authors run several experiments, over simulated data, MNIST, and on an Alzheimer’s disease dataset vs the passive sequential baseline and show that both type I and type II error incurred by a fixed label budget are significantly lowered using the active approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some small comments:\n\n$Q_n$ also needs to be defined more clearly and separately from the test statistic. It should not just be mentioned in the equation box for (2).\n\nSince TMLR is not a statistics journal, I suggest adding a prelims section with basic statistics terms, e.g. test power. These may not be as well known in the ML community and aren’t otherwise introduced.\n\n“parallel sequential testing baseline” is not defined in Thm 5.10", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The claims of the paper appear correct and the results are interesting.
Decision: Accept (poster)