The Cost of Replicability in Active Learning
Authors: Rupkatha Hira
Dominik Kau
Jessica Sorrell
Venue: Accepted by TMLR ()

Abstract: Active learning aims to reduce the number of labeled data points required by machine learning algorithms by selectively querying labels from initially unlabeled data. Ensuring replicability, where an algorithm produces consistent outcomes across different runs, is essential for the reliability of machine learning models but often increases sample complexity. This report investigates the cost of replicability in active learning using two classical disagreement-based methods: the CAL and A\textsuperscript{2} algorithms. Leveraging random thresholding techniques, we propose two replicable active learning algorithms: one for realizable learning of finite hypothesis classes, and another for agnostic. Our theoretical analysis shows that while enforcing replicability increases label complexity, CAL and A\textsuperscript{2} still achieve substantial label savings under this constraint. These findings provide key insights into balancing efficiency and stability in active learning.

Publishod Transactions on Machine Learning Research (01/2026)
The Cost of Replicability in Active Learning
Rupkatha Hira
rhira I @ig. edu
Department of Computer Science
Johns Hopkins Universily
substantial portion of the work for this project was completed while the author was at the University of Pennsglvania
Dominik Kau
dominitk edu
Penn Institute for Computational Science Universily of Pennsylvareia
Jessica Sorrell
jess Ressu, edu
Department of Computer Science
Johns Hopkins University
substantial portion of the work for this project was completed while the author was at the Universily of Pennsglvareia
Reviewed OpenReview: https: // openreview. net/ form/f id= Za Juq
Abstract
Active learning aims to reduce the number of labeled data points required by machine learning algorithms by selectively querying labels from ini- tially unlabeled data. Ensuring replicability, where an algorithm produces consistent oulcomes across different runs, is essential for the reliability machine learning models but often increases sample complexity. This report investigates the cost of replicability in active learning using two classical disagreeneent-based methods: the CAL and A algorithms. Lever- aging randomized thresholding techniques, we propose two replicable active learning algorithms: one for realizable learning of finite hypothesis classes, and another for agnostic. Our theoretical analysis shows that while enforcing replicability increases label complexity, CAL and A still achieve substantial label savings under this constraint. These findings provide key insights into balancing efficiency and stability active learning.
Introduction
Modern machine learning techniques have demonstrated an impressive ability to improve model performance by training on incrcasing amounts of data. While unlabeled training data abundant for many applications (e. g., text and image data sourced from the internet), obtaining large quantities of labeled data, required for classification and prediction tasks, can be prohibitively costly, For example, accurately labeling diagnostic imaging data requires medical expertise, so curating datasets for training medical risk predictors requires great deal of clinician time and effort.
In response to these challenges, active lcarning has emorged as a powerful approach to reduce the number of labeled samples required to learn a good model (Angluin, 1988; Cohn et al., 1994b). Active learning algorithms selectively query the labels (or predicates of the labels) of data points that are most informative, while also leveraging unlabeled data learn. A key challenge in active learning, with any learning framework, is ensuring the stability of results, which is crucial for the robustness and reliability of machine learning models. Stability,

---

Publishod in Transactions on Machine Learning Research (01/2026)
in the context of machine learning, refers to the insensitivity of an algorithm to perturbations in its training data. Informally, stability ensures that models do not overfit. their training data, and a varicty of stability notions have been studied for the purposes of guarantecing generalization to unseen data and privacy-preservation of training data (Bousquet and Elisseeff, 2002; Dwork et al., 2006; Shalev-Shwaree et al., 2010; Dwork et al., 2015; Bassily et al., 2016)-
In this work we consider the strong stability notion of replicabiityy, introduced in Impagliazzo et al. (2022). Replicability requires that running a learning algorithm twice, on two inde- pendent datasets drawn from the same distribution and with shared internal randomness across both runs, yields identical models with high probability (over the samples and internal randomness). Replicable learning algorithms not only generalize well under adaptive data analysis (Impagliazzo el al., 2022), but they also enable verification of experiments in machine learning. By publishing the randomness used to train a model, another team of researchers can obtain the same model, using their own data, removing ambiguity in whether or not a replication effort has been successful. These properties come at the cost of increased sample complexity, however. In the case of PAC learning, e. g-, it known that the sample complexity of replicable learners depends on Littlestone dimension, as opposed to VC dimension as in non-replicable PAC-learning (Ghazi et al., 2021; Bun et al., 2023).
In this work, we investigate whether techniques from active learning can be employed to reduce the sample complexity overhead of replicable learning. We develop the first replicable algorithms in the active learning setting, giving realizable and agnostic learning algorithms for finite hypothesis classes. We prove that, indeed, there are natural conditions on the target distribution and hypothesis class under which our algorithms enjoy sample complexity improvements over passive learning, establishing the utility of active label queries in replicable learning.
1.1 Our Results
We give the first replicable algorithms for active learning of finite hypothesis classes, in both the realizable and agnostic setting. The sample complexity bounds for our replicable algorithms show an improvement in sample complexity over passive Icarning analogous to known improvements from active learning for non-replicable algorithms. More precisely, for target error rate E, the sample bounds for our realizable algorithm has only logarithmic dependence on 1. For replicable passive learning, this dependence is linear, and so this represents a significant improvement in accuracy dependence. In the agnostic setting, our replicable active learning algorithm instead has a sample complexity dependence on (9)² where v is the error of the optimal hypothesis in the class C. While the dependence on technically still quadratic for our algorithm, as it for the replicable passive agnostic learning algorithm of Bun al. (2023), we note that when the optimal error v is quite close to the target error e, this still represents significant improvement in accuracy dependence, and therefore we do still improve over passive replicable learning in both realizable and agnostic cases.
Similarly Cohn et al. (1994a); Balcan et al. (2006); Hanneke (2007), we instead obtain a sample complexity dependence on the disagreement coefficient θ of a hypothesis class C for distribution D. We formally define the disagroement coefficient in section 2, but informally, the disagreement coefficient is a measure of the probability of disagreement among hypotheses in a class C' that are within some error ball centered on the optimal hypothesis in C. A small disagroement cocfficient mcans that relatively few labeled samples are needed to rule out hypotheses that are far from optimal, with the caveat that these samples should be points on which hypotheses in C disagree. Active learning allows us selectively query such points, and therefore obtain sample complexities dependent on θ and only logarithmicallyy on 1 (or quadratically on 1 in the agnostic case). The sample complexity dependence on θ we obtain for our replicable active learning algorithms is analogous to those in Cohn et al. (1994a);
2

---

Publishod in Transactions on Machine Learning Research (01 (01/20
Balcan et al. (2006); Hanneke (2007): linear dependence in the realizable case, and quadratic in the agnostic.
1.2 Related Work
Our replicable realizable PAC learner adapts techniques for replicable learning of finite hypothesis classes doveloped in Bun et al. (2023) to the CAL algorithm given in Cohn et al. (1994a). The CAL algorithm was analyzed and extended in Balcan (2015); Dasgupla et al. (2007); Hanneke et al. (2014) (see section 2.1.2 for description of the CAL algorithm)). Our replicable agnostic PAC learner builds on the work of Balcan et al. (2006); Dasgupta et al. (2007), taking the A algorithm as a starting point for our algorithm. The A algorithm was the first active learning algorithm to achieve e-optimal performance where the underlying distribution has arbitrary noise (see section 2.1.3 for a description of the A algorithm).
Castro and Nowak (2008); Dasgupta (2004) study the limits on the sample complexity improvements achievable by active learning. In particular Dasgupta (2004) show that even for the very simple hypothesis class of d-dimensional linear separators, there are target hypotheses for which aclive label queries cannot provide significant sample complexity improvements over passive learning. These fundamental limits motivated a line of work studying more expressive queries, such as comparison queries, which enabled exponential sample complexity improvements over label query aclive learning algorithus in some cases (Kane et al., 2017; Hopkins et al., 2020a;b). To initiate the study of replicability in active learning, we restrict our algorithms to make only label queries. Thus, our sample complexity improvements will depend on the disagreement coefficient + of the hypothesis class C and distribution D, and will not be guaranteed to hold for arbitrary distributions and classes.
Prior work has studied active learning under the related stability constraint of differential privacy (Balcan and Feldman (2013), Bittner et al. (2020), Ghassemi et al. (2016)). The connection between privacy and replicability was studied in Ghazi et al. (2021); Kalavasis et al. (2023); Bun et al. (2023), but the equivalence between the two was established only for statistical tasks in the batch setting. Hence, it is not immediately clear how to leverage this equivalence to obtain replicable learning algorithms from private ones in the active learning context. Replicable algorithums have been developed for other learning models outside of the batch PAC learning framework as well. Prior work has given replicable algorithms for sequential decision-making problems such bandits (Esfandiari et al., 2022), online learning (Ahmadi et al., 2024), and reinforcement learning (Karbasi et al,, 2023; Eaton et al., 2024), but none had yet been given for active learning.
1.3 Organization
The structure of this paper is as follows. In section 2, we introduce the theory of active learning, followed by the concept of replicability in machine learning. In section 3, we propose an algorithm for replicable active learning in the realizable sctting and analyze its convergence. In section 4, we adapt. the algorithm of section 3 to the agnostic setting and provide an analysis. Finally, we conclude with suggestions for future work. The appendix includes complete proofs and appendix A listing symbols used throughout the paper.
2
Background
2.1
Active Learning Theory
We work in the PAC learning framework of Valiant (1984). Fix a domain X, a binary label space Y {0, a concept class C of hypotheses h X + Y and define the ground truth or target function as e e C. Algorithm is said to be PAC learner for C' if there exists function m(s, polynomial in e 6 such that for every distribution D over X and every and 8 > 0, given mie, 5) samples outputs a hypothesis h E C' such that (h) Pr [h(x) a v) < E, except with probability x>D
X drawn i. d. from D and labels y = c(x) E Y, A
8 over the choice of samples.
3

---

Publishod Transactions on Machine Learning Research (01/2026)
In the agnostic setting, the ground truth is not a hypothesis in C, and therefore the minimum error achievable by a hypothesis h E C may be non-zero. We will use v - sometimes called the noise rate - to denote the error of the optimal hypothesis C: h" = argmin crr(h). An agnostic learning algorithm A will return hypothesis h with error that does not exceed the error rate by more than
In the active learning framework, learning algorithms do not reccive labels for all samples from D. Instead, they are assumed to have access to essentially unlimited unlabeled data, and their goal is to learn the ground truth function h by making targeted queries for labels (or functions of the labels). The aim active learning is to improve the sample- - and espocially label complexity of learning relative to passive algorithms for the equivalent task. This is especially useful for tasks where the unlabeled sample points are easily accessible but the labeling requires additional (e. g. computational or manual) effort. Examples of such tasks include image classification and speech recognition.
The field of active learning can be further subdivided based on how queries are contrived and how points are sampled. Algorithms that select queries via the query-by-ddssggeemmet principle base their queries on the disagreement of all candidate hypotheses. Stream-based selective sampling encompasses algorithms that receive one sample point at a time and determine for cach point if they want request a label or not (Scttles, 2012).
2.1.1 Disagreement Coefficient
The sot of x E X on which at least two hypotheses h from a version space V S C disagrec is defined as
DVS(V) fa E |h,, h2 E V s.t. (n) + h²()))
(1)
In the following, this set is referred as the disagreement region or set. The respective probability of sampling an in the disngroement region is
(n(V)=
Pr [r E DIS(V)) æ>
(2)
with probability distribution D. The distance metric for two hypotheses hy, h2
dD h2) = Pr ( h2(x))
(3)
is used to define a ball around a hypothesis
Bp(h,c) = {h' Clldb(h,)) E
(4)
The ball BD(c, E) where is the target function includes all hypotheses with an error rate of at most e. Then, Ap(Bp(c, the probability of sampling a point from distribution D on which at least two hypotheses with an error rate of at most disagree. The disagreement coefficient is defined
AD(Bu(c,)
OD sup =>0
and describes the maximum aforementioned probability normalized by Intuitively, this is a measure of how many points have to be sampled to improve upon a set of hypotheses with an error rate of at most e. In the agnostic case the definition uses lo" instead of c.
This becomes clear when considering the worst case round of the CAL algorithm, which will be explained in the next section. It is clear that the worst case occurs when all points in the current disagreement region have to be sampled to remove all hypotheses with error rate greater than e. Thus, consider the case where the target function and additional hypotheses remain in the version space. Each of the n hypotheses makes a mistake only on single point that is sampled with probability of 1 n. Then, the disagreement region has a probability mass of n = 1, and the disagreement coefficient for the critical error rate 1 n the number of points that have to be sampled.
In the following the subscript D will be omitted from the introduced variables for succinctness if the respective probability distribution is clear from context.
4

---

Publishod Transactions on Machine Learning Research (01/2026)
2.1.2 CAL Algorithm
The CAL algorithm, which was first proposed by and named after Cohn et al. (1994a) is based on the concept of query by disagreement and used for learning in the realizable case. The algorithm is given in algorithm as pseudo-code. Despite the pooling of points in each round r, the algorithm is categorized as stream-based selective sampling algorithm. The choice over requesting label depends on whether a given point is in the disagreement region. This is equivalent to sampling from an alternate probability distribution D, that is obtained by conditioning on the inclusion in the disagreement region. In this round-based formulation the probability mass of the disagreement region is al least halved each round. The exit condition of the loop ensures that all hypotheses in the final version space will have an error rate smaller than E, This results from the fact that the target function c never eliminated and no hypothesis may deviate more than from the ground truth. Furthermore, it follows that the number of rounds is O (log !)-
A detailed label complexity analysis of such a disagreement region based algorithm in terms of the disagreement coefficient was first derived in Balcan et al. (2006). The label complexity for a finite hypothesis class as given by Hsu (2010) is
o (108 Alog 1o 8
(6) Here, the first factor accounts for the number of rounds that the CAL algorithm will run for and the sccond factor is the number of points & that are sampled in each round. Compared to the sample complexity of passive learner Kearns and Vazirani (1994)
o ( log 8 )
the CAL algorithm yields an exponential improvement in label complexity with respect to the dependence on E, assuming that the disagreement coefficient. is finite.
Algorithm 1 CAL algorithm
input: 6,6
1: Set sample size it O ( log log 2: Initialize version space V C
C log
3: while A(V) > do
4: Sample & points Fı, Tkk from DIS(V)
5: Query labels yı....,B4 yk for sampled points
6: Update - (hEV e E [k] h((,)) = y1}
7: end while
8: return Any h hEv
2.1.3 2 Algorithm
The 2 algorithm was first proposed by Balcan el. al. (2006), the first agnostic active learning algorithm. It can be thought of as robust version of the CAL algorithm that allows for noise. It is dssgreementt-asee active learning algorithm that was shown to work in an agnostic setting with no assumptions about the mechanism producing noise. All it needs access to is a stream of examples drawn i. from some fixed distribution.
The algorithm is given algorithm as pseudo-code. This pseudocode chosen from Balcan (2015), over other flavors of the algorithm as depicted in Balcan al. (2006) and for the sake of simplicity.
To work in the Agnostic setting, the A algorithm must be more conservative than the CAL algorithm. The rejection of bad hypotheses based on disagreement over single example can
5

---

Publishod Transactions on Machine Learning Research (01/2026)
no longer be a valid step, since it would risk rejecting the best hypothesis with non-zero noise rate. Instead, in each round it estimates the distributional lower and upper bounds, and climinates all hypothoses from the disagrocment region whose lower bound is greater than the minimum estimated upper bound. Similar to the CAL algorithm, the probability mass of the disagreement region at least halved in each round. Since the exit condition of the loop is relatively weaker, the algorithm concludes with one last step where certain number of points are all labeled and the hypothesis from the remaining version space which has the lowest estimated error is finally chosen. The error of the final hypothesis is provably smaller than V + where y is the noise rate, or the true error of the ground truth.
It follows from the exit condition that the number of rounds in the loop is O (log )
The label complexity for a finite hypothesis class as given by Hanneke (2007) is
o 00
0 log 1 12 + [ogg Ov
(
|C| + log 5)) 5))
Compared to the sample complexity of passive agnostic (PAC) learner in Kearns and Vazirani (1994)
o 0 log [C] log ))
the 2 algorithm yiclds a significant improvement in label complexity with respect the dependence on E, assuming that the disagreement cocfficient is finite, and the noise rate is small enough.
Algorithm 2 A algorithm
input: v, 6,
Initialize Vi C, 1= k' - ( 5' 1+ log Ser
2: while A(V) 2 80v do
(a) Let D; be the conditional distribution D given that x E DIS(V)).
(b) Sample & i. labeled examples from D,. Denote this set by S,
(c) Update V4+1 = {h E V, LB(S,, 8') S mingev, UB M 8))
3: end while
4: Sample S of ke' points from D:.
return arg minsev; (hr)(h)
2.2 Replicability in Learning
The notion of replicability we in our work was introduced by Impagliazzo et al. (2022), to define randomized learning algorithms that are stable with high probability over different samples from the same underlying distribution. Following is the definition of replicability introduced by Impagliazzo et al. (2022) that we adopt in our work.
A randomized algorithm A(S; b) is replicable if there exists a function mo R + N such that for all p > 0, and any m > mp(p)
Pr S1.52.b
= A] 1 P.
2
(10)
where S₁ and S2 denote samples of size m drawn i. d. from D, and b denotes a random binary string representing the internal randomnoss used by A. We will call learning algorithms that simultaneously replicable and PAC learners replicable learning algorithms.
Replicable Learner for Finite Classes To develop our efficient RepliCAL algorithm, we have drawn from the random thresholding trick used to develop replicable learner for finite hypothesis classes in Bun et al. (2023). The idea is to estimate the risk of each
6

---

Publishod Transactions on Machine Learning Research (01/2026)
hypothesis in the class C' by standard uniform convergence bounds, choose a random error threshold v E [OPT, OPT + al, and finally output a random E C with empirical error crts(h) = [8] L(.D)s [h())= + yi guarantoed to be at most v. It was shown in the paper that such random thresholding achieves replicability with high probability when the hypothesis class is finite.
In the realizable case, the required sample complexity for this learner was shown to be
(log*
|C] log 1 + log (1)
(11)
Epp
This result was further improved upon with regards to the replicability parameter p by a boosting procedure. Then, the resulting sample complexity for the realizable case
(1 A
log |C| + log
o log p
(12)
ep
In our work we have extended the random thresholding concept to the active learning setting and proved that it leads to replicable learning.
In the last section, we propose an agnostic replicable learner for finite classes, with label complexity of
δ 0 log
v²) 5²)
log"
log 1 |C| log p By ))
Uv +
log
+
(13)
p
The dependence on can be brought down by boosting, and the resulting label complexity would be
δ 0 log"
(l08
1 n² Dv
+
log
|C' po
+
log²
log" 1
(14)
Replicable Active Realizable Learning
3.1 Algorithm
Our approach based on the replicable learning algorithm for finite hypothesis classes given by Bun et al. (2023). In each loop the RepliCAL algorithm, the version space is updated by thresholding the empirical, conditional error rate based on a random threshold which is selected the start. To compute the conditional error rate, the algorithm exclusively queries labels of points in the disagreement region. The size of the disagreement region is calculated using unlabeled data, and once it is smaller than the larget error rate, the algorithun exils the loop. After exiting the loop, all hypotheses in the final version space will be randomly reordered, and the first hypothesis returned. Replicability is achieved by ensuring that for two different runs of the algorithm the final version spaces are similar and therefore the same hypothesis will be returned with high probability, Importantly, we do not require the per-round version spaces to be similar across independent runs; our analysis only couples the terminal version spaces.
3.2 Theoretical Analysis
Theorem 1. Let C be any finite concept class. In the realizable setting, RepliCAL is replicable active learning algorithm for C' with label complerity:
log [C log : log + p log
|C| log
log
8
(15)
pr
7

---

Publishod Transactions on Machine Learning Research (01/2026)
Algorithm 3 RepliCAL algorithm
input: d,
1: Set interval size T = log C7
log? [0] log 1 log"
+ Ing ICI
2: Set sample size k = Ô + log
3: Initialize version space V C
Select random threshold v 2
23
while (V) do
6: Sample k points ,,...,, from DIS(V)
7: Query labels y1...., ys for sampled points
8: Define set S, = [(11, 91)..... (Ix, }b)}
9: Estimate conditional error err (h) for every h E
V {h E V.: errg, (h) S
11: end while
12: Sample k points Fi...., from DIS(V)
13: Query labels y1,..., for sampled points
14: Define set S, ((11,111 B1....., (Ix, yx]}
13: Estimate conditional error err Dr (h) for every
Set v' A(V)
17: + t V Sg
Pa-1 (h) S o'}
Randomly order all E
return The first hypothesis in
We prove theorem via lemma and lemma 2, which separately establish accuracy and replicability of algorithm 3.
Lemma 1. Let e, 6, O respectively denote accuracy, failure, and replicability parameters.
Let m(c, 6, Ps |C1) denote the total (labeled and unlabeled) sample complerity for algorithm Then for any fovile hypothesis class and distribution D, except with probability at most over Dm RepliCAL, terminates after O (log rounds and outputs hypothesis with error at most E.
The proof follows closely that of Balcan (2015) and is given in detail in appendix B.1.
It remains to argue that algorithm is replicable. We will follow the proof approach of Bun et al. (2023). Let V1 and V denote the final sets of candidate hypotheses upon exiting the main loop RepliCAL, for two independent runs the algorithm with resampled data, but shared internal randomness. We argue that the symmetric difference V1AV2 2 is small relative to their union V1 U V2, and therefore returning the first element of random permutation of C that is contained in V (resp. V2) returns the same hypothesis with high probability.
Lemma 2. Let E, 5, O respectively denote accuracy, failure, and replicability parameters. Let m(s, 8, p. ICI) denote the total (labeled and unlabeled) sample complerity for algorithm 3. Then for any finite hypothesis class C and distribution D,
Pr S1,5 m (R)))iCAL(:;:b) + RepliCAL(S2; b)] <
(16)
The complete proof given in appendix B.2 and the proof of theorem then follows as corollary of lemma 1 and lemma 2, by an accounting of the labeled sample complexity as given in appendix B.3.
3.3 Boosting
The label complexity be boosted via the procedure proposed in Impagliazzo et al. (2022) and modified in Bun et al. (2023) to improve the dependence p. The boosting
8

---

Publishod Transactions on Machine Learning Research (01/2026)
procedure is based on the idea of running the replicable learning algorithm on O (log) 5) different. random strings with constant replicability parameter p' 0.01. Different sets of samples induce distribution of hypotheses for each random string. Because of the constant replicability paramcter, with high probability at least one of these distributions will have (2(1) heavy-hitter, e. an element that is drawn with extremely high probability. The HHeavyHitters algorithm given in Impagliazzo et al. (2022) is used to replicably find a heavy-hitter hypothesis for which requires O [ogg(1/o)) samples that are shared between the multiple runs different random strings.
Setting the failure probability during the repeated running of the replicable learning algorithm to = 8. (1/p) R O poly(p)) ensures that - by a union bound over all samples the hypotheses will be good with probability 1 6. Therefore, the log z term of the non-boosted version changed log /
x²
This results in label complexity of
( 1 log log" E
log" |C] log log loo'" 1 + log
[C] log
6p
(17)
P
p²
Analogous to equation 51, this can be approximated as
1 & log 1 log² |C| _ + log
ICI op
δ + log
(18)
p2
3.4 Comparison to Replicability in Passive Learning
A direct comparison of the label complexity we obtained in equation 51 to the passive replicable learning guarantee of Bun et al. (2023) in equation 11 reveals a clear improvement in sample complexity whenever the hypothesis class and data distribution admit efficient active learning, as captured by a bounded disagreement coefficient O In particular, while passive replicable learning must draw labeled examples from the full underlying distribution in order to ensure stability of the learned hypothesis, RepliCAL concentrales label queries only within the evolving disagreement region. This allows the algorithm to simultaneously shrink the version space and maintain replicability, while avoiding the need to repeatedly label regions on which all surviving hypotheses already agree. As a consequence, the resulting sample complexity exhibits only polylogarithmic dependence on 1/e, in contrast to the linear dependence the realizable passive replicable learner of Bun et al. (2023). Thus, active learning not only reduces label complexity in the standard PAC sense, but also mitigates the additional sampling burden imposed by replicability constraints. Overall, this demonstraaes that active learning provides a principled avenue for overcoming the high sample complexity traditionally associated with replicable learning.
Replicable Active Agnostic Learning
4.1 Algorithm
In this section, we introduce the ReplicA algorithm (algorithm 4) for replicable active learning in the agnostic setting, Algorithm 4 adapts the approach of algorithm 3 to the agnostic sctting, by removing the implicit assumption that there always exists a perfectly consistent hypothesis within the version space V. This requires determining the size of the disagreement region exactly not only to determine when exit the main loop, but also approximate an upper bound on the global error of the optimal hypothesis each round using only labeled samples from the disagreement region, that can remove any hypothesis with conditional error exceeding this bound.
9

---

Publishod Transactions on Machine Learning Research (01/2026)
Algorithm 4 ReplicA? algorithm
input: &,e,p,
1: Set interval size O
pa
Ing CT
2: Set labeled sample size k O
@ log By
log
|Cl à
+
log" |C]
log tf log*
3: Set labeled sample size k' = O
log
CCl
log"
log log"
4: Initialize version space V C
5: Select. random threshold v + { 16e +
2 168
+ 2
106
3
2
6: while A(V) 2 80v do
7:
Define o, = A(V)
8: Sample & points TI from DIS(V)
9:
Query labels yı,..., yk for sampled points
10:
Define set S, = ((x1, y1)...., (Ix: yk)}
Estimate conditional error err s. (h) for every h E V
12: V V f h V: crr (h) u v
end while
Set interval size +' =0
Ep?
loV [C]
r'1
Select threshold o' in 9606 + 2 9609
with the same interval
969 2
index as before
16: Sample k' points æ1. 2 The from DIS(V)
17: Query labels y....., Uk for sampled points
18: Define set SR+1 = {(11
DR+ (
19: Estimate conditional error cr45 (h) for every h E V
20: Define conditional optimal error Daa+ = minsey ert (h)
DR-1
V < E V: erT
DR+1 (h) PPR11 + +0}
22: Randomly order all h E
23: return The first hypothesis in V
In the final round, scaled by the size of the disagreement region longer provides useful upper bound on the conditional optimal error, and so the algorithm instead takes the minimuu conditional error as an estimate. Analogous to the realizable case, replicability is achieved by ensuring that the final version spaces of two different runs of the algorithm are similar, and that therefore the same hypothesis will be returned with high probability.
4.2 Theoretical Analysis
Theorem 2. Let C be any finite concept class. In the agnostic setting, ReplicA is replicable active learning algorithm for C with label complerity:
δ
000
02
log Ov +
v² E
log
C 8
+
log" |C|
log" 1 ey
(19)
p
As with theorem 1, prove theorem 2 in two lemmas separately arguing for accuracy and replicability. For brevity, the proofs of both lemmas are omitted here and presented in the appendix under appendix C.1 and appendix C.2.
Lemma 3. Let 8, 0 respectively denote accuracy, failure, and replicability parameters. Let m(e, 5, P, ICI) denote the total (labeled and unlabeled) sample complesity for algorithem. 4. Then for any fivite hypothesis class C and distribution D, except with probability at most over S ~ n ReplicA terminates after O (log 1 rounds and outputs hypothesis h with error at most v E, where denotes the ervor of the optimal hypothesis in C.
10

---

Publishod in Transactions on Machine Learning Research (01/2026)
Lemma 4, Let E, 6. p> O respectively denote accuracy, foilure, and replicability parameters. Let mle, 6, P. (CI) denote the total (labeled and unlabeled) sample complerity for algorithm 4- Then for any finâte hypothesis class C and distribution D.
Pr S00
+ ReplicA? (S: (S2; < p.
(20)
Similarly to the realizable case, theorem 2 follows a corollary of lemmna 3 and lemin 4. A detailed derivation is given in appendix C.3 Applying Boosting to the algorithms using the same setup as in section 3.3, we can reduce this complexity to
0 log 1 O
+ v²) log"
log
|C| log log
log"
p²
Ov
E²
Ov
Ov
))
1
|C| log Bv
v²
|C|
+ log
log
log
(21)
Ov
pd
E2
pô
or
2 02
v2 e²
C pō
)
log
+
log
+ logg [C log"
(22)
Ov
4.3 Comparison to Replicability in Agnostic Passive Learning
We have an effective improvement of label complexity over the passive setting by having multiplicative factor of @ (for the first N rounds) and 1 (for the last round) instead of the g factor in passive agnostic learning (equation 9). For distributions which are suitable for active learning (characterized by a low value of θ), and for problems with a reasonably low noise rate (characterized by a low value of v),, both these values are much lower than .
1
5 Conclusions and Future Work
We presented the first replicable adaptations of two classical active-learning algorithms CAL in the realizable setting and A in the agnostic setting yielding the RepliCAL and ReplicA algorithms. By introducing randomized thresholding and replicable statistical-query subroutines, we show that one can retain the core label-complexity advantages of active learning under the strong stability requirement of replicability.
In the realizable case for finite hypothesis classes with suitable disagreement coefficients, RepliCAL matches the known dependence on θ log 1 of CAL, incurring only a mild overhead for replicability. In the agnostic case, ReplicA² leverages the A framework to handle noise and still improves over passive-learning bounds. These results demonstrate that, even under stringent stability constraints, adaptive querying can yield substantial label-complexity savings.
The transformation from replicability to differential privacy of Bun et al. (2023) continues to apply in the active-learning setting (though, notably, the reverse direction - from privacy to replicability does not). This suggests that lower bounds for differentially private active learning may transfer to the replicable regime, offering a path to establishing tightness of our bounds. That said, we expect our sample complexity to be nearly tight, based on lower bounds in terms of p and H for replicable lcarning the passive learning setting as well as lower bounds in terms of ④ and v/é for active learning without stability constraints.
A natural but challenging next step is to extend our results to infinite hypothesis classes. Standard active learning upper bounds in terms of VC dimension do not immediately carry over because private (hence replicable) learnability requires finite Littlestone dimension. It
11

---

Publishod Transactions on Machine Learning Research (01/2026)
would be valuable to show that finite Littlestone dimension, and therefore, global stability, still admits the active learning gains we obtain here.
Investigating a broader class active learning algorithins, including those applicable to infinite hypothesis classes or structured prediction tasks, would be valuable future directions. Empirical studies will be essential evaluate these methods in practical scenarios, providing further insights into their reliability and performance in real-world applications.
12

---

Publishod Transactions on Machine Learning Research (01/2026)
References
Saba Ahmadi, Siddharth Bhandari, and Avrim Blum. Replicable online learning. arXiv preprint wrXiv:2411.1377 2024.
Dana Angluin. Queries and concept learning. Machine learning, 2:319 342, 1988.
Maria-Florina Balcan. 10-806 foundations of machine learning and data science, 2015. URL https://www. cs. cmu. edu/ /tto///re/////////coeeeeeee/ 18.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceedings of the 23rd international conference Mochine learning, pages 65 72, 2006.
Maria-Florina F Balcan and Vitaly Feldman. Statistical active learning algorithms. Advances in newral information processing systems, 26, 2013.
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM sympostum on Theory of Computing, pages 1046-1059, 2016.
Daniel M Bittner, Alejandro E Brito, Mohsen Ghassemi, Shantanu Rane, Anand D Sarwate, and Rebecca N Wright. Understanding privacy-utility tradeoffs in differentially privale online active learning. Journal of Privacy and Confidentiality, 10(2), 2020.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):4499557) 526, 2002.
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptíve gencralization. In Proceedings of the 55th Annual ACM Symposium on Theory of Compuling, pages 520-527, 2023.
Rui M. Castro and Robert D. Nowak. Minimax bounds for active learning. IEEE Transactions Information Theory, 54(5))2339 2333--333, 2008. doi: 10.1109/TTII /
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15:201-222 221, 1994a.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15:201 221, 1994b.
Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural informa- lion processing systems, 17, 2004.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. In J. Platt, D. Koller, Y. Singer, and Roweis, editors, Ad- vances Neural Information Processing Systems, volume Curran Associates, Inc., 2007. URL https: h tttps://proceedings neurips. wwtpcccccpppcllleeeeee fiiles//aaper/207//fieee/ 4
Paper pdf.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data. analysis. In Theory of Cryplography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 8, pages 265-284. Springer, 2006.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pages 117-126, 2015.
Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
13

---

Publishod Transactions on Machine Learning Research (01/2026)
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. arXiv preprint arXiv:221000183 2022.
Mohsen Ghassemi, Anand D Sarwate, and Rebecca N Wright. Differentially private online active learning with applications to anomaly detection. In Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security, pages 117-128, 2016.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. Advances in Neural Information Processing Systems, 34:20172 20184, 2021.
Steve Hanneke. A bound on the label complexity agnostic active learning. In Proceedinggs of the 24th international conference on Machine leorning, pages 353 353-360, 2007.
Steve Hanneke et al. Theory of disagreement- based active learning. Foundations and Trends in Machine Learning, 7(2-3):131-31) 2014.
Max Hopkins, Daniel Kane, and Shachar Lovett. The power of comparisons for actively learning linear classifiers. Advances in Neural Information Processing Systems, 33:6342 6353, 2020a.
Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Conference Learning Theory, pages 1957 2006. PMLR, 2020b.
Daniel Joseph Hsu. Algorithms for active learning. PhD thesis, UC San Diego, USA, 2010.
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. CoRR, 2022.
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistin- guishability of learning algorithms. In International Conference on Machine Learning, pages 15586-15622. PMLR, 2023.
Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In 2017 IEFF 58th Annual Symposium on Foundalions of Computer Science (FOCS), pages 355 366. IEEE, 2017.
Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement lcarning. Advances in Neural Information Processing Systems, 36:74702-74735, 2023.
Michael J. Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory.
The MIT Press, 08 1994. ISBN 9780262276863. doi: 10.7551 http://///////////////////////// /wtpp/tss///97.0000..... ///////99700000001110 URL https: //op:://doii org/10. 2////11..551// 7551 7 101.000..00000 0001.
Burr Settles. Aclive Learning. Synthesis Lectures Artificial Intelligence and Ma-
chine Learning. Springer Cham, 1 edition, 2012. ISBN 978-3-031-00432-2. doi:
10.1007/978-33031--01566
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635 2670, 2010.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
14

---

Publishod Transactions on Machine Learning Research (01/2026)
A
Symbols
Symbol
Description
b
Random binary string
Target function (realizable case)
Hypothesis space
d
Distance metric
D
Probability distribution
DIS())
Disagreement region
8
Failure probability of model
A(-)
Probability mass of disagreement region
Maximum error of returned hypothesis Error of & hypothesis
err
errs
Empirical error of hypothesis
errs D
Empirical error of a hypothesis conditioned on disagreement region Query function in SQ learning
S
h
Hypothesis function
I
Threshold interval
k
Number of samples
m
Number of samples
N
Maximum number of rounds the algorithm runs for
Query function in SQ learning
Round of algorithm
R
Number rounds of the algorithm for a specific run Replicability parameter
Sample set
T
Sample set of unlabeled points
Disagreement coefficient.
V
Noise
Threshold for replicably discarding hypotheses
Threshold offset
Version space
T
Tolerance parameter in SQ learning
Interval width in Replicable learning
Global interval width in Replicable learning
Sample
y
Label
Empirical estimate
Quantity of the last round
B Replicable Active Realizable Learning
B.1 Proof of Lemma
Proof. Proof of lemma 1 runs analogons to Balcan (2015). Letting V, denote the hypothesis space at round r, we will first argue convergence by showing that the distributional size of the disagrecment region A(V,) will be at least halved with cach successive round, i.c., A(V,+1) A(V.)) with high probability. Let v be the set of hypotheses in V,, with large
15

---

Publishod Transactions on Machine Learning Research (01/2026)
еттоr
V =f=h = c(h,c)
A(V.)
ve
(23)
20
If all hypotheses in this set are removed, the distributional size of the disagreement region will indeed be halved
A(V++)) B cc. A(Vi)
A(V)) A(V))
Σ +
(24)
20
20 2
where the definition of the disagreement coefficient was used.
So as long as all high-error hypotheses are removed in each round, the size of the disagreement region is halved, and algorithm 3 converges in at most O (log }) steps, because the algorithm terminates when A(V,) S
We now argue that with high probability, all high-crror hypotheses removed at cach round. Note that because we are in the realizable setting, err(h) A(V,)errP-(th (h) for every A(K+) then we can lower-bound the E Vr, and so it follows that if A(V.)orPP-hh) (h) z 20
conditional error err 2 26' It therefore sulfices remove all hypotheses with least this conditional error the disagreement region.
From algorithm 3 it is clear that since the hypotheses in each round are chosen to fall under a random threshold that is upper-bouut bounded by se 1 this upper-bounds the conditional empirical error of the algorithm each round. By applying Chernolf-Heeldding bounds for the realizable case, we can bound the probability that any hypothesis with conditional error rate at least 2e has empirical error rate less than 3 se y for any of the N O (log !) rounds of the algorithm. We see that the number of labeled points needed in each round to ensure good error estimates for all hypotheses with probability at least - 2N is
0
C|N 8
o
log
+
log
(25)
We take the sample for our empirical estimate of conditional error to be greater than this quantity, and so except with probability 5, all high-error hypotheses are removed at every round. This guarantees convergence within O (log ?) rounds, and so in total
1
log 8
o
+ log
log
(26)
labeled samples are required for convergence.
The size of the disagreement region be estimated up to arbitrary accuracy using unlabeled data. Thus, we use the exact value in our algorithm.
remains to argue the accuracy the final hypothesis. union bound over the failure probabilities of the empirical error rate estimation in each round yields an overall failure probability of (δ). Then, the stop condition A(V) S guarantees that all Vy have error rate below This follows from the fact that in the realizable case, the ground truth will never be removed from the hypothesis space because the estimated error rate of the ground truth cannot exceed O. Since the ground truth is never removed, if all hypotheses agrec on a point, all of them must classify this point correctly. The final thresholding after exiting the loop added for the purpose replicability and does not have an adverse effect on accuracy.
16

---

Publishod Transactions on Machine Learning Research (01/2020)
B.2 Proof of Lemma 2
Proof Let the RepliCAL algorithm be on two different ordered sets of samples 8 [++] Sp and S = U S. drawn from the respective distributions {D).... D and 1- which are obtained by conditioning the distribution D on the disagreement region the corresponding round (+ 1).
Select an interval width π < e Tog|c] which divides 85 Define I; to be intervals corresponding the desired global error rate in the final thresholding round
To = [0. π
I1 IT, 2n)
(27)
80 T.
80
and v/A(Vi+1) = 2641 to be the respective global thresholds.
Let (i) and (i) denote the two final version spaces across the two independent sets of samples S and 5 and for shared randomly chosen threshold uy. In the following proof we will drop the explicit dependence on (i) for conciseness.
We will show that with probability at least g. for S and 5 each of size ① (og log" |C| log log'
we have:
V A V V2
S 0
(28)
To prove the claim, we, analogous to Bun et al. (2023), call threshold of "bad" if any of the following conditions hold:
1. The ith interval has too many elements:
4 >
P
1 y/
(29)
30
2. The number of elements beyond 7, increases too quickly:
3j 2 1: [ 2 ed |p-n|-
(30)
and "good" otherwise.
Here, [h| denotes the number of hypotheses whose true risk lies in interval T,, and [T the number of hypotheses in intervals up through 4.
We will be proving the following:
1. If oi is good threshold, then V and V are probably close
V'
P
Pr
<
(31)
S
VLUV2
2. At most fraction of thresholds are bad.
17

---

Publishod Transactions on Machine Learning Research (01/2026)
Part 1 To prove the first part, we consider three cases in which mistakes can occur. For this, we define a "good" hypothesis as hypothesis with a global true error rate less than A ((Vn+1) and call "bad" otherwise
1. A "bad" hypothesis with err(h) E 1it5 was accepted in every round.
2. A "good" hypothesis with err(h) li-j was rejected in any round.
3. For any hypothesis in the last round with err(h) E 4, the empirical error is on the wrong side of the threshold A(VR+1)
By a Chernoff bound, the probability of a hypothesis with true global error rate err(h) E h+g. > having an empirical error rate less than A(VR+1)u( after the final thresholding
U (n G43))
Dn+ (h) S o/ < Pr S441
Se ee- - _
(32)
where by = [S and the conditional error rate is computed by scaling the global error rate by the size of the disagreement region. The estimation tolerance of the order the global interval width scaled by the disagrocment region
T' 2 2A(VR+1) O A(VR+1) ( log C
Ep²
p²
20
(33)
+ log |C|
The probability of the first case occurring is upper-bounded by this Chernoff bound for any single round. For simplicity, here we choose the last round R 1. We introduce the random variable 2; that counts the number of hypotheses with err(h) Jttj. > 0 which cross the threshold of in the final round. Then, assuming the chosen threshold is good, the expected value can be bounded by
B [
|Ttsle -
850
[[-1]]
Σ
10g/-1))//--)) S [[-1] Σ (09))
(34)
j>0
350
p²
64 /
30
Here, the second condition for good thresholds and size of the samples by was used. The last step follows from an asymptotic consideration that holds for small enough constants. Using Markov's incquality, we conclude that
Pr
x;
P 30
P 64
(35)
For the second case, the probability of one good hypothosis - measured by the last round crossing the threshold in any round is given by a union bound over all rounds. The conditional error rates of any good hypothesis in rounds r s R + 1 where A(V,) 2 E will be lower or oqual than the threshold v;:
err(h) A(VR+1)e
(36)
A(VR+1) A(VR-1)
A(V,) v/ o/=
Vi
(37)
A(V.) A(VR+1)
</
(38)
Therefore, the probability of the error rate estimate crossing the threshold can be upper- bounded by the final round R +
Da+1 (h) s o/] Ne Ne---l (
Pr
err S441
(39)
18

---

Publishod Transactions on Machine Learning Research (01/2026)
Defining random variable ys to be the number of good hypotheses rejected at any round, we have
Elyll S N
Σ |4-5|e
320
(40)
< ||1-11] Ne (or - ||-1|| ND
Again, we conclude that with probability at least 1- ot only & fraction of hypotheses will fall under case 2.
30
In the third case, by definition of the first condition for bad thresholds, we directly see that in the worst case the number of hypotheses upper-bounded by the number of hypotheses in the interval
P 1/-1)1- 30
14
(41)
Thus, in total there will be no more than f--1 mistakes made with high probability 1 1 32. Considering two different runs of the algorithm, the symmetric difference of the final hypothesis sets will be less than ///-11/ with high probability at least. 1 fo-
Furthermore, the union of the scts is guaranteed to be at least (1 - fs) |/ with a failure probability of at most 1 1- Saz as seen in the analysis of the second case.
Finally, a union bound yields the desired result
V'AV2 VLUV2
Pr ST
P
0 8
(42)
4
Part 2 Now, let prove that almost all thresholds good. The structure of the proof is based lower-bounding the number of hypotheses "contributed" by each of the "bad" intervals, which in turn upper-bounds the number of "bad" intervals, since the total number of hypotheses is fixed by the size of the concept class, [C|-
Let the "bad" intervals be present in & clusters (longest consecutive "bad" intervals bounded by "good" interval(s)), with the jth "bad" cluster containing L continuous "bad" intervals. Thus, the total number of "bad" intervals is Ej=tt
First, let's say the intervals are "bad" by condition of "badness". Then the jth bad cluster increases the number hypotheses from [t,] by at least (1 30 4.
If the intervals are bad by condition 2 of "badness", the j cluster increases the number of hypotheses (corresponding to the future interval(s) causing them to be "bad" by condition 2), by at least ct, Since > (1 + ( the statement that the 7th cluster increases the number of hypotheses by "at least" (1 + ) still holds, for both conditions of "badness". Since [ol > 1, can write:
E t
C 2 1 + 30
(43)
follows that the number of "bad" intervals:
log [Cl
Σ t 5 1=1
(44)
P
Since T' has been chosen such that the total number of intervals is at least O Log C
the
fraction of intervals that are "bad" (p)
This true for each round of our algorithm. If want bound the probability of choosing bad interval in "any" round, we have to take union bound of the probability of bad intervals in each round. By choosing o' where p is the replicability-facee of the parent
19

---

Publishod Transactions on Machine Learning Research (01/2026)
algorithm, and using an appropriate constant, we can union- over N rounds to have the probability over all rounds to be g- This requirement of having to choose a smaller will be accounted for while calculating the label complexity.
Three events can break replicability of the proposed algorithm: bad interval is randomly selected, the sets V and V are not close or two different random hypotheses are chosen even though the final sets are close. The probabilities of these bad events occurring are & e and & respectively. Thus, union bound yields failure probability of at most. 5, satisfying p-replicability required.
B.3 Proof of Theorem 1
Proof. From the proof of lemma have bounds on the number of samples required for algorithm& 3 to get an error rate of at most with high probability 1 6, and converge within O (log ) rounds.
Furthermore, in lemma 2, we have seen the worst case sample complexity for the thresholding
to be p-replicable is ky = O size
log 0r²²
Since 7' s so @Tog ( we can replace 7' to get sample
o²
+ log" [C| 1
ky =
p
(45)
p+
This the label complexity required in each round. Hence, the total label complexity required for p-replicability after N rounds is
o (N. N
θ log" |C| log
(46)
p²
While proving lemma 2, we stated that in order for the algorithm to p-replicable, the thresholding subroutine has to run with a lower replicability parameter: &, where is the number of rounds. Hence, the corresponding label complexity should be corrected to:
+ log
|C| log N N p
N
(47)
pr
Lemma states that the number of rounds required for convergence is O (log 2). Hence, the label complexity is
o log 1 log 2 Co
log + log"
(48)
The label complexity required to ensure bounded error well as replicability can be found by combining equation 26 and equation 48. The overall complexity thus derived is:
o o (
log² |C| log ! log*
[C' 1
+ O
log
(49)
p
8
This gives us the required label complexity
(0l0g 1 log |C| l log" p² log
[C] log &
(50)
as stated in theorem 1, and concludes the proof.
20

---

Publishod Transactions on Machine Learning Research (01/20
It can be argued that log log 1 is trivial w.r. t. the other terms, and the label complexity thus reduces to
Ô + log 1 log" |C] log" 1
c + p² log 8
|C|
(51)
p
C Replicable Active Agnostic Learning
C.1 Proof of Lemma 3
Proof. Our proof runs analogous to Balcan (2015). Let V, denote the hypothesis space at round т. The distributional size of the disagreement region A(V,) will be at least halved with each successive round A(V++) x A(V, with high probability. Let v be the set of hypotheses in V, with large error
v - { h hev. d(h,
A(V,)
(52)
20
all hypotheses in this set are removed, the distributional size of the disagreement region will indeed be halved
A(V++1) & A B (1 20
) < +
A(V.)
AVV))
(53)
20
where the definition of the disagreement coefficient was used.
Since the size of the disagreement region is halved in each round with high probability, and the loop stops when A(V)) < 80v, the convergence would take at most N E O (log e steps.
First, we show that in the round basod portion of the algorithm, hypotheses in the V/ will be removed with high probability. From the definition of the distance metrie we get.
((h,h") A(V)) Pr [h(z) + h" (x)]
InD,
A(V,) [err (h) err (h*)]
(54)
$ A(V,)err Dr (h) +
Assuming that h E v get
A(V,)err (v.))erP.(h))) 2 d(h, h()) -
(1h)= 2
20 A(V,)
(55)
2 20 80
80
using A(V)] - This turn implies that the empirical conditional error e Dr (h), which estimated to within tolerance I must be greater than I6e
Recall that the largest value the empirical error threshold for removing hypothesis, v ors can take is
3
3
5
<
+
(56)
A(V)
160
2
80
160
160
Therefore
5
er
Dr (h) > Dr
Dr (h)
Or
(57)
160
160
21

---

Publishod Transactions on Machine Learning Research (01/2026)
and therefore we will remove h with probability at least 8
2(N+1)' This argument relies on and so we
estimating the conditional error of every hypothesis in C' to within tolerance 1 require labels for
169
IC|N
o
+ log
(58)
points sampled i. from A(V)), by a Chernoff bound. Thus, the total sample complexity for all N rounds
== |NOe log
JCIN 5
(59)
To see that with high probability the best hypothesis ht is never removed from the version space V, observe that the smallest value the empirical error threshold for removing hypothesis, e + Bry can take is
3R 2
(60)
AV,))
160
(V,)
160
The error of every hypothesis is estimated within 166 that
with high probability, so we have
err errg, (h))
(61)
A(V) 160
and therefore h" is never removed with high probability.
Now we consider the accuracy of the hypothesis returned at the end of the algorithm. We may assume, because the loop has terminated, that A(VR+1) & 80v.
err(h) - err(h)) = A((R+1) [err PR+1 (h) - err Pa+1 (h*)]
(62)
< 80v errr DRI (h) eer (R+)
Therefore, it suffices to find a hypothesis with err Pa+ (h) < Pn+1 (h*) + sØv to ensure err(h) S err(h") + e. We estimate the conditional error of every hypothesis on the last disagreement region with an accuracy of 1920E and failure probability of 2(N41)* This requires a sample set size of
02 log
NCC 8
(63)
Defining PP++ the minimum of all estimated error rates ensure that the optimal conditional error rate is estimated within tolerance of 1929.-
The largest threshold for the final round is
25 T' S err PRI2(H") +
2e
PRIL
(64)
960v
1920v
960v
Therefore any bad hypothosis h will be removed
DR+1 (h) err Da+ (h)+))) 192@w
err S.
err PRI1 (h") +
(65)
80v 192
2 0 + D0+1
Proving that the optimal hypothesis is never removed also proves that the version space will never be empty after the final round. This is guaranteed because
DRI err Sn41
(h²) err DR+1 (h")
1920>
(66)
Dn+i
+
8
1920>
1920>
22

---

Publishod Transactions on Machine Learning Research (01/2026)
is less or equal than the smallest threshold.
So overall, combining equation 59 and equation 63, and substituting N we get that
o @0"
log
1 av
log
1 C
tv
v²
log
log
ev
1
|C1
(67)
8
many labeled samples are required for convergence to good hypothesis.
C.2 Proof of Lemma 4
Proof. Let the ReplicA² algorithm be run on two different ordered sets of samples 5 U Sp and S = - 8 drawn from the respective distributions { DK+1) and (DR DR which are obtained by conditioning the distribution D on the disagreement region Vi of the corresponding round (1,...,
Select an interval width и v O
log [og|cT which should divide
e0²²
12' Define 7 to be intervals
corresponding the global error rate in the last round
To
+
12
12
I1
n
+ 2T
12
12
(68)
22
1
T,
12
12
and v(A(Vn+1) = 12 + 2i+1 2 be the respective thresholds.
Let (i) and (i) denote the two final version spaces across the two independent sets of samples S and 5 and for a shared randomly chosen threshold v/.
We prove that with probability least &. for samples S and 5 drawn i. from Dr, @
@o log" |C| log log" log av + )
each of size ①
1.
we have:
p
V A'VE2 0
(69)
12
Analogously to the realizable case, we define "good" and "bad" thresholds. As before, we will be proving the following:
1. If v/ is a good threshold, then Vi and 1/2 are probably close
MVVI
p
P 8 2
Pr S1.82
(70)
V
V
4
2. At most a & fraction of thresholds are bad.
Part 1 To prove the first part, we consider three cases in which mistakes can occur. For the following analysis we will define a hypothesis as "good" has a global true error rate less than v A(VR+1)u, and define as "bad" otherwise.
1. A "bad" hypothesis with err(h) - I+t accepted in every round, iee, with empirical error smaller than the threshold 8t.
23

---

Publishod Transactions on Machine Learning Research (01/2026)
2. A "good" hypothesis in the last round with err(h) - E I-- was rejected in any round, i.e., with empirical error larger than the threshold rt.-
3. For any hypothesis in the last round with err(h) - v E Li, the empirical error is on the wrong side of the threshold v + A(VR+1)u
By a Chernoff bound, the probability of hypothesis with true global error rate err(h) I+t5. > 0 having an empirical error rate less than DD + vf after the final thresholding is at most
Pr
err SR11 (h) S Pati + us} se 10-0) =e ~kN*
Dn+1
(71)
where ky = |-r|- The ostimation tolerance is of the order of the global interval width scaled by the disagreemeent region
T'
=0 E0²
((VR+1)) log |C| (
(
ep²
2
(72)
4 4A(VR+1)
tN log |C|
This ensures that hypothesis with estimation error _ does not cross the threshold which itself depends on the optimal hypothesis estimated to within an error z The probability of the first case occurring upper-bounded by this Chernoff bound for any single round. For simplicity, here we chose the final thresholding r R+1 1. We introduce the random variable H; that counts the number of hypotheses with err(h) - I+jj. 0 which cross the threshold of in the last round. Then, the expected value can be bounded by assuming that the chosen threshold is good
Σ
(())))))))))
jz0
<
[1-1
Σ
-2G log 1/p-1/ S [4-11 Σ ())))
(73)
j>0
3>0
p²
64 |(-1)/.
30
Here, the second condition for good thresholds and size of the samples k was used. The last step follows from an asymptotic consideration that holds for small enough constants. Using Markov's 's theorem, we conclude that.
Pr
2
11
| <
P 64
(74)
30
For the second case, the probability of one good hypothesis - measured by the last round crossing the threshold any round given by a union bound over all rounds. The conditional error rates of any good hesos rounds r < R where A(V,) > 80v will be lower or equal than the respective thresholds or + 14 under the benign assumption that e <
err(h) $ + A(VR+1)o
(75)
err Pr 5 Dr + A(Vn+1)
A(V,) 2/
(76)
Pr A(VR+1). U
(77)
A(V;)
V
+
(78)
A(V,)
Therefore, the probability of the error rate estimate crossing the threshold can be upper- bounded by the final round R + 1
err Dv+1 (h) DDai + of] Ne- 22
Pr
(79)
24

---

Publishod Transactions on Machine Learning Research (01/20
and the expectation of the random variable analogous to defined as is upper-bounded
by
Elydl N
> |4-5| 7
(80)
|/-11 Ne ((T
- |/--1|| NN
Again, we conclude that with probability at least 1 - 6I
o only fraction of & hypotheses 30
will have made a mistake according to case 2.
As before, in the third case the number of hypotheses is upper-bounded by the number of hypotheses in the interval by the definition of the first condition of bad thresholds
[4 - 30 |(-n)--
(81)
Thus, in total, there will be more than f--1l mistakes made with high probability
1 1- 22. Considering two different runs of the algorithm, the symmetric difference of the final hypothesis sets will be less than 51/--1 with high probability at least 1 & 16.
Furthermore, the union of the sets is guaranteed to be at least (1 ft) 1/- with a failure probability of at most - Soz as seen in the analysis of the second case.
Finally, a union bound yields the desired result
V A
AV
P 8
Pr ,155
2 1
(82)
( U V
Part 2 Proving that almost all thresholds are "good" follows the same argument as in the realizable setting, and we can conclude that the fraction of intervals that are "bad" is O (p).
This true for each round n ..., +1 of our algorithm. By choosing p' = Iा where is the replicability-fccorr of the parent algorithm, and using an appropriate constant, we can union-bound over N rounds to have the probability over all rounds to be g. Union-boudding over the "bad" events gives us a total failure probability of G, as the realizable setting, hence proving p-replicability as required.
C.3 Proof of Theorem 2
Proof. Equation 26 gives us the worst-case sample complexity of our algorithm required to get an error rate of at most v + s with high probability 6.
Furthermore, in the proof of lemma 4, we have seen the worst case sample complexity for the thresholding to be peroplicable is kN = 0 to get sample size
( log # 1
Since t s O + Ing ci): we can replace т
p²
O² log" [C|
bx
(83)
p²
This is the label complexity required in each round. Hence, the total label complexity required for p-replicability after N rounds is
ONN N @ log" log 1
(84)
p²
While proving lemma 4, we stated that in order for the algorithm to be p-replicable, the thresholding subroutine has to be run with lower replicability parameter of the order of &. Hence, the corresponding label complexity should be corrected to:
o o
@ log [ol N N N. ON.
p
(85)
p
25

---

Publishod Transactions on Machine Learning Research (01 (01/2026)
Lemma 1 states that the number of rounds required for convergence is O (log e..) Hence, the label complexity is
0² log Ov
1
log" |C] log
log oz
log" 4
OV
(86)
p²
To ensure p-replicability in the last round we need O log T²
labels. To ensure the same
number of intervals, the replicabilty-constaad should be the same as the one before, f Since cp² (orooicc): we have the label complexity in the last round as
r' S O
gaue E2
log"
|C| log log
(87)
p
The label complexity required to ensure bounded error as well as replicability can be found by combining equation 67, equation 86 and equation 87. The overall complexity thus derived is:
((008
Ou + 1²) log² E2
|C|
log
low ale log" B2
o
@
|o oz
1
122
|c|
) (88)
log
log
log
Ov
E2
1
v²)
IC' ô
log" C' log
1.
log
log
(89)
Ov
26


Reviews:
[{"review_id": "dxdF96sFGi", "reviewer": "Reviewer_8GiF", "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": "", "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 addresses replicability in active learning (CAL and A^{2}). Each algorithm combines rSTAT subroutines to estimate quantities from unlabeled samples with random thresholding to ensure that independent runs using shared randomness produce the same predictor with high probability. The authors provide sample-complexity bounds that ensure replicable recovery of the optimal hypothesis. In both cases they have a discussion to compare it with the passive version.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The core claims are formalized as Theorem 1 (realizable/RepliCAL) and Theorem 2 (agnostic/ReplicA2) and are backed by proofs that adapt standard disagreement-based analyses (CAL/A² halving of the disagreement mass) and the good/bad-threshold coupling used in replicable passive learning. The label-complexity statements track the intended dependencies on the disagreement coefficient , accuracy parameters , and the replicability parameter ρ; the sources of polylog factors (rSTAT tolerances, per-round union bounds, boosting) are identifiable in the arguments.", "audience_yn": "Yes", "audience_explanation": "Yes. Replicability is a central theme in contemporary learning theory and closely connected to differential privacy and algorithmic stability. This work offers the first (to my knowledge) replicable variants of CAL/A for finite classes, with explicit label-complexity guarantees—of clear interest to (i) theory readers following stability/DP/replicability, (ii) active learning researchers concerned with disagreement-based methods, and (iii) practitioners curious about enforcing replicability without sacrificing label efficiency. While the current scope is finite classes, the techniques suggest directions for extending to infinite classes, which should further engage the TMLR audience.", "requested_changes": "Include a table for symbols \nSome formulas has number and some does not have. Please pick one style.\nExtend boosting section in more detail", "broader_impact_concerns": "N/A", "additional_comments": "N/A", "extra_scores": {}, "extra_text": {}}, {"review_id": "ELLfKM75Bk", "reviewer": "Reviewer_Xj4P", "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": "", "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 extends two classical active learning algorithms, namely CAL and A^2, to replicable active learning algorithms that would yield identical models under independent runs with high probability. The authors show that, compared to replicable passive learning algorithms, replicable active learning algorithms enjoy substantial label savings, e.g., exponentially less labels in the realizable case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors provide complete proofs for the stated theorems, which appear reasonable to me.", "audience_yn": "Yes", "audience_explanation": "The findings of this paper would be of interest to researchers working on active learning and replicable learning.", "requested_changes": "1. Most of the techniques used in the proofs appear to be borrowed from existing literature: (1) active learning for label savings, and (2) replicable learning results for passive learning. It would be helpful if the authors could highlight their main technical contributions.\n2. While most existing active learning results (including CAL and A^2) are for infinite hypothesis classes, results presented in this paper are restricted to finite classes. The authors should highlight technical challenges involved and discuss potential directions to generalize these results to infinite classes.\n3. Please clarify if the presented replicable results for active learning imply other related properties, such as stability or differential privacy, in the context of active learning.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "STUU0RUHb1", "reviewer": "Reviewer_bvPC", "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": "", "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": "Summary:\n\n\nThis paper studies replicable learning in the context of active learning. It presents the first replicable learning algorithms for finite hypothesis classes in both the realizable and agnostic settings. The proposed methods are augmentations of CAL and A², enhanced with the randomized threshold trick of Bun et al. (2023). The authors provide label complexity bounds for these algorithms and compare them to replicable learners in the passive setting. In certain regimes—depending on the disagreement coefficient—the active learner achieves substantial label savings.\n\n\n\nStrengths:\n1. The paper addresses an interesting problem. Active learning is a classical topic in learning theory, while replicable learning has gained significant attention in recent years. Combining the two opens the door to potentially impactful applications.\n2. The proposed replicable active learner is the first of its kind. Although simple, it represents a solid first step toward tackling this problem.\n3. The sample complexity bounds are clean and directly parallel the improvements achieved by active learners over passive learners in the standard PAC setting.\n4. The introduction and background are well-written, providing sufficient context and a thorough overview of related work.\n\nWeakness:\n1. Many of the technical contributions appear to be adaptations of Bun et al. (2023), rather than novel developments.\n2. The technical sections (particularly Sections 3 and 4) feel repetitive and overly lengthy. While the introduction and background are well-written, they could be more concise, and the main body of the paper would benefit from tighter presentation.\n3. The technical exposition is largely descriptive but offers limited insight. In particular, some design choices in the algorithms raise questions:\n\n\n    a. Why is it necessary to approximate the disagreement region using the rSTAT algorithm? Given access to unlimited unlabeled data, the    mass of the disagreement region can in principle be calculated exactly.\n\n\n\n    b. Is it necessary to make all the version space V replicable? It feels like we can just use the replicable learning algorithm from Bun et al. (2023) on the last version space and we can get some theoretical guarantees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides rigorous mathematical proofs for all its claims. As an expert in active learning with knowledge of replicable learning, I find the results convincing at first glance. I reviewed the proofs and, upon a quick check, found them to be valid.", "audience_yn": "Yes", "audience_explanation": "As noted earlier, active learning is a classical area in learning theory, while replicable learning has emerged as a popular direction in recent years, with many researchers working on related topics. Prior to this work, no algorithms or label complexity bounds were known for this setting. This paper provides a valuable first step toward addressing this problem.", "requested_changes": "1. The writing has substantial room for improvement, particularly in the following ways:\n\n    a. The main body of the paper could be considerably shortened. The core idea is simple and intuitive for readers familiar with active learning or replicable learning, and the content could likely fit within eight pages or fewer. Much of the technical detail could be moved to the appendix.\n\n    b. The technical writing should focus more on how the techniques from Bun et al. (2023) are applied, rather than restating them in detail. Including additional examples and intuitive explanations would make the presentation more accessible.\n\n\n\n2. The algorithm may be simplified (as related to my earlier comments in the Weaknesses section). If simplification is not feasible, it would be valuable to explain why applying the randomized threshold trick only at the final iteration is insufficient.", "broader_impact_concerns": "This is a theoretical work, and I do not see any potential ethical concerns arising from it.", "additional_comments": "I believe the paper would be strengthened by including a lower bound, as this would clarify how tight the upper bound is. For a theory-focused conference, the current contribution may feel insufficient, but given TMLR’s broader standards, it can still be considered a meaningful contribution.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)