Corruption Robust Active Learning
Authors: Yifang Chen
Simon Shaolei Du
Kevin Jamieson
Venue: NeurIPS 2021 Poster (2021)
Keywords: active learning
robustness

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 ornot. 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 $\tilde{\mathcal{O}}(C_{\mathrm{total}})$ additional labels in the corrupted setting to achieve $\mathcal{O}(\varepsilon + \frac{C_{\mathrm{total}}}{n})$, where $\varepsilon$ is the target accuracy, $C_{\mathrm{total}}$ is the total number of corruptions and $n$ is the total number of unlabeled samples.

Corruption Robust Active Learning
Yifang Chen, Simon S. Du, Kevin Jamieson Paul G. Allen School of Computer Science & Engineering University of Washington, Seattle, WA lyifange, sadu, jamieson }.css wwshington. edu
Abstract
We conduct theoretical studies on streaming- active learning for binary classi- fication 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 hypoth- esis elimination threshold, the classical RobustCAL framework can (surprisingly) achieve nearly the same label complexity guarantee as 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 the presence of corruptions. Furthermore, this algorithm enjoys the minimax label complexity in the non-corrupted setting (which achieved by RobustCAL) and only requires (Ctotal) additional labels in the corrupted setting to achieve O + Sustal) where is the target accuracy, Crotal is the total number of corruptions and is the total number of unlabeled samples.
Introduction
An active learning algorithm for binary classification aims obtain the best hypothesis (classifier) from some given hypothesis set while requesting as few labels as possible. Under some favorable conditions, actíve learning algorithms can require exponentially fewer labels then passive, random sampling [Hanneke] 2014). Active learning is ideally suited for applications where large datasets required for accurate inference, but the cost of paying human annotators to label dataset is prohibitively large (Johi et al.) 2009 Yang et al., 2013 Beluch et al. 2018). A bit more formally, for an example space X (such contains a bumann-add object or not). let H. be hypothesis class such that for each h E H. we have h X - {0, 13. After certain number of labels are requested, the learner will output target hypothesis hum H. In this paper, we consider the streaming setting where at each time f nature reveals 24 Dx and an active learning algorithm must make the real-time decision on whether to request the corresponding label or not. Such streaming setting of active learning is frequently encountered online environments such as learning a spam filter or fraud detection (i.e., mark as spam/fraudulentt and do not request the label, or send to inbox/expert to obtain label).
set of images) and label space (0. I} (like whether the image
This paper is interested in setting when the requested label Vt is potentially corrupted by an adversary. That is. when requesting the label for some example 2; E X. if uncorrupted the learner will receive label drawn according to the "true" conditional label distribution, but corrupted, the learner will receive a label drawn from an arbitrary distribution decided by an ad adversary. This setting challenging because the learner has no 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 (NcurIPS 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. (014), Awasthi
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 Guppta et al. 2019 Zimmert and
Seldin 2019, Wei et al., 2020] and reinforcement learning [Lykouris et al., 2020 Chen et al.) 222 la Wei et al. 2021]. However, there striking lack of such literature in the active learning area. Existing disagreement-baae
active learning algorithmss 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 unknown number of labels are potentially corrupted by 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 (= Re" Rt"Caul -opiimal hypothesis as long as n E c benchmark for the following active learning results (Section 3)
n
1 + R where R' is the risk of best hypothesis. This result serves as a
If we assume that the disagreement coefficient, a quantity that characterizes the sample complexity of active learning algorithms (Hanneke 2014). some constant, then we obtain the following results for active learning.
Secondly, we analyze the performance of standard active learning algorithm called Robust- CAL [Balcan et al. 2009 Dasgupta et al. 2007 Hanneke 2014) under 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 OE + R Cass )-optimal hypothesis as long as n e2 Ö (R'n log(n)) number of labels (Section
n" with at most
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 ((Ciota) additional labels in the corrupted setting, That is, the algorithm will output an (s + Cueal )optimal hypothesis as long as ズ z² with at most δ (IR*)2 + log(n) + Cuocaa) number of labels. Besides, this algorithm also enjoys improved bound under benign assumption on the corruptions. That is, the algorithm will output an + R Cau -optimal hypothesis with at most Ô ((R*) )"n + log(n) + R2 (rouaa))
number of labels (Section
Note that Crotal can be regarded fixed budget or can be increasing with incoming samples. In the latter case, Grestl 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 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 learn classifier using as few annotated labels as possible by selecting examples sequentially is also somewhat mature [Settles] 2011 Hanneke, [0114). 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, 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 al. 2007 Hanneke 2014

---

The performance of RobustCAL is characterized by quantity known as the disagreement coefficient that can be large, but in many favorable situations can be bounded by a constant 6* which we assume is the case here. In particular, for any > O, once Nature has offered RobustCAL. n unlabelled samples, RobustCAL promises to return a classifier with error at most v R log( [2)))/+ [H4))n
and requests just nR* + 0" (* log([H() + log( (H()) labels with high probability. Said another way, RobustCAL returns an c-good classifier after requesting just 8 ((R*) ) log(1/c)) labels. If 0 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]. [alcaan and Long [2013] ..3....... Huang et al.] 20.152013), D. we use RobusTCAL our benchmark in the uncorrupted setting. We note that since RobustCAL is computationally inefficient for many classifier classes of interest, number of works have addressed the issue at the cost of a higher label sample complexity [Beygelzimer et al. 2009, 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.
2009,2010) 2010 Hsu 2010, Krishnamurthy et al. [211]] or higher
To the best of our knowledge, there 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 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 pool of a varying quality of annotators, some active learning algorithms have attempted to avoid and down- 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(Y - 1 X, = z) remains fixed, but P(X; x)) drifts and the active learner aims to compete with the best online predictor that observes all labels (Yang] 201 I Dekel et al.) 2012 Hanneke and Yang 2021 Chen et al. 2b221b] Another relevant line of work considers the case where the distribution of the examples drifts over time (i.e., P(X, = x)) (Rai et al. 2010) or the label proportions have changed (i.e, P(Y, 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-relate related works in the related problem areas of multi-arm bandits (MAB), linear bandits and episodic rein- forcement learning. To be specific, for MAB, Gupta et al. [2019 achieves Ō(Eazaa 1 + KC) by A.
adopting sampling strategy based on the estimated gap instead of eliminating arms permanently. Our proposed algorithm is inspired by this "soft climination" technique and requests labels based on the estimated gap of each hypothesis. Later, Zimmert and Seldin [019] achieves a near-optimal result
Ô Eaata A. Eayar Aa)
in MAB by using sallow-the-Regulariiee Leader (FTRL) with
Tsallis Entropy. How to apply the FTRL technique in active learning. however, remains an open prob- lem. Besides MAB, Lee et al. [022 achieves Ô (GapComplexity + C)) in stochastic linear bandits. We note that the linear bandits papers Le et al. [202T) and |amilllri et al. [202T) 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 δ (C CapComplexity + C²) in non-tabular RL and Chen et al. 2021aa achieves O
+ C²) in tabular RL. Very recently, Wei et al. [021 obtains an GapComplexity + C' bounds for linear MDP.
2 Preliminaries
General protocol: A hypothesis class H. is given to the learner such that for each h H. we have h: X' - f0, 1}. Before the start of the game, Nature will draw n unlabeled samples in total. At each time E {1,...,.0 n.. nature draws (x,, v1) E X x {0, 1} independently from a joint distribution D.. the leamer observes just ze and chooses whether to request yr or not. Note that in this paper, we assume is countable, but it can be directly extended to uncountable case. Next, We denote the expected risk of a classifier h E H under any distribution D as (h) = Ez.gyDD (1(h(z) 4 v}), the marginalized distribution of x as V and probability of y = given x and D as n7" Finally we define pD h²) Er-,, 1(((x) * h hz(z).
3

---

Uncorrupted model: In the traditional uncorrupted setting, there exists fixed underlying distri- bution D. where each (oe, 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 DD as T
Oblivious and non-oblivious adversary model: In the corrupted setting, the label at time is corrupted if (3e, m1 is drawn from some corrupted distribution Dj that differs from the base D.. At the start of the game, an oblivious adversary will choose a sequence of functions v7p" & - [0, for all t {I...., n). The corruption level at time is measured
max xEA
and the amount of corruptions during any time interval I as CI = Eter Ct- Correspondingly, we define Crotal = Cjo.nj. Then, Nature draws It ~ v, for each {L..... n. so that each 2y is independent of whether y/ was potentially corrupted or not.
One notable case case of the oblivious model is the y-miispecifiiation model. In the binary classifica- tion setting, it is equivalent to
c = (1- (1 + Mih Yx, t.
where oj, can be any arbitrary probability. Such label contamination model can be regarded a special case of corruption where for each
C2 max ME n max In
1
Moreover, our main algorithm actually works for the non-oblivious adversary. In this more challenging case, each time t, the adversary adaptively decides vi before seeing actual Ty, based on all the previous history.
Other notations: For convenience, we denote RdD, (h) as (h),), RD. (h) as (h()), PD, (h, h²) = Pe hi) and pp. (h, h') p- Rt). We also define average expected risk that will be used lot in our analysis. RT(h) エ TET Re(h). In addition, we define /² = arg min R. (h), R2 R. (h*)
and the gap of the suboptimal classifier h A (h) R"
Disagreement coefficient: For some hypothesis class H and subset V C H. the region of disagreement is defined Dis(V) {i E X' 3h, N E V s.t. h(x)) # M())), which is the set of unlabeled examples æ for which there are hypotheses in V that disagree on how to label r. Correspondingly, the disagreement coefficient of ht E with respect hypothesis class H and. distribution V, is defined as
PaNu, (X E Dis(B(h" .r)))
0" (ro) = sup r2na
Passive Learning in the Corrupted Setting
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 Noou = arg min, Et= 1(h(xz) + y. have
the empirical risk minimizer, then with probability at least 1
log( Hl/5))
8R" log( (
8Crotal R
5 log (7118))
R, (how))
- Rd
(1 4C )2
n
n
71
n
This implies that, as long as Crona is small than some fraction of n, e.g. Croat S n R. (how) R² < Coot R whenever
8, we can obtain
2 2og 2log(HH//8) n
8R" log((H1/))
E
22

---

Algorithm RobustCAL (modified the elimination condition)
1: Input: confidence parameter 8
2: for t= 1, ..2.....? ; do
3: Nature reveals unlabeled data point 24
4: if Ia E (V,) then
5: Query and set ((h) = 1(h(2,) # y for all h e H end if
6:
7:
if log(t) E N then
8:
Set (h) = Leet (h))) and h, arg min L((h)
9:
Set (e(h, = + (hb()) 11(21)) and Br log(3 (0g(())7((/0)
Set V2+1 = h Viog(o [.( (he s /28.0.
38,
(h,)
+
2r
11:
else
12:
V4+1 = Ve, 31+1 3r
13:
end if
14:
end for
15:
Output: arg min (h)
Proof Sketch
By using Bernstein inequality and the definition of corruptions, can get
Rs (howt) - R
4Croua n
max (hous) R 22" Alog((Hl/0) max R., (how) R 2R*}
log({Hl/0))
π
n
Then can directly get the result by solving this inequality. We postpone the details into Appendix In addition to this result providing benehmark, this passive learning result also inspires our analysis of RobustCAL in the corrupted setting as we will show in the next section.
B
4 Robust CAL in the Corrupted Setting
We restate the classical RobustCAL [Balcan et al. 2009 Dasgupta et al. 2007 Hanneke, 2014) 4) in Algorithm D with slightly enlargement on the confidence threshold used in the elimination condition (Line 10p. The additional term (h, hu) ensures robustness because each (Rt(h) R, Rh()) will be corrupted at most (h, N' N')c,- 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 corruptions is at most in certain fraction of number of unlabeled samples.
Theorem 4.1. Suppose the Cjo.e] & for all t E (log(t) = N). for example, the (1/8)- misspecificattion model. Then with high probubility as least 5, for any 2 (8R" 22 (og(log())))41{3// we have Rh R" S + O Rt Cuea) with label complexity at most
00 (14AHH + 120 log(log(()) (1)111))))
log(log( |) (1 log(n))
Remark 4.1. In Appendix C.2 we show the necessity of enlarging the threshold in line 10 from the original
Be (225 + 1. }
V441 {
Viog(1) : L.(0) - Le(he) s (8,
by giving an counter-example. The counter-example shows that, when R > O. the best hypothesis will be eliminated under the original condition even the "Cjo.y I 1 for all t E (log(t) = N)" assumption is satisfied.
Proof Sketch For correctness, it easy to show by Bernstein inequality. For the sample complexity, Theorem 3.1 implies that, for any interval [0, f), as long C/o.s) < 1. the learner can always identify
5

---

hypothesis which are ORR" + 2)) -optimal. Therefore, we get the probability of query as
R +
Be ))
( E Dis(()+))) S 3h V4+1+ : h(x)) + h (m)), S
Then by standard analysis we can connect this disagreement probability with the disagreement coefficient to get the final bound. One thing to note that, at the first glance Pe(h, he) 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 intuitive explanation on why this threshold is fine: If (h, h4) is close to the [R(h) R(he)l, then we can achieve the inequality above by using some self-bounding techniques. If De (h, he) close to the Rt, then we can directly get some Rt -feeeeendent term in the target bound. The full proof is deferred to Appendix C.I
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 Ö(R" n + Iog(n)) number of labels, which is the same as the non-corupped case.
Discussion on the "Coo. I & for all the {t] log(t) E NJ" condition: reduced to the (1/8) misspeccicciiiinnnnnnn model defined in Section 2 since Cz 8 for any I. But this condition does not contain the case where an adaptive poisoning adversary corrupts all the labels 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 S
This condition can be
we will show
more general result that applies to scenarios beyond Cja.i S $.
5
Main algorithm- CALruption
5.1
Algorithm
In this section we describe our new algorithm, CALruption. The pscudo-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 CAL- ruption algorithm, the learner never makes a "hard" decision to eliminate any hypothesis. Instead, assigns different query probability to each based the estimated gap for each hypothesis as shown in line 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 of
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, implement more complicated strategy to calculate the query probability at the end of each epoch I, as shown from line to line 13
In line 7 we estimate the disagreement probability for each hypothesis pair (h, with an empirical quantity that upper bounds the expectation. In line [ instead of estimating the value of each hypothesis, we estimate the gap between each hypothesis pair (h. h²), denoted as Whhh'', by any 6-robust estimator that satisfies eq. [ One example of d-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. [02T]. 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 W.'.''' as shown in line to Finally, we divide the hypothesis set into several layers based on the estimated gap and set the query probability for each based on the hypothesis layers, as shown line 12 and T3 For more detailed
explanation on line 9-13, please refer to Appendix D

---

Algorithm 2 CALruption
1: Initialize: 83 = 2 log( & [lo J2 - 32 * 640 32
5 32 2 N₁ = -Bic
Ag 0, V 2 and 71 1, 1 for all X
2: for t = 1,2..... do
3: Nature reveals unlabeled data point 24r
4:
Set Qt ~ Ber(gi") and request yr if Qt = 1.
5: Set estimated loss for all H (e(h) 1 [((())77))) Qr.
9f
6: if = Ni then
7: Set أi (h, h)) N; ΣIEZ, 1(h(x)) # (xx)) for all h, h²
8: For each (h, 1'), set W.t.k RobustEstimator ((L(M) ((01))-4((0))) ((()))e which satisfies
that, with probability least 1 1 8.
103z
- (((())) - w/t 1
Ni min of
where (h) म.. ELET, By [1(1(x=)) # v}l.
Set D. arg minp Ea (RD(h) RD(N() W/I.") )
min, a of (c(h.h))
9:
10: Set hi arg minncH (Rz (h) + 322/111
Set Å max {eL, Rb, (h) R,,, (hk) + B2 kt
11:
Construct V44, for all 0, 1, ,., such that,
b s vh Vi41 and
D Es vh $ Vi42
Therefore, V/41 C 1/#1 c... C V
13:
Calculate the query probability of for each follows
((x) {(hhhh)))))))) H x E (i)((
k(h, h1, h1,1+1) maxfi h, E V441}
Bipi(h, -2
4 (E())
No11 ((hh,e111)
Set T++1 = 7i + N2 and denote the epoch as I [T,, 741 1). Set + I I+ 1, go the next epoch end if
16: end for Output: h V
Remark 5.1. In Line 9 instead of estimating over all possible distribution DD we actually just need to estimate of for all x Latte and set the corresponding x distribution of D as the empirical distribution of inside Iz. Theorem 5.1 (CALruption). With n 2 72 2 number of unlabeled samples, with probability at least 1 8 we can get hout satisfying
R. (hout) - R² < 5 24 Crotal
with label complexity as most
o ( 0+ (R' + +3
B1
64C log(log(n)){4) /8) ((R))3n log(n) Cional))
n
where Conat = Ellor (1/ Capock ( Canti < 32 +
1
Cauah! +111 and B1 = 16
N.
640 log( [ [log(n)][7{ /8). Note that epoch is prescheduled and not algerithm-deeendden..
7

---

Corollary 5.1. Suppose the corruptions satisfy Caush1 S
Ni 32 for all epochs, for example, the (1/32)-
misspecification case, then for any n. Z 72e- number of unlabeled samples, with probability at least 1 - we can get hout satisfying
Crout
R. (hout) - R E
71
with label complexity as most
R B1 o (x +3/
64R Caeal log(log(n))11//) ((1 ((R)) (Rtaal + 1) log(n))
n
n
Comparison with passive learning and the Calruption: Consider the where 0 (.) of lower
order like a constant. The Corollary 5.1 shows that, when Capen achieves similar accuracy O
Ni S 32 for all epochs, our algorithm
R Croa as in the passive learning case, while only requiring
Ô ((R) ) + lo + R' Cuoal) number of labels, for n E z. So we set n = ( ). then the label complexity becomes Ö (R log(1/s)(11 1t" ((oaa)))) which matches the minimax label complexity in the non-corrupted case.
32 constraint, the general Theorem 5.1 shows that, for n 2 2. our algorithm achieves an accuracy O (s Sum)) while only requiring O((R))² + log(n) + Cwmw)) 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 Cunat by Ciotal is loose and many case Crocal will be close to R Croral instead of Grotal- We show one example in the paragraph below.
Going beyond the Casett
Ni S
When Calruption better than modified Robust CAL?
Consider the case where the adversary
fully corrupts some early epoch and then performs corruptions satisfying Cana < 1 for rest epochs. Nj 32
Then the modified Robust CAL will mistakenly eliminate h* so it can never achieve target result when E < min As while Calruption can surely output the correct hypothesis. Moreover, according to Theorem 5.1 since the total amount of early stage corruptions are small, here Ciotal is close to
R2 Croca,, 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 Croat in modified Robust CAL can be O It و + 2) while Gweat in CAL CAIruption can goes to ( 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 require larger number of unlabeled data than ERM in the passive learning setting. Here we explain the reason. Consider the version spaces 1²- for any fixed epoch I. In the non-corrupted setting, this version space serves the similar purpose the active hypothesis set in Robust CAL. In Robust CAL, its climination
threshold is about δ ( (.
+ (Ve
(or (h,,11 + (p.
in our modified version) while in our
δ (Vt). which is more conservative than the Robust CAL and leads to the extra unlabeled sample complexity. The reason about being conservative here that need more samples to weaken the effects of corruptions unlabeled samples complexity is unavoidable remains an open problem.
CALruption, the threshold is about
estimation. Whether such extra
5.2 Proof sketch for Theorem 5.1
Here provide main steps of the proof and postpone details in Appendix E
First we show a key lemma which guarantees the closeness between Á/, and As for all / and h.

---

Lemma 5.1 (Upper bound and lower bound for all estimation). With probability at least 1 5. for all epoch and all
H.
3
+ 3
1 - ( + +a 91).
n -
A h
2
2
where gi = p. E. C. (2R'1 { 20z. N. I 16
20z. N. 16
> 1 1
Here the Si term implies that, long the total corruption is sublinear in n, the misleading effeets 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 and layer j, we have max nav; Pa (h, h²) s 2 + 3c, + 391-1
In the following first deal with the correctness then then sample complexity. Correctness. By Lemma 5. we have
3 A A
23
Crotal
A hour
+ 2 2 391--91- S 6V + 24
Sample complexity. For any E I₁ recall that of max(L.N)Z(()) probability of æ4 being queried (Q: = 1) is
Bid: (
RR Jy the
Nr
EIQ.1 < 10
31 Ni
Σ
P(r: = x) max P. (h, (h, +8 31
NEV!
Ni
ZEX
< 10
31
Σ
P(æt x) 2R
Ejp
2
+ "e + 3g 1
+ & 31
N;
ZE
(2 +,, + 39 ))p P(x E Dis(V + 8 31 Σ
1-1
< 10
N
Ni
Here ji is some arbitrary mapping from X' to [[] which is formally defined in detailed version in Appendix E.6 The first inequality comes from the closeness of estimated (h, h²) and the true pa (h, H²), as well as some careful relaxation. The second inequality comes from Lemma 5.2
Now
the standard techniques upper bound P(z Dis(V/)) follows,
P ( M(x) + (x))
< PP (3h H h(x)(()))))))))))) + + (x), P- (h, h²) S 2R" + 3e, + 3g(-))
(x),
S 8r (2R' + 3c, + 91-1) (2R* + 3c, + 3g1-1
where again the first inequality comes from Lemma 5.2 Appendix E.6
Again postpone the full version into
Combining the above results with the fact that g: = 2 2 and CT-1 S E1=l Cz, $ 281
31
we get the expected number of queries inside a complete epoch as,
E[Q]] < 20,,,0 (2R" + + + 91)) * (A( +12R" +
132
B C1 10)
IET
Finally, summing over all log(n/3:)] number of epochs, for any n, we can get the target lable complexity.
6 Conclusion and future works
In this work we analyzed an existing active learning algorithm in the corruption setting, showed when it fails, and designed a algorithm that resolve the drawback. Relative to RobustCAL.

---

our algorithm requires larger number of unlabeled data. One natural question is to design corruption robust algorithm which requires the same number of unlabeled data as RobustCAL in the accuracy from Algo.
non-corrupted setting. Another potential question is that, the O +
Cusa
in the general corruption case is generally worse than O ( Rt Cueal " accuracy of passive learning.
Although we state that these two bounds are close in many cases, question is if there exists an alternative algorithm or analysis that will result a more smooth final bound interpolate between different corruptions cases.
Finally, believe it is possible 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. 20100's idea. We plan to work on this direction in the future.
Acknowledgements
SSD gratefully acknowledges funding from NSF Award's IIS-1100170 and 2M3-2134106
References
Steve Hanneke. Theory of Disagreement-Baseed Active Learning.
Foundations and
Trends@ in Machine Learning 7(2-3)1311-399 2014. ISSN 1935-8237, 1935-
8245. doi: 10.1561/2200000037. URL http://www hwtp::.wwwubllsshe...... com/ articles/ foundations and- trends- in machine Lea.aann-eaaaang/AL---033333
Ajay J. Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference Computer Vision and Puttern Recognition, pages 2372-2379, 2009,
doi: 10. 10..//CV..2009.2206666
Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, (13(2)113-122)) 2015.
William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9368 9377, 2018.
Brad Miller, Alex Kantchelian, Sadia Afroz, Rekha Bachwani. Edwin Dauber, Ling Huang, Michael Carl Tschantz, Anthony D Joseph, and Doug Tygar. Adversarial active learning. In Proceedings of the 2014 Workshop on Artificial Intelligent and Security Workshop, pages 3-14, 2014.
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 449-458, 2014.
Dan Hendrycks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel. Using trusted data to train deep networks on labels corrupted by severe noise. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 10477-10486, 2018.
Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 7164-7173. PMLR, 09-15 Jun 2019. URL httptt::pp//pccccinngi mlr. wwwpp/eee///// http:/9999yy99999011 httpyyullbbbbb html
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 467-475. PMLR, 2019.
10

---

Chen- Yu Wei, Haipeng Luo, and Alekh Agarwal. Taking a hint: How to leverage loss predictors in contextual bandits?, 2020.
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust explo- ration in episodic reinforcement learning, 2020.
Yifang Chen, Simon S. Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning, 2021a.
Chen-Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning, 2021.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89 2009.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20:353-360, 2007.
Burr Settles. From theories to queries: Active learning in practice. Active Learning and Experi- mental Design workshop In conjunction with AISTATS 2010, pages 1-18, 2011.
Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement-basse agnostic active learning. Advances in Neural Information Processing Systems, 27:442 2014.
Vladimir Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. The Journal of Machine Learning Research, 1 11:2457-2499 2010.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference on Computational Learning Theory, pages 35-50. Springer, 2007.
Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log- concave distributions. In Conference Learning Theory, pages 288-316, 2013.
Tzu-Kuo Huang, Alekh Agarwal, Daniel Hsu, John Langford, and Robert Schapire. Efficient and parsimonious agnostic active learning. In Advances in Neural Information Processing Systems, pages 2755-2763, 2015.
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.
Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. In Advances in neural information processing systems, pages 199-207, 2010.
Daniel Joseph Hsu. Algorithms for active learning. PhD thesis, UC San Diego, 2010.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference Machine Learning, pages 1924- PMLR, 2017.
Yue Deng, KaWai Chen, Yilin Shen, and Hongxia Jin. Adversarial active learning for sequences labeling and generation. In IJCAI, pages 4012-4018, 2018.
Lei Pi, Zhuo Lu, Yalin Sagduyu, and Su Chen. Defending active learning against adversarial inputs in automated document classification. In 2016 IEEE Global Conference Signal and Information Processing (GlobalSIP), pages 257-261. IEEE, 2016.
Ashish Khetan and Sewoong Oh. Achieving budget-optimality with adaptive schemes in crowd- sourcing. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4851-4859, 2016.
Liu Yang. Active learning with drifting distribution. In NIPS, pages 2079-2087. Citeseer, 2011.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-266 2012.

---

Steve Hanneke and Liu Yang. Toward a general theory of online selective sampling: Trading off mistakes and queries. In International Conference on Artificial Intelligence and Statisties, pages 3997-4005. PMLR, 2021.
Yining Chen, Haipeng Luo, Tengyu Ma, and Chicheng Zhang. Active online learning with hidden shifting domains. In International Conference on Artificial Intelligence and Statistics, pages 2053-2061. PMLR, 2021b.
Piyush Rai, Avishek Saha, Hal Daumé III, and Suresh Venkatasubraamanian. Domain adaptation meets active learning. In Proceedings of the NAACL HLT 2010 Workshop on Active Learning for Natural Language Processing, pages 27-32, 2010.
Eric Zhao, Anqi Liu, Animashree Anandkumar, and Yisong Yue. Active learning under label shift. In International Conference on Artificial Intelligence and Statistics, pages 112-3420. PMLR, 2021.
Chung-Was Meing-Weilln Lee, Haipeng I Luo, Chen-Ye Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and minimax--pptimlle in stochastic and adversarial linear bandits simultaneously, 2021.
Romain Camilleri, Julian Katz-Samucls and Kevin Jamieson. High-dimensional experimental design and kernel bandits, 2021.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distribu- tions: A survey. Foundations of Computational Mathematics, 19(5):1 145-145-1111 1990 2019.
12


Reviews:
[{"review_id": "p1bCnl_TEl", "reviewer": "Reviewer_EcVJ", "summary": "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper discusses an interesting problem in an interesting framework. Active learning, as well as robustness guarantees are sought for in many situations for classification and the content of this paper lies at the intersection of these two fields.\n\nI have not seen the proofs in detail. However, to me there are a few things that are a little bit unclear even at a higher level. For example, the authors cite 3 papers about RobustCAL, but it appears that the name comes from the most recent citation and it is a bit unclear if all the details are the same across all three references.\n\nAs another example, I would expect a little bit broader description of the results that are related to corrupted labels. For example, the first paper that comes to one's mind is \"Learning From Noisy Examples\", by Angluin and Laird with constant misclassification rate, and another one is Sloan's \"Four types of noise in data for PAC learning\" which discusses malicious misclassification. None of these two papers is cited and I believe they should -- even if they discuss results in the non-agnostic case. Then one can make the jump to the agnostic case and cite and compare related literature and finally discuss everything in the context of the paper where active learning is also taken into account. \n\nAnother issue that the paper has is that the papers are not listed in alphabetical order and this makes it hard to find the paper one is looking for.\n\nFor the claim in lines 38-40, which is the appropriate reference?\n\nMissing the reference (and a brief discussion) on the original CAL algorithm/paper in the related work section.\n\n- line 152: is the upper bound by epsilon, an assumption of the misspecification model?\n- Algorithm 1, line 7: the equality is perhaps set membership?\n- Algorithm 1, line 12: what is $\\hat{h}_{t+1}$?\n\nI would also like to see more discussion of the proposed algorithm (CALruption) on the main text and get more explanations on the actual operations that take place in the various lines of the pseudocode. Similarly, I think the paper would also benefit if one could state simple versions of the bounds, in terms of label complexity. For example, the label complexity in line 244 (Corollary 5.1) seems quite daunting to someone who reads the paper for the first time.\n\nSome typos:\n- l 136: extend -> extended\n- l 143: game -> label?\n- l 157, equation: X -> x (lowercase in the subscript of the numerator)\n- l 161: Is $\\hat{R}_{[1, n]}$ defined somewhere?\n- l 203: In the Section -> In Section\n- l 220: hypothesis -> hypotheses (both occurrences on that line)\n\nOverall, I think the paper should be above the acceptance threshold, but I would like to see some responses on the above.\n\n============================================================\n\nI am happy with the different points that have been raised in the reviews and the responses that we have received. Therefore, I am maintaining my recommendation for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could be more explicit with a paragraph dedicated for this purpose to explain the limitations of the algorithm. For example, while the statistical question is resolved in a nice way, nevertheless, the algorithm does not appear to be computationally efficient. So, this is one example of the limitations that could be discussed. Also, one can compare further the label complexity between RobustCAL and CALruption.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "hiEyJfmgAO", "reviewer": "Reviewer_Ev2r", "summary": "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)$.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n### Main Review\n- Strengths of this work: \n1. Extends previous approaches on robust active learning to the agnostic streaming setting, when there is not a priori information on the corruption size.\n2. Shows why known approaches fail in this setting.\n3. Suggest a new approach for this setting that in several cases is optimal.\n\n- Weaknesses:   \n1. The algorithm is much more complicated and less intuitive than RobustCAL.\n2. The difference between $R^* C/n$ and $C/n$ seems a large gap.\n\n\n### Other comments: \n- The paper is well organized and well written except pages 6-7 (and Appendix) which are the main contributions, which also hold for the respective section in the appendix (section D). \n- I would suggest the authors rephrase/clean algorithm 2 to make it easier to parse.\n- This section is notation-heavy and the authors fail to explain the use of each symbol. In order to understand several parts/notations, I needed to check the proofs in Appendix. \n- Appendix is full of typos and difficult to read. \n- I suggest the authors provide a full proof in the appendix and provide an intuition for the algorithm and the proof.\nSome Typos: \n- In label complexity: $|H|^2$ should be $|H|$ because of $O$.\n- Line 178: at least*\n- 157: h should be $h^\\ast$ and \"and.\" \n-  Typos in Appendix (including not limited to): Lines: 532, 558-559, 562-563,566-567,570,575-576,624.\n- Some inequalities need justification.\n\nI suggest the authors improve the clarity of this work in the camera-ready version (and in the full version of this work). For instance, I cannot understand why in some lemma statements the authors prove inequalities instead of doing it in the proof, e.g., Lemma C1. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work and has no negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "8Chm437xTp3", "reviewer": "Reviewer_yion", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work improves our understanding of the impact of corruption in active learning. While intuitative, it provides machinery for understanding the importance of the timing of the corruption during the learning process. \n\nAs pointed out by the authors, the proposed algorithm requires significantly more unlabeled samples. While it is often assumed that unlabeled data are cheap and/or easily obtained, this is not always the case. \n\nOverall the paper is well written and clear. The only real criticism I have is that the result is of middling impact. By improving our understanding of robust active learning, the authors make a step toward better learning algorithms, but do not create fundamentally new capabilities. Thus, the impact is not low, but neither is it high.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address limitations of unlabeled sample complexity and other weak points of the proposed algorithm.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5iHOl8CbsjF", "reviewer": "Reviewer_mLmE", "summary": "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. \n\nIt 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. \n\nTo 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).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers an interesting setting where the noise condition is harder than what existing active learning papers studied. Its results are new and nontrivial. I briefly went over its proofs and they look sound to me. However, this paper in its current shape is a bit premature to me, and I'm not sure if its quality is good enough for NeurIPS.\n\nMain concerns:\n- Clarity.\n  - The main algorithm, Algorithm 2, is not very well explained. The high level explanations before Theorem 5.1 are nice, but it would be better if you can provide some explanation and *intuition* of detailed designs (if page limit is a problem, putting them in Appendix would still be helpful). For example:\n    - how is the robust estimator constructed? What's the intuition behind the equation?\n    - lines 9~13 in Algorithm 2 are quite hard to parse. Could you explain what these variables stand for? What are the rationale behind the chosen values? \n    - If there is no corruption or under the mispecification case, is there any connection between Algorithm 2 and existing active learning algorithms with importance reweighting like [Beygelzimer et al 2010, Huang et al 2015] in your reference?\n  - There are a lot of notations. It would be clearer if you can have a list of notations, even just in Appendix.\n- Setup & results\n  - The characterization of corruption level $C_{total}$ looks quite loose. One extreme example is that this quantity can be large even if the adversarial only corrupts the labels on a zero-measure set. It would make more sense if this measure takes the distribution of P(X) into account.\n  - This is a relatively new setting, it would help understand the hardness of the problem and optimality of the proposed methods if you could show some lower bounds (even just for passive learning).\n  - This paper only considers *oblivious* adversary model where the adversary has to decide its corrupted distribution beforehand. This looks a bit weak. What's the main obstacle to work against that?\n\nMinor issues:\n- It might be worth citing [1] though it only works under the mispecification case for linear separators.\n- It would be clearer if you could provide some simple examples to show how traditional active learning algorithm fails with adversarial corruption.\n- Algorithm 2 has a worse label complexity than modified CAL under low corruption.\n- Disagreement coefficients are often not a constant (for example it can be O(\\sqrt{d}) for linear classifiers with log-concave distributions).\n\nA technical question:\nAt a glance, the guarantee for the robust estimator (Lemma D.2) is quite similar to what one typically gets with naive importance sampling. Could you state why importance sampling does not work for your use case?\n\n[1] Awasthi, Pranjal, Maria Florina Balcan, and Philip M. Long. \"The power of localization for efficiently learning linear separators with noise.\" Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies active learning under label corruptions and presents a robust version of the classical CAL algorithm. All the reviewers agreed that the paper studies an interesting direction and presents good theoretical results. While the results in the paper do not present a complete picture of the problem setting, there is enough technical novelty to make the paper slightly above the bar for publication. The authors are encourage to carefully take into account the reviewers' comments when preparing the final version.
Decision: Accept (Poster)