Promises and Pitfalls of Threshold-based Auto-labeling
Authors: Harit Vishwakarma
Heguang Lin
Frederic Sala
Ramya Korlakai Vinayak
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Auto Labeling
Active Learning
Selective Classification
TL;DR: In this work we analyze threshold-based auto-labeling (TBAL) that is getting widely used in practice for data labeling. Our work provides insights on when machine-labeled data obtained through TBAL can be relied on.

Abstract: Creating large-scale high-quality labeled datasets is a major bottleneck in supervised machine learning workflows. Threshold-based auto-labeling (TBAL), where validation data obtained from humans is used to find a confidence threshold above which the data is machine-labeled, reduces reliance on manual annotation. TBAL is emerging as a widely-used solution in practice. Given the long shelf-life and diverse usage of the resulting datasets, understanding when the data obtained by such auto-labeling systems can be relied on is crucial. This is the first work to analyze TBAL systems and derive sample complexity bounds on the amount of human-labeled validation data required for guaranteeing the quality of machine-labeled data. Our results provide two crucial insights. First, reasonable chunks of unlabeled data can be automatically and accurately labeled by seemingly bad models. Second, a hidden downside of TBAL systems is potentially prohibitive validation data usage. Together, these insights describe the promise and pitfalls of using such systems. 
We validate our theoretical guarantees with extensive experiments on synthetic and real datasets.

Promises and Pitfalls of Threshold-based Auto-labeling
Harit Vishwakarma
Heguang Lin hglin@seas. uuenn. edu University of Pennsylvania
hvishwakarma@cs. wisc.
University of Sasconsin-Madisee
Frederic Sala
Ramya Korlakai Vinayak
fredsala@cs wisc eis University of Risconsin-Madisne
ramya@ece wisc. edu University Wisconsin-Madison
Abstract
Creating large-scale high-quality labeled datasets is major bottleneck in supervised machine learning workflows. Threshold-based auto-labeling (TBAL), where validation data obtained from humans is used find confidence threshold above which the data machine-labeled, reduces reliance on manual annotation. TBAL is emerging as a widely-used solution in practice. Given the long shelf-life and diverse usage of the resulting datasets, understanding when the data obtained by such auto-labeling systems can be relied is crucial. This is the first work to analyze TBAL systems and derive sample complexity bounds on the amount of human-labeled validation data required for guarantecing the quality of machine-labeled data. Our results provide two crucial insights. First, reasonable chunks of unlabeled data can be automatically and accurately labeled by seemingly bad models. Second, hidden downside of TBAL systems is potentially prohibitive validation data usage. Together, these insights describe the promise and pitfalls of using such systems. We validate our theoretical guarantees with extensive experiments on synthetic and real datasets
Introduction
Machine learning (ML) models with millions or even billions of parameters are used obtain state-of-the-art performance in many applications, e.g., object identification [53], machine translation [63], and fraud detection [71]. Such large-scale models require training large-scale labeled datasets. As an outcome, the typical supervised ML workflow begins with the construction of large-scale high quality dataset. Datasets with up millions of labeled data points have played pivotal role in the advancement of computer vision. However, collecting labeled data is an expensive and time consuming process. common approach is rely on the services of crowdsoureing platforms such as Amazon Mechanical Turk (AMT) to get groundtruth labels.
Even with crowdsourcing, obtaining labels for the entire dataset is expensive. To reduce costs, data labeling systems that partially rely on using a model's predictions as labels have been developed. Such systems date back teacher-less training [21]. Modern examples include Amazon Sagemaker Ground Truth [58] and others [61, 55, 2, 64]. These approaches can be broadly termed auto-labeling,
Auto-labeling systems aim to label unlabeled data using predictions from ML models that often trained on small amounts of human labeled data which can produce incorrect labels. The shelf life of datasets is longer than those of models, c.g., ImageNet continues to be benchmark for many computer vision tasks [14] fifteen years after its initial development. As a result, to reliably train new models auto-labeled datasets and deploy them, need a thorough understanding of how reliable the datasets output by these luto-labeling systems are. Unfortunately. many widely
'https://github... http:/shhb...ooo//arr//////aa.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Threshold Based Auto Labeling System
A
Extimatee Auto Labeling Region
Unisbaled
Auto
Labeled Data
Bookstrap
Human Laboler
Parnta Humnan
Figure 1:
High-level workflow threshold-hased auto-labeling (TBAL). Box (B) shows the key component estimating the auto-labeling region using validation data and auto-labeling points in it.
used commercial auto-labeling systems [58, 55J are largely opaque with limited public information on their functionality. It is therefore unclear whether the quality of the datasets obtained can be trusted. To address this, we study the high level workflow of popular threshold- basddd auto-labeling (TBAL) system (see Figure 1). We emphasize that goal is to understand such systems and their performance not to promote them as a superior alternative to other approaches. Our goal is:
Goal. Develop a fundamental understanding of TBAL systems. This is crucial since there is lack of theoretical understanding of the reliability of these systems despite their wide adoption.
The TBAL systems we study (Figure 1) work iteratively. At a high level, in each iteration, the system trains model on currently available human labeled data and decides to label certain parts of unlabeled data using the trained model by finding high-accuracy regions using validation data. It then collects human labels on small portion of unlabeled data that is deemed helpful for training the current model in the next iteration. The validation data is created by sampling i.i.d. points from the unlabeled pool and querying human labels for them. In addition to training data, the validation data is a major driver of the cost and accuracy of auto-labeling and will be a key component in our study.
Our Contributions. We study TBAL systems (Figure and make the following contributions:
Provide the first theoretical characterization of TBAL systems, developing tradeoff's between the quantity of manually labeled data and the quantity and quality of auto-labeled data (Section 3).
Empirical results validating our theoretical understanding on real and synthetic data (Section 4).
Our results reveal two important insights. Promisingly, even poor quality models are capable of reliably labeling at least some data when we have access to sufficient validation data and a good confidence function that
accurately quantify the confidence of given model any data point. On the downside, in certain scenarios, the quantity of the validation data required to reach a certain quantity and quality of auto-labeled data be high.
Threshold-Based Auto-Labeling Algorithm
We begin with the problem setup and describe the TBAL algorithm that is inspired by the commercial systems [58]. Then we provide experiments and theoretical analysis shedding light on the pros and cons of TBAL. We emphasize that TBAL is not our proposal and our goal is to understand the effectiveness of such an auto-labeling system.
2.1 Problem Setup
Notation. Let the instance and label spaces be X' and y [1....,k} We assume that there is some deterministic but unknown function f X + y that assigns true label = f*)x) to any x X. We also assume that there noiseless oracle O that can provide the true label y y for any given x E X. Let X poot C X denote sufficiently large pool of unlabeled data to be labeled.
k).
The goal of an lube-labeling algorithm is produce accurate labels 5 E y for points X; E Xxpoo while minimizing the number of queries to the oracle. Let [m] == 2., m). A C [N] be the set of indices of luto-labeled points, and Xpoot (A) be these points. The auto-labeling error E(Xpoot (A))

---

and the coverage P(Xpool (A)) are defined as
[A|
Na
Eoopool (A))
Σ
1( (xx))) and p()
(1)
Na iEA
N
N
where Na denotes the size of auto-labeled set A. TBAL algorithm aims to auto-label the dataset so that ((Xpoot(A) S ca while maximizing coverage P(Xpoot for any given Ea (0,
Hypothesis Class and Confidence Function. A TBAL algorithm is given fixed hypothesis space H and confidence function g : H x X' + T S R that quantifies the confidence of h E H on any data point x E X. Confidence functions include prediction probabilities and margin scores. For example, when H a set of unit-norm homogeneous linear
Algorithm I Threshold- Auto-Labeling (TBAL)
Input: Unlabeled pool Xpoot. auto labeling error threshold Ea. seed data size ng, batch size for active query ni, labeled validation data pool Deat.
Output: Dout {(x, (t) Vx; E Xxoot)
1: x = poot: vol = Dval
2: D randomly-queee -uulyy--uuuuur- wwweauuuueeuaraeaee batch(Xi" .2,)
3: Remove queried points from x!!))
classifiers, i.c. (x) = sign(w"s x) with w E [w E Rd |w/2 = 1}, a reasonable confidence function is g(hw, x) x)= />/>>>=>/ //²x/. x
4: Didd = Φ; 1; Dout D D Dyuerr
5: while x! # o do
( brain D (i-ll U
D Query
6:
h empirical Bactriccalriikk-e rrik_miinn (,, (1)) D(rin))
Note that the target f might not be the hypothesis space H. Our analysis (Section 3) shows that the TBAL algorithm can work well, i.e., accurately label reasonable fraction of unlabeled data with simpler hypothesis classes that do not contain the target hypothesis f*. We illustrate this with a simple example in Section 2.3 and Figure 2. Note as well that the features x could be raw features
7:
f. Estimate Threshold (5) D eats Eas hi, no)
8:
9:
anto ((x)),(x) x E x ,9(h,, x) 2 (.) X fx: E
D
x." g(h,, x) < ftp
10:
D(+1)= = [(x, (x,y) E val I(h,, x) < {
11:
12:
Dyvery = acttiveqqueryaaeee -uttruuutrccccchh (h,, X1 (6+1))
mb)
13: Remove queried points from (6+1))
14: Dowt Dout U (()
auto D gquery
or representations from self-supervised techniques, pre-trained models, etc. We analyze TBAL in settings (i) with no assumptions on the features and (ii) when the features are linearly separable.
15:
i= -=i+1
16: end while
Algorithm 2 Estimate Threshold
Input: x!()) (()) val: Eay ho Output: Threshold &
2.2 Description of the algorithm
1: Ti = (g(,,, x) (x, v) E D
The TBAL algorithm is given in Algorithm 1. It starts with an unlabeled pool X Xpoot and an luto-lab error
2: for t T; do
N, = (x E x!!) : g((h,, x) 2 13]
3:
threshold e. For ease of exposition, the
4: end for
algorithm is given the labeled validation
5: T. = (t:t E T,, N₁ 2 not U foo)
set Drat of size N, separately. In practice, it is created by selecting points
6: i, = min(t E T. (h;, (|x! + Cio; S {a}
at random from X X The algorithm starts with an initial batch of n, random data points and obtains oracle labels for these. The algorithm works in an iterative manner using the following steps.
Oracle labeled data obtained each iteration is added to the training pool ((1) Prainn is used to train a model hy by performing empirical risk minimization (ERM).
2. Find the region where h; can luto-label accurately. The algorithm estimates a threshold f, on the confidence score above which it can auto-label with the desired auto-labeling accuracy on the validation data (see Algorithm 2). Thresholds that have too little validation data are discarded, since their estimates are unreliable. The minimum threshold is found such that the sum of the estimated error (he, ! (see eq. (2)) and an upper confidence bound using the standard deviation of the estimated error, is at most the given auto-labeling error threshold.
3. Auto-label the points in the pool, x-() which have confidence g x) > Í, These are added to the set Dout and removed from the unlabeled pool. The validation points that fall in the
labelld region are also removed from the validation set so that in the next round the validation
3

---

TBAL Cutput
SL+ Output
100
120
60
Queried
Urlose
Samsha
Samshh
Queledi-e
Autoilabeled we
M.-50
PLe5O
(a) TBAL AL+SC on Circles dataset
(b) Auto labeling performance of various methods
Figure 2: Comparison of TBAL, active learning (AL) followed by selective classification (AL+SC) and passive learning (PL) followed b selective classification (PL+SC) on Circles dataset (Sec. 2.3) using linear classifiers confidence functions. (a) Samples auto-laheled, queried, and unlaheled. (b) The auto-labeling error and coverage achieved by the algorithms. (50 trials.)
set and the unlabeled pool are from the same region and the same distribution. Removing the auto-labeled points from Xooo is a crucial step in the TBAL algorithm that enables to focus only on the remaining unlabeled regions in the next iteration.
4. If there are points left in puol, the algorithm selects points using some active querying strategy [57], obtains human labels for them, and adds them to the training pool. Note that the auto-labeled data is not added into the training set.
This process continues until there are no data points left to be labeled. The algorithm then outputs the labeled dataset, which is mixture of human- and machine-labele points.
2.3 Comparison between Auto-Labeling, Active Learning and Selective Classification
What is the difference between TBAL and methods such as active learning and selective classification?
Active learning. The goal of active learning [57] (AL) is to find the best model in hypothesis class H by training with less labeled data compared to passive learning. This is usually achieved by obtaining labels for the most informative points. Note that the end goal to output a model from the function class whose predictions on new data as good as the best model in the function class could.
Selective Classification. The goal of selective classification (SC) [17] is to find the best combination of the hypothesis and selection functions to minimize error and maximize coverage of selection regions.
Auto-Labeling.
The output of an auto-labeling procedure is labeled dataset (not a model). When the hypothesis class is of lower complexity, it is often not possible to find good classifier. The goal of an auto-labeling system is to label as much the unlabeled data as accurately as possible with a given function class and with limited labeled data from humans.
active learning alone enough auto-label data? AL has been found to be effective in reducing the number of labels needed to learn versus passive learning, particularly in low-noise cases [28]. Doing auto-labeling using AL followed by SC may be effective in such settings. However, in real-world scenarios, noise levels may be higher and the hypothesis class could be misspecified. In these instances, using the model learned through active learning to automatically label all data may result in high number of errors.
We illustrate this difference between AL. SC, and auto-labeling through an example. Suppose the data consists of two concentric circles, one for each class, with the same number of points per class (Figure 2(a)). This setting is not linearly separable. We run TBAL, AL, and AL followed by SC with an error tolerance of c, 1% and linear classifiers and confidence functions. The results are shown in Figure 2. Note that the multiple optimal linear classifiers will all incur an error of 50%. AL algorithms can only output models that make at least 50% error. If we naively use the output model for auto-labeling, we can obtain near full coverage but incur around 50% auto-labeling error. If we use the model output by AL with threshold-based SC, labeling emror is reduced. However, it can only label R5 25% of the unlabeled data. contrast, TBAL can label almost all of the data accurately (close to 100% coverage) with less than 1% labo-lab error.

---

3 Theoretical Analysis
The performance of the TBAL (Algorithm 1) depends on many factors including the hypothesis class, the accuracy of the confidence function, the data sampling strategy, and the size of the training and validation data. In particular, the amount of validation data plays a critical role in determining the accuracy of the confidence function, which in turn affects the accuracy and coverage.
We derive bounds on the auto-labeling error and the coverage for Algorithm 1 in terms of the size of the validation data, the number of auto-labeled points N²() and the Rademacher complexity of the extended hypothesis class HT7 induced by the confidence function g. Our first result, Theorem (3.2), applies to general settings and makes no assumptions on the particular form of the hypothesis class, the data distribution, and the confidence function. We then instantiate and specialize the results for a specific setting in Section 3.1. We introduce some notation to aid in stating our results,
Definition 3.1. (Hypothesis Class with Abstain) The function g, set T and H induce an extended hypothesis class H := H. x T. Any function (h,t) HTSS 8 is defined as (h, (x)) h(x) if g(h,x) 2 t and 1 otherwise. Here (h, t)(x) =1 means (h, t) abstains in classifying the point x.
Error Definitions. Let S X' denote a non-empty sub-region of X and S C be a finite set of i..dd samples from S. The subset S(h, () S S denotes the regions where (h, I) does not abstain i.e. S(h, (x E S (h, (x) 1 and the conditional probability mass associated with it is
([5) := ())()) and its empirical counterpart ([) == [h, /)S) We use P(S) to
denote the probability mass of set S and S() for the conditional probability of subset S' C
given S. The population level and empirical auto-labeling errors are defined as follows:
Eah, = Ex1s lo (h,,, x, 4)l /1/ (SS),
(h,tt())) = (Ex.Es(he) 1 t, x,, 3t)) ((),)) t)
(2)
Here (0-1(h, x. y) 4- (h,, eu (h,4, with 6 (h, x, y) 1(((x) # y), and L (1,,,, 1, x) = (g x) 2 1).
Rademacher Complexity. The Rademacher complexities for the function classes induced by the H. g and the loss functions are defined RR (?(T.s) == Ri (H, fa-1) + Rt (?(T=9, f1). Let h, and &, be the ERM solution and the auto-labeling threshold at epoch i. Let R E (0, 1) be a constant such that P(,,, ()) 2 R, for all i. Let x denote the validation set, and nh and na of validation and auto-labeled points at epoch i. Let Ea (h,, & x be the empirical conditional risk of hū in the region where g(h,, x) 2 & evaluated on the validation data x!
(+)
(4) the number
We provide the following guarantees the auto-labeling error and the coverage achieved by TBAL.
Theorem 3.2. (Overall Lube-Lab Error and Coverage) Let k denote the number of rounds of the TBAL Algorithm/ 1. Let (5) na denote the number of validation and auto-labeled points at epoch i and (3) = | Let Xpoot (As) be the set of auto-labeled points at the end of round (1)
k. N(R) = 5= =E,1 na be the lotal number of auto-labeled points. Then, for any 8 (0, 1), with probability at least -8. 8,
E(X {(Xpoo((A)) S Et
(E.
+
4 (9
(T(T.0)
2
8k log(
Tb nv
Pb
(0)
+
Pb
1
Li=1
N
(4)
R
m
(H(T.))
+ V
k log(
8k
8
and
(6)
((pooi(As)) Et ((x f.)) - 2 (M(T.0)
21.2 (8k)
log (
N
Discussion. We interpret this result, starting with the auto-labeling error term E(X poot (As)). The term (a) &, (h.. xx())) is the empirical conditional error in the auto-labeled region computed on the
validation data in i-th round, which at most ep- Thus, summing term (a) over all the rounds is at most cg. The term (b) provides upper bound on the excess error over the empirical estimate term
5

---

(a) as a function of the Rademacher complexity of HT and the validation data used in each round. The last term (c) captures the variance in the overall estimate as a function of the total number of auto-labeled points and the Rademacher complexity of H If we let nh 2 By i.c. the minimum validation points ensured in each round, then we can see the second term is (R,,, (H,...H and the third term is O 1//o)-
Therefore, validation data of size O (1/=²) in each round is sufficient get a (Eea) bound on the excess auto-labeling error. The terms with Rademacher complexities suggest that it is better to use a hypothesis class and confidence function such that the induced hypothesis class has low Rademacher complexity. While such a hypothesis class might not be rich enough to include the target function, it would still be helpful for efficient and accurate auto-labeling of the dataset which can then be used for training richer models in the downstream task. The coverage term provides a lower bound on the empirical coverage P(X pool (As)) in terms of the true coverage of the sequence of estimated hypotheses h, and threshold f..
We note that the size of the validation data needed to guarantee the auto-labeling error in each round by Algorithm is optimal up to log factors. This follows by applying result on the tail probability of the sum of independent random variables due to Feller [20]:
Lemma 3.3. Let C1, C2 and a > O. Let X; E X be set of n iid. points from X with corresponding true labels ys- Given (h. t) E HTSS, ler BerE[(4 [[ (h, t, x, x,,,,1) y:) {(),t)z)) of > α² for every x, for a; > 0 and let Σ of 2 01 then for every c E [0. (0= o with nee 12o log (4c2) the following holds w.p. at least 1/4, (h, t|x) > (h, +c.
Therefore, if sufficiently large validation set is not used in each round, there is a constant probability of erroneously deciding on a threshold for auto-labeling. Such a requirement on validation data also applies to active learning if we seek validate the output model. Bypassing this requirement demands the use of approaches that are different from threshold-based auto-labeling and traditional validation techniques. We note the possibility of using recently proposed active lesting techniques [33], a nascent approach to reducing validation data usage.
3.1 Linear Classifier Setting
Next, we consider a simple setting where active learning is known to be optimal to see if TBAL can offer similar performance guarantees. To do so, we instantiate results from 3.2 to homogeneous linear separators under the uniform distribution in the realizable setting. Let Px be supported on
the unit ball in R2d, X (x Rd ||x|| S 1}. Let W = {w E R |||||2 l| = =1 S.
H = {x + sign( (w. x)) Vw E W]. the score function be given by g(h, x) = g (w, x) (w. x)
and set T = [0, 1). For simplicity, we will use W in place of H.
Corollary 3.4. (Overall Lube-Labeling Error and Coverage) Let W., f, be the ERM solution and the
(6) auto-labeling threshold respectively at epoch i. Let ni nh denote the number of validation and auto-labeled points at epoch Let the TBAL algorithm run for keepochs. Then, for any 5 E (0, 1), w.p. at least 1 6,
E(Xpoa (Ax)) S St
n. !.
Eg (W,,
Cin,,1,2 (1x +
1 Bb
2d log
+ log 88
(a)
(6)
+ 4
2k N!AT
2d log (N((4)
+ log ( 88
(#/
and
Rb
(XX (Ax))(AA))) 2 min: Add/T
2kg 2 (2dlog ( (=M) + log (88) (%%)
These results imply that by ensuring the sum of the empirical validation error term (a) and the upper confidence interval to be less than 6, in each round of the algorithm we can ensure that the overall auto-laheling error remains below <g. Furthermore, by applying standard VC theory to the first round, we obtain that é < 1/2. Therefore, right after the first round, are guaranteed to label at least half of the unlabeled pool. We empirically observe that TBAL has coverage at par with active learning while respecting the auto-labeling error constraint (See Figure 4(a)).

---

Tightness of the Bounds. We study this in the setting of the Unit-Ball experiment. The
upper bound on excess risk in this setting is given Corollary 3.4 which an instantiation of our general results to this specific setting. We consider a simplified form the upper bound by ignoring the constants to get sense of the rate in terms of the validation data size. We compute this simplified upper bound for different amounts of validation data. We compare these with the maximum auto-labeling error observed over 25 runs of auto-labeling in the Unit-Ball setting with different random seeds for each validation data size. The results are in Figure 3. As expected, we see that the worst-case error rate follows similar rate our upper bound but the upper bound is conservative. Next, explain why this is the case.
1992
2009 2010
2289 2008
2033
Figure 3: Left:: Simplified upper bound from Corollary 3.4 (ignoring constants) on excess auto-laheling error for the Unit-Ball setting i.c. homogeneous linear classifier with d 30. Right: The worst observed auto-labeling enror over 25 trials in Unil-Ball experiment.
Our upper bound is slightly conservative, as it is based on uniform bound over all hypotheses in given hypothesis class. Since the individual hypotheses whose excess auto-labeling error we need to bound are not known priori need to derive a bound the number of validation samples using which we can guarantee that the excess auto-labeling error of any hypothesis (model) small with high probability. Note that this is conservative (worst-case) analysis to get an upper bound on the validation sample complexity. The upper bound has two parts: a) the Rademacher complexity of the hypothesis class and b) term with the number of validation samples. We note that the validation samples, it matches lower bounds order-wise (see Lemma 3.3). This is the first analysis to provide these bounds based on uniform convergence without making any assumptions about the data distributions or hypothesis class. We provide further discussion on the role of Rademacher complexity in the Appendix C.I.
4 Experiments
We study the effectiiveness of TBAL on synthetic and real datasets. We validate our thcoretical results and aim to understand the amount of labeled validation and training data required to achieve certain auto-labeling error and coverage. We also seek to understand whether our findings apply to real kata-where labels may be noisy-along with how TBAL performs compared common baselines.
Baselines. We compare TBAL to the following methods:.
a) Passive Learning (PI.) queries subset of the points randomly to train model from given model class and then uses it to predict the labels for the remaining unlabeled pool.
b) Active Learning (AL) (using margin-random query strategy, described below) trains model from a model class and uses it to predict the labels for the remaining unlabeled pool.
Passive Labeling + Selective Classification (PL+SC) first performs passive learning to train model from a given model class. Then it performs auto-labeling on the unlabeled data using threshold-based selective classification with the model output by passive learning. Only those unlabeled points that are deemed as fit to be labeled by the selection function are auto-labeled.
Active Learning + Selective Classification (AL+SC) first performs active learning (using margin-random query strategy) to train a model from a given model class. It then performs auto-labeling using threshold-based selective classification with the model output by AL.
For selective classification in the above methods, we use Algorithm 2 to estimate the threshold and use it to perform auto-labeling. In experiments, we modify Algorithm slightly-instedd of estimating a single threshold for all classes, we estimate thresholds for each class separately.
Active Querying Strategy. We use the margin-randowe query strategy for querying the next batch of training data. In this strategy, the algorithm first sorts the points based on the margin (uncertainty) score and then selects the top Cn, (C > 1) points from which nı points are picked at random. This a simple and computationally efficient method that balances the exploration and exploitation trade-off. We note that other eetive-uuerying strategies exist; we use margin-random as our standard querying strategy to keep the focus comparing nuto-labeling-naa not active learning approaches.
7

---

Error (%)
Coverage (%)
Error (%)
Coverage (%)
Nv
N
TBAL
ALASC
TBAL.
AL+SC
TBAL
AL+SC
TBAL
ALASC
100
3.10
0.68 +0st
71.43 tass
96.95 +18
100
3.10
0.68 +eat
71.43 +12e
96.95 +10
400
1.97 some
0.59 s0.s
93.99 #239
97.89 #0.00
400
1.65
0.32 +eus
93.27 #250
96.91
800
1.64
0.66 19
96.26
98.06 2033
800
1.08
0.24
96.01
96.31
1200
1.39 10:0
0.67
96.67 1ust
98.10 11:45
1200
0.78
0.17 1en
96.82
95.96
1600
1,33 1::00
0.70
97.13
98.16
1600
0.65
0.13 1:xm
96.93
95.70
2000
1.28 +0.3
0.71 +0.1
97.15 +0.54 98.20
2000
0.54 +0.66
0.21 +..11
97.23 +0.42
96.36
Table 1: Unit-Ball. Effect of variation of validation data size (Nw) with and without using UCB on error estimates. We keep training data size N₂ fixed at 500 and use error threshold ca 1%. We report the mean and std. deviation over 10 runs with different random seeds. Left: with C1 O. Right: with C1 0.25.
Error (%)
Coverage (%)
Error (%)
Coverage (%)
N.
N.
TBAL
AL+SC
TBAL
AL+SC
TBAL
AL+SC
TBAL
AL+SC
200
4.77 se
3.35 1030
83.14 150s
78.53 1785
200
2.28 1021
3.11 10w
68.24 1430
57.77 115
400
4.57 heas
3.53 ha1s
90.70 asm1
86.39 #8n1
400
1.29 =ow
1.98 te.w
63.81 1-16
63.06 =100
600
4.32
3.70
92.96 +0.4
88.90 +4:33
600
1.41
181 +0.
69.64
62.92 +9:00
800
4.66
3.84
92.42 20.8
88.67
#3:00
800
1.62
2.04 +0.3
67.45
63.22 #7,00
1000
4.67
3.90
92.89
89.79
1000
1 1.64
1.97
70.28
66. 11
Table 2: LMDB. Effect of variation of validation data size (N.) with and without using UCB error estimates. We keep training data size N, fixed 500 and use error threshold c. 5%. We report the and std. deviation over 10 runs with different random seeds. Left: with C1 Right: with C1 0.25.
Datasets. We use the following synthetic and real datasets. We also provide empirical results on MNIST and another synthetic dataset in the Appendix. For each dataset, we split the data into two sufficiently large pools. One is used as Xpool on which auto-labeling algorithms are run and the other is used as Xeat from which the algorithms subsample validation data.
a) Unit-Bal is a synthetic dataset of uniformly sampled points from the d-dimensional unit ball. The true labels are generated using a homogeneous linear separator with w = 1//vd.... 1/Vd, We use d = 30 and generate N 20K samples, out of which 16K are in Xpoot and 4K are in Xeat- The dataset has just two classes but there is no margin between them.
b) TingeeeaeeNer [1] is a subset of the larger ImageNet [1 [14] dataset, designed for image classification tasks. It consists of 200 classes, each with 500 training images and 50 validation and test images. With a total of 100K images, Tiny ImageNet provides a diverse and challenging dataset. We use pre-computed embeddings of the images using CLIP [50].
c) IMDB Reviews [41] is a comprehensive collection of movie reviews, consisting of 50K individual reviews. It is balanced dataset of positive and negative labels. We use the standard train set of size 25 and split into Xpool and X of sizes 20K and 5K respectively. We compute embeddings of reviews using pre-trained model bge-large-en [70] from the Massive Text Embedding Benchmark (MTEB) [44, 19].
d) CIFAR-IO [36] is an image dataset with 10 classes. We randomly split the standard training set into X poot of size 40K and the validation pool of size 10K. We use the raw features for training.
Models and Training. For the linear models, we use SVM with the usual hinge loss and train it to loss tolerance 10-5. To train a multi-layer perceptron (MLP) on the pre-computed embeddings of IMDB and
we use SGD with a learning rate of 0.05, 0.1 respectively, and batch size of 64. To train the medium CNN we use SGD with learning rate of 10-2, batch size 256, and momentum of 0.9. More details on model training are in the Appendix.
The score function g. For SVMs we use the standard implementations of [69, 46] in sklearn to get the prediction probabilities and use them as the score function. Neural networks use softmax output.
4.1 Role of Validation Data
The TBAL algorithm uses validation data to estimate the auto-labeling errors at various thresholds to determine the threshold for automatically labeling points accurately. Thus, it is crucial to have
8

---

Error (%)
Coverage (%)
Error (%)
Coverage (%)
Nv
Nv
TBAL
AL+SC
TBAL
AL+SC
TBAL
AL+SC
TBAL
AL+SC
2000
0.0 an0
0.0 ine
0.0 sne
0.0 ano
2000
0.0 ano
0.0 400
0.0 2.0
0.0 230
4000
13.88 25o
13.31 1007
0.72 201s
0.48 100
4000
10.50 aa
7.37 110
0.47 gom
0:48 gare
6000
14.18 4975
11.52 203
17.29 zwo
8.18 #1.2
6000
10.61 tax:
7.71 #m.
10.16 #1.0
4.31 +L
8000
13.97 2034
11.31 205
36.36 1m
23.40 2335
8000
9.90 2wa5
6.80 s0
25.84 a137
14.43 22m
10000
13.42
11.14
43.79
33.38 13m
10000
8.97
6.87
32.19
21.96
Table 3: Tiny-ImageNet. Effect of variation validation data size (N.) with and without using a UCB on enror estimates. We keep training data size N, fixed at 10k and use erorr threshold ea 10%. We report the mean and std. deviation over 5 runs with different random seeds. Left: with C1 = O. Right: with C1 = 0.25.
Labgiin Emor
Covorage (RU
N
200
400
500
B00
1000
230
4.0
630
R50
1000
10K
15K
20K
10CC
35K
10K
JUIC
25K
32K
35K
Mac Training Sampie
Mas Thiining Samples
Mia The Sampples
1922
Taining Sempiees
-x-
TBAL
AL+SC
-
AL
-
PL+SC
-
PL
-..
-
TBAL
+
AL+SC
-X--
AL
+
PL+5C
-
PL
(a) Unit-Ball varying training samples size, validation (b) CIFAR-10 10: varying training samples size, validation
samples size=4K, Ea = 1%, C1 = 0.25.
size=10K, 6, = 10%, C2 = 0.25.
Results for varying Ng. the maximum number of samples algorithm can use for training while providing sufficient validation samples.
Figure 4:
accurate estimates of the auto-labeling errors. Our analysis shows that to get such good estimates, large amounts of validation data are needed. In this section, we study the effect of varying the amount of validation data auto-labeling performance.
Setup. We fix the maximum training data size Ng and run the algorithm with different amounts of validation data. We also consider the two cases where the algorithm uses upper confidence bound on the error estimate and where it does not. We use the Unit-Ball, IMDB, Tiny-ImageNei and datasets for this study with N, 500, 500, and 10K respectively, and the auto-labeling error thresholds cg = 1%, 5%, 10%, respectively. Initial seed data of size n, is 20% of N₂ and query batch size ny is 5% of Ng: C = 2 for both AL and TBAL for both datasets. We give the same initial seed samples of size n, to all the methods to ensure they have the same starting point.
Results. Tables 1,2 and 3 demonstrate the impact of validation data on the performance of TBAL and other algorithms. The auto-labeling error and coverage of TBAL and other methods are affected by the amount of validation data provided. When the validation data is insufficient, the auto-labeling error of TBAL increases. However, as more validation data is used, the auto-labeling error and coverage of TBAL improves. Providing too little X can lead to incorrect estimates of the auto-labeling error, which in turn results in poor luto-labeling performance. This is further highlighted in our theoretical analysis as seen in Theorem 3.2. We also take more nuanced look at the performance when the algorithm uses an upper confidence bound (with C1 = 0.25) on the estimates and when does not. We see the effects of not using any upper confidence bound (i.e. C1 = 0). The left side tables in Tables 1,2 and 3 show the results when C₁ = and the right side tables show the results when C = 0.25. These show that not using UCB leads to high auto-labeling error (i.e. not meeting the guarantees) even when there is a sufficient amount of validation data. This can happen with high coverage as well-yielding dataset with large errors. On the other hand using UCB, i.e. C1 0.25, the algorithm can keep the auto-labeling error below the given threshold but suffers in coverage.
In the above Tables, we omitted AL, PL, and PL+SC for clarity. We provide full results with all baselines in Appendix D.3.
4.2 Role of Training Data Size
The labels queried for model training also play an important role in the process while incurring costs to obtain. The next experiment focuses on the impact of training data auto-labeling.

---

Error (%)
Coverage (%)
Error (%)
Coverage (%)
Na
N4
TBAL
ALASC
TBAL
ALASC
TBAL
AL4SC
TBAL
AL.SC
200
1.67 =020
2.15 +04
73:30
57.17 +11
2000
9.22
7.42 +am
17.51 +us
9.33
400
1,63 Low
1.61 1974
72.59 1316
64,53 11641
4000
9.30
Law
6,97 1030
25.01 11m)
14.25 1:m
600
1.67 2021
1.83 30.0
71.38 #215
70.50 #518
6000
9.12
2022
6.85 2926
28.00 2075
17.51 603s
800
1.67 =0ar
1.90 *0.
69.10 #451
65.74 +10.4
8000
9.21
=014
7.38 *..
30.88 =104
21.18 ma.0
1000
1.62 =02:
1.97 *0.s
73.42 #284
68.05 #336
10000
8.95
=022
7.10
+02s
32.31 +1a
22.34 #os1
Table 4: Results for varying N,, the maximum number of samples algorithm can use for training. Left: IMDB with N₂, = 1000, C₁ = 0.25, ta 5%. Right: Tiny-ImageNet with N₂ 10K, Ci 0.25, Ea = 10%. Mean and std. deviations are reported.
Setup. We limit the amount of training data the algorithm can use and record the resulting auto-labeling error and coverage. We ensure all algorithms have sufficiently large but equal amounts of validation data. We run on Unll-Ball, IMDB, Inn-leeeene,, and CIFAR-10 10 datasets with the same values of n,a, Ylb, and C' as in previous experiments.
Results. Figures 4(a), 4(b), and 2(b) indicate that TBAL and methods utilizing selective classification (AL+SC, PL+SC) maintain a high level of accuracy, even in scenarios where minimal training samples are used. This is expected as the threshold estimation method (when used with sufficient validation data) will find auto-labeling thresholds such that the auto-labeling error does not exceed Eg. The impact of training data size can be seen clearly in the coverage achieved by the algorithms. As expected, with fewer training samples the model has low accuracy leading to low coverage. However, as more samples are acquired, a more accurate model within the function class is leamee,, resulting in increased coverage. The Appendix D has additional discussion and results.
5 Related Work
We briefly review related work, deferring a more detailed discussion to the Appendix A.
There is a rich body of work on active learning (AL) [57, 12, 30, 28, 8] focused on learning the best model in function class with less labeled data than passive learning. Various AL algorithms have been developed and analyzed, e.g., uncertainty sampling [62, 45], disagreement region based [9, 27]. margin based [4] and abstention based methods that minimize the Chow's excess risk [72].
Selective classification (SC) equips a given classifier with the option to abstain from prediction in order to guarantee prediction quality. The foundations for SC are laid down in [17, 67, 18, 68) where results on the error rate in the prediction region and the coverage of the given classifier are provided. However, these works lack practical algorithms find the prediction region. A recent work [26] gives a disagreement-baas -based active learning strategy to learn selective classifier.
A recent paper [49] studies TBAL-like algorithm for auto-labeling. It focuses the cost of training incurred when these systems use large-scale model classes for auto-labeling. It proposes an algorithm to predict the training set size that minimizes the overall cost and provides empirical evaluation.
Weak supervision is another line of work aimed at auto-labeling that does not rely on obtaining human labels but instead uses potentially noisy but cheaply available sources to infer labels [51, 22]. In contrast, we are focused specifically on analyzing the performance of TBAL algorithms [58].
Conclusion and Future Work
In this work, we analyzed threshold-based lato-labeling systems and derived sample complexity bounds on the amount of human-labeled validation data required to guarantee the quality of machine-labeled data. Our study shows that these methods can accurately label a reasonable size of data using seemingly bad models when good confidence functions are available. Our analysis points to the hidden downside of these systems in terms of large amount of validation data usage and calls for more sample-efficient methods including active testing.
7 Acknowledgments
This work was partly supported by funding from the American Family Data Science Institute. We thank Stephen Mussmann, Changho Shin, Albert Ge, Yi Chen, Kendall Park, and Nick Roberts for their valuable inputs. We thank the anonymous reviewers for their valuable comments and constructive feedback on our work.
10

---

References
[1] Tiny imagenet dataset.
Accessed: May 16, 2023.
[2] Airbus. Airbus active labeling blog. http:///wwbddaaaaaaaa..co/co//// automatic-
htt.:a---oootttioo----ecccooaca- -eeteeiiinnnn-------- and-ai/,
2022. Accessed: 2022-11-18.
[3] Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. Margin based active learning. In COLT, 2007.
[4] Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-316. PMIR, 2013.
[5] Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning, pages 49-56, 2009.
[6] Kamalika Chaudhuri, Sham M. Kakade, Praneeth Netrapalli, and Sujay Sanghavi. Convergence rates of active learning for maximum likelihood estimation. In Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015.
[7] C Chow. On optimum recognition error and reject tradeoff. IEEE Transactions information theory, 16(1 1:41-46, 1970.
[8] Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning at scale. In Advances in Neural Information Processing Systems, volume 34, pages 1193--1944, 2021.
[9] David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning, 15(2):201-221, 1994.
[10] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82. Springer, 2016.
[11] Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Y. Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2006.
[12] Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 1177191:1767-1781, 2011. Algorithmic Learning Theory (ALT 2009).
[13] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In International conference computational learning theory, pages 249-263. Springer, 2005.
[14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Puttern Recognition, pages 248-255, 2009.
[15] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 2012.
[16] Giulia DeSalvo, Mehryar Mohri, and Umar Syed. Learning with deep cascades. In Proceedings of the Twenty-Sixth International Conference on Algorithmic Learning Theory (ALT 2015). 2015.
[17] Ran Gl-Yaniv and Yair Wiener. On the foundations of noise-free selective classification. JMLR, 11:1605-1641, aug 2010.
[18] Ran El-Yaniv and Yair Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
[19] Hugging Face. Hugging face mteb leaderboard. https://huggingface wttpaaacc..ccooppeeeeeeeeeeeeeee http:///gacccccco//ppc//////a/// leaderboard, 2023. Accessed: 2023-08-07.

---

[20] William Feller. Generalization of a probability limit theorem of cramér. In Transactions of the American Mathematical Sociery, pages 361-372., 1943.
[21] S. Fralick. Learning to recognize patterns without a teacher. IEEE Transactions on Information Theory, 13(1):57-64, 1967.
[22] Daniel Y. Fu, Mayee F. Chen, Frederic Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In Proceedings of the 37th International Conference Machine Learning (ICML 2020), 2020.
[23] Olivier Gascuel and Gilles Caraux. Distributiin-free performance bounds with the resubstitution error estimate. Pattern Recognition Letters, 13(11):7577764 1992.
[24] Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, al. A survey of uncertainty in deep neural networks. arXiv preprint arXiv:2107.
2021.
[25] Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
[26] Roei Gelbhart and Ran Ei- Yaniv. The relationship between agnostic selective classification, active learning and the disagreement coefficient. The Journal of Machine Learning Research, 20(1):1136 1173, 2019.
[27] Steve Hanneke. A bound on the label complexity of agnostic active learning. ICMI., 2007.
[28] Steve Hanneke. Theory of disagreement- based active learning. Found. Trends Mach. Learn., 7(2-3):131-309, jun 2014.
[29] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem. 2018.
[30] Daniel Joseph Hsu. Algorithmss for active learning. PhD thesis, UC San Diego, 2010.
[31] Matti Kääriäinen. Active learning in the non-realizable case. In International Conference on Algorithmic Learning Theory, pages 63-77. Springer, 2006.
[32] Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification. In International Conference on Machine Learning. pages
PMLR, 2021.
[33] Jannik Kossen, Sebastian Farquhar, Yarin Gal, and Tom Rainforth. Active testing: Sample-efficient model evaluation. International Conference Machine Learning, 2021.
[34] Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915-1924. PMLR, 2017.
[35] Ranganath Krishnan and Omesh Tickoo. Improving model calibration with accuracy versus uncertainty optimization. Advances in Neural Information Processing Systems, 33: 18:18887-18248, 2020.
[36] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[37] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11)2277--232, 1998.
[38] Yann LeCun, Sumit Chopra. Raia Hadsell, M Ranzato, and Fujie Huang. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
[39] Michel Ledoux and Michel Talagrand. Probability in banach spaces. 1991.
[40] Chunwei Ma. Ziyun Huang, Jiayi Xian, Mingchen Gao, and Jinhui Xu. Improving uncertainty calibration of deep neural networks via truth discovery and geometric optimization. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 75-85. PMLR, 27-30 Jul 2021.
12

---

[41] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts, Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pages 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguisties.
[42] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. In Advances in Neural Information Processing Systems, volume 34, pages 15682-15505 15694, 2021.
[43] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. The MIT Press, 2012.
[44] Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. Mteb: Massive text embedding benchmark. arXiv preprint arXiv:2210.07311 2022.
[45] Stephen Mussmann and Percy Liang. On the relationship between data efficiency and error for uncertainty sampling. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
[46] John Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances large margin classifiers, 10(3):61-74, 1999.
[47] Nikita Puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. Proceedings of Machine Learning Research, pages 3806-3832. PMIR, 2021.
[48] PyTorch, Cifar-10 pytorch tutorial. https://pytore: http:://pyroorc..orr/uttoiissss 1.ffa10_tuutoiill html, 2022. Accessed: 2022-11-18.
[49] Hang Qiu, Krishna Chintalapudi, and Ramesh Govindan. Minimum cost active labeling. arXiv preprint arXiv:2006. / 13999, 2020.
[50] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.
Learning transferable visual models from natural language supervision, 2021.
[51] J. J. Ratner, Christopher M. De Sa, Sen Wu, Daniel Selsam, and C. Ré. Data programming: Creating large training sets, quickly. In Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 2016
[52] Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the 44th International Conference Very Large Data Bases (VLDB), Rio de Janeiro, Brazil, 2018.
[53] Joseph Redmon and Ali Farhadi. YOL09000: better, faster, stronger. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6517-6525, 2017.
[54] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning, 2020.
(55] Samsung-SDSS Samsung sds auto-labeling service. https:/ / //www//www./a/ www.sssamungadsso wttpeaadss.cooooooooommmmeooo com/en/ Insights//Techhoolkits pttpooooookittiii___e_111 Ltapit__2221________11ee_e Lartel_Att___aaba Laatt_Labellngg.. html, 2022. Accessed: 2022-11-18.
[56] Nabeel Seedat and Christopher Kanan. Towards calibrated and scalable uncertainty representations for neural networks. arXiv preprint arXiv:1911.00100 2019.
[57] Burr Settles. Active learning literature survey. 2009.
[58] SGT. Aws sagemaker ground truth. data- 2022. Accessed: 2022-11-18.
https://aws amazon. wawaoo.cco//sageaaaaaa www.c/o/o/aaaaaceccc
[59] Kulin Shah and Naresh Manwani. Online active learning of reject option classifiers. Proceedings of the AAAI Conference Artificial Intelligence, (4(04))5652-566) 2020.
[60] Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. IEEE Journal on Selected Areas in Information Theory, 2(2):705-719, 2021.
13

---

[61] Superb-AI. Superb ai automated data labeling service. product/automate,, 2022. Accessed: 2022-11-18.
ai com/
[62]
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45 66, 2001.
[63] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 30th Conference on Neural Information Processing Systems (NIPS 2017), 2017.
[64] Rudy Venguswamy, Mike Levy, Anirudh Koul, Satyarth Praveen, Tarun Narayanan, Ajay Krishnan, Jenessa Peterson, Siddha Ganju, and Meher Kasam. Curator: A No-Code Self Self-Supervise Learning and Active Labeling Tool to Create Labeled Image Datasets from Petabyte-Scale Imagery. In EGU General Assembly Conference Abstracts, pages EGU21-6855
April 2021.
[65] Deng- Deng-Bao Wang, Lei Feng, and Min-Ling Zhang. Rethinking calibration of deep neural networks: Do not be afraid overconfidence. Advances in Neurul Information Processing Systems, volume 34, pages 11 1189--1820, 2021.
[66] Yingfan Wang. Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: An empirical approach to deciphering t-sne, umap, trimap. and pacmap for data visualization. Journal of Machine Learning Research, 22(201):1-73, 2021.
[67] Yair Wiener and Ran El- Yaniv. Agnostic selective classification. Advances in neural information processing systems, 24, 2011.
[68] Yair Wiener and Ran EI- Yaniv. Agnostic cointwise-compecitvee selective classification. Journal
of Artificial Intelligence Research, 52:171-201, 2015.
[69] Ting-Fan Fan Wu, Chih-Jen Lin, and Ruby Weng. Probability estimates for multi-class classification
by pairwise coupling. Advances Neural Information Processing Systems, 16, 2003.
[70] Shitao Xiao, Zheng Liu, Peitian Zhang, and Niklas Muennighoff.. C-pack: Packaged resources advance general chinese embedding, 2023.
[71] Yufan Zeng and Jiashan Tang. Rlc-gnn: An improved deep architecture for spatial-based graph
neural network with application fraud detection. Applied Sciences, 11, 06 2021.
[72] Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. arXiv preprint arXiv:2244.00043 2022.
14

---

Supplementary Material
The supplementary material is organized as follows. We provide a detailed discussion on related works in Section A. We give details of the definitions and notation in Section B.1. The notations are also summarized in the Table in section B. Then we give the proof of the main theorem (Theorem 3.2) followed by proofs of supporting lemmas in section C. We provide details of its instantiation for finite VC-dimension hypothesis classes and the homogeneous linear separators case in Section C.3. Then, we provide the technical details of the lower bound (Lemma 3.3). Then we provide details of additional experiments Section D. In Section D.4 we provide insights into auto-labeling using PaCMAP [66] visualizations of lube-la regions in each round.
A Extended Related Work
There is rich body of work on active learning on empirical and theoretical fronts [57, 12, 30, 28, 8, 54]. In active learning, the goal is to learn the best model in the given function class with fewer labeled data than in classical passive learning. To this end, various active learning algorithms have been developed and analyzed, e.g., uncertainty sampling [62, 45), disagreement region based [9, 27], margin based [3, 4]. importance sampling based [5] and others [6]. Active learning has been shown to achieve exponentially smaller label complexity than passive learning in noiseless and low-noise settings [13, 3. 27, 28, 4, 11, 30, 6, 34, 32]. This suggests, in these settings auto-labeling using active learning followed by selective classification is expected to work well. However, in practice we do not have favorable noise conditions and the hypothesis class could be misspecified i.e. it may not contain the Bayes optimal classifier. In such cases, [31] proved lower bounds on the label complexity of active learning that are order wise same as passive learning. These findings have motivated more refined goals for active learning- - abstain on hard to classify points and do well on the rest of the points. This idea captured by the Chow's excess risk [7] and some of the recent works [60, 59, 47, 72] have proved exponential savings in label complexity for active learning when the goal is to minimize Chow's excess risk. The classifier learned by these methods is equipped with the abstain option and hence it can be readily applied for auto-labeling. However, the problem of misspecification of the hypothesis class still remains. Nevertheless, it would be interesting future work to explore the connections between auto-labeling and active learning with abstention. We also note that similar works on learning with abstention are done in the context of passive learning [10].
Another closely related line of work is the selective classification where the goal is to equip a given classifier with the option to abstain from the prediction in order to guarantee prediction quality. The foundations for selective classification are laid down in [17, 67, 18, 68] where they give results on the error rate in the prediction region and the coverage of a given classifier. However, they lack practical algorithms to find the prediction region. A recent work [26] proposes new disagreement based active learning strategy to learn a selective classifier.
Recent work studies a practical algorithm for threshold-based selective classification on deep neural networks [25]. The algorithm estimates the prediction threshold using training samples and they bound the eгror rate of the selective classifier using [23]. We note that their result is applicable to a specific setting of a given classifier. In contrast, in the TBAL algorithm analyzed in this paper, selective classification is done in each round and the classifiers are not given a priori but instead learned via ERM on training data which is adaptively sampled in each round.
Another related work [49] studies an algorithm similar to TBAL for auto-labeling. Their emphasis is on the cost of training incurred when these systems use large-scale model classes for auto-labeling They propose an algorithm to predict the training set size that minimizes the overall cost and provides an empirical evaluation.
Well Well-calibrated uncertainty scores are essential to the success of threshold-based auto lubo-labeling. However, in practice, such scores are often hard to get. Moreover, neural networks can produce overconfident unreliable) scores [29]. Fortunately, there are plenty of methods in the literature to deal with this problem [46, 69]. More recently, various approaches have been proposed for uncertainty calibration for neural networks [24, 42, 65, 35, 40, 56]. A detailed study of calibration methods and their impact auto-labeling is beyond the scope of this work and left as future work.
There is another line of work emerging towards auto-labeling that does not rely on getting human labels but instead uses potentially noisy but cheaply available sources to infer labels 52, 22]. The focus of this paper, however, is on analyzing the performance of TBAL algorithms [58, 2] that have emerged recently as auto-labeling solutions in systems.
15

---

B Definitions and Notation
B.1 Basic Definitions
Let X be the instance space and p(x) be density function supported on X. For any x; E let yr be its true label. Let X (x.....;X)) } be set of N i.id samples drawn from X. Let set S X denote non-emply sub-region of X and S S X nS be a set of > iiidd samples.
Definition B.1. (Hypothesis Class with Abstain) We can think of the function g along with set T as inducing an extended hypothesis class HT) Let HT H x T. For any function (h, E H(T.a) defined as
(h, (x)) = [h(x)
if gh, x) 2
O.W.
Here (h, (x) = means the hypothesis (h,, 1) abstains in classifying the point x. Otherwise, it is equal h(x).
The subset S(h, 1) S S where (h,t) does not abstain and its complement S(h, t) where (h, t) abstains, are defined follows,
S(h, (x S: (1,))(x) #1},
8(h, = (x S (x) =1}
Probability Definitions. The probability P(S) of subset S S X and the conditional probability of any subset S' C S are given as follows,
(()
P(S) = P(S) =
p(x)dx, XES
P(S'SS) = P(S)
== P(((()))))))))
The empirical probabilities of S and S' C S are defined as follows,
P(()) = S
P(S')S)= = S
t(h, = [5(h, D)
SS]
[S]
Loss Functions.
The loss functions are defined as follows,
fo-1(h, (,, y) = 1(h(x) # v), (1h ((g(h, t), (h, ko- x, v) l (h,
Error Definitions.
Define the conditional error in set S X' as follows,
f (0,101,4,,,00
p(x) dx TP(S)
E(h, (S) == (0
Then, the conditional error in set S(h, f) i.e. the subset of S on which (h, does abstain,
Eh, HSS) P(h, t(S)
(h, ([S) == E(,, 1)) 1 v)]
Similarly, define their empirical counterparts as follows,
E(h,t|S) = 1 S
(h,
X,ES
ε, (h, = E(h,
Σ
f (h,
(s(h,t) t)
x,ES(h.))
Note that,
Σ
Σ
(,,
Σ
lo-1 X,,
X:ES
XiES(h.t)
XiES(h.1)
16

---

Symbol
Definition
feature space.
V
label space.
H
hypothesis space. hypothesis in H.
h
x.
x is an element in and y is its true label. iid. samples in S.
S.S
S _ X' is sub-region in X, = (xI,..., X,) unlabeled pool data points.
X Xpoot
X my
(i)
set of validation points at the beginning of ith round and ny (2)
|x
X1 ,
set of auto-labeled points in ith round and n |x,
ERM solution and luto-labeling thresholds respectively in ith round. unlabeled region left at the beginning ith round. unlabeled pool left the beginning of ith round.
X
m
number of auto-labeling mistakes in ith round. number of rounds the TBAL algorithm. set of all auto-labeled points till the end of round k. confidence function g x X + T. Where T S IRt, usually T = [0,1] Cartesian product of H and the range of g.
k
X Xpoot( As)
9
H
(4) >k Ra
(h,1(h,
I(h(x) # y).
(1, x)
I(g(h, x)
2t).
(h-1 v)
1--1 x, v) & (hh, x).
R,, 10-1)
E..s suPhEn n Ex= oi o x,, vi)
R, (H(:9, E1)
E, (H
á ii=1 o (h, xx:)
R. (H(T,,ed_))
E., (H 1 E oze (n, t, x3, x.
RM, lo-1) + Ri (H (11)))1) L1). (h, 1,,, 5) Li=l f- (h, X,, ExIs (i,ste(h,t,t) IS
(())
Exisl 1
E(),
[s|
P(),
P(h,
== E (h,,, t, N.))).) (/h, ((S). {( t(S).
E
E, (h,
(h,
Table 5: Glossary of variables and symbols used in this paper.
Rademacher Complexity, The Rademacher complexities for the function classes induced by the H. T. g and the loss functions are defined as follows,
Rn (o-1) Eo,g sup hew 71
Σ o 1 (k,,
Rn (7 ,,)) = -Er
ogli (1o, (,),,,)))
sup (H
i=1
Ri (H (001000011 = Reg.g
Σ
oit (hi, xi, vx)
sup
(h.1)EH?
1=1
Ri (HTT.)) = RR (7L, fo-1) + Rr (H (.TT) (11)
B.2 Glossary
The notation is summarized in Table 5 below. More detailed notation is in section B.I.
17

---

C Proofs
C.I Proofs for the General Setup
We begin by restating the theorem here and then give the proof.
Theorem 3.2. (Overall Auto-Labeling Error and Coverage) Let k denote the number of rounds of the TBAL Algorithm J. Let mh ,u
(8) (t) denote the number of validation and auto-labeled points at
epoch and (6) = Let Xpoot(As (At) be the set of auto-labeled points the end of round
N( =E==1 (t) denote the total number of auto-labeled points. Then, for any 8 E (0, with probability at least 8,
(1) No
E( ((Xpol(Ak))
Σ
Ea
+
4
(R (?(T.0)
2
log(
8k
P.
av
Po
n
(3)
(b)
+
-
4
N(k)
n2
(3)
(H
+
N=
k
log(
8k
and
P
(c)
((X)oo(AA)) P(Xpool (Ax)) 2
Σ P(xx0 - 2D, (H -V
2k2
log
18k
N
8
Proof. Recall the definition of auto-labeling error,
((Xpor(Ass) (As))
ma
ma (1)
n Eo (hi, (1)(())))))
N
(3)
Here, mi is the number of auto-labeling mistakes made by the Algorithm in the ith round and E. (he, (+)) is the auto-labeling error in that round. Note that we cannot observe these quantities since the true labels for the auto-labeled points are not available. To estimate the auto-labeling error of each round we make use of validation data. Using the validation data we first get an upper bound on the true error rate of the auto-labeling region i.c. Eg (h., & (z)()) in terms of the auto-labeling error on the validation data E. (h., & x!") and then get an upper bound on empirical auto-labeling error rate E. (hi, (0) using the true error rate of the auto-labeling region.
We get these bounds by application of Lemma C.I with 63 8/4k for each round and then apply union bound over all k epochs. Note that we have apply the lemma twice, first to get the concentration bound w.r.t the validation data and second to get the concentration w.r.t to the luto-labeled points.
Eg (he ((1(0) < Ea f(x!)) + - R
(H
+
2
log
8k
Pb
Pb
nh
(h,, s Ea (1)
+
- R
4
(HT
+
2
log
8k
Pb
ne
P
(3)
5
Substituting Ea (h., E, (0) by its upper confidence bound the validation data.
(he, s Es ( + 2
ca)
(HT.9)
T.0)
+
2
nt (s)
(H(Ti))
2
8k
8k
+
log
+
log
R
new
(4)
8
R
nu
(+)
18

---

Having an upper bound on the empirical auto-labeling error for 1th round gives an upper bound on the number of auto-labeling mistakes ma auto-labeling mistakes in all A rounds and thus the overall auto-labeling error as detailed below,
(8) made in that round. It allows us to upper bound the total
(1) ma N!R
{(Xmoc(AA)) (Ax))
m - nn - (h,,
Since we have an upper bound on the empirical auto-labeling error in each round, we have an upper bound for each m. (5) which are used as follows to get the bound on the auto-labeling error,
4:
(i)
(XXpool (oot)(AA)))
Ma
N(a)
(8)
(8)
ng
ma
N(k)
na
Eg ( (x())
N=(k)
n
Ea (h E/ x2
4
(H
2
1
log
8h
N(
P.
na
P.
V
na
(6)
8
na
Eg (h. E (()
+
R
(1(
+
log
8k
Pb
nu
P.
nhp
4
2
Sk
+ - R
(0)
(HL
T9
+
log
Pb
Pb
nha
8
Ea
(h
x(())
4
Ri
(H
+
4
(9) (H.T.))
(k)
Pb
nu
Pb
2
8k
na
(4)
2
8k"
log
+
log
[3)
N!6 (6)
(2)
ni
R.
na
The last term is simplified as follows,
Ra
(
1
8k
k
na
8k
log
log
Pb
na
(8)
(3)
k
8h
log
Pb
N
(8)
8
(8)
2
8k
V
log
P.
N
(k)
8h
k
log
N!!
88
log
The last inequality follows from the application of the inequality |/u|] VTl ///lu|/2 for any vector
Rt Here we let ( ..... .n... (') and since vi Vnd
(1) na > 0 so, Σ vna (3)
=||u||
19

---

and (((a)
-//u1/2
k -==1
(2) na
Vk
k N
((k)
To get the bound on coverage we follow the same steps except that we can use all the unlabeled pool of size n(i) to estimate the coverage in each round which gives the bound in terms of vz()) and N as follows,
k
p(XpoolAAp) = N
n
1=1
(8)
11
N
n
n
0) -P(X x(1) |(())
(.) .0..phh,, & (110)
k (()
(i -2 (H(T10)
1 log
8k
V (n))
N
n(()
(P 2D (A(110))
V. N
h:
log
(75)
88
N
We bound the first term as follows,
( (h),
The,
(1)2(00)
N
N P(X(0)
(P(at(ng
(P(x(0)
-Vx
1
log (8h))
88
P(2(())
N
// 1
8h
Σ
(ha,
log
N
5
Substituting it back we get,
P(Xpoot (Ax)) 2 Σ (h.,) 29, (7( kV N
1 log
8k
8
V N
k
log
8h
8
Σ p (hx) f.)) -2R (H(
4k2
8k'
log
N
For the last step we use the inequality v Vb s 22(a + b) for any a, E R
Rademacher complexity and validation error trade-off. The bound contains validation errors at different thresholds. We revisit the definition of validation error appearing in the bound. Let X, = (x1,... Vn,) } be the validation samples and y; be the label corresponding to z,. Given any h H. and the confidence function g, we have different subsets X, (h, t) of the validation points for
20

---

which the model's confidence is higher than t. More precisely, (h, - {z, E Xx: g(h, 2;) 2 z} and the validation error Eg (h, ((x)) is computed on each of these subsets follows, & (h, t|X.)) (A,A Exsex. ((((z,) # Hy; this error is different from the overall validation error which is computed over the entire set of validation points Xg:
{(|[x,)
Σ Z,EX,
1(h(2;)) # y:).
X
The TBAL method computes & (h, ()) at different thresholds (t) and selects the threshold at which it is at most Thus even if the overall validation eπror {h),X,,, is bad, there could still be regions in the space where the conditional validation error & (h, x(X,) is small. This can be easily seen in Figure 2 in the paper. Here we are doing auto-labeling using a linear function class that has low Rademacher complexity. All the models in this class have high overall validation error (,))x,, but there are subsets where the conditional validation error (h, x)x,) is small and TBAL is able to find those subsets. Thus we see that working with low Rademacher complexity classes might lead to high overall validation error. However, it does not affect TBAL as long as there are regions of low conditional validation error Ed x)) Furthermore, our upper bound on excess auto-labeling error depends on E. (h, x) which due to the TBAL procedure is most and hence it is not in conflict with the Rademacher complexity term.
Next, we state the result for uniform convergence between &a (f,, Ea (h,) and give its proof.
Lemma C.I. For any 83.R, E (0, 1), let S and be defined as above. Let F(h, t|5) 2 P. and 4(), 2 R v4h,,) 1) E H. ,, the following holds w.p. at least 1 - 03/2
4 Ri (H(
2 2 log
E. (h. - (h, S
+
V(h,t) E HT.
(4)
Pb
P.
83
Proof. We begin with proving one side of the inequality and the other side is shown by following the same steps. The proof is based applying the uniform convergence results for E(h, t|S) and t(h, from Lemma C.2. The main difficulty here is that Es(Ea (h. t t[s)] * &a (h, t|S). so we cannot directly get the above result from standard uniform convergence bounds.
We prove it, by using the results from the Lemma C.2 and restricting the region S such that it has probability mass at least Rb-
By definitions of & (h, S) and & (h, ((S) we have,
S(h,48)= = Ph, (S)) Ea (h, ())) and
((144)) = ((4 (1,
Let Ei (ll/))oog(2/0))555 v ((1/)) log (2)2). From lemma C.2 we have,
E(h,18) S E(H,4S) + 29R, (H(T:9)
+ + v(h,t) t) E HTs
w.p. 1 51
(5)
(hh, (|S) < ((), + 2nR (HTTw)) + E2 V(h, t) E HT Plugging in the above definitions of errors in equation (5) we get,
w.p. 1 - 82/2.
(6)
Phh,, 1[8) Ea (h, < P(h,1)) Eo (1) 29t, (?(Ti)
+ E1-
(7)
E. (h, < P(h, (|S & (1,4(s) + 2 P(h,, ([8)
R
E1
(8)
P(h, I())
P(h, 1[8)
Substituting (Phh,t f) from equation 6 in the above equation, we get the following w.p. (1- 2)) 62/2), V(h,t) t) E HT.9
Ea (h, () < 118, + 29R, (H E2 E, (1.,t)s) + 2R,, (H(
E1 P(h, ([)
+
IPh (|5)
P(h,!S)
21

---

= =(1+ P(h, ((h,
29,, (H(T-0)
&2 E (h, t|s) + 29h, (2(T.9)
E1
P(),
P(h, 1(S)
29,, (H.T.s) Ea (h,) + P(h,t|s) th, + 2DR, (H.T.))
Ea (h,
P(h,)
P(h, t|s)
E
+
P(h, t|s)
Using upper bound (h, (|) S 1 in the second and third terms,
+ 4 R, (HT.a)
+ & + E2 t(),
th,) s (h.tls)
v(h,t) E 7L2 w.p. 2 1 - (61 + -2)/2.
t(h,
Using P(h, t|5) 2 R En (b,1)8)) < En (b, [|5)
+ 4 Ri (HT
1 + &2
v(h,t) E HT w.p. 2 1 (61 + 022/2.
Pb
Pb
Letting 81 = 82 = 83 and & = E =
f1h
gives E =
log
2
and
2
V 16
0g
t|s v Eg h, ( + 4 Ri (7( + v(h,t) E H w.p. 21 8g. Ea (h. (h,
Po
This proves one side of the result, and the other side of the result follows similarly.
Lemma C.2. Let S C X be sub-region of X and S = (xi.... Xn) be set of n. i.id samples in S drawn from distribution Px. Let (y1.... 3n be the corresponding true labels, let Rr (HH"ss be the rademacher complexity of class H then for any 81, 82 E (0, 1) we have,
2
18 (() - ((1, < 29 (H
V
log(
v(h,1) E HT
w.p. 1- 81/2. (9)
51
1
2 )oo v(h,t) E HT w.p. 1 1- 1-22/ (10)
[(hh, ((h, ib, [[S] S 29R, (H(T.)
-
+
[V log(
Proof. The proof is similar the standard proofs for Rademacher complexity based generalization error bound. Since we work with the modified loss function and hypothesis class to include the abstain option, for completeness we give the proof here. The proofs for error and probability bounds are very much the same except for the change in the loss function. We give the proof for the error bound here.
The result follows by applying McDiarmid's inequality on the function Φ(S) defined as below,
Φ(S)= = sup E(h,t|S) - (,, (hhhht|5) t|S).
(M.
To apply McDiarmid's inequality we first show that c(S) satisfies the bounded difference property (Lemma C.4). This gives us
81 w.p. 1 2
-(s(, < ((S)= S Es(d(S)] + log( v(h,t) E HTTs
Using the bound on EEs [oS)] from Lemma C.3 we get,
E(h, t|S) < Eh,, t|s) + 29t (H(T.0) + V log(
v(h,t) E TTo w.p.
51 2
81
Similarly, the bound for the other side is obtained which holds w.p. 1 62, and combining both we get eq. (9). The bound of probabilities is obtained by following the same steps above but with different loss function, é since (h, 4SS) is the probability mass of the region where (hr, 4) does not abstain.
22

---

Lemma C.3. Let S S X be sub-region of X and S = (xi,..., Nnn f be set of i..d samples in S drawn from distribution Px. Let fy1.... -yn be the corresponding true labels and let R, (Hf..) be the Rademacher complexity of the function class HT defined over iid. samples. Then we have,
Es (W.E)TT
sup
t(h, - - S 29% (7
(11)
Proof. Let (81, x2.... x be another set of independent draws from the same distribution as of S and let the corresponding labels be {y1,.... .Jn.. These samples are usually termed as ghost samples and do not need to be counted in the sample complexity.
Es
sup (N,
E(k,
E(h,&[s)]
Es
sup (1,0)ETTT
g ((h,, [[5]] - E(h,
= Ess
sup (H,))EHT
Eg [g(E(h, - E(h, [s]]
< Es
Es
sup (h,d)EHT
[E(1,115) - E(,,4)]]
Es,s
sup NEMT
[Eth, 115) - E(h, [1s]]
n Σ
1 n
=Es,s
sup (h.))ETT.
60 (h, x,,
(h,
t (h, x.,x)
n
n
i=1
i=1
E G,5.
sup
Σ
a 0,00-11 1,, (1)
Σ 1 t,, wi)]]
hEHTi
in
I E 5
sup (Hi
(h, 1,, t,, 01)
n (h,
Eg,
sup (h.t)EHT
Σ
(h,t,,,,
2n (H (._
S 29t (HT:s).
In the last step, we used the upper bound on the Rademacher complexity from Lemma C.5.
Lemma C.4. (Bounded Difference) Let S be set of i.idd samples from Px then for @(S)
:=
SUP(L,)ETTT t()) - E(h, t|S), with probability at least
1 S
o(S) < Es(o(S)] +
log(
(12)
Proof. It is proved by showing that d(S) satisfies the conditions (in particular the bounded difference assumption) needed for the application of McDiarmid Inequality. To see this Let
S= (x1. X2.... X.,] and let S' = (x1,X2 X2.........X x!...., xn), i.e. S and S' may differ only on the 7th sample.
((S) - -((5))= = sup (H.
E(h,18) E(h,11)- sup
E(h, E(h,
(K.DERT
(E(h,t|s) - E(h, - E(h,t()) + E(h. ((0
sup (h,D)
(E(h, - E(h, (1s)
= sup (b.
Σ e (
Σ
4 (h, t, X,x,, 8))
sup (h.
S
|
E,ES
2,ES'
23

---

= sup (A.DEHT
(c (h, U)) f (h,,,,,; +
1
( -t)
sup (h.1)E7Ta
The last step follows since 6 is a 0-1 loss function so letting ( L, x4, v1) and f (h, t, x1, v/4 = gives an upper bound on the difference. Thus we can apply McDiarmid Inequality here and get the bound.
The relationship between the Rademacher complexities is obtained using the following Lemma C.5 due to [16].
Lemma C.S. ([16)) Let to-1, l be the loss functions defined as above and the Rademacher complexities i...d. samples S be Rn (H, fo-1) R., (H(T.0, RT,T. L.).RR, (H lj-1) respectively. Then,
R, (H l (0_)) 1 Hi (H, f0-1) R. (H (L) Rn (H(
(13)
Detailed proof of this lemma can be found in [16]. The result follows by expressing fo-1 li as (fo-1 + E 1)+ and then applying Talagrand's contraction lemma [39].
C.2 Bounds for Finite VC-Dimension Classes
Here we specialize the auto-labeling error and coverage bounds to the setting of finite VC-dimension classes and then instantiate for specific setting of homogeneous linear classifiers and uniform distribution.
Lemma C.6. [43] (Corollary 3.8 and 3.18). Let the VC-dimension of function class induced by F be any class of functions from X' + y } and L: [U + {0, 1) be 0-1 function. Then,
2V(F,() E) R. (F,0F
log V(F, E)
en
(14)
n
Corollary C.7. (Auto-Labeling Error and Coverage for Finite VC-dimension Classes) le denote the number of rounds TBAL algorithmm 1. Let (H(Taa) d Let X poot (Ax) be the set of auto-labeled
points at the end of round k. _R. Di=1 na denote the total number of outo-labeled points. With probability at least - 8.
(2)
ppo (Ax)) 5
Tha (R)
2d log
eeny
+ log
8k
(3)
Re
(a)
(b)
(N((k) d
4
2k
8h
2d
+ log
Pb
!!(k)
and
P(X (Ax)) Σ p(x 1.)) 2 N 2d (-))
(eN
+ log
(7))
8h
24

---

Proof. The proof follows by substituting the Rademacher complexity bounds for finite VC dimension function classes from Lemma C.6 in the general result from Theorem 3.2.
(i)
p(Xpoo(AAk)
no
4 (R n +
(H + " ( (H!TI))
N(
(0)
(6)
4
8k
4
8k
+
log
log
Pb
(3)
P6
N(k)
(c)
(d)
We first simplify the terms dependent on n /2(a + b) for any a, b E IR+
as follows. Here we use the inequality vā + vb
Ri 19 (H
+
log
8k
2d
log
Enly
+
log
4k
(8)
d
7hp
eel (2)
2
8K 8
2d log
+ log
(5)
Thv
Next, simplify the terms dependent na follows. First, substitute the Rademacher complexity using the bound in Lemma C.6 and then apply the same steps as in the proof of Theorem
(6)
3.2 bound Ei i- Vnad get the final term.
(i) /N by V k//! followed by the application of Vā vb S 2(a + b)
H k))
(9)
(HTT))
+
k (k]
log
Sk
na
(k)
(
2d
log
ena
(8)
+
N:(k)
k
log
8k
i=1
nh
na
(
(enaa (1)
k
8h'
2d
+
log
\r(k)
5
(eN(k)
k
8k'
2d
2d
log
((k)
(k)
(x(
5)
(.V.(k)
2dk:
k
8k 8
log
log
(k)
d
N
2k
(e.Ve) d
8h
2d
+ log
8 )
C.3 Homogeneous Linear Classifiers with Uniform Distribution
Here we instantiate Theorem 3.2 for the case of homogeneous linear separators under the uniform distribution in the realizable setting. Formally, let Px be a uniform distribution supported on the unit ball in Rdd, X' = fx E Rd |x||| < 1}. Let W {w Rdd ||w||2 1} S and H (x >> sign(ww, x)) Vw W). the score function is given by g(h, x) = g(w, x) (w: x) and set T = [0, 1]. For simplicity, will use W in place of H.
Corollary 3.4. (Overall Auto- Labellng Error and Coverage) Let W., Eg be the ERM solution and the (8) auto-labeling margin threshold respectively at epoch Let (5) no denote the number of validation and labeled points at epoch i. Let the labo-labeling algorithm run for k-epochs. Then, for any
25

---

5 E (0, 1), w.p. at least 1 - --/22
* nl
(8)
2
cnb
(2)
8h:
(Ax))
2d
log
+ log
((k)
Pb
n
d
5
(a)
(b)
4
2k:
(eN2()
8h:
+
2d
+ log
N((
d
8
and w.p. least 1 - -8/2
TeNV d
Sh' 8
2d log P(X (Ax))) 2 1 min 4, /d/ π 2kg
+ log
N
Proof. The bound on auto-labeling error follows directly from Theorem C.7 as the VC dimension for this setting is d. For the coverage bound, utilize the fact that the distribution Px is the uniform distribution over the unit ball. This enables us to obtain explicit lower bounds on the coverage. The details are given in Lemma C.8 and Lemma C.9.
Lemma C.8. Let the auto-labeling algorithm run for k-epochs and let w., l be the ERM solution and the luto-labeling margin threshold respectively epoch i. Let X be the unlabeled region at the beginning of epoch i, then we have,
Σ P( 2 1-mmmnn--- & / /d/m
(15)
Proof. Let t4) fx E X (W,, x)1 2 & denote the region that be auto-labeled by w,,4, However, since in each round the remaining region is x00 the actual auto-labeled region of epoch is x!(() = {x x00 1(w;, x) 2 G.). Let X 4;) denote the complement set 44.
atd)) Now observe that X. = dá and X(wa, &e) C Xr because any x E X(W,, (x) is either labe-labeled in previous rounds < l or not then will be auto-labeled the t round. More specifically, any x E X'(w,, fx) is either in - (1) and if not then it must be in (kk) Thus the sum of probabilities.
k
&
Σ P(2
1=1
= P((aa)
2 min IP (P (:))
max Pl E (w., 1:))
2 min /4d/m
The last step used Lemma 4 from [3]) with 71 = i, and 72 = 0 to upper bound (( (.) by Ad/ The lemma is stated follows in Lemma C.9,
Lemma C.9. ([3) (Lemma 4)) Let d 2 2 and let = Iæ za) be uniformly distributed in the d-dimensional unit ball. Given 71 E [0, 1], 72 E [0, 1). we have:
(((11,02) E 70 x (72, 1)) x 71 Vd
exp ( (d 2)-2
2 2
2
26

---

C.4 Lower Bound
Lemma 3.3. Let Ct, 22 and O. Let x; E X be set of n i... points from X with corresponding
true labels yo- Given (h, t) E H let El ( (h, L, x,, - E(h, 112)) $ = of > o² for every
X; for o; > 0 and let Σ; of 2 then for every E 10, -
with uh < 12x log(402) the
vei
following holds w.p. at least 1/4, 4() > (h,44 +
Proof. It follows by application of Feller's result stated in lemma C.10.
Lemma C.10. (Feller, Lower Bound on Tail Probability of Sum of Independent Random Variables)
There exists positive universal constants C1 and 02 such that for any set of independent random
variables X1...., Xm satisfying [[X,] TM R((X))
and [X,]] S M. for every E mi,...,m), if
E B[(()}) 2 then for every E [0
M
P
X5 >
2 C2 exp
(16)
12 12 m
1==
(
27

---

D Additional Experiments
In this section, we discuss additional experiments on the role of hypothesis class in auto-labeling datasets and experiments for studying the role of confidence function in auto-labeling. Finally, we visualize PaCMAP embeddings of the CIFAR-I0 and MNIST data points to get sense of auto-labeling regions in various rounds of the algorithm.
D.1 Additional Experiments Role of the Hypothesis Class
First, we provide details of the datasets.
XOR is synthetic dataset. Recall that it is created by uniformly drawing points from 4 circles, each centered at the corners of square of with side length 4 centered at the origin. Points the diagonally opposite balls belong the same class. We generate total of N 10, 000 samples, out of which we keep 8, 000 in X pooo and 2, 000 in the validation pool X
MNIST [15] is standard image dataset of hand-written digits. We randomly split the standard training set into pooo and validation pool yva of sizes 48,000 and 12,000 respectively. While training a linear classifier this dataset we flatten the 28 28 images vectors of size 784.
Output
40
20
Untabdied
Querfed we
Auto Labeld ve
TDA
AL-SC
-10 PL-5C
- 7L
Output of TBAL AL+SC on XOR dataset
(b) Auto labeling performance various methods
Figure 5: Comparison of Threshold-Baan Auto-Labeling (TBAL) and Active-Lcarning followed by Selective Classification (AL+SC) on XOR-dataset. Left figure (a) shows samples that were auto-labeled, queried, and left unlabeled by these methods. Right figure (b) shows the auto-labeling error and coverage achieved. The lines show the mean and the shaded region shows 1-standard deviation estimated over 10 trials with different random seeds.
XOR Experiment. We run the TBAL algorithm with an error tolerance ef = 1%. we use 20% of N₂ seed training data and keep query size Tıs 5% of Nę. We compare with active learning and active learning followed by selective classification. The given function class and selective classifier both linear for all the algorithms. The results are shown in Figure 5. Clearly, there is linear classifier that can correctly classify this data. We note that there are multiple optimal classifiers in the function class of linear classifiers and they will all incur error of 25%. So, active learning algorithms can only output models that make at least 25% error. If we naively use the output model obtain near full coverage but incur 25% auto-labeling error. If we the
for auto-labeling, model output by active learning with threshold-based selective classification, then can attain lower error in labeling. However, it can only label 25% of the unlabeled data. In contrast, the TBAL algorithm can label almost all of the data accurately, i.e., attain close to 100% coverage, with an error close to 1 % auto-labeling error.
MNIST Experiment. For training LeNet [37] we use SGD with a learning rate of 0.1, batch size of 32, and train for 20 epochs. We luto-labeling error threshold as seed training data and keep query size n, as 5% of Ng. The results are presented in Figure observe that TBAL using less powerful models can still yield highly accurate datasets with significant fraction points labeled by the models. This confirms the notion that bad models can still provide good datasets.
5%. We use 20% of N,
D.2 Role of Confidence Function
The confidence function g is used to obtain uncertainty scores is an important factor in auto-labeling. In particular, for threshold-based auto-labeling we expect the scores of correctly classified and incorrectly classified points to be reasonably well separated and if this is not the case then the
28

---

200
620
1.000
270
6003
1000
3480
253
907
3470
300
620
1030
1.00
AL-SC
-0-
72AL
AL-SC
7.-55
-0
(a) Auto-labeling MNIST data using linear classifier.
(b) Auto-labeling MNIST data using LeNet classifier.
The validation size used here 12k.
validation size used here 12k.
Figure 6: Auto- late-labliing performance on MNIST data using different models (hypothesis classes) as function of samples available for training. The left figure (a) shows the results with the linear classifier and the right figure (b) shows the results with the LeNet classifier. The auto-labeling error threshold and the algorithms are given the amount of validation data. The lines show the and the shaded region shows I-standard deviation estimated over 5 trials with different random seeds.
5% in both experiments
100 Traiiing Samullet
Ma5 Toiiing Sampoi
Max Thiiing
Taniing
(a) Auto-labeling CIFAR-10 data using small network and softmax scores. Validation size 10k.
(b) Auto-labeling CIFAR-I0 data using a small network and energy scores. Validation size 10k.
Auto-labeling performance on CIFAR- 10 data using a small network and different scoring functions. The left figure (a) shows the results with softmax scores and the right figure (b) shows the results with the energy score. The auto-labeling error threshold c, 10% in both experiments and methods are given the same amount of validation data. The lines show the and the shaded region shows I-standard deviation estimated over S trials with different random seeds.
Figure 7:
algorithm will struggle to find good threshold if the given classifier has good accuracy in certain regions.
Setup. We perform auto-labeling on the CIFAR-10 dataset using a small CNN network with 2 convolution layers followed by 3 fully connected layers [48]. We use two different scores for auto-labeling, a) Usual softmax output b) Energy score with temperature maximum number of training samples N₂, and keep 20% of Ng as seed samples and query points in the batches of 10% of Ng. The model is trained for 50 epochs, using SGD with learning rate of 0.05, batch size 256, weight decay = 54- and momentum=0.9, and use = 10%.
[38]. We vary the
Results. The results with softmax scores and energy scores used as confidence functions can be seen in Figures 8(a) and 8(b) respectively. We see that for both of these cases, TBAL does not obtain coverage of more than 2 6%. We observe that using the energy score the confidence function performed marginally better than using the softmax scores. We note that this is the case even though the test accuracies of the trained models were around 50% for most of the rounds. Note that CIFAR-I0 has 10 classes, so an accuracy of 50% is much better than random guessing and one would expect to be able to auto-label a significant chunk of the data with such a model. However, the softmax scores and energy scores are not well calibrated, and therefore, when used as confidence functions, they result in a poor separation between correct and incorrect predictions by the model. This can be seen in Figure 8 where neither of the sofumax and energy scores provides good separation between the correct and incorrect predictions. We can also see that energy score marginally better in terms of the separation, which allows it to achieve slightly better luto-labeling coverage in comparison to using softmax scores. This suggests that more investigation is needed to understand the properties of good confidence functions for labe-lg which is left to future work.
29

---

Intereett
Incammet
1500
1000
430
540
230
22
Score
Energy Score
221mmo Sare
Erery
(a) Histogram scores round 2.
(b) Histogram scores in round
Figure 8: Histograms of scores computed the validation data in few rounds of TBAL CIFAR-I0 with a small net. We picked two rounds where auto-labeled the most i.e. around 800 points.
For more detailed visualization of the rounds of TBAL for this experiment, see Figures 10 and 11 in the Appendix.
D.3 Detailed Results
In the main paper, we omitted AL, PL, and PL+SC for clarity and due to lack space. We provide results including these baselines in the following tables for IMDB, Imny-ImageNet, and Unit-Ball datasets.
Error (%)
Coverage (%)
N,
TBAL
AL+SC
PLASC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
200
4.77 bus
3.35 2000
3.68 20
83.14 23s
78.53 aive
81.20 201
98.75 201e
400
4.57
3.53
3.96
6.60 2/s
6.16
90.70
86.39
87.43
98.75
97.
600
4.32 1017
3.70 100
4.17 2e3
6.60 11
6.16 2010
92.96
88.90 11
90.12 a1
98.75 sare
97.50 1a0
800
4.66 1030
3.84 1am
4.15 2035
6.60 110s
6.16 2010
92.42 2am
88.67 1738
89.37 2144
98.75 _are
97.50 1.00
1000
4.67
3,90
4,21 2839
6.60 61.0
6.16 20m0
92.89
89.79 doum
90.18 ai.
98,75
97,50
Table IMDB. Effect of variation of validation data size (N,) without using a UCB (i.e., C₁ = 0) on error estimates. We keep training data size N₂ fixed at 500 and use error threshold 6, = 5%. We report the mean and std. deviation over runs with different random seeds.
N.
Error (%)
Coverage (S)
TBAL
AL+SC
PL+SC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
200
2.28
3.11
2.86 ue3
6.60 suss
6.16 sur
68.24
57.77 s01e
60.45 sus
98.75
97.50
400
1.29 sato
1.98 1010
1.54 sen
6.60 410s
6.16 snm
63.81 p4s
63.06 1107
68.32 10.0
98.75 100
97.50 1000
600
1.41 saz0
1.81 a0z
1.87 se0
6.60 buss
6.16 sam
69.64 eass
62.92 1921
69.84 amm
98.75 60.0
97.50 2000
800
1.62
2.04
2.33 =033
eiss
67.45
63.22
72.50 t2.
98.75
97.50
1000
1.64
1.97
1.93
6.60 ki.s
6.16 sum
70.28
66.11 11 =se)
73.04 +2.0
98.75
97.50
Table 7: IMDB. Effect of variation validation data size (N,), using a UCB (i.c., C₁ = 0.25) on error
estimates. We keep training data size N, fixed at 500 and use error threshold ca = 3%. We report the mean and std. deviation over 10 runs with different random seeds.
30

---

Error (%)
Coverage (%)
Na
TBAL
ALASC
PLASC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
200
4.57 1921
4.30 2020
3,97 201e
6.44 1020
6.20 aoce
93.46 ao
90.60 a291
91.97 201
99.50 que
99.00 1.200
400
4.60 tom
3.75 swo
3.92 wea
11.86 au3
6.81 m123
92.55 sose
84.27 souss
89.95 =2
99.00 swo
98.00 50.00
600
4.93
3.99 zwm
4.69 2010
6.31 #12
6.33 esus
92.45 soss
91.69 #200
91.20 m04
98.50 swve
97.00
800
4.76 tuzz
3.55 zum
4.37 2014
6.91 +1.
6.12 eauz
92.15 uue
89.98 $2.2
89.97 =0
98.00 swe
96.00 t0.20
1000
4.49 2000
4.19 2001
4.25 2019
5.65 201s
6.14 sau
92.25 2000
92.28 #200
89.47 20:0
97.50 1100
95.00 20.00
Table 8: IMDB. Effect of variation of N₃. the maximum number of samples the algorithm can for training. without using a UCB (i.c., C1 0) on error estimates. We keep validation data size N₂ fixed at 1000 and use error threshold Ea = 5%. We report the mean and std. deviation over 10 runs with different random seeds.
N₂
Error (%)
Coverage (%)
TBAL
AL+SC
PL+SC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
200
1.67 buz
2.15 aus
1.59 =a
6.44 sua
6.20 asss
73.30 as.
57.17 sum
57.39 e41
99.50 awe
99.00
400
1.63 ja19
1.61 1020
1,76 sen
11.86 ansi
6,81 a12s
72.59 1316
64,53 pma
58.48 117
99.00 goze
98.00 10.00
600
1.67 sam
1.83 1000
1.67 201
6,31 112
6.33 aous
71.38 2215
70.50 a:/4
65.71 2214
98.50 aove
97.00 10.0
800
1.67 taz
1.90 2021
1.79 =00
6.91 +1.0
69.10 +451
65.74 s0as
73.21 =as
98.00
96.00 +0.20
1000
1.62
1.97 aus
1,70
5.65 4uas
6.14 esu:
73.42 +2
68.05 4326
64.18 =2
97,50 s1ue 95.00
Table 9: IMDB. Effect of variation of Ng. the maximum number of samples the algorithm can use for training, using a UCB (i.c.. C1 = 0.25) on error estimates. We keep validation data size N. fixed at 1000 and use error threshold e 5%. We report the mean and std. deviation over 10 runs with different random seeds.
D.4 Auto Labeling Visualization
In this section, we visualize the process of TBAL. We use the dimensionality reduction method, PaCMAP [66]. to visualize the features of the samples. For neural network models, we visualize the PaCMAP embeddings of the penultimate layer's output and for linear models, we use PaCMAP on the raw features. In these figures, each row corresponds to one TBAL round. Each figure shows few selected rounds of auto-labeling. Each figure has four columns (left to right), which show: a) The samples that are labeled by TBAL in the round are shown in that row. b) The embeddings for training samples in that round. c) The embeddings for validation data points in that round. d) The score distribution for the validation dataset in that round.
In Figure 9 we see visualizations for auto-labeling on the MNIST data using linear models. In this setting the data exhibits clustering structure in the PaCMAP embeddings learned on the raw features and the confidence (probability) scores produced are also reasonably well calibrated which leads to good auto-labeling performance.
The visualizations for the process of TBAL on CIFAR-10 using the small network (a small CNN network with 2 convolution layers followed by 3 fully connected layers [48]) with energy scores and soft-max scores for confidence functions are shown in Figures 10 and 11 respectively. We note that both the energy scores and soft-max scores do not seem to be calibrated to the correctness of the predicted labels which makes it difficult to identify subsets of unlabeled data where the current hypothesis in each round could have potentially auto-labeled. We also note that the test accuracies of the trained models were around 50% for most of the rounds of TBAL even though the small network model is not a powerful enough model class for this dataset. Note that CIFAR- 10 has 10 classes, the accuracy of 50% is much better than random guessing and one would expect to be able to auto-label a reasonably large chunk of the data with such a model if accompanied by good confidence function. This highlights the important role that the confidence function plays in a TBAL system and more investigation is needed which is left to future work.
Note that, in our auto-labeling implementation we find class specific thresholds. In these figures, we show the histograms of scores for all classes for simplicity. We want to emphasize that the visualization figures in this section are 2D representations (approximation) of the high- nigh-dimensional features (either of the penultimate layer or the raw features).
31

---

Error (%)
Coverage (%)
Nv
TBAL
AL+SC
PL+SC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
100
3.10
0.68
1.45 was
1.23 sam
2.87 1057
71.43
96.95 sum
92.29 1357
98.52
96.88 som
400
1.97 2016 0.59 201
1.19 219
0.81 was
2.87 an3:
93,99 an
97.89 ando
91.73 2m
98.44 20re
96.88 2000
1.64 10:
0.66 2019
1.21 gen
0.81 sat
2.87 an
96.26 gm
98.06 ane
92.25 1211
98.44 g0re
96.88 1000
1200
1.39
0.67
1.11 L838
0.81 103
2.87 1057
96.67 20m1
98.10 aove
91.98 10:0
98.44
96.88 1000
1600
1.33 Jam
0.70 2010
1.11 pa3
0,81 1a3
2.87
10.77
97.13 201s
98.16 a04
92.01
98.44 gare
96.88 1,00
2000
1.28 10m
0.71 1021
1.07 weas
0.81 6a.
2.87 1057
97.15 w054
98.20 ancs
91.86
s217
98.44 mese
96.88 1000
Table 10: Unit Ball. Effect of variation of validation data size (N.). without using UCB (i.e., error estimates. We keep training data size N, fixed at 500 and use error threshold ca. mean and std. deviation over 10 runs with different random seeds.
Ci 0) on
1%. We report the
Error (%)
Coverage (%)
N.
TBAL
ALASC
PLASC
AL
PL
TBAL
AL,4C
PL.SC
AL
PI.
100
3.10
0.68
1.45 um
1.23 so
2.87 20
71.43
96.95 2im
92.29 am
98.52
96.88 100
400
1.65 ioss
0.32 201r
0.52 2e3
0.81 1a3
2.87 10:t
93,27 gass
96.91 1000
87.86 1m
98.44 gare
96.88 1mm
800
1.08 1ove
0.24 20rr
0.31 2017
0.81 1a3
2.87 1om
96.01 211s
96.31 1136
86,21 2ass
98.44 gare
96.88 1,0
1200
0.78
0.17 aun
0.18 =014
0.81 tass
2.87 smo:
96.82 2014
95.96 21
84.65 4414
98.44
96.88 88
1600
0.65 20.0
0.13 2o1
0.12 251
0.81 20
2.87
96.93 2a57
25.70 2:3
83,76 2::0
98.44
96 88 2m0
2000
0.54 2016
0.21 2011
0.21 18
0.81 2035
2.87 s0
97.23 gan
96.36 an
85.72
an
98.44 gere
96.88 10000
Table 11: Unit-Ball. Effect of variation of validation data size (N,), without using UCB (i.c.. C1 0.25) on error estimates. We keep training data size N₂ fixed at 500 and use error threshold 6a = 1%. We report the mean and std. deviation over 10 runs with different random seeds.
Error (%)
Coverage (%)
Na
TBAL
AL+SC
PL4SC
AL
PL
TBAL
AL+SC
PL+SC
AL
PL
100
1.53 a0m
1,16 2015
1.14
16.93
12:53 aaH
75.31 ar1s
31.69 giot
51.47 ans
99.69 2am
99.38 sore
200
1,25 saa
1.04 sas
0.98 ea.
7.85 sue
7.08 =112
96.24 asas
73.27 :324
76.05 tate
99.38 sam
98.75 sove
400
1,20 pus
0.94 parr
1.03 axd
1.81 ause
3.25 cxa
97.70 ax.
96.48 21:4
91.08 2200
98.75 sum
97.50 sume
600
1.21
0.44 2o15
1.09
0.44 101
2.25 gess
97.56 5333
98.11
93.19
98.12 103
96.25 sare
800
1.13 2000
0.12 ses
1.02 aals
0.12 200
1.76 ce3e
97.25 201
97.49 2sm
93.23 amm
97.50 201
95 .0 2om
1000
1.08 2010
0.04 ge
1.00 g2:0
0.04 gom
1.37 2014
97.02
2033
96.87
92.90 10
96.88 and
93.75 20re
Table 12: Unit-Ball. Effect of variation of Ng- the maximum number of samples the algorithm can use for training, without using a UCB (i.e., C1 0) on error estimates. We keep validation data size N. fixed at 4000 and use error threshold 6a = 1%. We report the mean and std. deviation over runs with different random seeds.
Error (%)
Coverage (%)
N₂
TBAL
AL+SC
PL+SC
AL
PL
TBAL
AL+SC
PLASC
AL
PL
100
0.78
0.29 a0x
0.24 2a
16.93 an
12.53 10
71.40 asm
19.31
35,90 gloss
99.69
99.38
200
0.49 201s
0.16 200
0.17 2010
7,85 214
7.08 1r
95,28 212
59.41 1000
63.77 2015
99.38 201
98.75 2000
400
0.40
2012
0.15 2oin
0.15 2e10
1.81 gos
3.25 iou
97.63 anr
92.06 23m
83.64 142
98.75 1.00
97.50 2000
600
0.34 2015
0.12 gore
0.17 co0
0.44 geu
2.25 10.6
97.36 1030
97.07 2est
87.92 aaza
98.12 us
96.25 g000
800
0.28
0.07 awd
0.15 Hore
0.12
1.76 sam
97.10 4023
97.36
88.96
97,50
00:00
95.00
1000
0.25 tas
0.03 suu
0.19 =0.8
0.04 =eue
1.37 sus
96.90 #021
96.84 2010
89.61
1140
96.88
93.75 2x0
Table 13: Unit-Ball. Effect of variation of Ng, the maximum number of samples the algorithm can use for training, using a UCB (i.c., C₁ = 0.25) on error estimates. We keep validation data size N. fixed at 4000 and use error threshold ea = 1%. We report the mean and std. deviation over 10 runs with different random seeds.
32

---

N.
(%)
Coverage (%)
TBAL
AL+SC
PL+SC
AL
PL
TRAL
ALASC
PL++CC
AL
PL
2000
as0
0.0
0.0 awo
0.0 awo
0.0
0.0
0.0
0.0 amo
0.0
4000
13.88 u540
13.31 2000
12.55 an2s
34.34 1032
31.46 1020
0,72 jors
0.48 s0m
0.69 103s
95.00 s0m
90.00 $000
6000
14.18 2a7e
11.52 2010
12:21 21
34.42 2014
31.46 2000
17.29 207
8.18 2:
11.81 22M
95. 2000
90.00 1000
8000
13.97
11.31
12.22 toot
34.42 1034
31.46 1020
36.36 61.3
23.40 s1ie
29.99 sur
95.00
90,00
10000
13:42 g370
11.14 2014
12.12 gov0
34.42 goi
31.46 10:0
43.79 gov
33.38 1m77
39.40
20:0
95.00 2,100
90:00 10100
Table 14: -mageeee Effect of variation of validation data size (No), without using UCB (i.e., C1
on error estimates. We keep training data size Ng fixed at 10K and use error threshold Eq 10%. We report the mean and std. deviation over 10 runs with different random seeds.
Error (%)
Coverage (%)
TBAL
AL,4C
PLASC
AI.
PL
TBAL
ALASC
PI.+CC
AL
PL.
2000
0.0
0.0 aso
0.0 noo
0.0
0.0 soe
0.0 eso
0.0 sos
0.0 soe
0.0
0.0
4000
10.50 2411
7.37 210
6.04 21s
34.20 an
31.52 am
0.47 230s
0.48 ans
0.43 aom
95.00 gole
90.00 2::0
6000
2as
7.71 g:
8.53 2m
34.42 sa
10
10.16 2010
4.31 2010
201e
-::0
8000
9.90 2ox
6.80
7.81
34.42 sa
31.46 sua
25.84 #137
14.43 sa
19,23
95.00
90.00
10000
8.97 1036
6.87 aom
7.32 se1
34.42 past
31.46 10.00
32.19
1134
21.96
2135
27.01
100
95.00 gove
90.00 1000
Table 15:
Effect of variation of validation data size (N.), using a UCB (i.c., C₁ 0.25) on
error estimates. We keep training data size N, fixed at 10K and use error threshold ca. 10%. report the mean and std. deviation over 10 runs with different randorn seeds.
Error (%)
Coverage (%)
Ng
TBAL
AL&SC
PLASC
AI.
PL.
TBAL
ALASC
PLASC
AL.
PL.
2000
14.02 gas
11.49 2.
12. was
52.34 s.
42.94 21
24.34 gas
14.41 2100
25. sast
99.00 cam
98.00 2101
4000
14.10 eam
11.58 sa26
11.92 =a>
43.14 6ass
36.07 #24
34.16 #130
21.84 213
33:41 was
98.00 =4m
96.00 =:00
6000
13.55 2317
11.33
12.31
38.73 2a
33.51
37.80
28.59
38.14
97.00
94.00
8000
13.79 saz7
11.72 sa.
12,36 =a.
36.06 saM
32.33 2232
42,00 a1M
32,00
39.64 2137
96.00 =s
92.00 s:01
2a3s
2028
as
34.27 1421
31.47 2317
43.63 233
33.80
2037
95.00
90.00 a3
Table 16: Tiny-ImageNee Effect of variation of Ng. the maximum number of samples the algorithm can use for training, without using UCB (i.e., Ci 0) error estimates. We keep validation data size N. fixed 10K and use error threshold e, = 10%. We report mean and std. deviation over 5 runs with different random seeds.
Error (%)
Coverage (%)
Ng
TBAL
ALASC
PL.SC
AL
PL.
TBAL
AL.4C
PLASC
AL.
PL.
2000
9.22
7422
7.48 52.34
42.94 -226
17.51 #116
9.33
17.02
99.00
98.00
4000
9.30 20o
6.97 20w
7.37 2011
43.14 200
36.07 =
25.01 21
14:25 am
22.29 sse
98.00 cmm
96.00 201
6000
9.12 aom
6.85 18x
7.49 jam
gore
28.06 107s
17.51 ao0
25.60 gem1
97.00 10:0
2000
8000
9.21 201
7.38
7.71 sazs
36.06
32.33 =x12
30.88 aose
21.18 awee
27.26 esos
96.00
92.00
10000
8.95
2033
7.10 1826
7,42 1036
34.27 1821
31.47 2a17
32,31 aa
22.34 2001
27.36 aada
95.00 10:0
90.00 1008
Table 17: Tiny- ImageNet Efffect of variation of N₃. the maximum number of samples the algorithm can for training, using a UCB (i.c., Ci = (.255) on error estimates. We keep validation data size N., fixed at 10K and use emor threshold e, = 10%. We report the mean and std. deviation over 5 runs with different random seeds.
33

---

Acto Laowed: 1899
ratting Samptes
Sampas:
Dxtribuconn
75
-15
Scaee
Sound 4502
Volida
-1
20
382
-30
-22
0.
Found 3 Auto Labele: 2020
Taining Samoles 480
Volidation Samples: 5123
Vo Store Detribition
38C
380
-15
-30
-10
-32
10
0.2
0.
0.5
0.0
3.0
Round Auto Labeled 408
Taining Samples: 1440
Volidatinn Samples: 5436
Volldat on Score Distribciion
420
10
-10
-10
380
-15
Sumples:
Samples:
commect
15
-10
50099
Figure 9: Auto-labeling MNIST data using linear classifiers. Validation size 12k. Maximum training samples 1600. Each round algorithm queries 160 samples. Coverage of auto-labeling is 62.9% 98.0% accuracy. For the rounds we show, the test error rates are 21.4%, 13.9%, 12.5%, 10.2%, and 9.8%, respectively. For four columns (left to right), we show: a) The samples that are labeled by TBAL in this round. b) The embeddings for training samples. The embeddings for validation data points. d) The score distribution for the validation dataset.
34

---

300
100
-00
-50
-13
Roun) Anto abred 195
triingg Semples: 2000
Vildetion Samples 9/13
Vel SIO Ditrisstion
-25
-22
23
5.0
50
-22
-10
Auto Jibe 110
Trsting Samples 2250)
Samples
dadiodionn Dinribation
-30
-75
-22
87
-50
-00
200
-23
26g
5009
Figure 10: Auto-labeling CIFAR-10 data using small network and energy scores. Validation size 10k. Maximum training samples 25k. Each round algorithm queries 2500 samples. Coverage auto-labeling 5.3% with 90.0% accuracy. For rounds we show, the test error rates are 56.6%, 55.2%, 55.6%, 53.0%, and 49.3% respectively. For four columns (left to right), we show: a) The samples that are labeled by TBAL in this round. b) The embeddings for training samples. The embeddings for validation data points. d) The score distribution for the validation dataset.
35

---

Labeled:
Samples $000
Samplle
Idation Seare Sterr bublon
7.
1905
Sereita
2500 -330
-04
-0.
-006
Labeled
Samples 7100
Vaddttioon 15000
194
300
300
-50
-165
160
Hayed Adoo Lubeha) 457
baring Samplss: 20003
Welddon Samplho: 2993
1Jatio Suare budians
200
-35
-80
burnng
2300
503
P Auzo Dabeled::
Twiing Samples 25000
Velcatoo Samplies 9734
Edatton Scare Outtr bution
-10
-15
-30
-30
33
30
0.2
3.4
00
10
5/5
02
340
69
822
7036
88
Figure 11: Auto-labeling CIFAR-10 data using small network softmax scores. Validation size Maximum training samples = 25k. Each round algorithm queries 2500 samples. Coverage of auto-labeling is 2.3% with 91.0% accuracy. For the rounds visualized here in each row, the test error rates of the trained classifiers are 56.6%, 59.1%. 52.8%, 50.5%, and 51.7% respectively. For four columns (left right), we show: a) The samples that labeled by TBAL in this round. b) The embeddings for training samples. e) The embeddings for validation data points. d) score distribution for the validation dataset.
36


Reviews:
[{"review_id": "6FTsT9X0ig", "reviewer": "Reviewer_RfNU", "summary": "Threshold-based auto-labelling (TBAL) is widely adopted in academic and industrial settings and this is the first work that studies TBAL from a theoretical standpoint, answering the questions of 1) Does TBAL works even if our models are not perfect and 2) what are the key requirements to having a successful TBAL pipeline? The paper suggests that even with a low-performant model, TBAL still helps accelerates the annotations. However, to facilitate a successful TBAL system, a potentially prohibitively large validation dataset might be needed. After anchoring the keys of TBAL, the paper experiments with several simple settings to validate the effectiveness of TBAL.\n", "questions": "- L204 suggests to use a hypothesis class that induces lower Rademacher complexities to reduce the second term in Eq. 2. However, a hypothesis class (e.g., Lipchitz-constrained neural networks) with lower Rademacher complexities usually leads to higher validation errors, therefore, increasing the first term in Eq. 1. If so, do the authors still suggest practitioners to use a hypothesis class that indices lower Rademacher complexities. How to balance the trade-off here?\n    - This matters since a practitioner wants a rule of thumb for using TBAL. It’s important to discuss the trade-off here.\n- Minor: As mentioned in #weakness, the current experimental results show that annotating 5k TinyImageNet effectively requires a validation dataset with 5k images, which does not sound “promising”.  Have the authors tried to push the limits a little bit further by using a better feature extractor?\n", "limitations": "The paper provides a novel view of TBAL, but the theoretical and empirical parts are not connected well. The authors should provide more numbers on how tight the proposed bound is under auto-labelling.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "TBAL is widely adopted in both academic and industrial settings and the paper is the first that study it theoretically. The derivation is sound and can be easily drawn connections with the active learning literature. I expect more follow-up work in the future. \nThe strength of this work include\n- Novelty: first work to study TBAL theoretically \n- Clarity: The delivery is easy to follow", "weaknesses": "Although the paper is novel, section 3 and section 4 are disconnected to me. Section 3 gives us a bound on the error rate and coverage of TBAL, which provides insightful relations between the performance and different design factors. \nHowever, I cannot find the bound in Figure 3 and Figure 4. I expect to see how tight the bound is empirically.\n\nOn the other hand, Eq. 2 also provides insights into the empirical validation error (term a). I expect the authors to push the limits for using a more expressive feature extractor and discuss the relation between the empirical validation error and the TBAL error rate empirically.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and for recognizing the strengths of our paper. We greatly appreciate your acknowledgment of the significance of TBAL, which is heavily used in practice. As you rightly pointed out, our paper is the first theoretical study of TBAL and provides an understanding of conditions when we can ensure performance. We appreciate your comments on the soundness and clarity of the paper.\n\n**On tightness of the bounds:** Thank you for asking this question. We study this in the setting of the Unit-Ball experiment discussed in the main paper. The upper bound on excess risk in this setting is given in Corollary 3.4 which is an instantiation of our general results to this specific setting. We consider a simplified form of the upper bound by ignoring the constants to get a sense of the rate in terms of the validation data size. We compute this simplified upper bound for different amounts of validation data. We compare these with the maximum auto-labeling error observed over 25 runs of auto-labeling in the Unit-Ball setting with different random seeds for each validation data size. The results are in Figure 1 in the attached pdf.  As expected, we see that the worst-case error rate follows a similar rate as our upper bound but the upper bound is conservative. Next, we provide an explanation for why this is the case.\n\nOur upper bound is slightly conservative, as it is based on a uniform bound over all hypotheses in a given hypothesis class. Since the individual hypotheses whose excess auto-labeling error we need to bound are not known a priori we need to derive a bound on the number of validation samples using which we can guarantee that the excess auto-labeling errors of **any** hypothesis (model) is small with high probability. Note that this is a conservative (worst-case) analysis to get an upper bound on the validation sample complexity. The upper bound has two parts: a) the Rademacher complexity of the hypothesis class and b) a term with the number of validation samples.  We note that on the validation samples, it **matches lower bounds order-wise (see lemma 3.3)**.  This is the first analysis to provide these bounds based on uniform convergence **without making any assumptions on the data distributions or hypothesis class**. Tighter results are possible if we assume specific settings, and we shall pursue this in the future. \n\n**On using more expressive feature extractors:**\nThank you for the valuable suggestion. We used a more expressive feature extractor in the IMDB experiment and saw a massive boost in the auto-labeling performance. Results can be seen in the attached pdf. We use the *bge-large-en* model from the MTEB leaderboard [1]. This additional experiment serves as a further insight into the possibilities of TBAL systems. \n\n[1] https://huggingface.co/spaces/mteb/leaderboard\n\n**Rademacher complexity and validation error trade-off:** Thank you for raising this interesting question. The bound contains validation errors at different thresholds. We revisit the definitions of validation errors appearing in the bound.  Let $X_v =$ { $x_1,\\ldots x_{n_v}$} be the validation samples and $y_i$ be the label corresponding to $x_i$. Given any $h\\in \\mathcal{H}$ and the confidence function $g$, we have different subsets $X_v(h,t)$  of the validation points for which the model’s confidence is higher than $t$. More precisely, $X_v(h,t) =$ { $x_i \\in X_v : g(h,x_i)\\ge t$} and the validation error $\\hat{\\mathcal{E}}_a(h,t|X_v)$ is computed on each of these subsets as follows, \n\n$\\hat{M}(h,t|X_v) = \\sum_{x_i \\in X_v(h,t)} \\mathbf{1}( h(x_i) \\neq y_i)$, \n$\\quad{\\hat{\\mathcal{E}}}_{a}(h,t|X_v) = \\frac{\\hat{M}(h,t | X_v)}{|X_v(h,t)|}$.\n\nThis error is different from the overall validation error which is computed over the entire set of validation points $X_v$: \n\n$\\hat{\\mathcal{E}}(h|X_v) = \\frac{1}{|X_v|} \\sum_{x_i \\in X_v} \\mathbf{1}(h(x_i)\\neq y_i)$. \n\nThe TBAL method computes $\\hat{\\mathcal{E}}_a(h,t|X_v)$ at different thresholds ($t$) and selects the threshold at which it is at most $\\epsilon$. Thus even if the overall validation error $\\hat{\\mathcal{E}}(h|X_v)$ is bad, there could still be regions in the space where the conditional validation error $\\hat{\\mathcal{E}}_a(h,t|X_v) $ is small. This can be easily seen in Figure 2 in the paper. Here we are doing auto-labeling using a linear function class that has low Rademacher complexity. All the models in this class have high overall validation error  $\\hat{\\mathcal{E}}(h|X_v)$ but there are subsets where the conditional validation error  $\\hat{\\mathcal{E}}_a(h,t|X_v)$ is small and TBAL is able to find those subsets. \n\nThus we see that working with low Rademacher complexity classes might lead to high overall validation error. However, it does not affect TBAL as long as there are regions of low conditional validation error $\\hat{\\mathcal{E}}_a(h,t|X_v) $. Furthermore, our upper bound on excess auto-labeling error depends on $\\hat{\\mathcal{E}}_a(h,t|X_v) $ which due to the TBAL procedure is at most $\\epsilon$ and hence it is not in conflict with the Rademacher complexity term.\n\nOnce again, we sincerely thank you for the positive feedback and questions. These insightful comments have helped us to further strengthen our paper. We are excited to engage in the discussion and answer further questions.\n"}, {"review_id": "azplVVaXFD", "reviewer": "Reviewer_zavU", "summary": "This paper provides an analysis of Threshold-Based Auto-Labeling (TBAL) systems by deriving sample complexity bounds on the amount of human-labeled validation data required for guaranteeing the quality of the machine-labeled data. The paper provides two main insights: (1) large amounts of unlabeled data can be automatically/accurately labeled by weak models, and (2) a downside of TBAL systems is the need of potentially prohibitive amounts of necessary validation data. ", "questions": "1) on line 268, the paper says that it is using five datasets, but it only lists four (Unit-Ball, Tiny-Imagenet, IMDB Reviews, and CIFAR-10). In the APPENDICES, the authors also bring up XOR & MNIST, for a total of six, rather than five, datasets \n\n2) In the main paper, why don't you show the results for all 4 datasets (see above)?\n\n3) would a scatter plot of AutoLabel Error vs Coverage help illuminate any trade-offs/insights for the domains in which the error/coverage are not totally/mostly flat?\n\n4) line 261: could you please explain why is Algo 2 is estimating a single threshold for all classes, while in Section 4 you estimate per-class thresholds?\n\n", "limitations": "Could you please discuss in depth the practical impact/usefulness of a TBAL-created dataset that has only 25% coverage? ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To the best of this reviewer's knowledge, this is the first paper that derives sample complexity bounds on the amount of validation data required for the confident use of TBAL systems. The contributions appear to be novel, and the paper is well-written & reasonably easy to follow. The authors provide both a theoretical analysis and an empirical validation for TBAL systems. Figure 1 is extremely intuitive and summarizes very well TBAL systems for readers unfamiliar with the problem.    ", "weaknesses": "The paper could further benefit from additional discussion along the key findings. \n\n1) while Fig 2.a is crisp & intuitive, Fig 2.b is less so. The authors should (1) explain why the coverage of AL & PL is decreasing as the training sample increases, and (2) discuss why the coverage of AL+DC & PL+SC does not really change for various amounts of training data\n\n2) for Fig 3, the authors should (1) drop PL+SC with a note saying that AL+SC is always comparable/better, (2) explain why the coverage is so low for both IMDB & Tiny ImageNet, (3) discuss the usefulness of a TBAL approach with a coverage of about 25%, and (4) \"zoom in\" on an in-depth, 1:1 comparison between TBAL and AL+SC, which seem to be performing quite similarly (TBAL with a slightly better coverage, while AL+SC with a slightly better auto-labeling error); this comparison & potential trade-offs analysis should represent a major contribution of the paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted to receive your positive feedback and recognition of the strengths in our paper.\nOur work represents the first attempt to derive sample complexity bounds on the validation data for the confident utilization of TBAL systems. Moreover, we are happy to know that the paper's clarity and coherence have made it reasonably easy to follow. We are pleased that Figure 1 has been regarded as extremely intuitive and useful, particularly for readers who may not be familiar with the problem. It was designed with the intent to provide an accessible summary of TBAL systems and their workings, and we are glad it has served its purpose effectively.\nWe appreciate your questions and suggestions and address them below,\n\n**On coverage of AL & PL:** This is due to the way we compute coverage – with more points taken into the training pool there are lesser points available for auto-labeling. This leads to a decrease in coverage as all the training samples available for that run are used. We have added discussion on this in the paper to further clarify.\n\n**On coverage of AL+SC & PL+SC:** There are two factors that lead to the observed behavior. First, due to the choice of the model class there is a limitation on the best model that can be learned irrespective of the training data provided i.e. the Bayes optimal classifier in this setting has error around 25% and AL, PL methods can only learn a classifier which is close to the Bayes optimal classifier. Once they reach close to the optimal classifier with more training data the improvements in the model will be negligible. Second, these methods only do a single round of auto-labeling i.e. learn the best possible model first and then do auto-labeling using this model. As we saw in the first point they hit a limit on the best model that can be learned, which leads to a limit on the coverage that they can achieve.\n\n**Suggested drop of PL+SC:** Thank you for the suggestion. We have updated the draft accordingly.\n\n**Why the coverage is low for both IMDB & Tiny ImageNet:** The coverage depends on several other factors, e.g. feature separability, confidence functions etc. In this work we wanted to study the role of validation data in the estimation of threshold estimation and overall auto-labeling performance.  We used a more expressive feature extractor in the IMDB experiment and saw a massive boost in the auto-labeling performance. Results can be seen in the attached pdf. This additional experiment serves as a further insight into the possibilities of TBAL systems.\n\n**On usefulness of TBAL with 25% coverage:** The coverage achieved by TBAL depends on many factors including the label noise tolerance, separability of features etc. \n\nIn the context of data-labeling with crowd-sourcing, this fraction could mean a non-trivial reduction in the cost. 25% of what are large datasets are still quite sizable, implying that it may be possible to train a high-quality downstream classifier on a provably-clean dataset.  Even in cases where 25% coverage is too low for great downstream performance, our approach clarifies the tradeoffs between dataset size and label noise. That is, we could vary our confidence levels to achieve higher noise/higher coverage and see which is the \"right\" setting for a particular task and model. Such a setting may be more robust to noise but more data hungry, while others may be hurt by noise but robust to dataset size. Our approach disambiguates these---which wasn't possible before.\n\n**On an in-depth, 1:1 comparison between TBAL and AL+SC:** We show the data in tables in the attached pdf.\n\n**Number of datasets:**  Thanks for pointing this out. We have made these corrections in the updated draft.\n\n**On a scatter plot of AutoLabel Error vs Coverage:** Please see our new experiments in the attached pdf.\n\n**On why is Algo 2  estimating a single threshold for all classes:** We did this for easier exposition of the analysis. \n\nOnce again, we sincerely thank you for their positive feedback and questions, which have further strengthened our paper. We are excited to engage in the discussion and answer any additional questions.\n"}, {"review_id": "m7L1TRA6jI", "reviewer": "Reviewer_L2k7", "summary": "The paper studies an important problem. It theoretically analyzes TBAL systems and develops tradeoffs between\nthe quantity of manually-labeled data and the quantity and quality of auto-labeled data. Empirical results on real/synthetic data also support their findings.\nTheir results provide two crucial insights. when having access to sufficient validation data and a good confidence function, even bad\nmodels can reliably label at least some data, meanwhile, the quantity requirement of the validation data can be high.", "questions": "See weaknesses.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper is the first to study the theoretic performance of TBAL, which is important in practice.\n2. For the proposed TBAL, this paper gives theoretic guarantees on the auto-labeling error and the coverage using Rademacher Complexity and PAC theory.\n3. The paper designs a series of experiments including synthetic data, and real data. The experiments do reveal some interesting observations (though some observations are unexpected, need more disscusions, see W3.)\n4. The writing is good, easy to understand", "weaknesses": "W1. The goal of the paper seems a little confusing. On the one hand, it aims to study an existing popular TBAL system.\nOn the other hand, it seems that the studied TBAL algorithm is in fact proposed in this current paper.\n\nW2. Several questions need to be clarified (possibly in the related work section): \n(1) Is the proposed TBAL the same with any existing popular TBAL?\n(2) Whether the theories apply to an existing popular TBAL system, what if their workflows are different?\n(3) The paper claims that the TBAL is popular. But it didn't provide any evidence for its popularity, e.g., use cases, scenarios.\n\nW3. In experiments, it seems AL+SC can outperform TBAL (in terms of error rate, given that the difference in coverage is not significant).\nThis is very different from Figure 2, why this can happen? Please add more discussions for explaining the different performance among the 4 competing methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback and acknowledgment of the paper's strengths. Being the first theoretical study of TBAL systems, our research offers essential guarantees on auto-labeling error and coverage using learning theoretic tools. The experiments conducted not only validate our theoretical insights but also reveal intriguing observations regarding TBAL behavior. We are delighted that you found our writing to be clear and easily understandable.\n\n**Clarification on the goal of our work**: We would like to emphasize that the goal of our paper is to understand the pros and cons of the TBAL systems. **We are not proposing** this system.\n\n**Popularity of TBAL**: These systems are indeed used heavily in practice and this is what inspired us to study them. Since these are commercial systems, only high level descriptions of their methods are available. In our work we closely follow the workflow of Amazon Sagemaker GroundTruth [1] which is getting used in various domains including telecom, healthcare, recruiting etc (see their customers [2]). Similar workflows are also adopted in other systems e.g. Samsung SDS [3], Labelbox [4], V7[5] etc. \n\n**Comparison of AL+SC and TBAL**: Our goal is not to show TBAL is better than the other methods across the board. However, we are interested in understanding the behavior in TBAL in various settings and we compare it against AL+SC, which is a strong baseline for TBAL.\n\nWe observe, in settings similar to Figure 2, where the model class does not contain a model with error at most $\\epsilon$ then the end model in AL will have error more than $\\epsilon$ and will lead to lesser coverage than TBAL. On the other hand the dynamics of TBAL are very different, it iteratively auto-labels and eliminates the data which enables it to achieve high coverage even in settings where the model class does not contain a model with error at most $\\epsilon$. These differences can be easily seen Figure 2. However, in settings where the model class has models with error at most $\\epsilon$ then AL+SC and TBAL will have similar performances. Please see table 1 and 2 in the attached pdf to see more clear comparison between these methods.\n\n[1] https://aws.amazon.com/blogs/machine-learning/annotate-data-for-less-with-amazon-sagemaker-ground-truth-and-automated-data-labeling/\n\n[2] https://aws.amazon.com/sagemaker/data-labeling/\n\n[3] https://www.samsungsds.com/us/autolabel/autolabel.html\n\n[4] https://labelbox.com/product/annotate/\n\n[5] https://www.v7labs.com/auto-annotation\n\n\nWe appreciate your positive feedback and insightful questions, which have enhanced our paper. We are excited to answer any additional questions during the discussion phase. \n"}]

Author rebuttal:
Thank you all for the thoughtful and positive feedback on our paper. With your constructive suggestions, we have been able to further strengthen our work with additional experiments and improved clarity. 

Your questions and comments have provided us with valuable insights and we answer each of them in the individual responses. In this common response, we note the strengths that you have highlighted in your reviews and provide a summary of the individual responses.

**Strengths of our work as noted in your reviews:**


1. **Novelty**: Our paper is the first to study the widely used TBAL systems [RfNU, zavU, L2k7]. 


2. **Theoretical analysis of TBAL**: We derive sample complexity bounds on the amount of validation data required for the confident use of TBAL systems. In other words, we provide theoretical guarantees on the auto-labeling error and the coverage using Rademacher Complexity and PAC theory  [RfNU,zavU, L2k7].


3. **Empirical evaluation of TBAL**: Our paper provides an extensive set of experiments on synthetic and real datasets that evaluate TBAL in a variety of settings and validate our theoretical insights [zavU, L2k7]


4. **Clarity** :  All the reviewers found our paper well written and easy to follow.  [RfNU,zavU, L2k7]. We are delighted to hear that reviewer zavU found that “Figure 1 is extremely intuitive and summarizes very well TBAL systems for readers unfamiliar with the problem”. 


In response to the reviewers' suggestions, we have done additional experiments and updated the draft to include those. Some of the experiments are included in the attached pdf file. These new results and clarifications have further strengthened our paper. 


Meta-review: This paper on threshold-based autolabeling studies an important and understudied problem.
The reviewers are unanimous that the paper is interesting, clearly presented, and warrants publication.
Decision: Accept (spotlight)