Corruption Robust Active Learning

Abstract:
We conduct theoretical studies on streaming-based active learning for binary classification under unknown adversarial label corruptions. In this setting, every time before the learner observes a sample, the adversary decides whether to corrupt the label or not. First, we show that, in a benign corruption setting (which includes the misspecification setting as a special case), with a slight enlargement on the hypothesis elimination threshold, the classical RobustCAL framework can (surprisingly) achieve nearly the same label complexity guarantee as in the non-corrupted setting. However, this algorithm can fail in the general corruption setting. To resolve this drawback, we propose a new algorithm which is provably correct without any assumptions on the presence of corruptions. Furthermore, this algorithm enjoys the minimax label complexity in the non-corrupted setting (which is achieved by RobustCAL) and only requires Õ(Ctotal) additional labels in the corrupted setting to achieve O(ε+ Ctotal n ), where ε is the target accuracy, Ctotal is the total number of corruptions and n is the total number of unlabeled samples.

heading: 1 Introduction
text: An active learning algorithm for binary classification aims to obtain the best hypothesis (classifier) from some given hypothesis set while requesting as few labels as possible. Under some favorable conditions, active learning algorithms can require exponentially fewer labels then passive, random sampling [Hanneke, 2014]. Active learning is ideally suited for applications where large datasets are required for accurate inference, but the cost of paying human annotators to label a dataset is prohibitively large [Joshi et al., 2009, Yang et al., 2015, Beluch et al., 2018]. A bit more formally, for an example space X (such as a set of images) and label space {0, 1} (like whether the image contains a human-made object or not), let H be a hypothesis class such that for each h ∈ H, we have h : X → {0, 1}. After a certain number of labels are requested, the learner will output a target hypothesis hout ∈ H. In this paper, we consider the streaming setting where at each time t nature reveals xt ∼ DX and an active learning algorithm must make the real-time decision on whether to request the corresponding label yt or not. Such a streaming setting of active learning is frequently encountered in online environments such as learning a spam filter or fraud detection (i.e., mark as spam/fraudulent and do not request the label, or send to inbox/expert to obtain a label).
This paper is interested in a setting when the requested label yt is potentially corrupted by an adversary. That is, when requesting the label for some example xt ∈ X , if uncorrupted the learner will receive a label drawn according to the “true” conditional label distribution, but if corrupted, the learner will receive a label drawn from an arbitrary distribution decided by an adversary. This setting is challenging because the learner has no a priori knowledge of when or how many corruptions will occur. And if the learner is collecting data adaptively, he may easily be misled into becoming confident in an incorrect belief, collect data based on that belief, and never recover to output an accurate classifier even if the adversary eventually stops serving corrupted labels later. This greatly contrasts with the passive setting (when all labels are observed) where as long as the number of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
corrupts grows sub-linearly over time, the effect of the corruptions will fade and the empirical risk minimizer will converge to an accurate classifier with respect to the uncorrupted labels.
The source of corruptions can come from automatic labeling, non-expert labeling, and, mostly severely, adaptive data poisoning adversaries. Particularly, with the rise of crowdsourcing, it is increasingly feasible for such malicious labelers to enter the system (Miller et al. [2014], Awasthi et al. [2014]). There have been many prior works that consider robust offline training using corrupted labels (i.e., the passive setting) [Hendrycks et al., 2018, Yu et al., 2019]. Correspondingly, related corruption settings have also been considered in online learning [Gupta et al., 2019, Zimmert and Seldin, 2019, Wei et al., 2020] and reinforcement learning [Lykouris et al., 2020, Chen et al., 2021a, Wei et al., 2021]. However, there is a striking lack of such literature in the active learning area. Existing disagreement-based active learning algorithms nearly achieve the minimax label complexity for a given target accuracy when labels are trusted [Hanneke, 2014], but they fail to deal with the case where the labels are potentially corrupted.
Our contributions: In this paper, we study active learning in the agnostic, streaming setting where an unknown number of labels are potentially corrupted by an adversary. We begin with the performance of existing baseline algorithms.
• Firstly, we analyze the performance of empirical risk minimization (ERM) for the passive setting where all labels are observed, which will output an ( ε+ R
∗Ctotal n
) -optimal hypothesis
as long as n ' 1 + R∗ ε2 , where R ∗ is the risk of best hypothesis. This result serves as a benchmark for the following active learning results (Section 3).
If we assume that the disagreement coefficient, a quantity that characterizes the sample complexity of active learning algorithms [Hanneke, 2014], is some constant, then we obtain the following results for active learning.
• Secondly, we analyze the performance of a standard active learning algorithm called RobustCAL [Balcan et al., 2009, Dasgupta et al., 2007, Hanneke, 2014] under a benign assumption on the corruptions (misspecification model is a special case under that assumption).We show that, by slightly enlarging the hypothesis elimintion threshold, this algorithm can achieve almost the same label complexity as in the non-corrupted setting. That is, the algorithm will output an O(ε + R
∗Ctotal n )-optimal hypothesis as long as n ' R∗ ε2 + 1 ε with at most
Õ (R∗n+ log(n)) number of labels (Section 4). • Finally and most importantly, in the general corruption case without any assumptions on
how corruptions allocated, we propose a new algorithm that matches RobustCAL in the non-corrupted case and only requires Õ(Ctotal) additional labels in the corrupted setting. That is, the algorithm will output an ( ε+ Ctotaln ) -optimal hypothesis as long as n ' 1ε2 with
at most Õ ( (R∗)2n+ log(n) + Ctotal ) number of labels. Besides, this algorithm also enjoys an improved bound under a benign assumption on the corruptions. That is, the algorithm will output an ( ε+ R
∗Ctotal n
) -optimal hypothesis with at most Õ ( (R∗)2n+ log(n) +R∗Ctotal ) number of labels (Section 5)
Note that Ctotal can be regarded as a fixed budget or can be increasing with incoming samples. In the latter case, Ctotal in the second and third result can be different since they may require different n. Detailed comparison between these two results will be discussed in corresponding sections.
Related work: For nearly as long as researchers have studied how well classifiers generalize beyond their performance on a finite labelled dataset, they have also been trying to understand how to minimize the potentially expensive labeling burden. Consequently, the field of active learning that aims to learn a classifier using as few annotated labels as possible by selecting examples sequentially is also somewhat mature [Settles, 2011, Hanneke, 2014]. Here, we focus on just the agnostic, streaming setting where there is no relationship assumed a priori between the hypothesis class and the example-label pairs provided by Nature. More than a decade ago, a landmark algorithm we call RobustCAL was developed for the agnostic, streaming setting and analyzed by a number of authors that obtains nearly minimax performance [Balcan et al., 2009, Dasgupta et al., 2007, Hanneke, 2014].
The performance of RobustCAL is characterized by a quantity known as the disagreement coefficient that can be large, but in many favorable situations can be bounded by a constant θ∗ which we assume is the case here. In particular, for any > 0, once Nature has offered RobustCAL n unlabelled samples, RobustCAL promises to return a classifier with error at most √ R∗ log(|H|)/n+log(|H|)/n
and requests just nR∗ + θ∗( √ nR∗ log(|H|) + log(|H|)) labels with high probability. Said another way, RobustCAL returns an -good classifier after requesting just θ∗((R∗)2/ 2 + log(1/ )) labels. If θ is treated as an absolute constant, this label complexity is minimax opitmal [Hanneke, 2014]. While there exist algorithms with other favorable properties and superior performance under special distributional assumptions (c.f., Zhang and Chaudhuri [2014], Koltchinskii [2010], Balcan et al. [2007], Balcan and Long [2013], Huang et al. [2015]), we use RobustCAL as our benchmark in the uncorrupted setting. We note that since RobustCAL is computationally inefficient for many classifier classes of interest, a number of works have addressed the issue at the cost of a higher label sample complexity [Beygelzimer et al., 2009, 2010, Hsu, 2010, Krishnamurthy et al., 2017] or higher unlabeled sample complexity [Huang et al., 2015]. Our own work, like RobustCAL, is also not computationally efficient but could benefit from the ideas in these works as well.
To the best of our knowledge, there are few works that address the non-IID active learning setting, such as the corrupted setting of this paper. Nevertheless, Miller et al. [2014] describes the need for robust active learning algorithms and the many potential attack models. While some applied works have proposed heuristics for active learning algorithms that are robust to an adversary [Deng et al., 2018, Pi et al., 2016], we are not aware of any that are provably robust in the sense defined in this paper. Active learning in crowd-sourcing settings where labels are provided by a pool of a varying quality of annotators, some active learning algorithms have attempted to avoid and down-weight poorly performing annotators, but these models are more stochastic than adversarial [Khetan and Oh, 2016]. The problem of selective sampling or online domain adaptation studies the setting where P (Yt = 1|Xt = x) remains fixed, but P (Xt = x) drifts and the active learner aims to compete with the best online predictor that observes all labels [Yang, 2011, Dekel et al., 2012, Hanneke and Yang, 2021, Chen et al., 2021b]. Another relevant line of work considers the case where the distribution of the examples drifts over time (i.e., P (Xt = x)) [Rai et al., 2010] or the label proportions have changed (i.e, P (Yt = 1)) [Zhao et al., 2021], but the learner is aware of the time when the change has occurred and needs to adapt. These setting are incomparable to our own.
Despite the limited literature in active learning, there have been many existing corruption-related works in the related problem areas of multi-arm bandits (MAB), linear bandits and episodic reinforcement learning. To be specific, for MAB, Gupta et al. [2019] achieves Õ( ∑ a6=a∗ 1 ∆a
+KC) by adopting a sampling strategy based on the estimated gap instead of eliminating arms permanently. Our proposed algorithm is inspired by this “soft elimination" technique and requests labels based on the estimated gap of each hypothesis. Later, Zimmert and Seldin [2019] achieves a near-optimal result
Õ (∑
a6=a∗ 1 ∆a + √∑ a6=a∗ C ∆a ) in MAB by using Follow-the-Regularized Leader (FTRL) with
Tsallis Entropy. How to apply the FTRL technique in active learning, however, remains an open problem. Besides MAB, Lee et al. [2021] achieves Õ (GapComplexity + C) in stochastic linear bandits. We note that the linear bandits papers of Lee et al. [2021] and Camilleri et al. [2021] both leverage the Catoni estimator that we have repurposed for robust gap estimation in our algorithm. Finally, in the episodic reinforcement learning, Lykouris et al. [2020] achieves Õ ( C · GapComplexity + C2
) in non-tabular RL and Chen et al. [2021a] achieves Õ ( PolicyGapComplexity + C2 ) in tabular RL. Very recently, Wei et al. [2021] obtains an GapComplexity + C bounds for linear MDP.

heading: 2 Preliminaries
text: General protocol: A hypothesis classH is given to the learner such that for each h ∈ H we have h : X → {0, 1}. Before the start of the game, Nature will draw n unlabeled samples in total. At each time t ∈ {1, . . . , n}, nature draws (xt, yt) ∈ X × {0, 1} independently from a joint distribution Dt, the learner observes just xt and chooses whether to request yt or not. Note that in this paper, we assume X is countable, but it can be directly extended to uncountable case. Next, We denote the expected risk of a classifier h ∈ H under any distribution D as RD(h) = Ex,y∼D (1{h(x) 6= y}), the marginalized distribution of x as ν and probability of y = 1 given x and D as ηx. Finally we define ρD(h, h′) = Ex∼ν1{h(x) 6= h′(x)}.
Uncorrupted model: In the traditional uncorrupted setting, there exists a fixed underlying distribution D∗ where each (xt, yt) is drawn from this i.i.d distribution. Correspondingly, we define the marginalized distribution of x as ν∗ and probability of y = 1 given x and D∗ as ηx∗ .
Oblivious and non-oblivious adversary model: In the corrupted setting, the label at time t is corrupted if (xt, yt) is drawn from some corrupted distribution Dt that differs from the base D∗. At the start of the game, an oblivious adversary will choose a sequence of functions ηxt : X → [0, 1] for all t ∈ {1, . . . , n}. The corruption level at time t is measured as
ct = max x∈X |ηx∗ − ηxt |,
and the amount of corruptions during any time interval I as CI = ∑ t∈I ct. Correspondingly, we define Ctotal = C[0,n]. Then, Nature draws xt ∼ ν∗ for each t ∈ {1, . . . , n} so that each xt is independent of whether yt was potentially corrupted or not.
One notable case case of the oblivious model is the γ-misspecification model. In the binary classification setting, it is equivalent to
ηxt = (1− γ)ηx∗ + γη̃xt ,∀x, t.
where η̃xt can be any arbitrary probability. Such label contamination model can be regarded a special case of corruption where for each t,
ct = max x |ηxt − ηx∗ | = γmax x |ηx∗ − η̃x|
Moreover, our main algorithm actually works for the non-oblivious adversary. In this more challenging case, each time t, the adversary adaptively decides ηxt before seeing actual xt, based on all the previous history.
Other notations: For convenience, we denote RDt(h) as Rt(h), RD∗(h) as R∗(h), ρDt(h, h′) = ρt(h, h ′) and ρD∗(h, h ′) = ρ∗(h, h
′). We also define an average expected risk that will be used a lot in our analysis, R̄I(h) = 1|I| ∑ t∈I Rt(h). In addition, we define h
∗ = arg minR∗(h), R∗ = R∗(h∗) and the gap of the suboptimal classifier h as ∆h = R∗(h)−R∗.
Disagreement coefficient: For some hypothesis class H and subset V ⊂ H, the region of disagreement is defined as Dis(V ) = {x ∈ X : ∃h, h′ ∈ V s.t. h(x) 6= h′(x)} , which is the set of unlabeled examples x for which there are hypotheses in V that disagree on how to label x. Correspondingly, the disagreement coefficient of h∗ ∈ H with respect to a hypothesis classH and. distribution ν∗ is defined as
θ∗(r0) = sup r≥r0 Px∼ν∗(X ∈ Dis(B(h∗, r))) r .

heading: 3 Passive Learning in the Corrupted Setting
text: We first analyze the performance of empirical risk minimization (ERM) for passive learning in the corrupted setting as a benchmark.
Theorem 3.1 (Passive Learning). After n labeled samples, if hout = arg minh ∑n t=1 1{h(xt) 6= yt} is the empirical risk minimizer, then with probability at least 1− δ, we have
R∗(hout)−R∗ ≤ log(|H|/δ)
n +
√ 8R∗ log(|H|/δ)
n + 8Ctotal n R∗ + 5 log(|H|/δ) n
1
(1− 4Ctotaln )2 ,
This implies that, as long as Ctotal is small than some fraction of n, e.g., Ctotal ≤ n8 , we can obtain R∗(hout)−R∗ ≤ ε+ Ctotaln R ∗ whenever
n ≥ 2 log(|H|/δ) ε + 8R∗ log(|H|/δ) ε2
Algorithm 1 RobustCAL (modified the elimination condition) 1: Input: confidence parameter δ 2: for t = 1, 2, . . . , n do 3: Nature reveals unlabeled data point xt 4: if xt ∈ Dis(Vt) then 5: Query yt and set l̂t(h) = 1{h(xt) 6= yt} for all h ∈ H 6: end if 7: if log(t) ∈ N then 8: Set L̂t(h) = 1t ∑ s∈t l̂s(h) and ĥt = arg minh∈Vt L̂t(h)
9: Set ρ̂t(h, h′) = 1t ∑ t 1{h(xt) 6= h′(xt)} and βt = log(3 log(t)|H|2/δ)
10: Set Vt+1 = { h ∈ Vlog(t) : L̂t(h)− L̂t(ĥt) ≤ √ 2βtρ̂t(h,ĥt) t + 3βt 2t + 1 2 ρ̂t(h, ĥt) } 11: else 12: Vt+1 = Vt, βt+1 = βt 13: end if 14: end for 15: Output: arg minh∈Vt L̂t(h)
Proof Sketch By using Bernstein inequality and the definition of corruptions, we can get
R∗(hout)−R∗
≤ 4Ctotal n
max{R∗(hout)−R∗, 2R∗}+ √
4 log(|H|/δ) max{R∗(hout)−R∗, 2R∗} n + log(|H|/δ) n
Then we can directly get the result by solving this inequality. We postpone the details into Appendix B.
In addition to this result providing a benchmark, this passive learning result also inspires our analysis of RobustCAL in the corrupted setting as we will show in the next section.

heading: 4 Robust CAL in the Corrupted Setting
text: We restate the classical RobustCAL [Balcan et al., 2009, Dasgupta et al., 2007, Hanneke, 2014] in Algorithm 1 with slightly enlargement on the confidence threshold used in the elimination condition (Line 10). The additional term 12 ρ̂t(h, ĥt) ensures robustness because each (Rt(h)−Rt(h
′) will be corrupted at most 2ρ∗(h, h′)ct. In the theorem below we show that, it can achieve the similar label complexity result as in the non-corrupted setting as long as the growth rate of corruptions is at most in a certain fraction of number of unlabeled samples. Theorem 4.1. Suppose the C[0,t] ≤ t8 for all t ∈ {log(t) = N}, for example, the (1/8)- misspecification model. Then with high probability as least 1 − δ, for any n ≥ ( 8R ∗
ε2 + 22 ε ) log(log(n)|H| 2/δ), we have Rhout −R∗ ≤ ε+O(R ∗Ctotal n ) with label complexity at most
O ( θ∗(14R∗ + 120
log(log(n)|H|/δ) n
) log(log(n)|H|2/δ) (R∗n+ log(n)) )
Remark 4.1. In Appendix C.2, we show the necessity of enlarging the threshold in line 10 from the original
Vt+1 = h ∈ Vlog(t) : L̂t(h)− L̂t(ĥt) ≤ o √2βtρ̂t(h, ĥt) t + βt t  . by giving an counter-example. The counter-example shows that, when R∗ 0, the best hypothesis will be eliminated under the original condition even the “C[0,t] ≤ t8 for all t ∈ {log(t) = N}" assumption is satisfied.
Proof Sketch For correctness, it is easy to show by Bernstein inequality. For the sample complexity, Theorem 3.1 implies that, for any interval [0, t], as long as C[0,t] ≤ t8 , the learner can always identify
hypothesis which are O(R∗ + 1n )-optimal. Therefore, we get the probability of query as P (xt+1 ∈ Dis(Vt+1)) ≤ P ( ∃h ∈ Vt+1 : h(xt) 6= h∗(xt),∆h ≤ O ( R∗ +
βt t )) Then by standard analysis we can connect this disagreement probability with the disagreement coefficient to get the final bound. One thing to note is that, at the first glance ρ̂t(h, ĥt) might be much larger than the other two terms since it can goes to 1, which possibly renders a worse label complexity. Here we give an intuitive explanation on why this threshold is fine: If ρ̂t(h, ĥt) is close to the |R(h)−R(ĥt)|, then we can achieve the inequality above by using some self-bounding techniques. If ρ̂t(h, ĥt) is close to the R∗, then we can directly get some R∗-dependent term in the target bound. The full proof is deferred to Appendix C.1.
Comparison between the modified RobustCal and passive learning: Assume disagreement coefficient is a constant. In the non-corrupted case, the algorithm achieves the same performance guarantee as the vanilla Robust CAL. In the corrupted case, we still get the same accuracy as in Theorem 3.1 with at most Õ(R∗n+log(n)) number of labels, which is the same as the non-corrupted case.
Discussion on the “C[0,t] ≤ t8 for all the {t| log(t) ∈ N}" condition: This condition can be reduced to the (1/8)-misspecification model as defined in Section 2 since CI ≤ |I|8 for any I. But this condition does not contain the case where an adaptive poisoning adversary corrupts all the labels at the earlier stage and stop corrupting later, which still ensures the small total amount of corruptions, but will clearly mislead the algorithm to delete a true best hypothesis h∗. In Section 5, we will show a more general result that applies to scenarios beyond C[0,t] ≤ t8 .

heading: 5 Main algorithm - CALruption

heading: 5.1 Algorithm
text: In this section we describe our new algorithm, CALruption. The pseudo-code is listed in Algorithm 2. Our previous analysis showed that in the agnostic setting the classical RobustCAL may permanently eliminate the best hypothesis due to the presence of corruptions. To fix this problem, in our CALruption algorithm, the learner never makes a “hard" decision to eliminate any hypothesis. Instead, it assigns different query probability to each x based on the estimated gap for each hypothesis as shown in line 4 and 5, which can be regarded as “soft elimination". With this step, the key question becomes how to connect the estimated gaps with the query probability qxl .
We adopt the idea from the BARBAR algorithm proposed by Gupta et al. [2019] which was originally designed for multi-armed bandits (MAB). Instead of permanently eliminating a hypothesis, the learner will continue pulling each arm with a certain probability defined by its estimated gap. However, the original BARBAR algorithm is mainly focused on estimating the reward of each individual arm. This aligns with its MAB feedback structure, where only the information of the pulled arm will be gained at each time. In the active learning setting, we instead focus on the difference of the risks of different hypotheses, because each time we request a label, values of all the hypotheses will be updated. Therefore, we implement a more complicated strategy to calculate the query probability at the end of each epoch l, as shown from line 7 to line 13.
In line 7, we estimate the disagreement probability for each hypothesis pair (h, h′) with an empirical quantity that upper bounds the expectation. In line 8, instead of estimating the value of each hypothesis, we estimate the gap between each hypothesis pair (h, h′), denoted as Wh,h ′
l , by any δ-robust estimator that satisfies eq. 1. One example of δ-robust estimator is Catoni estimator [Lugosi and Mendelson, 2019]. Note that simple empirical estimator will lead to potentially rare but large variance, which has been discussed in Stochastic rounding section in Camilleri et al. [2021]. But what we truly care is the gap between any hypothesis h and the best hypothesis h∗. Therefore, inspired by Camilleri et al. [2021], we construct such estimation by using Wh,h ′
l as shown in line 9 to 11. Finally, we divide the hypothesis set into several layers based on the estimated gap and set the query probability for each x based on the hypothesis layers, as shown in line 12 and 13. For more detailed explanation on line 9-13, please refer to Appendix D.
Algorithm 2 CALruption 1: Initialize: β3 = 2 log( 32blog(n)c|H| 2/δ), β1 = 32 ∗ 640β3, β2 = 532 , i = 2 −i, Nl = β1 −2 l ,
∆̂0h = 0, V 0 1 = Z and τ1 = 1, qxl = 1 for all x ∈ X
2: for t = 1, 2, . . . , n do 3: Nature reveals unlabeled data point xt 4: Set Qt ∼ Ber(qxl ) and request yt if Qt = 1. 5: Set estimated loss for all h ∈ H as ˆ̀t(h) = 1{h(xt) 6=yt}qxl Qt 6: if t = τl +Nl − 1 then 7: Set ρ̂l(h, h′) = 1Nl ∑ t∈Il 1{h(xt) 6= h
′(xt)} for all h, h′ ∈ H 8: For each (h, h′), set Wh,h ′ l = RobustEstimator ( {ˆ̀t(h)− ˆ̀t(h′)}t∈Il ) , which satisfies
that, with probability at least 1− δ,
|(R̂l(h)− R̂l(h′))−Wh,h ′ l | ≤
√ 10β3ρ̂l(h, h′)
Nl minx∈Dis(h,h′) q x l
, (1)
where R̂l(h) = 1|Il| ∑ t∈Il Ey∼Ber(ηxtt ) [1{h(xt) 6= y}].
9: Set D̂l = arg minDmaxh,h′∈H(RD(h)−RD(h′)−W h,h′ l ) √ minx∈Dis(h,h′) q x l
ρ̂l(h,h′) 10: Set ĥl∗ = arg minh∈H ( RD̂l(h) + β2∆̂ l−1 h ) 11: Set ∆̂lh = max { l, RD̂l(h)− ( RD̂l(ĥ l ∗) + β2∆̂ l−1 ĥl∗
)} 12: Construct V il+1 for all i = 0, 1, 2, . . . , l, such that,
∆̂lh ≤ i,∀h ∈ V il+1 and ∆̂lh > i,∀h /∈ V il+1
Therefore, V ll+1 ⊂ V l−1 l+1 ⊂ . . . ⊂ V 0l+1
13: Calculate the query probability qxl for each x as follows
Z(x) = {(h, h′) ∈ H | x ∈ Dis({h, h′})} k(h, h′, l + 1) = max{i | h, h′ ∈ V il+1}
qxl+1 = max (h,h′)∈Z(x)
β1ρ̂l(h, h ′)
Nl+1 −2k(h,h′,l+1)
14: Set τl+1 = τl +Nl and denote the epoch l as I = [τl, τl+1 − 1]. Set l ← l + 1, go to the next epoch 15: end if 16: end for 17: Output: h ∈ V l−1l
Remark 5.1. In Line 9, instead of estimating over all possible distribution D, we actually just need to estimate ηx∗ for all x ∈ {xt}t∈Il and set the corresponding x distribution of D as the empirical distribution of x inside Il. Theorem 5.1 (CALruption). With n ≥ 72ε−2β1 number of unlabeled samples, with probability at least 1− δ we can get an hout satisfying
R∗(hout)−R∗ ≤ ε+ 24 C total n ,
with label complexity as most
O ( θ∗(R∗ + 3 √ β1 n + 64C total n ) log(log(n)|H|2/δ) ( (R∗)2n+ log(n)(1 + C total) ))
where C total = ∑blog4(n/β1)c l=1 Cepoch l ( R∗1{Cepoch lNl ≤ 1 32}+ 1{ Cepoch l Nl > 132} )
and β1 = 16 ∗ 640 log(32blog(n)c|H| 2/δ). Note that epoch l is prescheduled and not algorithm-dependent.
Corollary 5.1. Suppose the corruptions satisfy Cepoch lNl ≤ 1 32 for all epochs, for example, the (1/32)- misspecification case, then for any n ≥ 72ε−2β1 number of unlabeled samples, with probability at least 1− δ we can get a hout satisfying
R∗(hout)−R∗ ≤ ε+ 24R∗ Ctotal n ,
with label complexity as most
O ( θ∗(R∗ + 3 √ R∗β1 n + 64R∗Ctotal n ) log(log(n)|H|/δ) ( (R∗)2n+ (R∗Ctotal + 1) log(n) ))
Comparison with passive learning and the Calruption: Consider the case where θ∗(·) is of lower order like a constant. The Corollary 5.1 shows that, when Cepoch lNl ≤ 1 32 for all epochs, our algorithm
achieves a similar accuracy O ( ε+ R
∗Ctotal n
) as in the passive learning case, while only requiring
Õ ( (R∗)2n+ log(n)(1 +R∗Ctotal) ) number of labels, for n ' 1ε2 . So if we set n = Õ( 1 ε2 ), then the
label complexity becomes Õ ( (R∗)2
ε2 + log(1/ε)(1 +R ∗Ctotal)
) , which matches the minimax label
complexity in the non-corrupted case.
Going beyond the Cepoch lNl ≤ 1 32 constraint, the general Theorem 5.1 shows that, for n ' 1 ε2 , our algorithm achieves an accuracy O ( ε+ Ctotaln ) while only requiring Õ((R∗)2n + log(n) + Ctotal) number of labels no matter how corruptions are allocated. When R∗ is some constant, this result becomes similar to the Corollary 5.1. Moreover, we will argue that upper bound C total by Ctotal is loose and in many case C total will be close to R∗Ctotal instead of Ctotal. We show one example in the paragraph below.
When is Calruption better than modified Robust CAL? Consider the case where the adversary fully corrupts some early epoch and then performs corruptions satisfying Cepoch lNl ≤ 1 32 for rest epochs. Then the modified Robust CAL will mistakenly eliminate h∗ so it can never achieve target result when ε < minh∈H∆h while Calruption can surely output the correct hypothesis. Moreover, according to Theorem 5.1, since the total amount of early stage corruptions are small, so here C total is close to R∗Ctotal, which implies a similar result as in Corrollary 5.1.
When is Calruption worse then modified Robust CAL ? Consider the case where the total amount of corruption is, instead of fixed, increasing with incoming unlabeled samples, for example, the misspecification case. Then Ctotal in modified Robust CAL can be O(R ∗ ε2 + 1 ε ) while Ctotal in CALruption can goes to O( 1ε2 ). Such gap comes from the extra unlabeled sample complexity, which we discuss in the paragraph below.
Discussion on the extra unlabeled samples complexity: We note that we require a larger number of unlabeled data than ERM in the passive learning setting. Here we explain the reason. Consider the version spaces V l−1l for any fixed epoch l. In the non-corrupted setting, this version space serves the similar purpose as the active hypothesis set in Robust CAL. In Robust CAL, its elimination
threshold is about Õ (√
ρ∗(h,h′) t + 1 t
) (or Õ ( ρ∗(h, h ′) + 1t ) in our modified version) while in our
CALruption, the threshold is about Õ (√
1 t
) , which is more conservative than the Robust CAL and
leads to the extra unlabeled sample complexity. The reason about being conservative here is that we need more samples to weaken the effects of corruptions on our estimation. Whether such extra unlabeled samples complexity is unavoidable remains an open problem.

heading: 5.2 Proof sketch for Theorem 5.1
text: Here we provide main steps of the proof and postpone details in Appendix E.
First we show a key lemma which guarantees the closeness between ∆̂lh and ∆h for all l and h.
Lemma 5.1 (Upper bound and lower bound for all estimation). With probability at least 1− δ, for all epoch l and all h ∈ H,
∆̂lh ≤ 2 (∆h + l + gl) , ∆h ≤ 3
2 ∆̂lh +
3 2 l + 3gl,
where gl = 2β1 2 l ∑l s=1 Cs ( 2R∗1 { 2CIs Ns ≤ 116 } + 1 { 2CIs Ns > 116 }) .
Here the gl term implies that, as long as the total corruption is sublinear in n, the misleading effects on the gap estimations will fade when the number of unlabeled samples increasing.
Based on this lemma, we can directly get another useful lemma as follows. Lemma 5.2. For all epoch l and layer j, we have maxh∈V jl ρ∗(h, h ∗) ≤ 2R∗ + 3 j + 3gl−1
In the following we first deal with the correctness then then sample complexity.
Correctness. By Lemma 5.1, we have
∆hout ≤ 3 2 ∆̂L−1hout + 3 2 L−1 + 3gL−1 ≤ 6 √ 2β1 n + 24 C̄total n .
Sample complexity. For any t ∈ Il, recall that qxl = max(h,h′)∈Z(x) β1ρ̂l−1(h,h ′) Nl −2k(h,h′,l), the probability of xt being queried (Qt = 1) is
E[Qt] ≤ 10 β1 Nl ∑ x∈X P (xt = x) max h∈V jx l
l
ρ∗(h, h ∗) −2jxl + 8 β1 Nl
≤ 10β1 Nl ∑ x∈X P (xt = x) ( 2R∗ −2jxl + 3 −1jxl + 3gl−1 −2 jxl ) + 8 β1 Nl
≤ 10β1 Nl l−1∑ i=0 ( 2R∗ −2i + 3 −1 i + 3gl−1 −2 i ) P(x ∈ Dis(V il )) + 8 β1 Nl
Here jxl is some arbitrary mapping from X to [l], which is formally defined in detailed version in Appendix E.6. The first inequality comes from the closeness of estimated ρ̂l(h, h′) and the true ρ∗(h, h ′), as well as some careful relaxation. The second inequality comes from Lemma 5.2.
Now we can use the standard techniques to upper bound P(x ∈ Dis(V il )) as follows, P ( ∃h ∈ V il : h(x) 6= h∗(x) ) ≤ P (∃h ∈ H : h(x) 6= h∗(x), ρ∗(h, h∗) ≤ 2R∗ + 3 i + 3gl−1) ≤ θ∗(2R∗ + 3 i + gl−1) (2R∗ + 3 i + 3gl−1)
where again the first inequality comes from Lemma 5.2. Again we postpone the full version into Appendix E.6.
Combining the above results with the fact that gl = 2β1 2 l C̄l−1 and C̄l−1 ≤ ∑l−1 s=1 CIs ≤ 2β1 −2 l−1, we get the expected number of queries inside a complete epoch l as,∑ t∈Il E[Qt] ≤ 20β1θ∗(2R∗ + 3 l−1 + gl−1) ∗ ( 4(R∗)2 −2l + 12R ∗ −1l + 132 β1 C̄l−1 + 10 )
Finally, summing over all L = d 12 log(n/β1)e number of epochs, for any n, we can get the target lable complexity.

heading: 6 Conclusion and future works
text: In this work we analyzed an existing active learning algorithm in the corruption setting, showed when it fails, and designed a new algorithm that resolve the drawback. Relative to RobustCAL,
our algorithm requires a larger number of unlabeled data. One natural question is to design a corruption robust algorithm which requires the same number of unlabeled data as RobustCAL in the non-corrupted setting. Another potential question is that, the O ( ε+ C totaln ) accuracy from Algo. 2
in the general corruption case is generally worse than O ( ε+ R
∗Ctotal n
) accuracy of passive learning.
Although we state that these two bounds are close in many cases, a question is if there exists an alternative algorithm or analysis that will result a more smooth final bound to interpolate between different corruptions cases.
Finally, we believe it is possible to replace the Catoni estimator with naive importance sampling estimator and even further simplify the layered active hypothesis sets construction step by adopting Beygelzimer et al. [2010]’s idea. We plan to work on this direction in the future.

heading: Acknowledgements
text: SSD gratefully acknowledges funding from NSF Award’s IIS-2110170 and DMS-2134106

Review summaries:
The paper discusses binary classification when the labels can be corrupted by noise in an active learning scenario. In this direction the authors show that in a benign corruption setting the, a known algorithm, which the authors call RobustCAL, can achieve pretty-much the same label complexity as in a non-corrupted setting. However, the algorithm may fail in general and the authors propose a variation of this algorithm in order to be able to deal with the general case. This latter algorithm, though it requires more labels compared to RobustCAL, nevertheless it does come with good theoretical properties.  

This paper considers active learning with an "oblivious adversarial model": before the start of learning, an adversarial chooses a series of distributions $P_t(Y\mid X)$ , and at time t the label $Y$ would be drawn from that distribution. The adversarial level is characterized by $C_{total}=\sum_t \sup_x |P_t(Y\mid X=x)-P(Y\mid X=x)|$ where $P(Y\mid X=x)$ is the distribution over which the error for the model is calculated.   It first shows an error bound for passive learning with ERM. Then, it shows a slightly modified version of CAL (disagreement based active learning) could tolerate around $C_{total} <= n/8$ and achieve an error of $R^* + \epsilon + O(R^* C_{total}/n)$ where R* is the best error achievable without corruption and n is the number of unlabeled samples. Its label complexity is similar to that of the original CAL.   To tolerate any level of adversarial, instead of shrinking the version space permanently, it proposes a new algorithm that queries examples with some carefully designed probabilities. It gives its label complexity bounds, and shows that (1) its label complexity matches standard CAL without corruption; (2) it can tolerate higher corruption ($C_{total}>n/8$) while the previous modified CAL cannot; (3) its label complexity is slightly worse when the adversarial corruption is not high (e.g. the mispecification case where the probability that the adversarial corrupts the label in each round is uniformly upper bounded).

The authors study the problem of active learning in binary classification with the presence of agnostic noise in the streaming model. The adversary chooses a priori some corrupted distributions $D_t$ for each round $t$. The goal is to design an algorithm that outputs a hypothesis $h$ that minimizes the expected risk using a few labeled samples. In this work, they assume that they do not have any a priori information on corruption. The authors proceed by first analyzing the ERM for the passive learning for using it as a benchmark for the rest of the algorithms. The authors analyze two algorithms the RobustCAL (which has been analyzed extensively in previous works) and the CALruption which is the new algorithm they propose. For RobustCAL they show that as long as the corruption is bounded enough (the number of corruptions is less than $t/8$) in all the $t=1,2,4,...,2^k$ then the classic RobustCAL along with a regularization term will output a hypothesis that achieves expected risk competitive with the passive learning, i.e., the RobustCAL will not eliminate the optimal hypothesis in any elimination step. Moreover, they show that the regularization term is necessary by showing that without this term the best hypothesis will be eliminated. In order to remove the assumption on the bounded corruptions, the authors suggest a new algorithm CALruption, that overcomes this issue. However, this algorithm in the general case outputs a hypothesis $h$, such that $R(h)-R^* \leq \epsilon +O(\bar{C}/n)$ where RobustCAL gets $R(h)-R^* \leq \epsilon +O(R^* C/n)$, $\bar{C}$ is the number of corruptions in each epoch with some weights if the corruptions are large or small. Furthermore, if the corruptions are bounded enough in each epoch, then the difference of expected risk can be improved to $\epsilon +O(R^*C/n)$. 

The authors consider robust active learning. They demonstrate that an existing algorithm Robust CAL can be tricked into permanently discarding the optimal hypothesis by large amounts of corruption early on during learning (followed by no corruption to keep overall levels low). The authors repair this flaw by modifying the algorithm to do a soft-elimination so that no hypothesis is permanently discarded. However, the cost is a higher unlabeled sample complexity, which also creates a weakness to increasing corruption.