Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness
Authors: Avrim Blum
Omar Montasser
Greg Shakhnarovich
Hongyang Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: boosting
adversarial robustness
sample complexity
oracle complexity

Abstract: We present an oracle-efficient algorithm for boosting the adversarial robustness of barely robust learners. Barely robust learning algorithms learn predictors that are adversarially robust only on a small fraction $\beta \ll 1$ of the data distribution. Our proposed notion of barely robust learning requires robustness with respect to a ``larger'' perturbation set; which we show is necessary for strongly robust learning, and that weaker relaxations are not sufficient for strongly robust learning. Our results reveal a qualitative and quantitative equivalence between two seemingly unrelated problems: strongly robust learning and barely robust learning.

Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness
Avrim Blum avrimOttic. edu TTI Chicago
Omar Montasser omar@ttic.edt edu TTI Chicago
Greg Shakhnarovich greg@ttic. .dd TTI Chicago
Hongyang Zhang first. last@usateereerec
University of Waterloo
Abstract
We present oracle-efficient algorithm for boosting the adversarial robustness of barely robust learners. Barely robust learning algorithms learn predictors that are adversarially robust only Our proposed notion of barely robust learning requires robustness with respect to a "larger" perturbation set; which we show is necessary for strongly robust learning, and that weaker relaxations are not sufficient for strongly robust learning. Our results reveal a qualitative and quantitative equivalence between two seemingly unrelated problems: strongly robust learning and barely robust learning.
small fraction < of the data distribution.
Introduction
We consider the problem of learning predictors that are robust to adversarial examples at test time. That is, we would like be robust against a perturbation set U X' - 2 where U(x) C X the set of allowed perturbations that an adversary might replace x with, e.g., U could be perturbations of bounded p--ormss [10]. The goal learn predictor with small robust risk:
(h; D)
A
Pr (aaai)~
[3 U((x) h(=) +
Adversarially robust learning has proven be quite challenging in practice, where current adversarial learning methods typically learn predictors with low natural error but robust only on a small fraction of the data. For example, according to the RobustBench Ieaderboard [7], the highest achieved robust accuracy with respect to l perturbations on CIFARIO is Rs 66% and on ImageNet is s 38%. Can leverage existing methods and go beyond their limits? This motivates us pursue the idea of boosting robustness, and study the following theoretical question:
Can boost barely robust learning algorithms to learn predictors with high robust accuracy?
That is, given a barely robust learning algorithm which can only learn predictors robust on say 10% fraction of the data distribution, we asking whether it is possible to boost the robustness of and learn predictors with high robust accuracy, say 90%. We want to emphasize that we are interested here in extreme situations when the robustness parameter < 1. We interested in generic boosting algorithms that take as input a black-bor box learner A and specification of the perturbation set U. and output predictor with high robust accuracy by repeatedly calling A.
In this work, by studying the question above, we offer a new perspective on adversarial robustness. Specifically, we discover qualitative and quantitative equivalence between two seemingly unrelated problems: strongly robust learning and barely robust learning. We show that barely robust learning implies strongly robust learning through novel algorithm for boosting robustness. As we elaborate below, our proposed notion barely robust learning requires robustness with respect to a "larger" perturbation set. We also show that this is necessary for strongly robust learning, and that weaker relaxations of barely robust learning do not imply strongly robust learning.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Main contributions
When formally studying the problem of boosting robustness, an important question emerges which is: what notion of "barely robust" learning is required for boosting robustness? As we shall show, this is not immediately obvious. One of the main contributions of this work is the following key definition of barely robust learners:
Definition (Barely Robust Learner). Learner A (3, c, ()
a concept X + Y w.r.. (2) if (8,c,) E N s.t. for any distribution D over X s.t. PrzDD [3 E u(x)) : c(z) * c(x)] = O, with prob. at least 1 1 over = {(x,, dz)))) ~ De
and any internal randomness in the learner, A outputs predictor h (S) satisfying:
Pr 2nD
Vi EE M(0) = -(x)] 2 3 and Pr m>D
[(x) + dx)] cc.
Notice that we require 8-robustness with respect to a "larger" perturbation set sst441244 (2)). Specifically, (z))() is the set of all natural examples è that share an adversarial perturbation with (see Equation 2). R.g., if (I) is an b,-ball with radius y, then (4)(()) ) is an Ey-ball with radius 2y.
On the other hand, (e, -oassssllyyyln a concept with respect to U is concerned with learning predictor h from samples S with small robust risk (h; D.) with probability at least 1 over S ~ D (see Equation! 1 and Definition 2), where we are interested in robustness with respect to U1 and not (2)). Despite this qualitative difference between barely robust learning and strongly robust learning, we provably show next that they are in fact equivalent.
Our main algorithmic result is 3-RoBoost, oracle-efficiett boosting algorithm that boosts barely robust learners to strongly robust learners:
Theorem 1. For any perturbation set U, 3-RoBoost (e, -obustiyiyyy any target concept c : X' + y w.r.t U using T = B
Im(2/e) black-box oracle calls to any (3, 8r 8 -bbrrely-roobust learner A.
T TT
for e w.r.. l (U),. with sample complexity 4T'm, where m& is the sample complexity of learner A.
The result above shows that barely robust learning is sufficient for strongly robust learning. An important question remains, however: our proposed notion of barely robust learning necessary for strongly robust learning? In particular, our proposed notion of barely robust learning requires 3-robustness with respect to a "larger" perturbation set 22 (24), instead of the actual perturbation set U that we care about. We provably show next that this is necessary.
Theorem 4. For any Ut learner B. and e E (0, 1/4), if B (e, 8) robustly-leaaee some unknown target concept e w.r.t. U, then there is a learner B that (-- 2e, bare-aaall---bbulllleeeee e w.r.t. (M).
This still does not rule out the possibility that boosting robustness is possible even with the weaker requirement of 3-robustness with respect to U. But we show next that, indeed, barely robust learning with respect to L is not sufficient for strongly robust learning with respect to U::
Theorem 6. There is a space X, perturbation set U, and a class of concepts C s.t. is (B = 2,6 = 0, b--bbareyyrobuutty-leeene
w.r.t U, but C is not (e, probustly-eaarnale w.r.t. U for any < 1/2.
Our results offer a new perspective on ad adversarially robust learning. We show that two seemingly unrelated problems: barely robust learning w.r.t. 24 (24) and strongly robust learning w.r.t. U, are in fact equivalent. The following corollary follows from Theorem and Theorem 4.
Corollary I. For any class C and any perturbation set U, C strongly robustly learnable with respect to U if and only if is barely robustly learnable with respect to U (U))
We would like to note that having a separate robustness parameter B3 and a natural error parameter e allows us to consider regimes where B < 2 and e is small. This models typical scenarios in practice where learning algorithms are able to learn predictors with reasonably low natural error but the predictors are only barely robust. More generally, this allows us to explore the relationship between 33 and in terms of boosting robustness (see Section 5 for a more elaborate discussion).
Landscape of boosting robustness. Our results reveal an interesting landscape for boosting ro- bustness when put in context of prior work. When the robustness parameter 2. it is known from prior work that 3-robustness with respect to U suffices for boosting robustness [sce e.g., 15, 1], which
2

---

is witnessed by the a-Boost algorithm [18]. When the robustness parameter 3 S 2 our results show that boosting is still possible, but 3-robustness with respect to (44) is necessary and we cannot boost robustness with β-robustness with respect to U.
1
In fact, by combining our algorithm 3-RoBoost with a-Boost, we obtain an even stronger boosting result that only requires barely robust learners with a natural error parameter that does not scale with the targeted robust error. Beyond that, our results imply that we can even boost robustness with (24). This is summarized in the following corollary which follows from Theorem 1,
respect to 2-1 (24). Lemma 8, and Theorem 4.
Corollary II (Landscape of Boosting Robustness). Let C be class of concepts. For fixed Eq, 60 (g. 3) and any target c < 6o and 8 > 5g:
1. IfC is (3, Sen 860
barrey--oobstt--leammbbe w.r.t. (4)), then C is (co, robuussy 2 ln/2/ca)
learnable w.r.l U.
2. IfC is (Eo, bobstrrbustt-llaaruuble w.r.t. U, then C is (e, (robbussyy learnable w.r.t. U.
3. C is (c, o-robussly learnable w.r.t. U, then C is (² 2e, baeebbrrr
w.r.f. 4 (11).
In particular, 1 1 2 = 3 revealls that we can also algorithmically boost robustness w.E.t. U (2))
Boosting robustness with unlabeled data. In Appendix A and Theorem 7, we show that variant of our boosting algorithm, B-URoBoost, can boost robustness using unlabeled data when having access barely robust learner A that is tolerant to small noise in the labels. In Appendix E, we discuss an idea of obtaining robustness at different levels of granularity through our boosting learn predictor h with different robustness levels: 7: 3: 2 ...... in different regions of the distribution.
algorithm. Specifically, when 2/ (ar) is metric-ball around with radius 7,
1.2 Related work
To put our work in context, the classic and pioneering works of [12, 17, 8, boosting the accuracy of weak learning algorithms, from accuracy slightly better than å to arbitrarily high accuracy in the realizable PAC learning setting. Later works have explored boosting the accuracy in the agnostic PAC setting [see e.g., 11].
9] explored the question of
In this work, we are interested in the problem of boosting robustness rather than accuracy. Specifically, boosting robustness of leamerr A that are highly accurate on natural examples drawn from the data distribution, but robust only on some 3 fraction of them. We consider this problem in the robust realizable setting, that is, when the unknown target concept has zero robust risk Rer(c; Da) = O. For example, with linear classifiers and l2 perturbations, robust realizability equivalent to linear separability with margin, which is setting that is studied extensively in the literature. Furthermore, for vision datasets in practice (c.g., CIFAR 10 and ImageNet), it has been observed that the classes can be robustly separated with some negligglie distance, indicating that robust classifiers for these datasets do exist, i.e., the robust realizability assumption holds [see Section 3 in 19].
1 We know from prior work [see e.g., 15, 1, 20] that if the robustness parameter 3 > 2. then barely robust learning w.r.t. implies strongly robust learning w.r.t. 2. In this case, we essentially have weak learners w.r.t. the robust risk Riz, and the original boosting algorithms such as the a-Boost algorithm [18, Section 6.4.2] can boost the robust risk. In this work, we focus on boosting barely robust learners, i.e., mainly when the robustness parameter 3 < 1/2, but our algorithm works for any < 3 < 1.
[15] studied the problem of adversarially robust learning (as in Definition 2). They showed that if a hypothesis class C is PAC learnable non-robustly (i.e., C has finite VC dimension), then C is adversarially robustly learnable. This result, however, is not constructive and the robust learning algorithm given does not directly use a black-box non-robust learner. Later on, [16] studied a more constructive version of the same question: reducing strongly robust learning to non-robust PAC learning when given access to black-box non-robust PAC learners. This different from the question we study in this work. In particular, we explore the relationship between strongly robust learning and barely robust learning, and we present boosting algorithm for learners that already have some non-trivial robustness guarantee 3 0.
3

---

2 Preliminaries
Let X denote the instance space and y denote the label space. We would like to be robust with respect to a perturbation set U X' + 2*, where U(x) S X' is the set of allowed adversarial perturbations that adversary might replace with at test time. Denote by 2 the inverse image {I X' :2 U(z)). Observe that for any x, E X it holds that 2 E U(x) + x U (2). Furthermore, when U is symmetric, where for any I, E X, z E U(x) & E (2). it holds that U = -4-1 For each z E X, denote by 1- (2) the set of all natural examples ã that share some adversarial perturbation Z with x; i.e.
of U4 where for each 2 E X, 4 (2)
u (4) = ( (x) (a: 72 E ((x)) (2)
(2)
For example, when (xx) = (x) = f2 E: p(x, S > where Y > and p is some metric on (x)
X' (e.g.. bp- bp-balls), then (4) = (z). For any classifier h X - y and any U, denote by (obu(h) the robust region of h with respect to u defined as:
(h) fx E X: V2 E E(()), = M(x))
(3)
Definition 2 (Strongly Robust Learner). Learner B (e, bo-uslsstly--a concept : X - y with respect to if there exists m(c,6) E N s.t. for any distribution over X satisfying PraND [Ez U(z) c(2) c(z)] 0, with probability at least 1 5 over S = {(x, c(x:)))
Do. IB outputs a predictor h = (SS) satisfying:
Rh D.) Pr
3 u((x) h(=) + c(w) sc. D~D
3 Boosting barely robust Learner to a strongly robust learner
We present our main result in this section: 3-RoBoost an algorithm for boosting the robustness of burely robust learners. Specifically, in Theorem 1, we show that given burely robust learner A for some unknown target concept e (according to Definition I), it is possible to strongly robustly learn e with 8-RoBoost by making black-box oracle calls to A.
Algorithm 1: 3 3-RoBoost - Boosting barely robust learners.
Input: Sampling oracle for distribution De. black-box box (3, e, 8) bbreeleyy-oobust learner A.
Set T ln(2/e) and m max { mm (3, 2 A 4 }
3
2 while s do
Call RejectionSamp on his.... h- and m, and let S, be the returned dataset.
4
S + 0, then call learner A on S, and let h = AS,)) be its output. Otherwise, break.
Output: The cascade predictor defined as
& (2) where min {1 < t T Gh. (2) } and [y, if (3a y) (Vī u (z)) h(ā) y; Gz) [1 otherwise.
selective classifiers
s RejectionSampling (predictors hi,.... his and sample size m)) for 1 S i S m do Draw samples (I, ~ D until sampling an (Ii, M4) s.t.: Ve Ghy (2) =L. // eampling from the region of D vhere atl predictore ha...., he are not robust. If this costs more than samples from abort and return an empty dataset Š = 0. // If the wass of the non-robust regien is small, then we can safely terninate. Output dataset š = ((11,1)),...... (Fms }m
9
Theorem 1. For any perturbation set U, 3-RoBoost (e, -obusttll-yss any target concept c w.r.t. U using T =
in(2/e) black-box oracle calls to any (3, 2 2r
Be
6. hharely-robuss learner A for
w.t.. 4 '(4), with total sample complexity
4T max { (3,, Be 5
27 4. ),,
2T
m(c. 8)
e

---

with fixed error 6o S and confidence do = 6lu(6]- This is established by combining two boosting algorithms: B-RoBoost from Theorem and a-Boost from earlier work [see e.g., 15, 18] which is presented in Appendix B for convenience. The main idea is to perform two layers of boosting. In the first layer, we use 3-RoBoost to get a (3. ( --robust-eearner w.r.t. 2 from a (3, ED. du) -barely- robust-learner A w.r.t. (2). Then, in the second layer, we use a-Boost boost 3-RoBoost from a (3+ ( >rrobust-eearner to an (c, (c,5)-ro (0--)))ost--eeamee w.r.t. U.
In fact, we present next an even stronger result for boosting co, 3
Corollary 2 (Stronger Boosting Guarantee). For any perturbation set U. a-Boost com- bined with B-RoBoost (c, (c.8)-robustly-larr any target concept e. w.r.t. U usiing T = (log(m) (10g(1/6) + log log m))- black-box oracle calls any (3, 6 6lm(6) -bareyy--arly learner for w.r.t. (U), with total sample complexity
B
m(c, 0) =0
ma Bc
log²
111
log(1/0)
c
8 6 ml) ) 4 In (6ln(() where mo max mA (3,
}}-
We begin with describing the intuition behind 3-RoBoost, and then we will prove Theorem 1. The proof of Corollary 2 is deferred to Appendix B.
High-level strategy. Let D. be the unknown distribution want to robustly learn. Since A is barely robust learner for c, calling learner A on an i.i.d. sample S from D. will return a predictor hi, where h1 is robust only on region Ri S. X' of small mass 8 0 under distribution D, Præ~D x+ E R1] 2 3. We can trust the predictions of h1 in the region R2 but not in the complement region R3 where it not robust. For this reason, we will use a selective classifier Gb, (see Equation 4) which makes predictions on all adversarial perturbations in region R1, but abstains on adversarial perturbations not from R1. In each round t 1, the strategy to focus on the region of distribution D where all predictors h....., 1 returned by A. so far are not robust. By rejection sampling, 3- RoBoost gives barely robust learner A sample Sy from this non-robust region, and then A returns a predictor he with robustness at least 8 in this region. Thus, in each round, we shrink by a factor of 3 the mass of region D where the predictors learned so far are not robust. After T rounds, BoRottts outputs a cascade of selective classifiers Gaj..... Gny where roughly each selective classifier Gh, is responsible for making predictions in the region where he is robust.
As mentioned above. one of the main components in our boosting algorithm selective classifiers that essentially abstain from predicting in the region where they are not robust. Formally, for any classifier h: -> y and any U1 denote by G₁, X + YuR {1} selective classifier defined as:
V/ L1,
if (Ey E )) (4Y E 21 (z)) h(ā) y;
Gn()))
otherwise.
Before proceeding with the proof of Theorem 1, we prove the following key Lemma about selective classifier Gn which states that G2, will not abstain in the region where is robust, and whenever G predicts a label for a perturbation 2 then we are guaranteed that this is the same label that h predicts on the corresponding natural example x where: Z E U(z).
Lemma 3. For any distribution D over X. any U, and any B > O, given classifier h h: X + y
satisfying Præ-n [x E (oby-ruy 2 3, then the selective classifier Gn : X + y {1} (see
Equation 4) satisfies:
Pr (V2 E u(()) Gn(z) h(x)) 2 B and Pr V22 E U(x): Gn(z) = h(x) V G = a>D
= = 1.
a>D
Proof. Observe that, by the definition of the robust region of h w.r.t. (2) (see Equation 3), for
any x E Roby-rqu)h)) (h) the following holds:(Vz E (xx)) (vā E u=)) h(t) h(x). By the
definition of the selective classifier Gr, (see Equation 4), this implies that: V2 ((x)) Gx(=) = h(x).
Since Prz-D [a E Roby ((n)()) 2 3, the above implies Prz-D Vv2 E (4()) Gx(()) = h(x))] 2 3. Furthermore, for any E X and any E (ax), by definition of 4-_ x E (=)) Thus, by definition of Gn, (see Equation 4), (2) = y for some y E V, then it holds that h(x)) = y. Altogether, this implies that Pr VZ E (x)) Gx(22) h(z) V Gz( =1]= =1.
5

---

We are now ready to proceed with the proof of Theorem 1.
Proof of Theorem I. Let U be an arbitrary adversary, and A a (3,c, c. bj-barely-robust learner for some unknown target concept : X' - 3/ with respect to (24). We will show that 3-RoBoost (c. (..0))obbstlyy-aan c with respect to 24 Let D be some unknown distribution over X' such that Pra-D [3z (xx)= c(=) & c(x) = 0. Let > be our target robust error, and e' be the error guarantee of learner A (which we will set later be )
Without loss of generality, suppose that 8-RoBoost ran for T = In(2/c) rounds (Step 4 takes care of the scenario where progress is made faster). Let h1 = A(S)). ....).....h. hr A(Sr) be the predictors returned by learner A rounds 1 S t S T. For any S t S T and any E X, denote by R₁ the event that x E Roby 1:20 (he), and by Rg the event that x & Roby -00 (h+) (as defined in Equation 3). Observe that by properties of A. (see Definition 1), we guaranteed that
Pr [1x(1r) + c()) S VISIST: Pr [R..] 2 3 and BwD, z-D.
(5)
where Dr is the distribution from which Se drawn. words, distribution Dr is a conditional distribution focusing on the region of distribution D where all predictors .i.....hu h4-1 are non- robust. Specifically, for any x D, in case R1 U... R (i.e., there a predictor among 11....,h4-11 that is robust on x)), then Lemma 3 guarantees that one of the selective classifiers Gby..... .G.,, will not abstain on any E U(x): Et' S t 1, E (1x)), (2) #1. In case x R2 n.... R then, by definition of Ri..... Ri-1, each of the selective classifiers Gby..... ,Gh, can be forced to abstain: A < ( 1, E U(xr), Gn, (z) =T. Thus, in Step 7 of 3-RoBoost, rejection sampling guarantees that S₁ is sample drawn from distribution D conditioned on the region R1-0-1 A Rı R.... R Formally, distribution De is defined such that for any measurable event E:
Pr D.D.
FE] A
Pr [F]R O R
RND
Low error on natural examples. Lemma 3 guarantees that whenever any of the selective classifiers Ghy...., Gby (see Equation 4) chooses to classify an instance at test-time their prediction will be correct with high probability. We consider two cases. First, in case of event RG, x E Roby- (hz). and therefore, by Lemma 3, V2 E U(x)) Gn, = hx()). Thus, Equation 6 implies that V1 < t S T:
Pr RR (3x E(()): : (Gn, #1) A (G),(=) c(x))) [Ba-1]] r>D
= Pr R A A2 (()): (G), *1) A (Gn, (=) c(x)))
D>D,
Pr [R, (h+(x) # cx))).
anD,
Second, in case of the complement event Re & (hg Therefore, by Lemma 3, Vz E U(x), we have Gh, =1 or (z) = h,(x). Thus,
Pr R2 A (3x EU()) (G), #1) (G),()) + c(x))) [1a-1]
= Pr [R, (32 E ((x): : (=), (L) A (Gn
& c(x))) S PP. [Re A (lr(2) + c()))
z>Di
(8)
By law of total probability Equation 7, Equation 8, and Equation 5,
Pr [RR V RR) A E(()) (Gn, (=) #1) A (Gn, (2) # c(x))) [R1-11]
D
Pr [he(x) # c(x)) <e. (9)
Pr (z) c(x) + Pr hx(z) # c(x)] anDD
DwD)
a>D:
Boosted robustness. We claim that for each 1 < L T PrawD [1x]] < (1 - We proceed by induction on the number of rounds 1 S.ST. In the base case, when 1, Dr and by Equation 5, we have Pr [R]] 2 3 and therefore Prz-D [R]] < 1-11- 1.1.. B.

---

When t >> 1. again by Equation 5, we have that PIæND, [Ra] 2 8 and therefore, by Equation 6,
PraND Re R1:0-1 = Pr we get
[Rg] I - B. Finally, by the inductive hypothesis and Bayes' rule,
Pr anD
Rig
Pr anD
R1
Pr anD
RI: (1- 3)- = (1- (1-10 -)) (10)
Analysis of robust risk. For each 1 S S T. let
A = f R2 3z E ((x) s.t. Gha(s) #1 AV (t),
denote the non-robust region of classifier he where the selective classifier Gt, does not abstain but all selective classifiers G.......,Gr Gh.,,, abstain. By the law of total probability, we can analyze the robust risk of the cascade predictor CAS(hI,..... hr) by partitioning the space into the robust and non-robust regions of
Specifically, by the structure of the cascade predictor CAS(h1:)): each x D such that 32 (2x) where CAS((h:))(a) o c(x) satisfies the following condition:
Bxeu((:) CAS(h1r))))) # dxx) = (3igesT) (Ezeu(s)) Veree (2) =1 AGH, (z) #1 AG (z) # c(x).
Thus, each ~ D such that 32 (xx) where CAS(har))()) # c(x) can be mapped one (or more) of the following regions:
R1 A1
( v A2)
R12 A (Ra V As)
| .... RITTIA V Ar)
| RITT-
Gh₁ does not abstain
Ciug
Gby does nat abstain
We will now analyze the robust risk based on the above decomposition:
Pr B E u(x): (2) # c(x)]
T+1
Pr [R A (Re V A.) A (3 E(()) CAS(Hur) + [c())] anD
T
Pr R A (Re V A) A (3x E : + Pr [RI.]] znD
Pr 1 V A.) A (3 EU()) Gn. (G,, # d(+))] Pr
[
AND
Pr [
Pr ((..VA.) (3x (z) #1 AGM, (2) + clx)) R I]+ Pr [RET]
DND AND
anD
T Σ t=1
6 + (1- = Σ (1-3)) 1- (1- 3) (1-1 + (1 (1-
T
(1-B)*
<
+ (1 -1.
3
(11)
where inequality (i) follows from the definitions of R1.--1, Ra, and A,, and inequality (ii) follows from Equation 10 and Equation remains to choose T and e' such that the robust risk is at most e.
Sample and oracle complexity. It suffices to choose T = In(2/e) the sample complexity. Fix an arbitrary round 1 < t S T. In order to obtain good predictor he from learner A satisfying Equation 5, we need to draw m (,,, Be/2, 6/2l) samples from D.. We do this by drawing samples from the original distribution D and doing rejection sampling. Specifically, (24) }
B and e' <B We next analyze
I
(as defined in Step 1). Then, for each 1 S i S m, let X2,s be a random variable counting the number of samples (x,y) drawn from D until sample (x,, v) R is obtained. Notice that Xx,, is geometric random variable with expectation 1/p. where Pt PrawD [R.c]- Then, the expected number of samples drawn from D in round is By applying a standard concentration inequality for the sums of i.idd. geometric
let m = max ma (3,
2 4 4n
|> X1 na
random variables [4]. we get
m
m Pt.
2mi1 1/212
8
Pr
X >
<
E S
27
7

---

where the last inequality follows from our choice of m. By standard union bound, we get that with probability at least 1 g the total number of samples > Li=1 Xz, 2m
S - 2m
Pc
AmT Ei= Pt
4 The Necessity of barely robust learning
have established in Section 3 (Theorem 1) that our proposed notion of barely robust learning in Definition suffices for strongly robust learning. But is our notion actually necessary for strongly robust learning? In particular, notice that in our proposed notion of barely robust learning in Definition we require 3-robustness with respect to a "larger" perturbation set 21 (24, instead of the actual perturbation set L/ that we care about. Is this necessary? or can we perhaps boost robustness even with the weaker guarantee of 3-robustness with respect L/?
We
In this section, we answer this question in the negative. First, we provably show in Theorem 4 that strongly robust learning with respect to // implies barely robust learning with respect (2). This indicates that our proposed notion of barely robust learning with respect to U (44(4) (Definition 1) is necessary for strongly robust learning with respect to U. Second, we provably show in Theorem that barely robust learning with respect to U does not imply strongly robust learning with respect to U when the robustness parameter 3 S 1/ which is the main regime of interest that we study in this work.
Theorem 4. For any U, learner B. and c E (0, 1/4), B (c, 6) -robussyy learns some unknown target concept e w.r.l. U, then there learner B that ( 2e, 28) bur-srely-rrussll--eerrrr e w.r.I. U (1)).
We defer the proof of Theorem 4 to Appendix C, but we briefly describe the high-level strategy here. The main idea is to convert strongly robust learner IR with respect to U to barely robust learner IB with respect to 2 (4-1)24), (27). We do this with a simple expansion trick that modifies a predictor h robust with respect to 2/ to predictor g robust with respect to 44 (24). For each label y E V, we do this expansion conditional on the label to get a predictor Jy that is robust w.r.t. 4-1(24) (2() but only in the region of X' where l predicts the label y robustly w.r.t. U. This is described in the following key Lemma. We then use fresh samples to select predictor a 9, whose label y occurs more often.
Lemma 5. For any distribution D over X and any concept C X + {+1}, given a predictor h X - {+1} such that Ru (hx;; De) S e for some e E (0, then for each y E {+1], the predictor 9y defined for each E X as
(x) e y iff (u)) satisfies
RERobu (b)A
Pr (0)(z) + c(x)) < 2c and Pr [ E Roby- (o,) 2 (1-c) Pr anD
[Ma)) = y/ E Robu (h) anD
znD
As mentioned earlier, Theorem still leaves open the question of whether the weaker requirement of barely robust learning with respect to U suffices for strongly robust learning with respect to U. We show next that this weaker requirement is not sufficient.
Theorem 6. There is an instance space X. a perturbation set U, and a class such that C is (B = f, O, 0, baarey--obustly-learnce with respect to U for any e < 1/2.
with respect to U, but C is not (e, rrousll)-bulll
We defer the proof of Theorem 6 Appendix D, but briefly sketch the high-level argument here. To show this impossibility result, we construct a collection of distributions that is barely robustly learnable w.r.t. t with robustness parameter 33 1/2 and natural error e 0 using a randomized predictor. We also show that it is not possible to robustly learn this collection with robust risk strictly smaller than J.- The second part is shown by relying on necessary condition for strongly robust learning proposed by [15] which is the finiteness of the robust shattering dimension.
5 Discussion
In this paper, we put forward theory for boosting adversarial robustness. We discuss below practical implications and outstanding directions that remain to be addressed.
8

---

Practical implications. Our algorithm 3-RoBoost is generic and can be used with any blx barely robust learner A. In the context of deep learning and E robustness, our results suggest the following: for targeted robustness of radius y, use an adversarial learning method [e.g.. 13, 21, 6] to learn neural net huy predictor robust with radius 2%, then filter the training examples to include only the ones on which IN is not robust with radius 27, and repeat the training process on the filtered examples to learn a second neural net, and so on. Finally, use the cascade of neural nets CA ...) defined in 8-RoBoost to predict.
would be interesting to empirically explore whether adversarial learning methods [e.g.. 13, 21, 6] satisfy the barely robust learning condition: on each round of boosting, the learning algorithm can shrink the fraction of the training examples on which the predictor from the previous round is not robust on. This is crucial for progress.
Multiclass. We would like to emphasize that our theory for boosting barely robust learners extends seamlessly to multiclass learning problems. In particular, when the label space [ > 2. obtain the same guarantees in Theorem using the same algorithm 3 R-ooBoost. The other direction of converting an (e, rrobtttruseee with respect U/ to an (3, 2e, 28) ---brely-robus--eaaeeee with respect to 1- (24) also holds, using the same technique in Theorem 4, but now we get ,3 T
Relationship between robustness parameter 3 and error parameter To achieve robust risk most e using a barely robust learner A with robustness parameter 3, our algorithm 3-RoBoost requires A to achieve a natural error of غ = fBea for any constant cy < 1 2 (say غ = $ (see Corollary 2). It would be interesting resolve whether requiring natural risk ? that depends 6
2
/3 is necessary, whether it is possible to avoid dependence on B. Concretely, an open question here is: can we achieve robust risk most using (8, O(e), baarelyrobuut-learee instead of requiring (8, ((3), 5) --barely-robuust learner? It actually suffices to answer the following: given a (3, 3. 6) bb-bbrely-robus--earre
is it possible to achieve robust risk at most ? A related question is whether it is possible to boost the error while maintaining robustness fixed at some level. For example, given (8, 5.4 b--bbrrll--roooo reatt-rerbust A, is it possible to boost this to a (8, e, d) -b-bebelyrrbuss--eeeee
IB?
Agnostic setting. We focused only on boosting robustness in the realizable setting, where the target unknown concept and the unknown distribution D satisfy an equivalence between burely-robust-leande of obtaining stronger guarantees, we remark that an genostic-to-realizee
= 0, and we showed and strongly-robuse reuus-lerrnngg in this setting. In terms reduction described in is equivalent to
[15, Theorem 8]. implies, together with Theorem 1, that parely-robust-leanee agnostic-robust-lernnn The agnostic-to-realizbble reduction in [15] is not oracle-efficient, however, so the interesting open question here is to explore oracle-efficient boosting algorithms in the agnostic setting. A key step in this direction is to identify reasonable definitions of ggnostic-barely-robuss learners that go beyond Definition
Computational efficiency. Our algorithm 3-RoBoost is guaranteed terminate in most T In(2/o) rounds of boosting (see Theorem 1), because our rejection sampling mechanism (Step B
8) will safely terminate when the mass of the non-robust region becomes small (mass at most e/2). In each round t of boosting, rejection sampling (Step 7) in 8-RoBoost needs to sample from the region of the distribution where all previous predictors f,,.... h are non-robust, and doing this computationally efficiently requires an efficient procedure to certify robustness of h; on perturbation set 4 (z) Certifying robustness of predictors is an active area of research [e.g., randomized smoothing with & perturbations in 6]. but is outside the scope of this work, since we make no assumptions on the form of the returned predictors h; or the perturbation sets and (L4). In general, it's hard to imagine a world where efficient robust learning is possible without efficient certification of robustness. In other words, efficient certification of robustness seems to be a "necessary" condition for efficient robust learning, not not just for our proposed boosting algorithm, but for any algorithm that is devised for robust learning. Without efficient certification of robustness, we can't 't even compute the robust loss, so how can we even learn.
Comparing (() vs. As mentioned earlier in the introduction, if is a metric-ball of radius 7, then (2) is metric-ball of radius 2%, More generally, we think of robustness w.r.t. (44) as being robust to "twice" the adversary's 's power (which is represented by U). For example, for
9

---

general vector space X. (z) = z B, where B is some arbitrary symmetric set (i.e. B and only if vv B), then (4) where (4) is much "larger" than 4. but this is an interesting direction to explore. More generally, would interesting to explore whether barely-robustleaming w.r.t. (11) is computationally equivalent to trong-robust-learing w.r.t. U.
+ B. We do not yet know of examples of 2
6 Simple Experiments
We conduct simple experiments that illustrate the utility of our theoretical contribution for boosting robustness. These experiments demonstrate that our algorithm, B-RoBoost, can boost and improve the robustness of black-box learning algorithms. We describe the setup and the results below.
Datasets. A synthetic binary classification dataset (make_moons moons from scikit-learn), and MNIST (rescaled by dividing by 255, and converted to binary classification of odd vs. even).
Perturbation set U. We consider & perturbations of some radius y. In the respective datasets, we computed the minimum distance between examples from different classes and chose radius 7 that's smaller than this minimum distance.
off-the-shelve Linear SVM solver (from scikit-lear) barely-robust-lcareer Using linear predictors and lg perturbations simplifies the computation of the robust loss since it exactly corresponds computing the margin loss [see Lemma 4.2 14]. Formally, for any linear predictor w and example (æ,, y),
Barely Robust Learner. We
sup [ssin((( (w,, x + 6)) # y) II y/
S
w
We ran our boosting algorithm, 3-RoBoost, and compared it against the baseline of a single Linear SVM call. In our boosting algorithm, we run for as many rounds as possible until there are no more examples left in the training set to run LinearSVM on.
Results On make_ moons with perturbation radius = 0.1, the baseline Linear SVM achieves robust accuracy of 84.78%, while 3-RoBoost (with rounds of boosting) achieves robust accuracy of 89.86%. On MNIST with perturbation radius 0.5, the baseline Linear SVM achieves a robust accuracy of 73.9%, while 3-RoBoost (with 2 rounds boosting) achieves robust accuracy 80.05%. Finally, on MNIST with a bigger perturbation radius = 1.0, the baseline Linear SVM achieves robust accuracy of 48.18 1%, while 3-RoBoost (with 2 rounds of boosting) achieves robust accuracy of 70.12%.
We observe that 3-RoBoost improves the robustness of Linear SVM. Notice that even in the regime where the baseline Linear SVM archives robust-accuracy < 50% (MNIST with perturbation radius 1.0), Roost can actually improve the robust-accuracy beyond 50%.
We include code to reproduce our MNIST experiments with perturbation radius 7 = 1.0 in Appendix
Acknowledgments and Disclosure of Funding
We would like to thank Steve Hanneke and Nathan Srebro for insightful discussions, and the anonymous reviewers for their detailed and valuable feedback. This work was supported in part by DARPA under cooperative agreement HR001 12020003." This work was supported in part by the National Science Foundation under grant 185-18
References
[1] D. Abernethy, Awasthi, and S. Kale. A multiclass boosting framework for achieving fast and provable adversarial robustness. CoRR, abs/2103.01276. 2021. 1.1, 1.2
'The views expressed in this work do not necessarily reflect the position or the policy of the Government and official endorsement should be inferred. Approved for public release; distribution is unlimited.
10

---

[2] J. Alayrac, J. Uesato, P. Huang, A. Fawzi, R. Stanforth, and P. Kohli. Are labels required for improving adversarial robustness? In Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 12122- 2019. A
[3] H. Ashtiani, V. Pathak, and R. Urner. Black-box certification and learning under adversarial perturbations. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 388-398. PMLR, 2020. A
[4] D. G. Brown. How wasted too long finding concentration inequality for sums of geometric variables. Found at https://cs. uwaterloo. ca/" browndg/negbin. pdf, 8(4), 2011. 9, C
[5] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pages 11 11190-11201 2019. A
[6] J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1310-1320. PMLR, 2019. 5,5
[7] E. Croce, M. Andriushchenko, V. Sehwag, F. Debenedetri, N. Flammarion, M. Chiang, P. Mittal, and M. Hein. Robusthench: a standardized adversarial robustness benchmark. arXiv preprint arXi::2010.09677 2020. 1
[8] Y. Freund. Boosting a weak learning algorithm by majority. In M. A. Fulk and J. Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 202-216. Morgan Kaufmann, 1990. 1.2
[9] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-139) 1997. 1.2
[10] J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. 1
[11] A. Kalai and V. Kanade. Potential lotential-based agnostic boosting. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pages 880-888. Curran Associates, Inc., 2009. 1.2
[12] M. Kearns. Thoughts on hypothesis boosting. Unpublished, Dec. 1988. 1.2
[13] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[14] O. Montasser, S. Goel, I. Diakonikolas, and N. Srebro. Efficiently learning adversarially robust halfspaces with noise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7010-7021. PMLR, 2020. 6
[15) O. Montasser, S. Hanneke, and N. Srebro. VC classes are adversarially robustly learnable, but only improperly. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thirty-Secome Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2512-2530, Phoenix, USA, 25-28 Jun 2019. PMLR. 1.1, 1.2, 9, 4, 8, 9. 10
11

---

[16] O. Montasser, S. Hanneke, and N. Srebro. Reducing adversarially robust learning to non- robust PAC learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin. editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 12, 2020, virtual, 2020. 1.2
[17] R. E. Schapire. The strength of weak learnability. Mach. Learn., 5:197-227, 1990. 1.2
[18] R. E. Schapire and Y. Freund. Boosting. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2012. 1.1, 1,2,955
[19] Y. Yang, C. Rashtchian, H. Zhang, R. Salakhutdinov, and K. Chaudhuri. A closer look at accuracy vs. robustness. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. 1.2
[20] D. Zhang, H. Zhang, A. Courville, Y. Bengio, P. Ravikumar, and A. S. Suggala. Building robust ensembles via margin boosting. In International Conference on Machine Learning. 2022. 1.2
[21] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pages 1482-7482. PMLR, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "l1xT9rJ3W_Z", "reviewer": "Reviewer_Lbb7", "summary": "The authors introduce a notion of \\emph{barely robust} learning. Their main results demonstrate the an equivalence with strongly robust learning by showing (Theorem 4) that if a concept is strongly robustly learnable, it is barely robustly learnable as well, and then by proposing an oracle-efficient algorithm (Theorem 1) that calls a barely robust learner in order to produce a strongly robust one. Their formal equivalence statement (Corollary I) shows that being strongly robustly learnable with respect to an adversarial perturbation set $\\mathcal{U}$ is equivalent to being barely robustly learnable with respect to a larger perturbation set $\\mathcal{U}^{-1}(\\mathcal{U})$, and they further demonstrate (Theorem 6) that barely robust learnability w.r.t. $\\mathcal{U}$ does not in general imply strong robust learnability. \n\n", "questions": "See comments under Significance above. Any enlightenment on either of these aspects would greatly improve the paper. ", "limitations": "The authors have not discussed potential negative societal impact of their work, although it is hard to see what one might have to say here that is not totally banal.  ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nHighly original; the authors have proposed the first algorithm that boosts the robustness of what they call barely robust learners, and provide a comprehensive characterization of their newly proposed notion as it relates to previously studied notions.\n\nQuality:\nGood. The theory is elegantly laid out, and comprehensively addresses the salient questions. The discussion provides a satisfying contextualization of the results. \n\nClarity:\nGenerally quite good, although perhaps it would read more straightforwardly if relevant definitions were placed before they are required in theorem statements. (I believe there is a typo in line 151: a missing subscript t in the def. of $G_{h_t}(z)$.)  \n\nSignificance: \nThe open question of whether one can boost the error of a barely robust learner without sacrificing robustness remains, it would seem, an impediment to greater significance. In the same vein, more insight into the possibility of currently known adversarial learning methods being barely robust would also be welcome.  \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kzbKunQD27d", "reviewer": "Reviewer_DokF", "summary": "This paper mainly shows that strongly robust learnable w.r.t. $\\mathcal{U}$ is equivalent to barely robust learable w.r.t. $\\mathcal{U}^{-1}(\\mathcal{U})$, bu giving an algorithm $\\beta$-RoBoost to boost robustness of barely robust learners and an algorithm to return a barely robust classifier through calling the strongly robust learner.\n\nThis paper also shows that barely robust learable w.r.t. $\\mathcal{U}$ is not sufficient for strongly robust learnable w.r.t. $\\mathcal{U}$ by a counterexample. What's more, the paper also gives algorithms to boost robustness with unlabeled data.", "questions": "In the proof of Theorem 6, the paper uses a randomized learner which do not need any data as input, and proves that it is $(\\frac{1}{2},0,\\delta)$-barely robust learnable. And the paper proves that the expected value of the **robust risk** w.r.t. the random choice of $\\tilde{y}$ is $\\frac{1}{2}$, but not to be $\\frac{1}{2}$ with probability at least $1 - \\delta$ over the choice of samples as in the definition of the barely robust learner. Although we can use concentration inequality to get a confidence, but it is over the random choice of $\\tilde{y}$, so there seems to be a mismatch in the definition of the barely robust learner and the proof of Theorem 6.\n\nIn Corollary 2, the paper claims it is a stronger boosting guarantee, I wonder in what sense is it stronger than Thoerem 1? Is it falls on better sample complexity, or falls on weaker requirement on the barely robust learner, or others else?", "limitations": "The authors does.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper shows a sufficient and necessary condition for strongly robust learning and gives a novelty method to boost robustness of barely robust learners. The theoretical results are quite solid.\n- The results of this paper in significant since it provides another way to study the robustness.\n- The paper gives some high-level strategies to help understanding the spirit in the algorithms and proofs.\n\nWeaknesses:\n- As discussed in the discussion part, verifying whether a classifier is robust on the perturbation set $\\mathcal{U}^{-1}(\\mathcal{U})$ is a key issue in the computational efficiency of the proposed algorithm, but **to the best of my knowledge, there is now no theoretiacl gurantee for precisely verifying robustness for a general perturbation set and a general hypothesis class**. As stated in [1], the popular method random smooth might fail in verifying the $\\ell_\\infty$ robustness for high-dimensional images. So the realizability of the proposed algorithm highly depends on the development of robust verification.\n\n[1] Blum, Avrim, et al. \"Random Smoothing Might be Unable to Certify $\\ell_\\infty$ Robustness for High-Dimensional Images.\" J. Mach. Learn. Res. 21 (2020): 211-1.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YP8dJgYulOa", "reviewer": "Reviewer_VncC", "summary": "This paper studies how to achieve adversarially robust learning with weak robust learners. The investigation follows a quite natural agenda and gives quite complete answers. The contributions are three folds.\n\nFirst, at the conceptual level, the paper propose the key definition of barely robust learning, and point out the importance to look at a larger perturbation set $U^{-1}(U)$. \n\nSecond, the paper gives an oracle efficient reduction from adversarially robust learning to barely robust learning. This shows that barely robust learning with respect to $U^{-1}(U)$ is sufficient for adversarial robust learning. This is by Theorem 1 and Algorithm 1.\n\nThird, the paper shows that adversarial robust learning implies barely robust learning with respect to $U^{-1}(U)$ (Theorem 4), but it can not be achieved if one only has barely robust learning with respect to $U$ (Theorem 6). This shows that barely robust learning with respect to $U^{-1}(U)$ is necessary for adversarially robust learning. ", "questions": "I am confident that I understand the theme and conclusions of the paper. But I only go through the algorithm and proof part, so it's hard for me to evaluate the novelty of the algorithm and the theoretical analysis. I think the concept of barely robustness is quite essential, but is the analysis somewhat similar to existing routines after one discover this concept? ", "limitations": "The proposed algorithm in the paper is more useful when the robust parameter $\\beta$ is small, since existing results could not provide theoretical guarantees in this regime. However, experiments may be needed if the authors want to advertise their algorithm to be better than existing methods that are directly based on canonical results and already work for $\\beta>1/2$.\n\nI think the paper should put more space and content to discuss when the perturbation set $U^{-1}(U)$ is much larger than $U$, and when they are similar. The current paper only uses the $\\ell_p$ ball examples, where requiring robustness with respect to $U^{-1}(U)$ is very reasonable (it's just a ball with twice radius). However, as looking at this larger perturbation set is one of the major novelty of the paper, the author should carefully explain for what $U$ this requirement is strong (which means boosting robustness is not easy, according to the theorems in the paper), and for what $U$ this requirement is weak (which means boosting robustness is easy).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the flow of writing in this paper, especially the introduction section. Although this is a purely theoretical paper, the pace makes its proposed questions and main contributions easy to understand. In particular, when I read the introduction, the first question coming to mind is, isn't boosting easier if the robust parameter $\\beta$ is larger than 1/2? This is answered immediately in the paragraph \"Landscape of boosting robustness.\" The second question coming to mind is, is the assumption of robust realizability more restrictive than the traditional concept of realizability. And the authors give examples to answer this question in the related work part. I also like the  discussion section (Section 5), which answers my concerns about the agnostic setting and computation efficiency. This part also propose several open questions.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PScJsiN12Er", "reviewer": "Reviewer_TbrQ", "summary": "The paper studies a new direction in adversarial training, on the distinctions between barely robust leaners and strongly robust learners. The paper provides theoretical results on whether we can make a barely robust classifier into a strongly robust classifier. The paper also provided two algorithms to guarantee a strongly robust learner. The authors also prove that for any distribution, there would exist a barely robust classifier and that classifier is not a strongly robust classifier.", "questions": "1. You mentioned that  $U^{-1}(U)$ is a ball with $2\\gamma$ radius and $U$ is a ball with $\\gamma$ radius. This statement and Colloray I sound contradicitng with you claim that \"weaker relaxations of barely robust learning do not imply strongly robust learning\" in line 33.\n2. Is it possible to implement black-box oracle calls to A on real-world datasets?\n3. ", "limitations": "Although the theoretical results are novel and interesting, the paper does not provide numerical experiments to support its findings. This makes me question the possibility of using the definition of the strongly robust learner or implementing the two algorithms in real-world applications. It would be more convincing if the authors can provide some numerical experiments even on small datasets, like MNIST.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The definition of a barely robust learner is solid and new.\n2. The authors provide many theorems to explain the relationship between a barely robust classifier and a strongly robust classifier, including their equivalence under some conditions.\n3. There are two algorithms that guarantee getting a strongly robust classifier.\n\nWeaknesses:\n1. It is still unclear if the barely robust classifier for $U^{-1}(U)$ and strongly robust classifier $U$ are equivalent, is it that important to train a strongly robust classifier? It is unclear why we would care about the definition of a strongly robust learner.\n2. There are no numerical experiments to support the applications or benefits of a strongly robust classifier. \n3. There are no comparisons between existing literature in either theoretical or numerical results, so we don't understand what is the relationship between a strongly robust classifier with other related literature.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6fc5Oo0XNCH", "reviewer": "Reviewer_YxMp", "summary": "This paper presents theoretical analysis over barely robust learner and strong robust learner.", "questions": "Could we add an empirical analysis to show that the proposed methods are effective?", "limitations": "I suggest the authors to discuss how the users can adapt the proposed algorithms in real applications.", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong Points\n----\n1. Adversarial robustness analysis is an important problem in machine learning community.\n\nWeak Points\n----\n1. I spent more than 8 hours to read the paper. However, at least for me, it is very hard to follow the analysis. For example, U^{-1} is heavily used in Section 1.1 while its description locates in Section 2. \n2. I didn't check the correctness of the theorems and proofs. I wonder if it is possible to add an empirical analysis to show that the proposed methods are effective? The termination rounds could be very large for real applications.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept