On Achieving Optimal Adversarial Test Error
Authors: Justin D. Li
Matus Telgarsky
Venue: ICLR 2023 poster (2023)

Abstract: We first elucidate various fundamental properties of optimal adversarial predictors: the structure of optimal adversarial convex predictors in terms of optimal adversarial zero-one predictors, bounds relating the adversarial convex loss to the adversarial zero-one loss, and the fact that continuous predictors can get arbitrarily close to the optimal adversarial error for both convex and zero-one losses. Applying these results along with new Rademacher complexity bounds for adversarial training near initialization, we prove that for general data distributions and perturbation sets, adversarial training on shallow networks with early stopping and an idealized optimal adversary is able to achieve optimal adversarial test error. By contrast, prior theoretical work either considered specialized data distributions or only provided training error guarantees.

Published as a conference paper at ICLR 2023
ON ACHIEVING OPTIMAL ADVERSARIAL TEST ERROR
Justin D. Li & Matus Telgarsky
University of Illinois, Urbana-Champaa
(jdli3, mjt) eiliiniiiiiiini.m
ABSTRACT
We first elucidate various fundamental properties of optimal adversarial predictors: the structure optimal adversarial convex predictors in terms of optimal adversarial zero-one predictors, bounds relating the adversarial convex loss to the adversarial zero-one loss, and the fact that continuous predictors can get arbitrarily close to the optimal adversarial error for both convex and zero-one losses. Applying these results along with new Rademacher complexity bounds for adversarial training near initialization, we prove that for general data distributions and perturbation sets, adversarial training on shallow networks with early stopping and an idcalized optimal adversary is able to achieve optimal adversarial test error. By contrast, prior theoretical work either considered specialized data distributions or only provided training error guarantees.
INTRODUCTION
Imperceptibly altering the input data in a malicious fashion can dramatically decrease the accuracy of neural networks (Szegedy et al. 2014). To defend against such adversarial attacks, maliciously altered training examples can be incorporated into the training process, encouraging robustness the final neural network. Differing types of attacks used during this adversarial training, such FGSM GGoddellow et al. 2013), PGD (Madry et al.) 2019), and the C&W attack (Carlini & Wagner 2016), which are optimization- based procedures that try find bad perturbations around the inputs, have been shown to help with robustness. While many other defenses have been proposed (Guo et al. 2017 Dhillon al. 2018 Xie al.) (017). adversarial training the standard approach (Athalye et al. 2018). Despite many advances, large gap still persists between the accuracies we are able to achieve on non-adversarial and adversarial test sets. For instance, in Madry al. (2019), wide ResNet model was able to achieve 95% accuracy on CIFAR-10 with standard training, but only 46% accuracy on CIFAR-10 images with perturbations arising from PGD bounded by 8/ 8/255 in each with the benefit of adversarial training.
coordinate,
In this work we seek to better understand the optimal adversarial predictors we are trying to achieve, as well as how adversarial training can help us get there. While several recent works have analyzed properties of optimal adversarial zero-one classifiers (Bhagoji et al., 2019 Pydi & Jog 2020) Awasthi al. 2021b), the present work we build off of these analyses to characterize optimal adversarial convex surrogate loss classifiers. Even though some prior works have suggested shifting away from the use of convex losses in the adversarial setting because they are not adversarially calibrated (Bao ct al. 2020; Awasthi et al.) 2021a c 2022a b). we show the use of convex losses is not an issue as long as a threshold appropriately chosen.
We will also show that under idealized settings adversarial training can achieve the optimal adversarial test error. In prior work guarantees on the adversarial test error have been elusive, except in the specialized case of linear regression (Donhauser et al., 2021 Javanmard et al.) 2020 Hassani & Javanmard, 2022). Our analysis is in the Neural Tangent Kernel (NTK) or near-inttialization regime, where recent work has shown analyzing gradient descent can be more tractable (Jacot et al.) [0188] Du ctt al.) 2018). Of many such works our analysis is closest to Ji et al. (2021), which provides general test error analysis, but for standard (non-adversarial) training.
recent work Rice et al., 2020 suggests that early stopping helps with adversarial training, as otherwise the network enters a robust overfitting phase in which the adversarial test error quickly rises while the adversarial training error continues to decrease. The present work uses a form of early stopping, and so is in the earlier regime where there is little to overfitting.

---

Published as a conference paper at ICLR 2023
0.8
Early phase (this paper) Late phase (not this paper)
Zero-one loss
0.6
0.4
Robust loss (train)
0.2
Robust loss (test)
Standard loss (train)
Standard loss (test)
0.0
100
10a
10a
10a
Epochs
Figure 1: A plot of the (robust/standard) zero-one (training/test) loss throughout training for an adversarially trained network. We ran Rice et al.ss code, using a constant step size of 0.01. The present work is set within the early phase of training, where can get arbitrarily close to the optimal adversarial test error. In fact, due to technical reasons our analysis will be further restricted to an earlier portion of this phase, in prior work, adversarial training, as compared with standard training, seems to have more fragile test-time performance and quickly enters phase of severe overfitting, but we do not consider this issue here.
remain within the near sea--iittaalzzaiionNTTE regime. As noted
1.1 OUR CONTRIBUTIONS
In this work, we prove structural results on the nature of predictors that are close to, even achieve, optimal adversarial test error. addition, we prove adversarial training on shallow ReLU networks can get arbitrarily close to the optimal adversarial test error over all measurable functions. This theoretical guarantee requires the use optimal adversarial attacks during training, meaning we have access an oracle that gives, within an allowed set of perturbations, the data point which maximizes the loss. We also use early stopping so that we remain in the intiiaiiiiaiiooioonn regime and ensure low model complexity. The main technical contributions are follows.
1. Optimal adversarial predictor structure (Section 3). We prove fundamental results about optimal adversarial predictors by relating the global adversarial convex loss to global adversarial zero-one losses (cf. Lemma 3.I. We show that optimal adversarial convex loss predictors are directly related to optimal adversarial zero-one loss predictors (cf. Lemma B.2). In addition, for predictors whose adversarial convex loss almost optimal, we show that when an appropriate threshold is chosen its adversarial zero-one loss is also almost optimal (ef. Theorem 3.3) This theorem translates bounds on adversarial convex losses, such as those in Section 4 into bounds adversarial zero-one losses when optimal thresholds are chosen. Using structural results of optimal adversarial predictors, we prove that continuous functions can get arbitrarily close to the optimal test error given by measurable functions (cf. Lemma 3.4
2. Adversarial training (Section 4). Under idealized settings, we show adversarial training leads to optimal adversarial predictors.
(a) Generalization bound.
We prove a near-initialization generalization bound for adversarial risk (cf. Lemma 4.4). To do so, we provide Rademacher complexity bound for linearized functions around initialization (cf. Lemma 4.5). The overall bound scales directly with the parameter's distance from initialization, and 1/ /n, where is the number of training points. Included in the bound a perturbation term which depends on the width of the network, and the worst case scales like 1/4 where r bounds the & norm of the perturbations.
(b) Optimization bound. We show that using an optimal adversarial attack during gradient descent training results in network which is adversarially robust the training set, in the sense that it is not much worse compared to an arbitrary reference network (cf. Lemma (4.).. Comparing to a reference network instead of just ensuring low training error (as in prior work) will be key to obtaining a good generalization analysis, as the optimal adversarial test error may be high.
2

---

Published as a conference paper at ICLR 2023
(c) Optimal test error. As the generalization and optimization bounds are both in near- initialization setting, these two bounds can be used in conjunction. We first bound the test eπrоr of our trained network in terms of its training error using the generalization bound, and then apply the optimization bound to compare against training error of an arbitrary reference network. Another application of our generalization bound then allows us to compare against the test еттоr of an arbitrary reference network (cf. Theorem (41). Applying approximation bounds and Lemma 3.4 then lets us bound our trained network's test error in terms of the optimal test error over all measurable functions (cf. Corollary 4.2)
2 RELATED WORK
We highlight several papers in the adversarial and near-initialization communities that relevant this work.
Optimal adversarial predictors. Several works study the properties of optimal adversarial pre- dictors when considering the zero-one loss (Bhagoji et al. 2019 Pydi & Jog, 2020; Awasthi et al.) 2021b). In this work, we are able to understand optimal adversarial predictors under convex losses in terms of those under zero-one losses, although we will not make of any properties of optimal zero-one adversarial predictors other than the fact that they exist. Other works study the inherent tradcoff between robust and standard accuracy (Tsipras al. 2019 Zhang et al., 2019), but these are complementary to this work as we only focus on the vdvesrriial setting.
Convex losses. Several works explore the relationship between convex losses and zero-one losses in the non-adversarial setting (Zhang) 2004 Bartlett et al., (2066). Whereas the optimal predictor in the non-adversaria setting can be understood locally at individual points in the input domain, it is difficult do so in the adversarial setting due to the possibility of overlapping perturbation sets. As result, our analysis will be focused on the global structure of optimal adversarial predictors. Convex losses as an integral over reweighted zero-one losses have appeared before (Savage 1971, Schervish 1989 (lernández-Oralll et al. 2012), and we will adapt and make use of this representation in the adversarial setting.
Adversarial surrogate losses. Several works have suggested convex losses are inappropriate the adversarial setting because they are not calibrated, and instead propose using non non-convex surrogate losses (Bao et al., 2020 Awasthi et al. (2021a 2022a[b). (). In this work, we show that with appropriate thresholding convex losses are calibrated, and so are an appropriate choice for the adversarial setting.
Near-inittalization. Several works utilize the properties of networks in the near- near-initializan initialization regime to obtain bounds on the test error when using gradient descent (Li & Liang 2018: Arora et 2019; Cao & Gu 2019 Nitanda et al.] 2020 Ji & Telgarsky] 2019 Chen et al. [2019 et al. 2021). In particular, this paper most directly builds upon the prior work oi et al. (2021). which showed that shallow neural networks could learn to predict arbitrarily well. We adapt their analysis to the adversarial setting.
Adversarial training techniques. Adversarial training initially used FGSM (Goodfellow et al. 2015) to find adversarial examples. Numerous improvements have since been proposed, such as iterated FGSM (Kurakin et al.) 2016) and PGD (Madry et al.) (019)). which strives to find even stronger adversarial examples. These works are complementary to ours, because here we assume that we have an optimal adversarial attack, and show that with such an algorithm we can get optimal adversarial test error. Some of these alterations (Zhang et al. 2019 Wang et al. 2021; Miyato jet al.] 2018 Kannan et al.) 2018) do not strictly attempt to find a maximal adversarial attack at every iteration, but instead use some other criteria. However, Rice et al. (2020) proposes that many of the advancements to adversarial training since PGD can be matched with early stopping. Our work corroborates the power of the early stopping in adversarial training
it in analysis.
Adversarial training error bounds. Several works are able to show convergence of the adversarial training error. Gao et al. (2019) did so for networks with smooth activations, but is unable to handle constant-sized perturbations as the width increases. Meanwhile Zhang al. (2020) uses ReLU
3

---

Published as a conference paper at ICLR 2023
activations, but imposes a strong separability condition the training data. Our training error bounds use ReLU activations, and in contrast to these previous works simultaneously hold for constant-sizer perturbations and consider general data distributions. However, note that the ultimate goals of these works differ, as we focus on adversarial test error.
Adversarial generalization bounds. There are several works providing adversarial generalization bounds. They not tailored to the iaaiiaiitiaiization setting, and they either looser require assumptions that are not satisfied here. These other approaches include SDP relaxation based bounds (Yin et al.] 2018), tree transforms (Khim & Lohi (019),, and covering arguments (Tu et al. 2019 Awasthi et al., 2020: Balda et al. 2019). Our generalization bound also uses a covering argument, but pairs this with mear-initialization decoupling. There are a few works that are able achieve adversarial test error bounds in specialized cases. They have been analyzed when the data distribution linear, both when the model is linear too (Donhauser et al., 2021 Javanmard al. 2020), and for random features (Hassani & Javanmard 2022). In the present work, we are able to handle general data distributions.
3 PROPERTIES OF OPTIMAL ADVERSARIAL PREDICTORS
This section builds towards Theorem 3.3 relating zero-one losses to convex surrogate losses.
3.1 SETTING
We consider distribution DD with associated measure y that is Borel measurable over X x Y, where X S IRd compact, and Y (-1,1}, 1). For simplicity, throughout we will take B1 to be the closed Euclidean ball of radius centered at the origin. We allow arbitrary P(y 1|x) [0, 1] that is, the true labels may be noisy.
We will consider general adversarial perturbations. For E B1, let P(x)) be the closed set of allowed perturbations. That is, an adversarial attack is allowed to change the input x to any x' E P(x). We will impose the natural restrictions that () & P(z) B1 for all 2 E B1. That is. there always exists at least one perturbed input, and perturbations cannot exceed the natural domain of the problem. In addition, will assume the set-valued function P is upper hemicontinuous. That is, for any X and any open set U 2 Pxx), there exists an open set V 3 x such that P(V) = UVevP(()) S U. For the commonly used fo perturbations as well as many other commonly used perturbation sets (Yang et al. 2020), these assumptions hold. As an example, in the above notation we would write foo perturbations P(x)= {a' Br ||ay x11.0 T).
Let f: B1 + R be a predictor. We will let le be any nonincreasing convex loss with continuous derivative. The adversarial loss is (2, y, f) maxx'e (vf(()))) and the adversarial convex
risk (f) = I (a y, f) du(z,)) y). For convenience, define ft (x) sup='ep(z)) f(z') and (x) = ('))) f (zz), the worst-case values for perturbations in P (z) when y = -1 and y = 1,
respectively. Then we can write the adversarial zero-one risk as
Raz(f) = / (11= (x) < 0] 1ly 1]1(f(()))))))))))(111) 2 0J) du(z, v).
To relate the adversarial convex and zero-one risks, we will use reweighted adversarial zero-one risks (J) as intermediate quantity, defined follows. The adversarial zero-one risk when the +1 labels have weight (t) and the -1 labels have weight (-(((-t))
RAz(l)= = / (1 (x) < ())(
+1 = - 1|1 (x) 0] (((-)((())) dp(x,
3.2 RESULTS
We present a number of structural properties of optimal adversarial predictors. The key insight will be write the global adversarial convex loss in terms of global adversarial zero-one losses, as follows.
4

---

Published as a conference paper at ICLR 2023
Lemma 3.1. For any predictor f. RA(f) f Riz(f - dt.
Ri 1) is an intuitive quantity consider for the following reason. In the non-adversarial setting, a predictor outputting value of (1x) corresponds to prediction of -- (-((-1(0))
of the labels being +1 that point. If +1 labels are given weight (- and -1 labels weight (-f(-((), then f()) would predict at least half the labels being +1 if and only if (-((-0)
(-((-((()) (-ft))(--(((-
2 (-1:(0)+((((()))) As result, the optimal non-adversarial predictor is also an optimal non- -onverarral zero-one classifier at thresholds for the corresponding reweighting of +1 and -1 labels. Even though we won't be able to rely on the same local analysis as our intuition above, it turns out the same thing is globally true in the adversarial setting.
Lemma 3.2. There exists a predictor g g: X + such that RA (g) is minimal. For any such predictor, Rg - = -infy (f) for all E IR.
Note that the predictor in Lemma 3.2 is not necessarily unique. For instance, the predictor's value at a particular point might not matter to the adversarial risk because there are no points in the underlying distribution whose perturbation sets include æ. To prove Lemma 3.2] we will use optimal adversarial zero-one predictors to construct can also use an optimal adversarial convex loss predictor to construct optimal adversarial zero-one predictors. In general, the predictors we find will not exactly have the optimal adversarial convex loss. For these predictors we have the following error gap.
optimal adversarial convex loss predictor g. Conversely,
Theorem 3.3. Suppose there exists
21 and > 0 such that
(2p -11) * .
(p) == lo inf (plc(2) + p)ecl=2)) zER
Then for any predictor g.
Raz(g inf Raz(h) 31-1c lc menx.
1/e
Rg
inf (1)) As meus.
The idea of using Gt, (p) comes from Zhang 2004 When we explicitly set le be the logistic loss in Section 4 we can choose
and /2 Zhang 2004). While similar bounds exist in the non-adversarial case with (g) instead of inf, Raz(g t) (Zhang) 2004 Bartlett et al. (006), the analogue with Raz(g - t) - inf, mens. RAz(h) appearing on the left-hand side is false in the adversarial setting, which can be seen as follows. Consider uniform distribution of (xr, y) pairs over {1) and suppose {-1,+1 +1] E P(-1) P(+1). Then the optimal adversarial convex risk is (0) given by f(x 0, and the optimal adversarial zero-one risk is 1/2 given by sgn(f(z)) = +1. However, for e > 0 the predictor g. with g+(++) 6, g=(-1) = -, and ge (x) E [-e, 6) everywhere else gives adversarial convex risk (Po(e) + Eo(-)) and adversarial zero-one risk 1. This results in
Raz(ge) - inf RAz(h)
c+0 1/2.
Rg inf RA
O,
demonstrating the necessity for some change compared to the analogous non-adversarial bound. As this example shows, getting arbitrarily close to the optimal adversarial convex risk does not guarantee getting arbitrarily close to the optimal adversarial zero-one risk. This inadequacy of convex losses in the adversarial setting has been noted in prior work (Bao et al. 2020; Awasthi et al. 202 c 2022a b), leading them to suggest the use of non-convex losses. However, as Theorem 3.3 shows, we circumvent this inadequacy if allow the choice of an optimal (possibly nonzero) threshold.
While we have compared against optimal measurable predictors here, in Section 4 we will use continuous predictors. This presents potential problem, there may be gap between the adversarial risks achievable by measurable and continuous predictors. It turns out this is not the case, as the following lemma shows.
Lemma 3.4. For the adversarial risk, comparing against all continuous functions is equivalent to comparing against all measurable functions. That is, infget. etz. Rx(g) = inf meas. R (h).
In the next section, we will use Lemma 3.4 to compare trained continuous predictors against all measurable functions.
5

---

Published as a conference paper at ICLR 2023
4 ADVERSARIAL TRAINING
Theorem 3.3 shows that with optimally chosen thresholds, to achieve nearly optimal adversarial zero-one risk it suffices to achieve nearly optimal adversarial convex risk. However, it is unclear how to find such a predictor. In this section we remedy this issue, proving bounds on the adversarial convex risk when adversarial training used on shallow ReLU networks. In particular, we show with appropriately chosen parameters we can achieve adversarial convex risk that is arbitrarily close to optimal. Unlike Section
B our results here will be specific the logistic loss.
4.1 SETTING
Training points (It, 31 3n){== are drawn from the distribution D. Note that ||xx|| S 1, where by default we use ||| to denote the E norm. We will let r = sup ||= 2||2 : x' E P(x), x: E B1] be the restrictions
maximum Eg norm of the adversarial perturbations. By
the perturbation sets, have 0 < r S 2. Throughout this section we will set l. to be the logistic loss {(z) = In(1 + The empirical adversarial loss and risk are (f, = L (2 yk. f) and (f( = Ei= (f) The predictors will be shallow ReLU networks of the form f(W;
m (uor(w)rr). where W is vm 2j=1 an m x d matrix, w/ is the jth row of W, (2) = max(0, 2) is the ReLU, a, E {+1} are initialized uniformly at random, and p is temperature parameter that we can set. Out of all of these parameters, only W will be trained. The initial parameters Wo will have entries initialized from standard Gaussians with variance 1, which we then train to get future iterates W, We will frequently use the features of W. for other parameters W; that is, we will consider (W; x)) = (W;;;) W). where the gradient taken with respect to the matrix, not the input. Note that f is not differentiable at all points. When this is the case by V f we mean some choice of V E θf, the Clarke differential. For notational convenience we define R.(W) = -A()(W:)) Rw) = (A( :)) R²02 (W) = ( (W;:)()))))) (W:.)) and (2x² (W)- (R (xW:)) ()) Our adversarial training will be as follows. To get the next iterate W from W; for 2 0 we will use gradient descent with W++1 = W -V,-n/7 -,, Normally adversarial training occurs in two steps:
1. For each k find o'e E P(x) such that f( xf))) is maximized.
2. Perform gradient descent update using the adversarial inputs found in the previous step: W W.- v/ ( Ei= l(r'k, yk. -);
Step is an adversarial attack, in practice done with a method such as PGD that does not necessarily find an optimal attack. However, we will assume the idealized scenario where we are able to find an optimal attack. Our goal will be to find a network that has low risk with respect to optimal adversarial attacks. That is, we want find such that Rx(f) is small as possible.
4.2 RESULTS
Our adversarial training theorem will compare the risk we obtain to that of arbitrary reference param- eters Z R mx which we will choose appropriately when we apply this theorem in Corollaries 4.2
and 4.3 To get near-optimal risk, we will apply our early stopping criterion of running gradient descent until IW; Woll > 2Rz, where Rz 2 max(1, (1, mp, I Woll), a quantity we assume knowledge of, at which point we will stop. It is possible this may never occur in that case, will stop at some time step f, which is a parameter we are free to choose. We just need to choose t sufficiently large to allow for enough training to occur. The iterate choose as our final model will be the one with the best training risk.
Theorem 4.1. Let m 2 In (emd) and np² < 2. For any Z E Rxdd let Rz 2 max(1, np, Il
Woll and Wst = arg min( (R, : I i s t, IW, - Woll < <2Rz Vj < i). Then with probability at least 125,
RW < 2-
2
R (0) (Z)
+5
((-122) m )
R2 + pRz (d + v rm nt.
p 4/3 d//3 m2-6 1/6
mpl
Vn
where ① suppresses In(n), In(m). In(d), (n(1/)), (n(1/) terms.

---

Published as a conference paper at ICLR 2023
In Corollary 4.2 we will show
parameters that all error terms arbitrarily small.
The early stopping criterion [WW-- - Woll > 2Rz will allow us to get a good generalization bound, as we will show that all iterates then have |[W, Woll s 2Rz + mp. When the early stopping criterion is met, we will be able to get a good optimization bound. When it is not, choosing t large enough allows us do
It may be concerning that we require knowledge of R2, as otherwise the algorithm changes depending on which reference parameters use. However, in practice could instead validation set and instead of choosing the model with the best training risk, we could choose the model with the best validation risk, which would remove the need for knowing Rz. Ultimately, our assumption of knowing Rz is there to simplify the analysis and highlight other aspects of the problem, and we leave dropping this assumption to future work.
To compare against all continuous functions, we will use the universal approximation of infinite-wind neural networks (Barron [993). We use a specific form that adapts Barronns s arguments to give an estimate of the complexity of the infinite-width neural network (Ji et al. 2019). We consider infinite- width networks of the form f(:; Usa) := I (U>o (v), xll [uTx 2 0}) dN(),, where Us Rd + I&d parameterizes the network, and N is standard d-dimensional Gaussian distribution. We will choose an infinite-widtt network [(; U.) with a finite complexity measure sup, [[U{(()]] that c-close to a near-optimal continuous function. Letting R. == max (p, np² supp, ||U (z)]l}. with high probability we can extract a finite-width network Z close to the infinite-width network whose distance from Wo is most Rz- Re/p. Note that our assumed knowledge of Rz is equivalent assuming knowledge of Re From Lemma [344 we know continuous functions can get arbitrarily close to the optimal adversarial risk over all measurable functions, so we can instead compare against all measurable functions.
We immediately have issue with our formulation - the comparator in Theorem 4.1 is homogeneous. To have any hope of predicting general functions, we need biases. We simulate biases by adding a dummy dimension to the input, and then normalizing. That is, we transform the input + - (z; 1). The dummy dimension, while part of the input to the network, is not truly part of the input, and so we do not allow adversarial perturbations to affect this dummy dimension.
v2
Corollary 4.2. Let > 0. Then there exists a finite R. 2 max(p, np²} representing the complexity measure of an wifth network that is within e of the optimal adversarial risk. Then with probability at least - 8, setting
R 22
R c5p2
p = Ō())
7 = G(1/e),
t= Ω
with n satisfying
n == â maxx(1, Tm) R² RRR 1222)
where θ H suppresses In (R,),, (011/)),n((1/0) terms, we have
(W S inf (R measurable) O(e).
Once again, it may be concerning that we require knowledge of the complexity of the data distribution for Corollary 4.2 However, the following result demonstrates that we effectively guaranteed to converge to the optimal risk as n - oc, as long as parameters are set appropriately.
Corollary 4.3. we set (n) 1 1/6
(n) 1/6
(()) n,
m
n/2
then
R((w()) n=ce, inf (R 9 measurable)
almost surely.
4.3
PROOF SKETCH OF THEOREM 4.1
The proof has two main components: a generalization bound and an optimization bound. We describe both in further detail below.
7

---

Published as a conference paper at ICLR 2023
4.3.1 GENERALIZATION
Let 7 == 22T +
32r (n(n/6))
1/4
+ 2V We prove a new near-initialization generalization bound.
m
Lemma 4.4. If B and 2 In(emd), then with probability at least
56,
sup WV
R (V) (V) - R (v) 2
2
PB Vn
+
+2
PBF vn
14
In
mn
72
TTpBdIn 3/2 (4em²
+
Vn
The key term to focus on is the middle term. Note that 7 is quantity that grows with the perturbation radius 7, and importantly is 0 when r is O. When we are in the non-adversarial setting (T - 0), the middle term is dropped and in (Ji et al. 2021). In the general setting when r is a constant, so f, resulting in an additional dependence on the width of the network.
recover Rademacher bound qualitatively similar Lemma A.8
Lemma 4.4 will easily follow from the following Rademacher complexity bound. Lemma 4.5. Define V {V ||V Woll S B), and let
F = {xp + x1 <m(x)
min Vs (a Wo), V) V V).
Then with probability at least 1 35,
pBT
1
v m
mi F
Rad F) S pB Vn
In the setting of linear predictors with normed ball perturbations, an exact characterization of the perturbations can be obtained, leading to some of the Rademacher bounds in Yin et al. (2018); Khim & Loh 2 characterization. Instead, we prove Lemma 4.5 by decomposing the adversarially perturbed network into its nonperturbed term and the value added by the perturbation. The nonperturbed term can then be handled by prior Rademacher bound for standard networks. The difficult part is in bounding the complexity added by the perturbation. A naive argument would worst-case the adversarial perturbations, resulting in perturbation term that scales linearly with and does not decrease with n. Obtaining the Rademacher bound that appears here requires better understanding of the adversarial perturbations.
al. (2020). In our setting, it is unclear how to get a similar exact
In comparison to simple linear models, we use a more sophisticated approach, utilizing our under- standing of linearized models. Because we are using the features the initial network, for a particular perturbation at a particular point, the same features are used across all networks. As the parameter distance between all networks is close, the same perturbation achieves similar effects. We also control the change in features caused by the perturbations, which is given by Lemma A.9 Having bounded the effect of the perturbation term, we then apply a covering argument over the parameter space to get the Rademacher bound.
4.3.2 OPTIMIZATION
Our optimization bound is as follows.
Lemma 4.6. Let Rgg 2Rz + np, with np² < 2. Then with probability at least 1 8,
R2
RA(W5d s)) < 2 n
R (2) ( +
2n 172
1
4/3 1/1 In(ed2 + 178p 1/3 In In(ed m/
52pR4/3 gd
ml //
2 - mp²
m/112
5p (n(1/))
+
5/6
8

---

Published as a conference paper at ICLR 2023
The main difference between the adversarial case here and the non non- adversaaal case in Ji al. (2021)
is in appropriately bounding || [/ (W)I,, which is Lemma A.10 In order to do so, we utilize relation between adversarial and non-adversarial losses. The rest of the adversarial optimization proofs follow similarly to the non-adversarial case, although simplified because assume that Rz
is known.
5 DISCUSSION AND OPEN PROBLEMS
This paper leaves open many potential avenues for future work, several of which we highlight below.
Early stopping. Early stopping played key technical role in our proofs, allowing us take advan- tage of properties that hold in wear-initialization regime, as well as achieve a good generalization bound. However, early stopping necessary?
The necessity of early stopping is suggested by the phenomenon of robust overfitting (Rice et al. 2020), in which the adversarial training error continues to decrease, but the adversarial test error dramatically increases after certain point. Early stopping is one method that allows adversarial training to avoid this phase, and achieve better adversarial test error as a result. However, should be noted that early stopping is necessary in this work to stay in the near-initialization regime, which likely occurs much earlier than the robust overfitting phase.
Our generalization bound increases with the width. As result, get our generalization bound to converge to 0 we required the width to be sublinear in the number of training points. Is it possible to remove this dependence on width?
Unddrparameeterization
Recent works suggest that some sort of dependence on the width may be necessary. In the setting of linear regression, overparameterization has been shown to hurt adversarial generalization for specific types of networks (Hassani & Javanmard| [2022] Javanmard et al. [020; Donhauser et al. (021). Note that in this simple data setting a simple network can fit the data, so underparameetrizzaionn does not hurt the approximation capabilities of the network.
However, in a more complicated data setting, Madry et al. (2019) notes that increased width helps with the adversarial test error. One explanation is that networks need to be sufficiently large to approximate an optimal robust predictor, which may be more complicated than optimal nonrobust predictors. Indeed, they note that smaller networks, under adversarial training, would converge to the trivial classifier of predicting a single class. Interestingly, they also note that width helps more when the adversarial perturbation radius is small. This observation is reflected in generalization bound, since the dependence on width is tied to the perturbation term. If the perturbation radius is small, then large width is less harmful to our generalization bound. We propose further empirical exploration into how the width affects generalization and approximation error, and how other factors influence this relationship. This includes investigating whether larger perturbation radius causes larger widths to be more harmful to the generalization bound, the effect of early stopping on these relationships, and how the approximation error for a given width changes with the perturbation radius.
Using weaker attacks. Within our proof used the assumption that had access to optimal adversarial attack. In turn, we got a guarantee against optimal adversarial attacks. However, in practice we do not know of computationally efficient algorithm for generating optimal attacks. Could we prove a similar theorem, getting a guarantee against optimal attacks, using weaker attack like PGD our training algorithm? If this was the case, then we would be using a weaker attack to successfully defend against stronger attack. Perhaps this is too much to ask for - could we get a guarantee against PGD attacks instead?
Transferability to other settings. We have only considered the binary classification setting here. natural extension would be to consider the same questions in the multiclass setting, where there are three (or more) possible labels. In addition, our results in Section only hold for shallow ReLU networks a inaariiitiaiittinnn regime. To what extent do the relationships observed here transfer to other settings, such training state-of-the the-art networks? For instance, does excessive overparameterizztion beyond the need to capture the complexity of the data hurt adversarial robustness in practice?

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors are grateful for support from the NSF under grant IIS-1750051.
REFERENCES
Charalambos Aliprantis and Kim C. Border. Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer, 3rd edition, 2006.
Martin Anthony and Peter L.. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1st edition, 2009.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR, 2019.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. CoRR, 10s..0002004 2018.
Pranjal Awasthi, Natalic Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. CoRR, abs/2004.11360 2020.
Pranjal Awasthi, Natalie Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consistency of adversarial surrogate losses. CoRR, hins2200400955. 2021a.
Pranjal Awasthi, Natalie S. Frank, and Mehryar Mohri. On the existence of the adversarial bayes classifier (extended version). CoRR, abs/2112.01625 2021b.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. finer calibration analysis for adversarial robustness. CoRR, abs/2105.01550, 2021c.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds for surrogate loss minimizers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 1117-1174. PMLR, 17-23 Jul 2022a.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-class H Hcconsistency bounds. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022b.
Emilio Rafael Balda, Arash Behboodi, Niklas Koep, and Rudolf Mathar. Adversarial risk bounds for neural networks through sparsity based compression. CoRR, hass/906.00699 2019.
Han Bao, Clay Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 408 451. PMLR, 09-12 Jul 2020.
A.R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information Theory, 39(3):930 945, 1993. doi: 10. 10.1109/18.25633 8,25500..
Peter L. Bartlett, Michael Jordan, and Jon Mcauliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006. ISSN 01621459.
Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robustness from optimal transport. CoRR, /ttp//99.122777 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks, 2019.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. CoRR, abs/1 01166680644444 2016.
10

---

Published as a conference paper at ICLR 2023
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameterization is sufficient to learn deep relu networks? CoRR, 1tt//9911122600 2019.
Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi,
Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. CoRR, abs/1803. 0442,,114222. 2018.
Konstantin Donhauser, Alexandru Tifrea, Michael Aerni, Reinhard Heckel, and Fanny Yang. Interpo- lation can hurt robust generalization even when there is no noise, 2021.
Simon S. Du, Xiyu Zhai, Barnabás P6czos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. CoRR, abs/1810.0205. 2018.
Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications. Wiley Interscience, 2nd edition, 1999.
Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsieh, and Jason D. Lee. Convergence of adversarial training in overparametrized networks. CoRR, abs/1906.07916. 2019.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, 2015.
Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens van der Maaten. Countering adversarial images using imput transformations. CoRR, abs/1711.001 2017.
Hamed Hassani and Adel Javanmard. The curse of overparametrizztion in adversarial training:
Precise analysis of robust generalization for random features regression, 2022.
José Hernández-Orallo, Peter Flach, and Cèsar Ferri. A unified view of performance metrics: Translating threshold choice into expected classification loss. Journal of Machine Learning Research, (801))288-128888 2012.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffss in adversarial training for linear regression. CoRR, abs/2002.10077, 2020.
Ziwei and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint /8Xiv:/803.074
2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. CoRR, abs/1909.12292, 2019.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. CoRR, abs/1910.06956, 2019.
Ziwei Ji, Justin D. Li, and Matus Telgarsky. Early-stopped neural networks are consistent. CORR, abs/2106.05932, 2021.
Harini Kannan, Alexey Kurakin, and Ian J. Goodfellow. Adversarial logit pairing. CoRR,
abs/ abs//803..mm 100.00033.6333 2018
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation, 2019.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. CoRR, Abs/1607.00253. 2016.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. CoRR, 0tt//8888.0200 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks, 2019.

---

Published as a conference paper at ICLR 2023
Takeru Miyato, Shin ichi Maeda, Masanori Koyama, and Shin Ishii Virtual adversarial training: A regularization method for supervised and semi cuni-supereieed learning, 2018.
Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient descent learn less parameterized two-layer neural networks on classification problems, 2020.
Muni Sreenivas Pydi and Varun Jog. Adversarial risk via optimal transport and optimal couplings. 2020.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. CoRR, abs/2002. 11569, 2020.
Leonard J. Savage.
Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336):783-80) 1971. ISSN 01621459.
Mark J. Schervish. A general method for comparing probability assessors. The Annals of Statistics, 17(4):186-1189, 1989. ISSN 00905364.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Dimitris Tsipras Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. 2019.
Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis of adversarial learning: A minimax approach, 2019.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. CoRR, 12.08344 2021.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan L. Yuille. Mitigating adversarial effects through randomization. CoRR, abs/1771.01991, 2017.
Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes, 2020.
Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversarially robust generalization. CoRR, abs/1810) 110. 1914, 2018.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing. Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. CoRR, abs/1901.08573, 2019.
Tong Zhang. Statistical behavior and consistency classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56 85, 2004. ISSN (19953364.
Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. CoRR, abs/2002.06668,, 2020.
A
APPENDIX
A.1 1 OPTIMAL ADVERSARIAL PREDICTOR AND APPROXIMATION PROOFS
In this section we prove various properties of optimal adversarial predictors. First we need to handle some basic limits.
12

---

Published as a conference paper at ICLR 2023
Recall the definition of Razz(f)
Riz(f)== = f +1 ( - ((( (((-(((t))) du(z,,).
The following lemmas various forms of continuity for (f) making of the continuity of
Lemma A.1. For any infinite family of predictors 9. : X - (-1,+1} indexed by E R, and any
1 e I,
lim (g.) Riz (gx)
Proof. By the Dominated Convergence Theorem (Folland 1999 Theorem 2.24),
lim (g,) - Raz(ga))
/ - (10) (-((s))
lim
+ [bb=-])1b[00> (-f((-))) du(a,y)
$ lim / 1ly --)((-(()))-((((
+ + - (-fo(-s)) dp(z,
$ / 1/y = +1] -(--((()))--((())))
- (-((())
+ 1ly - - (-6 -(-E((s)) (-5))) 8)
0.
The following lemma allows us to switch the order of the limit and adversarial risk.
Lemma A.2. For any predictors 9s X + {-1,+1] +1} indexed by s E R, and any E R.
lim Ra,( = R2Az lim 9o s
when lim 9s exists. In particular, when gs = S for all E R, then lim Riz(s) = Rizz (f).
Proof. By the Dominated Convergence Theorem Folland 1999 Theorem 2.24).
lim (gz(
/
-lim
[ly = +1|
fly 1-1-==1[[0 1] (x) (
5-1
f
lim
1ly 111(0 2 ([(-E(()))) du( v)
limm
f [ly +1|1
lim go (x) 0 (t) x-
+ [/y
1|
lim lim (x) 0 (-(((-t) du(x, v)
Rizz
lim gs s
13

---

Published as a conference paper at ICLR 2023
For the rest of this section, let f. : X (-1,++11 be optimal adversarial zero-one predictors when the -1 labels are given weight (-r) and the +1 labels are given weight (-é, (r)) (fr minimizes (fz(fr), for all R. These predictors exist by Theorem 1 of Bhagoji et al. (2019), although they may not be unique. The following lemma states that (fz) is continuous as a function of r.
Lemma A.3. For any E R. lim (fx( Riz((f).
8-2
Proof. By Lemma A.1
lim sup sup (Ja) - (s1) = lim sup (Sa( - RAz( S 0, 8-2
8-1
inf (ffos) - RFzz(f)= = lim inf (ffe - Riiz(f) 2 0.
8-3
8-26
Together, we get lim (f,) = (xtz
s-1
The following lemma gives some structure to optimal adversarial zero-one predictors. Lemma A.4. For any S t, R&z (max(fe. f.)) (fa) and (min fa)) (fa)
Proof. Let A= = fa fz( < f((x)), and define
A {(x.+1): ( f. S
A, (( \) (-1)),
A ((a= (+1}),
Let ps (2, 3) = 1B = ((2-1));90000444000600))0)111111 -1) be the associated
AT =
measures when the +1 labels have weight (-(((+) and the -1 labels have weight (-f((-)) and define Mr similarly. Then
pa(At)= = ((- (A77,, = mc(A)))
Ma(A,) = (-( (-( (( As result,
- (a,)) 2 (((A)))((A)
The reweighted adversarial zero-one loss can be written in terms of the reweighted measures, as follows.
Riz(1)= = f
f fly 1 (+) < -)({((()))
(x)
= 2 +1 ()-((
= /
< +1y=- 2 (x)
The following lower bound then be computed.
RAa(mmx (ft, fs)) Rāz(fa)
/ lyy = +1] (
+1 - (1m) -1f+((x)( 2 0) d2)(
= =-1((At) + (A7,))
2 0.
Similarly,
Riz (minmmfee - Ria(fa)
/ 1/ = +1] [1 <x) (0
+ +1 1] - 0) dx,(x.g)
= - -
20.
14

---

Published as a conference paper at ICLR 2023
As 0 (A,) N. (a(A)) (((A)) mc(AA) 2 0 we must have equality everywhere, giving the desired result.
Using our understanding of optimal adversarial zero-one predictors, we can construct a predictor that is optimal at all thresholds.
Lemma A.5. There exists f : X + IR such that R - 1) is the minimum possible value for all t e R.
Proof. Define f(x) supfr e [x) +1}. To prove Ri is minimal for all t R, we first do so for all E Q and then for all t E E E Q
For any i Q. by definition - Jr. Let 9ı 92.... ... be an enumeration of Q n (t, oo). Let 9o = ft. and recursively define 0i+1 max fa; for all i 2 0. Note that lim; 9i = sgn( - l). Inductively applying Lemma A.4 results in ((z( R (fe)) for all 2 0. By the Dominated
Convergence Theorem (Folland 1999 Theorem 2.24),
(f - = Riz(sgn(f t))
RiA
lim gi 1-000
lim Riaz(gi) +1000
lim R(z((s)
For any / E R \ Q, note that sgn(J 1) lim stt sgn(J - s). By the Dominated Convergence #50
Theorem Folland 1999
Theorem 2.24), Lemma
A.2 and Lemma A.3
Ri Rigns - t))
Rriz(lim (limsgn(( s))
stt .EQ
lim RRzz(sgn) -)) 872
.EQ
lim Riz(fs) att
=EQ R(z(f().
For any predictor, its adversarial convex loss can be written as weighted sum of adversarial zero-one losses across thresholds. This then implies the function defined Lemmal A.5 has optimal adversarial convex loss.
Proof of Lemma 3.1 Recall the definition of RA (f):
Ra(5) [1ly +1).0 (x)) Ily - (](c(-f++xx)) dp(x, v).
15

---

Published as a conference paper at ICLR 2023
Applying the fundamental theorem of calculus and rearranging,
/
1 +1| { (-L dt + -1] [_y1cs (-(((t) dt du(a,
Ra(f)-
/
1/y +1| / 1[ (x) < ((((((()))
+ +1-y= f1ly=-1] / (x)
2 -1((((-))))) dt du(a,,)
- - (+)= <
+ (1==-111f dt du(z, v)
As the integrand nonnegative, Tonelli's theorem (Folland 1999
Theorem 2.37) gives
RA(F) = 00
+ +1yy=-111[(t))) 2 (()-((-t)) v)
dt
Ri -
dt. dt.
While optimal adversarial zero-one predictors were used construct predictor with optimal adversarial convex loss in Lemma the reverse is also possible: using predictor with optimal adversarial convex loss to construct optimal adversarial zero-one predictors.
Proof of Lemma 3.2 Let be the optimal predictor defined in Lemma A.5 which gives existence. Suppose, towards contradiction, that there exists X -> IR with minimal RA (g) and E R such that 2g - >> (f - t). By Lemma A.2 Ag f) left continuous as a function of 4, and by Lemma A.3 R (f t) is continuous as a function of t. As result, there exists 6, e > 0 such
that for all E t).
Rizlg 8) - 26
Then
00
Ra(g) - RA( =
Rizlg - - -Raz(s 88
2 Rizlg - -s) - -f -8) ds
1-8
> eds de O,
contradicting the assumption that Rg( was minimal, So we must have Riz( - -) minimal for all
t IR.
The next two lemmas bound the zero-one loss different thresholds in terms of the zero-one loss threshold 0.
Lemma A.6. Let f be the optimal predictor defined in Lemma A.S Then Ra - t) S (-((())))RRz(())
16

---

Published as a conference paper at ICLR 2023
Proof.
RA -1)
- / fly = [00--110000010000000000000122120
< / 1ly 1M0-1110770000000000011110001100
Σ / 1yy 1111::/:000000000000001011001000
< (- (z1))
In contrast to the previous lemma, the following bound works for any predictor.
Lemma A.7. Let be any predictor. Then Riz(9 - t) 2 (- (-(,(1)))Rz2l t).
Proof.
Ri -
/ Lly = +1]1ig < + 1(y= -100 du(x,
2 / 1ly = +1|1ig (z) =((--((()) + 1ly = -111|0 2 t]( (1(-2 ((t) du(z, y)
(-((1)))~~Z2 1).
Now we can relate proximity to the optimal adversarial zero-one loss and proximity to the optimal adversarial convex loss.
Proof of Theorem 3.3 Let f be the optimal predictor defined in Lemma A.5
Then
Ra(g)
inf meas.
(h) Ra(g) - RA(F)
Rx uu -R u) du
max(0, (-E u) -(((((-lu)))RA((()) du
(-E inf RNz(g (-(((-lu)))RA du
max(0, ( (-( inf Razlg - t) (-(((-u) du.
As (u) inf, Raz(g- - 1) - (-C((-u)) is continuous and nonincreasing as a function of u, as well as nonnegative when u = 0, there exists some r E [0, oc] such that
(0 (u) inl Rizla - 1) 1)
du
- (-C(())) inf Raz(g t) - (-f du.
17

---

Published as a conference paper at ICLR 2023
inf, Raz(g-t) Letting p Riz(s)+inf, Rxzla-t); we find that this occurs when
(-((r)) inf Raz(a - 1) - (-(((--)))A((())) 0
(r) RAZ(s)
Pd(-r) Raz -t)
(d(r+ + -((-r)
Rxz(f) + inf, Raz(g -t)
(((-T)
inf, RAZ - 1) inf, RAz - 1) RRx(ff) + inf, Raz(g - -)
(((-)
+ + (-(-))
(((r))
(-rr) P
(((r)= - (C.(r) + +r(--r) p
(1-))) =0.
Since le is convex, this implies minimizes plc(r) (1 p))c(-r). The integral can then be computed exactly as follows.
Rg(9) inf Ra(h) meas.
2
(n) - t) --
(6((0) - (c(r)) inf Raz(g - t) - (la(-r) (c) RaZ(F)
= 2
(6()) (Raa()) + inl RAzl1- - 1) La(r) Razly - 1) (c(-r)RAz(()
(0)
RaZ(f) + inf RaZlg - 11)
inf, Raz(g 1) (a(r)) (az(f) + inff, Raz(g- -t) + fc(-r)
Raz(s) Rxz(f) + inf, Razlg - t)
(RA(()) + inf Razlg - 11)
(c(0) Raz(f)) + inf Razlg- - t)
(co(r)p (o(-r)(1 -p)) (Raz(f) + inf RazlR b) 2 Raz(f) inf Raz(g - 1) (c(0))(p66))) +
(1- +11 -))))()-))
2 RAz(s) + inl Razlg - 1) Gc.()).
Using our assumption of lower bound on Ge, (p) results in
RAz(f) inf RAz(g (t)( :)) ( 12p 1 (120-112 RAz(f) + inf Raz(g - :)
Rx(g)
RA(h) 2 inf meas.
c
(inf, Razlg 1) RAz(g-t) Raz(f) *
c²
Raz(f) + inf, Raz(g - t)
2
(inf, Raz(g - 1) Rrz(
(Raz(f) + inf, Razlg t))
18

---

Published as a conference paper at ICLR 2023
Finally, since Raz(f)= & 1/2 and inf, Raz(9
S 1,
2
inf Ra -t) -Rxx(f)))
(g) inf mens.
RA (h)
2
3
c
2
-)- inf - -t) - inf Raz(h))
c=
meas.
Rearranging then gives the desired inequality.
The following lemmas states that continuous predictors can get arbitrarily close the optimal adversarial zero-one risk, even if we require the predictors to output the exact label.
Lemma A.8. Define
ReAz(f) l(u(((())) # {+1])du(Za.))
the adversarial zero-one risk when we require f to exactly output the right label over the entire perturbation set. Then for any measurable f :X + 1-1,+ +1} and any e 0, there exists continuous g X - 11] such that u(((r,)) (P(((x)) & [+1] and y (P())) = {+1}}) < In par- ticular, this implies inf, cts. ggA = inf REAZ(h) = inf, ets. RAz(g) = inf meas. Rxz(h).
Proof. Let
A (x: fx() 1}}
P(A) = U(rr)(r))
B = {a : f (x) -1},
P(B) UZEBP(r)
By the inner regularity of uz (Folland 1999.
Theorem 7.8), there exist compact sets K C A, C B
such that
(A) (m(() < t/2, Ma (B Mr (L) E/2.
As P is upper hemicontinuous and K and L are compact, both P(K) and P(L) are also compact (Aliprantis & Border 2006 Lemma 17.8). Note that they are also disjoint as P(K) P(L) S P P(B) = 0. By Urysohn's 's Lemma (Folland 1999 Lemma 4.32), there exists continuous function g X - [o, 1] such that go (x) 0 for all E P(K,) and (x) for all P(L).
The continuous function 2g - 1: X + [, then satisfies
p({(z, 8) : (2g 1)(P(z)) # (+1} and yf(P(z)) (+1}))
- (A (A) + (B) \ L)) <e
(A
Note that we also have
Reaz(2g - 1) < REAZ(F) + Mo(A) ( K) - Mz L) < REAZ(f) +e.
As of and > 0 were arbitrary, inf as. RgN S inf meas. (E)
To get the implication, note that inf inf cts. Raz(g) < inf cts. REAZ(g) < inf meas. inf, mens. (h) < inf, g Rx)(g). we must have equality everywhere.
meas. Reaz(h)
While the optimal adversarial predictor may be discontinuous, continuous predictors can get arbitrarily close to the optimal adversarial convex risk.
Proof of Lemma 3.4 We have inf Ra(g) inf, cts. (x) S inf, meas. RA (h).
inf, meas. Rh).). so suffices to show
Let be the optimal predictor defined Lemma A.5 Then RA(f) = inf, meas. RA (h), so we want to show inf g ess. Rx(g) < Rf).).
19

---

Published as a conference paper at ICLR 2023
Let O. Choose M 0 large enough so that (a(min(max((.. -M), RA(f) + c/3. and let f = min
MMM As le continuous, there exists a finite-sized partition = {po, P1, ................................ Pp with Po - M and pr = M such that (x(p,) (a(P--1) - e/3 and (<(-p:)
Pc(-Pi1) S e/3 for all 1 S S
By Lemma A.8 for every p: there exists continuous 9p.
X [-1,+1] such that ((((2, v)
v9p. (P(x)) + [+ and ysgn( f p)) =
3r 3r(fc(-M)-<c(MM))
Consider the continuous function = M + Ei=(p; (p: - -Pi-1) g0, adversarial risk within of the optimal. Define
2 which will be shown to have
Dj = {xx y) 99p. (P(x)) # [+1] and ysgn(s pı) (p) VI,
E = {zz, y) (2, > (x v. f) + e/3).
will now show that C - Dr. Let (a, v) & Uب D.. Then y9p, (P(x)) ysgn(s (P)()) for all S S r. Let 1' arg max, (sgn(f - p:) +1}. Then yg. (P(x)) 2 min (Pmox((+1r)) and vf(((x)) S max ( v.) max((c(ypr) (e(VPmux(( 1 minffe minfle(ypr)) ( (c())mxx(++1)))) + ce/ S S f) + t/3,
which implies (x,1)= $ E. Consequently,
e 3 (ec(- M) - (MMM)
m(E)= < ((D) <
3r (lc(- (c(M))
Combining the bounds results in
inf (g( S Ra(ge)
g cts.
RR((F + t/33 + ((B) (lo(-M) Lc(M)
< RA(s) + c/33+ + c/3 x/3+//3 c
= RR(s) +
As this holds for all E > 0, we have infg Ra(g) S RA(J), completing the proof.
A.2 GENERALIZATION PROOFS
The following lemma controls the difference in features for nearby points, which will be useful when proving our Rademacher complexity bound.
Lemma A.9. With probability at least 3nd,
1 max Vf(zz; Wo) - V + dx: Wo)l S 2F
32r ln(1/)) 1/4
+ +
P T
m
for all
Proof. As in Lemma A.2 of li al. 2021). with probability least 3no, for any o% # 0.
Σ 1 Al zxl Txl[zx mt, + S/mr ln(1/)),
and henceforth assume the failure event does not hold. With Tk
T we have, for any os # O.
Smr In (m(88)
Σ 1 1llwb,rrk
<]
||>
|xx]
20

---

Published as a conference paper at ICLR 2023
As such, define the set Sk = {i l I T, sgn(w0,,50
o sgn wh (ox + do))) where the
preceding concentration inequality implies |Sk] S T
8mm lu(1/o) for all vr # 0. Then for any 1
Ik (including zyk = 0) and any ||6 S т,
[f Wo) Vf( + dz; Wo
The (1. 2k 2 0] (ax + 3 (10 (x2 + 06) 2 0] l
2
mx [w) 2h 2 0] xx (I& + 5k) 2 o
m71
2
Σ
2 (10b + 5x) 2 0] (#x 6g) (Ix + +xx) 2 o|l2
m
As Sy is exactly the set of indices j over which [ 2 0] could possibly differ from 11 [wb (1
5k) 2 0). we can restrict the sum in the first term to these indices, resulting in
Vf(=k; Wo) - vf(x + 66; Wo)l
<
2
Σ
||
[1 2 0J 1 1[wo, (ox + 0b) 2 01)²
m
jES
2
b [w0, + 6x) 2 0/
+ m
+ 27"
m
32r In(1/8) + 2
$ 2T +
m
where we used |2 || I 1 in the last step. Taking the square root of both sides gives
1/4 332 (32T1((100)
[f(x;; vf(ax + 86; Wo)l V2T
+ +/22,
m
completing the proof.
We will now prove Rademacher complexity bound.
21

---

Published as a conference paper at ICLR 2023
Proof of Lemma 4.3
We have
B
(F)
Eg sup VEV
ck
min = (P(x)
yk (V)( Wo). v)
E. sup
Σ
Ck
min yk (VI(1) Wo).V) yu (VS(r):W)) (LEP(z)))
VEV k=1
+ ERUb (Vf(z Wo). v)
S Ex sup VEV
Ek
min y/ (Vi(<(:WW) V//(x; Wo), v)(ex; (P(a))
E. sup UEV
ERyR (Vf(z Wo).
n < E, sup VEV k=1
Σ
Ck
min (PP())
y/ (Vf(<<; vf( Wo), v)
+ pBVn,
where in the last step we use the Rademacher bound provided in the proof of Lemma A.8 from Ji et al. 2021).
We now focus bounding E. sup VEV
Σe 6k
min EP(()
ys (VI( Wo) 1 (s Wo).
For notational simplicity let D&(V)
min (P(()
Yk (Vi(a); Wo) Vf(2:: V). so that the
n Σ (v). VEV
quantity we want bound can be rewritten E, sup
As Rademacher complexity is invariant under constant shifts, we can subtract the constant C2 from D&(V), where Ck := (suPre (V) + infvew Dx(V))
2
With this constant shift, the expression becomes E, sup Vev
Σ Ek (D&(V) C+) nRad(g)), where
{Ir +
min yu (Vi( Wo) Vf(z;; Wo), V) - C vel V}.
(((L)
We will now bound nga using a covering argument in the parameter space V.
Instead of directly finding covering for the ball of radius B, first find a covering for cube with side length 2B containing the ball. Projecting the cube to the ball then yields a proper covering of the ball, as this mapping non-expansive. To ensure every point the surface of the cube is at most distance away from point, we use grid with scale 2c/ /mm, which results in B.m points in the cover. This cover C. has the property that for every V E V, there is some U E C. such that VV Ti < since every coordinate of V is e/ym-cllse IIV WV-UUp Ul| mapping from the cube to the sphere, the e-cover for the cube projects to an e-cover for the sphere. points.
coordinate in Cc, and Due the non-expansive projection
V
U.
As result, we have an e-cover for the sphere of radius B with
Bym
22

---

Published as a conference paper at ICLR 2023
A geometric e-cover gives only pře-cover in the function space, since for any V and U with IV U|| I e, and any 2k:
min yh (VI(vv;Wo) - vs(z;; Wo), V) - Ca) aVEP(aL)
min yk (VI(zu; Wo) - Vx((x Wo), U) - Ckk (UEP(EE)
< sup IV Si 20 (Pma))
min #vEP(())
Us (Vf(ar; - Vf(=x: Wo), V) Cx)
- -(uh (Vf(zu: Wo) Vf(x CG)
(Vun(V)(Zo:wo)- - - Wo), - Ci
sup | zo EP(()
(In (Vf(zu:Wo) Vo)x::Wo), -Ca) Ct))
yyk (Vf(ru:Wo) - Vf( Wo), V - -U})
sup IV-U 20EP(
sup zu (((a))
[V](r;; Wo) Vf(ax; Wo) UI
sup 160 1
Vf Wo)
- U
přc,
where the last step follows with probability at least 38 by Lemma A.9
As result, we can get an e-cover in the function space with just (BFym
points.
This bound on the covering number AVG (1-1u))
(BBFym)
then implices
pB /mn
N(g.c, c 112) s N(G 11a)
which we can use a standard parameter-base based covering argument (Anthony & Bartlett 2009 to get
nRad(9) < inf
avá+
sup NEg
|U1|
V2lnN( a, 1112)
a>0
p mn
< inf a20
av + (pBivn)
2
To calculate supueg ||U||2 note that each of the entries is bounded above by
Dz(V) Ck: - ( inf D2(U) - C+ ) VEW
sup VEE
D&(V) - C+ = max
sup
(vev
suPvev DL(V) infuev Di(U))
p42B
pBF
23

---

Published as a conference paper at ICLR 2023
so su ||0||2 pBt
Setting a = pBT (let a - 0 i = 0) we get
mn
mn In nRad(G)) < SBBiv pBf mn
72
Putting this together with our previous bound results in
gR) S pB RRRd(FF) S (Ra()+
pBivn
11
m In
mn
72
and dividing by n then completes the proof.
With our Rademacher complexity bound we can prove our generalization bound, as follows.
Proof of Lemma 4.4
By Lemma A.6 part of et (2021 with probability at least 5,
(f Wo), v) I 18pB In(emd(1 + 3(md)/2)0)/6)
sup [ <B |
sup
18pBdln(4em2dd
By the decreasing monotonicity of the logistic loss,
sup sup (x y, (V](: Wo), V))
w |
E [(18pBd (118pdd)ee /5)]
S [2n(2) 18pBdIn(4em' d² (6), In(2) + 18pBd In(emm /6)].
With a bound the range from above that holds with probability at least 1 5 and a bound on the Rademacher complexity from Lemma 4.5 that holds with probability at least 1 - 36, we can now apply a standard Rademacher bound (Shalev-Shwarzz at least 1 - to get that altogether with probability at least
Shwartz & Ben- Ben-David, (2014) that holds with probability 50,
In(4//) 2n
R (V) - R200 R (V)
< 2Rad (RRa((A(FF)) + Bn3 (2)))2/)/))))))))
sup [|V-
Wollsn
< 2 PB
+ 2BP
mn
77pBd 1n32 (4em d8/8)
Vnl
V
1 + V
m
72
+
Vn
A.3 OPTIMIZATION PROOFS
The following lemma bounds the gradient the adversarial risk.
Lemma A.10. For any matrix W E R.mxd
/RA s pmin 1 (11)).
24

---

Published as a conference paper at ICLR 2023
Proof. By properties of the logistic loss (Ji & Telgarsky 2018).
(m)
min ()P())
yk (Waark)
A
min yh (WW(W))
m1 (x(x)
E' min yh (&W (PP())
A
min m1 (((x)
yt (WW
)
|
min UkJ(W;ak) 5 x)p((z))
min (k((W;))) x)E((s))
}
min 1,6
min 3nf(W; o(Ep)(a))
min (1.aa((f)) P
k=1
S pmin { L, RW]3
We have the following guarantee when using adversarial training. Lemma A.11. When adversarially training with step size n, for any iterate t and any reference parameters Z E Rmxxd x
[|, - Z (2n Σ RA,,) s IW Z1I² + 2n Σ R10 (Z).
K
Proof. It suffices show
W (2n- (2n < I|W; -| + 22 (2) (2)
for 0 < < I, as summing the left- and right-hand sides over < then gives the desired bound.
By the definition of W1+1.
WH+1 - 2112 = IW, - 212 2m WW,, - 2)+ +n² (Wa))
Note that
-2 (VRA(W.), W, -2) -)= = 2n (W,,,, W.
2n VRA (W.,, W,
VR (W,). 2- W,
2n
S 21 R1)) (Z) - (wa).
where the last inequality follows because (00 (W) R. (F(0) (f(O((())))) (W;+)) :)) is convex in the function space A
(W:-), which in turn linear in W, so R(0 (W) is convex in W.
Using this bound, in addition to Lemma A.10 gives
WH+1 2 IW 2 + 2n (R - ((((())) + p
and rearranging then gives the desired inequality.
25

---

Published as a conference paper at ICLR 2023
We want bound R (2) in terms of R, the value at every point remains close to its original value. Towards this goal, we first show that the features small ball do change much.
(0) (Z). To do so, we will show that when changing features
Lemma A.12. For any | S and any S (dmm), with probability at least
sup -
[V V) - v[(=;
|=||<] I1V WollsRv
[n(edmm00 1/4
TpRRy/ m m-mmm//// 1/6 11/6 (In(em/8)) 12pd-/1 (In(em/6)) 1/3 2pe + 15p
m
Proof. For notational convenience let W = Wo- First, note that
V)
$ V/f V/ V vf(2; V)Il
By Lemma A.5 of Ji et al. (202). with probability at least 1 the middle term is bounded by
(Ineddm/0) 1/4
[V W)
vf(2; WIll 11p
m
The first and last terms are both bounded by sup
| =| ||||| <T
W)ll, so we will
IV Wy
now focus on bounding this term. Note that
V) Vf(x:W) m
aj 1 2 0] 1[wf 2 0] e,x".
We consider cases: || S (A: 1)e and |||||| > (k: + 1)e, for some k: 2 1 be determined later.
Case 1: ||0||| S (k: + 1)c.
Then [a; V) vf(x:W) & L vm + 1)c = (I 1)pc.
Case 2: ||>||| > (k + 1)c.
Then ||=|| > kc. With probability at least 1 mo, ||w1|l S Vd+ (2 for all S S m Define
S {i [m] |w]e| S |||=1|
S2 {i E [m] +luJal r||=]||
S3 {i [m] 11e, wyll 2 r)
5 S₂ Sa:
where g: = 2 (r+ 1 v + 1. 25/2n(115)) with parameter we will choose later. Note that
S2 C Si, since if in]Ta < r|| then
+ i I|wslllaa|| = (r+ |10yy]] ||:|||
|u]e| |u]ar + ||wz/le = r||k=||
1 k < k (r+
1
||w/|]
|||||| < 2 r vd (222(1155) ||||| < g||=/|
By Lemma A.2 part I of Ji al.
1 we have that with probability least 1 - 36, |S2 <
qm++ + V8qmln(1 Within the proof of Lemma A.7 part of et al. 2002 it is shown that
26

---

Published as a conference paper at ICLR 2023
|Sa] < / So altogether, with probability at least (m + 3)6,
|S| & | + S
R2 x2
S qm + 8qm ( +
2 r
1 Vd++ 1
(211(110) m+ + 16
r+
1 Va
1
/221(1100) m mln(1/0)
k
K
x:
Rt
72
1
Vd+ V21n(1165 my mVln(e/8) +
R2
r
h
y²
3 /dlnle/6) my mm/n(e/0)
R2
r+ k
2²
6rm//n(e/8) (8m(//)()/0)
Rt ,2
Setting r = R2/3 m 1/3 In (n(/0))-1/6 we get |S|
S 7R
7/22/322/ m2/3 (In(e/8)) 1/3 +
18m (n(e/5)
Substituting this upper bound on |.S] results in
- Vfx; VV Will
mm x
P
S
m
P
(3
/3 m
1/3 (In(e/6)) 1/6
+ 5m /n(e//))
m
3 /3 m 1/6 (In(e/8)) 1/6
+ +5pd /In(e/)).
Combining the two cases results in [Vf(<;;) V) ff(x;; W|]l
$ max + pc, R/ /0m////mm11/// 11/6 (In(e/6)) 1/6 + 5pd //n////B)///((//))))
After setting k = 2//3 (In(e/8)) 1/3
to balance the terms,
[V - V fz; Will
< max /6 1/3 (In(e/o)) 1/3
+ pe, pe, 3pR2/3 m- (In(e/8)) 1/6 + 50d (In(e/0)) 1/3
1/6 + /0 1/3 (In(e/0)) 2/3 pe. < 3pRp m 1/6 (In(e/))
So with probability at least - (m + 3)5
sup 5e | IV-IISRR-
VV Vf(;; V)ll
In(edm/0) 1/4
< 66pRt/3 m- 116 (In(e/8)) 1/6 10pd /9/1/3 1/3 (In(e/8)) 1/3 2pe + 11p
m
Rescaling the probability of failure, we get that with probability at least 1 - 6,
sup
[V]((;; V=(+V)
||--=||s< | -WWISRR
IIneedm/ (8)
1/4
< <TpR1/3 m 1/6 (ln(em/6)) 12pa-/6 (In(em/6)) 2pc + 15p
m
27

---

Published as a conference paper at ICLR 2023
Using sphere covering argument, bound ( terms of R R (Z).
(Z) in terms of R2
(2). as well as R(0 in
Lemma A.13. 1. For any ||=|| S and Ry 2 and Rg 2 0, with probability at least 1 - 6,
(VI(<;V) Vs(;:W)) B)
sup | V Wollsny
B- RB
26p( RB + Ry Ry d In(edmm2/5))
89p(RB + Rv / In(edmm² m² /8)//
+
m/6
1/1
5m//0(110)
dm
2. With probability least 6, simultaneously
R (B) R (B)
sup
W. Rv
|B-Wo Wol &Ra
26p(PA + Ryy ) R 02/2 In(edd m² /88/2///
89p(RB + Rv dd2/3 In(ed m2 /0)2/3
m/6
2/4
5p 5p/1m(110) In(1/8)
dm
and
(B) - (B)
sup W: WollWol|-R 1B-Wo Wol SRn
26p(R, RBB + Rv R 1/3 d2/4 In(eddm m22 /8
80p(Rs + Ry Rd3 In(ed 15/1///3
1/6
m 1/4
5p//m(110)
dm
Proof.
1. For notational convenience let W := Wo- For some 0 < E S 1/(dm) which we will choose later, instantiate cover C at scale /d,,, with |C| S (Vd/e)*, For given point let z denote the closest point the cover. Then by the triangle inequality.
sup |ar] |VIWI W
Ry
B W R
[V WV WV)
sup VV
B WI| R
+ (VS(<V W)(::)
(VI(=;)) VV(2 -V(=),) / -V)
<
sup
|x]
[V WI|Ssy By [0-W|RR,
(Vf(2; -)
28

---

Published as a conference paper at ICLR 2023
Upper bounding this expression by taking the supremum separately over each of terms,
(Vf(z;V) V), VV( +
-
sup |= IV Ry
sup
|V- ||
gRy
B
W
R
BB-W R
VV B)
sup | & S
and noticing the second term is bounded above by the first term, results in
(V](=;V) Wx W), B)
sup 1 <1
Sy
B3 W Rg
sup
<Vf(<z - B)
B) +
sup |
Vf(2;
|a 11 V Ry
RV- [8-W -t
B RR
-V/(a/))vv/++)>>, VV + V)
sup | <1
VV Ry
B- 3B
-
sup
|
IV-W WR
SSRn
2[[Vf(z;VV V + Rv) 22)xa V(=
sup
V Sy
B SR
-V)(:\)-VV( W))
sup
|
IV W &y
B3 S
Instantiating Lemma A.7 part 1 of et al. (2021) for all 2 E C, we get that with probability at
least 3(vd/e)46,
3p(RB 2Rv Ry In(e/8)2/4
W); [VS(Z; V5 W), BY
1/16
By Lemma A.2 part 2 of Ji et al. 2021), with probability at least - (Vd/e) IIWI S
(vm+ vd v (21(11((vV/e)
Assuming this holds, then for all || | Se
f(; =
a (c(ofx) < alt}3) -((o2)
m
u.J u32/ S v V 211 S p(Rr + [[]])
v m
< p(Rv + vm + vd + In((I(((Vd/e))d))
Instantiating Lemma A.12 for all = E C, we get that with probability at least - (Vdl/e385
sup 1 V W RR
[Vf(x; f2(;
S 7 T/R m 1/66 (In(em/8)) 1/6 (In(edm/8) 1/4
+ 16 (In(em/5)) 1/3 + 2pc
+ 15p
m
29

---

Published as a conference paper at ICLR 2023
Altogether, with probability at least 1 5(vd/e)/8,
VV
sup |
I ---W gRy B W Rg
2 7pRy 1/3 mmm m-16 (In(em/6)) 1/6
+ 12 (In(em/6)) 1/3
+ 2pc
[n(edm/0) 1/4
+ 15p
(RB Rv)
m
+ 2p + vm vd+ V2
+ 3p(RB ) R In(e/5)1/4
m 1/6
Setting (dmm) we get with probability at least 5(dvdm))
20p( Rs + Rv Rt In(em/5)1/4
(Vi(z;V) VF(x; W),
sup | IV Ry BB RRg
m/6
64p RB + Rv) In /
m/4
2v 2p (n(1((v//cc00))
dm
Rescaling 8 get that with probability least 1 1- 6.
20p(RB Rv) 1/3 d2/4 In(ed mm² /8/2///4
[VI(<;)) V) (I;;;)), B)
sup | VV Sy B W R
m
64p(Rn Ra + Rv /22 In(5edd /2/2///3
1/4
2v 2/2pv (mp//n(5/// dm 26p( Ry R 1/3 2/4 In(ed
m
89p RB + Ry )d In(ed m² /8)1/3
1/4
5p 3p/1n(110)
dm
2. With probability least 1 6, the previous part holds. This part is then immediate conse- quence since the logistic loss is 1-Lipschitz.
We now prove the main optimization lemma.
Proof of Lemma 4.6 We will use the fact that it does not matter much which feature use, because the function values on the domain will differ by a small amount, and hence the resulting difference in risk will be small. This is encapsulated by Lemma A.13
30

---

Published as a conference paper at ICLR 2023
We stop training once reach t iterations, or the parameter distance from initialization exceeds 2R2. That is, we stop at iteration T, where T min {t, inf { |W, Woll > 2R2}]. By definition [[W
Woll s 2Rx= I Ryd for all i T, and
| Woll S | Woll / - 22 + 7p Rga.
Then by Lemma A.13 part 2, we have that with probability at least - 8,
R24 (B) R (B)
sup no
BB
52pR //4 In(eddm /8)2/4 gd
1/3
178pRaad4/3 In(edd /8)//3 m/4
5p//m(11/0) K1-
1/6
dm
Note that this holds for all iterations of interest as well as when B represents the reference parameters.
By Lemma A. and the interchangeability of features, we get
T 2 (2n - p²) <<
Ra(W,) S 1 2 + 241
R(0 (7)
K<
S |W -1 + 2n
Σ
(R( (2) + k1)
KT
| - 212 + 21/TR 10)
A (2) + 24/Tn1.
Rearranging and using the definition of Ws gives
(W s.) S T K<T
Σ
S 2 Ra(W))
2
R
(1)
(Z)
+
2
+
W - WT 2
np²
2 np
T(2n 122
It remains to bound the term
712g -" I Z1e Note that if | -1 2 1 Z|1. we can
bound the term above by O. Otherwise, have
|| Woll S I|W Z| + 1 Woll < 2 - S 2R2,
so we must have T = L. Using this bound results in
W Z W 2
R2
T(2 p2
((21) 17 (2)*
giving us the final bound.
A.4 ADVERSARIAL TRAINING RESULTS
We can now prove our results on adversarial training.
Proof Theorem 4./ To bound the risk of final iterate, we will first linearize it, apply our generalization bound to get the linearized training risk, use our optimization lemma to get the linearized training risk of the reference model, and then repeat our steps in reverse get the risk of the linearized finite reference model. Let
4/pR4/3
4/3 d'/4 In(ed m² 15/ gd
178pRgad 13 In(edm23/8)11 5p (oV/n(1/))
R1
m 1/6
1/4
dm
2
27 Vn
mn 72
In 77
77d
3/2 (4em² 1 /6)))
Ky
1
In
vn
Vn
By Lemma
A.13 with probability at least - 8, we have (A <+) S R (Wsr) + and
R (W
RA
(W (t) 11. By Lemma 4.6 with probability at least 1 d, we have
2 (Z)
R2
2
RA gt) S np²
(0)0)
t(2n 72 p2
np
ni
31

---

Published as a conference paper at ICLR 2023
By Lemma 4.4 with probability at least 1 - 56, we have R, (Wst) S R, (Wst) + pRgakins and (0)
(W
with another probability at least 1 - 55 we have R (Z) I R (2) + pR Adding several of these inequalities together.
Ra(W S (Wg)) + K1,
S R2 (Wsr) + p
R (Wst) S s()
+ k1
RA (W - 2 n0²
2
R (Z) +
RZ
2
((21)) 12)
+
2 m10
K1
and cancelling results in
Ra(Ws)) S 2 ?pn R (Z) (Z) + t(2n p2)
2 100
R2
+ p + (2+ 2 np?
2
R1.
Using 11) S R (Z) pRak,, and simplifying gives the final bound, as follows.
RA(Ws)) st)
2
(0) (Z)
((2)) - 17 p2) +p Ryd +
RB
2
Rx
Kin +
2
2
np
2 2- 2-1p²
2 np?
2
RA
(0) (Z)
((2n) - 17 p2) + p
RT%
2R + up
2
Rz
d + vTm
np
np
vn
2
(2Rz + 1/3/1/1
(2 + np)a
1
p
2
2 np²
1/6
1/4
dm
(
2
R2
pRz (d + vTm)
pR m/6
4/3
/1/3
<
R1 (2)+
2 npp )
+
2
1p
vn
Setting parameters appropriately, we can make all terms in Theorem 4.1 small, and get arbitrarily close to the optimal adversarial convex loss. This is encapsulated by Corollaries 4.2 and 4.3 which we prove at the same time.
Proof of Corollary 4.2 and Corollary function h such that
4.3
By definition and by Lemma 3.4 can find continuous
(h( S inf (g) continuous} + e/2 = (R) measurable] + e/2.
By Theorem 4.3 of Ji et al. (2019), can find infinite-wide network 1f( [f( v2 (2: 1): U):
h( +/2 (z: 1))l < c/2, with associated R. == max(p, pp? sup,, UU (x)11}
< 20. Define Ri2 ==
Inemdd /8) + 20 (in(ed-mmm/ Then within the proof of Lemma A.1I of al. (021)) it is m²1/4
shown that with probability at least 1 - 65, we can sample finite width reference parameters Z such
that ( - (z; 1): - - (4; 1); ) S K2- By the triangle inequality, | 72 (z; 1); 2)
A (I; 1))l < K2 + e/2 for all ||ж||| < 1. So for any ||ق||| < 1, [e y. f( (z; 1):
(z y, h( (x; 1))) S K2 + c/2. As result.
1000 (2) - (b) + 22 c/2 < inf (Rx(g) measurable]- + K2 + 6.
32

---

Published as a conference paper at ICLR 2023
Combining this with Theorem 4.1 holding with probability at least 126, and altogether with probability at least 1 186,
RW St) S
2
R
(2) ())
+
((
R2
pRz (d + VTm)
plt d/i3
n
- m1p²
vn
m 1/6
2
2
<
inf (R\(g)} +
(K2 +6)
np
2 np²
R2
pRz
(d + vT
pRZ 1//3
2 2 mp²
77
Vn
m2/6
Corollary 4.2 then follows by setting parameters and reducing.
To get Corollary 4.3 let g(m) -2 Notice that for any 0, there exists n. such that for all
2 Ne. with probability at least - 1/n2,
RA(W inf (R) +e.
g meas.
Since Enzn, 1/n² co, by the Borel-Cantelli lemma we have
lim sup RA (W!r))
inf (Rx(g)} + meas.
==
almost surely.
As e > 0 was arbitrary, we get Corollary
33


Reviews:
[{"review_id": "endcR7oFX", "reviewer": "Reviewer_Quhe", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper provides generalization bounds for the adversarial risk of two-layers neural networks trained with early stopping and an ideal adversary (i.e., an adversary that computes perfect adversarial attacks). They do so by providing new results on the Rademacher complexity of the outcome of adversarial attacks on linearized two-layers NNs close to initialization.", "summary_of_the_review": "This paper is well written. The presentation of the contributions and the results is clear and the results seem significant (to the extent of my knowledge). It is a clear accept to me.  \n", "strength_and_weaknesses": "## Strengths:\n\n- The results seem novel\n- The question of learning efficient, robust classifiers is a critical question. Establishing connections between generalization and robustness is an important problem. \n- The paper is well written, and the authors made an effort to make the results accessible to a broad audience of experts. \n\n## Weaknesses: \n\n- This paper does not provide any experiments to test the gap between their theory and the practice. Since showing non-vacuous standard generalization bounds for NNs is not fully solved, it seems too much to expect it is the more challenging setting of adversarial test risk. However, I think the author could still propose some experimental exploration in the same vein as what they mention in the discussion. (more width helps, influence of the perturbation radius,...)  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TsHoQXC_a1", "reviewer": "Reviewer_k1gN", "summary": "", "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": "", "summary_of_the_paper": "This paper contains two parts. The first part discusses properties of optimal adversarial estimators w.r.t. convex loss and 0-1 loss, including their connection. The second part discusses adversarial lazy training of one-layer wide network, and demonstrates a convergence of population adversarial loss.", "summary_of_the_review": "I currently recommend marginal acceptance.\nAlthough the results are new, but it does depends on limited model setup.", "strength_and_weaknesses": "Strength: Overall the paper delivers reasonable theoretical results.\nWeakness: results in section 4 are restricted to a relatively simple model; results in section 3 and section 4 are not well integrated, and they feels like two separate topics.\n\nThm 4.1: I don't understand the role of t. If we let t go to infinite, the definition of W_{<=t} essentially doesn't change. However, one of the terms in upper bound decays to zero.\n\nCol 4.2: The condition says m needs to be bounded (big O notation). But I believe the author(s) means that m needs to be larger than the given rate.\n\nThe conditions of Lemma 4.4-4.6 are not mentioned in theorem 4.1.\n\nAccording to Thm 3.3, to get a good zero-one loss, one can train a model based on convex loss and tune the threshold t value. Does Fig 1 reflect this tuning?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HCy8S-EOgP", "reviewer": "Reviewer_7qcR", "summary": "", "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": "", "summary_of_the_paper": "The authors consider two problems: 1) relating convex surrogate losses with zero-ones losses in adversarial training; 2) bounding the (adversarial) convex risk of shallow ReLU networks. \n\nFor the former, the authors' results apply to a very broad setting -- arbitrary perturbation sets and general data distributions. They show a global relation between convex and zero-one losses. Previous work indicated that convex losses may not be calibrated, making them inadequate surrogates for the zero-one loss in adversarial settings. The authors show that if an optimal threshold is chosen, one can bound the zero-one loss via the convex surrogate.\n\nFor the latter problem, the authors restrict their attention to $\\ell_2$ perturbations. Following the approach of [2], the authors characterize the (adversarial) risk near initialization of training shallow ReLU networks using the logistic loss.", "summary_of_the_review": "The authors present novel ideas about convex surrogates for adversarial training, and extend previous works on generalization from standard training to the adversarial training. The paper is well-written. Overall, I believe it will be a valuable addition to the field. Thus, I recommend acceptance.", "strength_and_weaknesses": "# Strengths\n\nThe results connecting zero-one losses with convex surrogates are elegant and easy to follow. In particular, I like how the simple statement of Lemma 3.1 opens the door for the remaining results in Section 3.\n\n# Weaknesses\nThere are multiple axes along which the current paper falls short of applying to realistic settings: 1) the assumption that one is given an oracle adversary, i.e. we have access to the worst-case perturbation (as opposed to a noisy gradient oracle, i.e. just doing PGD); 2) the results in section 4 apply only to shallow fully-connected ReLU networks; 3) the results hold only in a regime very close to initialization and it is assumed one has an early stopping criterion/oracle.\n\nWeaknesses 2) and 3) are not unique to this work, and thus I heavily discount their severity when considering my overall recommendation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster