The Price of Implicit Bias in Adversarially Robust Generalization
Authors: Nikolaos Tsilivis
Natalie Frank
Nathan Srebro
Julia Kempe
Venue: NeurIPS 2024 poster (2024)
Keywords: Adversarial Robustness
Robust Generalization Gap
Implicit Bias
Optimisation
Generalization
Primary area: learning_theory
TL;DR: We study the importance of optimization in robust ERM and its connection to the (adversarially robust) generalization of the model.

Abstract: We study the implicit bias of optimization in robust empirical risk minimization (robust ERM) and its connection with robust generalization.  In classification settings under adversarial perturbations with linear models, we study what type of regularization should ideally be applied for a given perturbation set to improve (robust) generalization. We then show that the implicit bias of optimization in robust ERM can significantly affect the robustness of the model and identify two ways this can happen; either through the optimization algorithm or the architecture. We verify our predictions in simulations with synthetic data and experimentally study the importance of implicit bias in robust ERM with deep neural networks.

The Price of Implicit Bias in Adversarially Robust Generalization
Nikolaos Tsilivis" New York University nt2231 @nyu. edu
Natalie S. Frank New York University nf 1016@nyu.
Nathan Srebro TTI-Chicago nati@ttic. edu
Julia Kempe New York University Meta FAIR
kempeênyu. edu
Abstract
We study the implicit bias of optimization in robust empirical risk minimization (robust ERM) and its connection with robust generalization. In classification settings under adversarial perturbations with linear models, we study what type of regularization should ideally be applied for given perturbation set to improve (robust) generalization. We then show that the implicit bias of optimization in robust ERM can significantly affect the robustness of the model and identify two ways this can happen; either through the optimization algorithm or the architecture. We verify our predictions in simulations with synthetic data and experimentally study the importance of implicit bias in robust ERM with deep neural networks.
Introduction
Robustness is highly desired property of any machine learning system. Since the discovery of adversarial examples in deep neural networks (Szegedy et al., 2014 [Bggii al. 2013), adversarial robustness the ability of a model to withstand small, adversarial, perturbations of the input at test time has received significant attention. A canonical way to obtain robust model f. parameterized by w, is to optimize it for robustness during training, i.c. given set of training examples (x;, yı y optimize the empirical, worst-case, loss I, where worst-case refers to a predefined threat model A(-) which encodes notion of proximity for the task:
m
min W
Σ max I (f(xs w), ys). x(E((x))
772
This method of robust Empirical Risk Minimization (robust ERM aka adversarial training (Madry et al. 2018)) has been the workhorse in deep learning for optimizing robust models in the past few years. However, despite the outstanding performance of deep networks in "standard" classification settings, the same networks under robust ERM lag behind; progress, in terms of absolute performance, has stagnated measured on relevant benchmarks [Croce al. 2021] and predicted by experimental scaling laws for robustness [Debenedetti et af.] [023], and any advances mainly rely on extreme amounts of synthetic data (see, e.g., [Wang 2022)). Additionally, the (robust) generalization gap of neural networks obtained with robust ERM is large and, during training, networks typically exhibit overfitting [Rice al. 20200: (robust) test error goes up after initially going down, even though (robust) train error continues to decrease. How can we reconcile all this with the modern paradigm of deep learning, where overparameterized models interpolate their (even noisy) training data and seamlessly generalize to new inputs [Belkin| 2021]? What is different in robust ERM?
In "standard" classification, it is understood that the optimization procedure is responsible for capacity control during ERM [Neyshabur et al. 2015) and this in turn permits generalization.
Part of this work was done while author was with TTI-Chicago.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Class B
Class B
min &
Class
Class
min Eg
ERM (d 512, k, 512, kx
512)
Robust ERM (d 512, == 7 kw 512, 2.2,k,5500 512)
Generalization Gap
Robust Generalization Gap
80
80
60
60
%
m d
40
40
price of implicit blas
20
20
2
27
2
2
2 20
2
27
2
2
20
m
m
CD
GD
diag-net-GD
Figure 1: The price of implicit bias in adversarially robust generalization. Top: An illustration of the role of geometry in robust generalization: a separator that maximizes the & distance between the training points (circles) might suffer large error for test points (stars) perturbed within fo balls, while separator that maximizes the foo distance might generalize better. Bottom: Binary classification of Gaussian data with (right) or without (left) loo perturbations the input in Rd using linear models. We plot the (robust) generalization gap, i.e., (robust) train minus (robust) test accuracy, of different learning algorithms versus the training size m. standard ERM (e O), the algorithms generalize similarly. In robust ERM, however, the implicit bias of gradient descent is hurting the robust generalization of the models, while the implicit bias coordinate descent/gradient descent with diagonal linear networks aids it. See Section 4 for details.
We use the term capacity control to refer to the way that our algorithm imposes constraints on the hypotheses considered during learning; this can be achieved by means either explicit (e.g. weight decay [Krogh and Hertz 1991)) I) or implicit regularization [Neyshabur et al.) (2015) induced by the optimization algorithm [Soudry al. 2018 Gunasekar et al. [018a]. the loss function [Gunasekar et al. 201 8a). the architecture [unaasekar et al. 2018b] and more. This implicit bias of optimization towards empirical risk minimizers with small capacity (some kind of "norm"" what allows them to generalize, even in the absence of explicit regularization (Zhang et al., (207]) and can, at least partially, explain why gradient descent returns well-generalizing solutions (Soudry et al., 2018).
Our contributions In this work, we explore the implicit bias of optimization in robust ERM and study carefully how it affects the robust generalization of a model. In order overcome the hurdles of the bilevel optimization in the definition of robust ERM (eq. (T)). we seek to first understand the situation in linear models, where the inner minimization problem admits a closed form solution. Prior work (Yin et al. 2019 Awasthh et al. 2020) that studied generalization bounds for this class of models for E,p norm-constrainee perturbations observed that the hypothesis class (class of linear predictors) should better be constrained in its f, norm with r smaller than or equal to p² where p* is the dual of the perturbation norm p. i.c 1 +
P p" 1. For instance, the case of fo perturbations, these works postulated that searching for robust empirical risk minimizers with small E norm is beneficial for robust generalization. In Section 2 we further refine these arguments and demonstrate that there are also other factors, namely the sparsity of the data and the magnitude of the perturbation, which can influence the choice of the regularizer norm r. Nevertheless, in accordance with (Yin et al. 2019 Awasthi et al.] 2020), we do identify cases where insisting on a suboptimal type of regularization makes generalization more difficult much more difficult than in "standard" classification.

---

This observation has significant implications for training robust models. The hidden gift of opti- mization that allowed generalization in the context of ERM can now become a punishment in robust FRM, if implicit bias and threat model happen to be "misaligned" with each other. We call this the price of implicit bias in adversarially robust generalization and demonstrate two ways this price can appear; either by varying the optimization algorithm or the architecture. In particular, we first focus on robust ERM over the class of linear functions füi (x: w) = (w, x) with steepest descent with respect to an l, norm, class of algorithms which generalizes gradient descent to other geometries besides the Euclidean (Section B.T.. In the case of separable data, we prove that robust ERM with infinitesimal step size with the exponential loss asymptotically reaches solution with minimum L norm that classifies the training points robustly (Theorem 3.3 Although this result is to be expected, minimum norm solution (without
given that standard ERM with steepest descent also converges the robustness constraint, however) [Gunasekar et al.) 2018a 8a). it lets us argue that, in certain cases, gradient descent-based robust ERM will generalize poorly despite the existence of better alternatives see Figure (bottom). We then turn our attention to study the role of architecture in robust ERM. In study the implicit bias of gradient susscett-based robust ERM in models of the form u_) = {u² - u², x). commonly referred to as diagonal neural networks (Woodworth 2020 These are just reparameterized linear models ftin. and thus their expressive power does al.
Section 3.2
fdiag
x; u
not change. Yet, as we show, robust ERM drives them to solutions with very different properties
(Proposition 3.8) than those of fin. which can generalize robustly much better- see Figure (bottom).
Finally, in Section [. we perform extensive simulations with linear models over synthetic data which illustrate the theoretical predictions and, then, investigate the importance of implicit bias in robust ERM with deep neural networks over image classification problems. In analogy to situations we en- countered in linear models, find evidence that the choice of the algorithm and the induced implicit bias affect the final robustness of the model more and more as the magnitude of the perturbation increases.
Let [m] = (I.....,,)) m.. The dual norm of a vector is defined as ||z||_ supp|i| S (2, x). The dual of an l, norm is the Eyr with & + p- to denote the set of subgradients of f at x: 0x = {g E Rd fz) 2 f(x) + (g. z x) }. We
Notation
1 = 1. For a function f : Rd + R. we use (x)))
denote by x2 E IRd the element-wise square of x. We defer full discussion of prior work to App. A
2 Capacity Control in Adversarially Robust Classification
We begin by studying the connection between explicit regularization and robust generalization error in linear models. In particular, we set out to understand how constraining the &, norm of model affects its robustness with respect to lp norm perturbations, i.e., how r interacts with p.
2.1 Generalization Bounds for Adversarially Robust Classification
We focus on binary classification with linear models over examples x X R and labels y E {+1}. We denote by D an unknown distribution over X' x {+1). We assume access to m pairs from D,
S {(x1, (xx,,)))-. ..,, (Xm: Jm J. Let Hr be the class of linear hypotheses with restricted & norm:
H {x (w: x) ||w|| < W,).
(2)
where W; > is an arbitrary upper bound. We consider loss functions of the form [(h(x).)) y) (y)(())) by explicitly overloading the notation with /: R - [0, 1). The quantity yh(x) is sometimes referred to as the confidence margin of on (x,y). We assume a threat model ép balls of radius e centered around the original samples and we define G, to be the class of functions that map samples to their worst-case loss value, i.c. G. = ((x,)) + max||x' ((hh(x)) h E H. We define the (expected) risk and empirical risk of hypothesis with respect to the worst-case loss as:
(b(h) = B(x,)~D max 1(vh((')) and (s(h)= = 1 max ((sch(x4), (3)
xx
respectively.
Let us also define the robust 0-1 risk as: o)) E(x,))D [mxx|xx x1Ip 1 (yh((x)= < 0)]. Central to the analysis of the robust generaliza-
3

---

tion enror is the notion of the (empirical) Rademacher Complexity of the function class G,:
(gr) = E
sup DEG.
( 81)) = EE
sup MEH,
max 1
((vr((2())
(4)
==1
where the a:'s 's are Rademacher random variables. If, additionally, we consider decreasing, Lipschitz, losses ((-), then, as observed by Yin et al. [2019), Awasthi et al. (2020), we can equivalently analyse the following Rademacher Complexity Ri(H,, (H,)) = E.g Im suPREH. Di=1 o4 min -.,. M.x.V,hle hx](x and by taking the loss in LD(+), (-)-) in eq.
(3 to be the ramp loss: I(u)
min max (0.1-)) p 0, arrive the following margin- margin-based generalization bound.
111-5
Theorem 2.1. /Mohri al.) 2012 Awasthi et al. 2020 Fix p O. For any d >> O, with probability
at least 5 over the draw of the dataset for all h E Mr with Hy defined as in eq. (2) it holds:
log 2/5
As,,) + +3 [b(h)= S Ls(h) + p
(5)
2m
Margin bounds of this kind are attractive, since they promise that, if the empirical margin risk T.s is small for large P then the second term in the RHS will shrink, and expected and empirical risk
will be close. As shown in [Awasthi et al. [020]. the above Rademacher complexity admits an upper bound (and matching lower bound) of the form:
Rs (H,) S (H. + + 2mm
W
max dd (d=-
(6)
where (H, is the "standard" Rademacher complexity. As pointed out in [Awasthi et al. 2020
there is dimension dependence appearing in this bound, that is not present in the "standard" case of = 0, and, thus, it makes sense to choose r so that we eliminate that term. One such choice is of course p", the dual of p. This made the works of Yin et al. (2019). J, Awasthi et al. [2020) to advocate for an Ep- regularization during training, in order to minimize the complexity term and, hence, the robust generalization error. However, the factor W, that appears in the RHS of eq. (6) might also depend on r (and potentially d) so it is not entirely clear what the optimal choice of r is for problem at hand.
2.2 Optimal Regularization Depends Sparsity of Data
To illustrate the previous point, we place ourselves in the realizable setting, where there exists a linear
"teacher" which labels the samples robustly. That is, there is vector w* Rd which labels points
and their neighbors with the same label: y = sgn ( (ww,, x')) for all x' E (z E Rd l|z - x||, S e). Let us specialize to hypothesis classes with bounded & E2 norm, i.e. Hi, , H2. Since the data assumed to be labeled by a robust "teacher", the robust empirical risk that corresponds to the ramp loss be driven zero with sufficiently large hypothesis class. The next Proposition provides bound on the robust generalization of predictors who belong to such a class.
Proposition 2.2. (Generalization bound for robust interpolators) Consider a distribution D over TRd x {+1} with P(x.))>D ly = sgn((w*,x)) Vx' ||xx x|1p S] = 1 for some w Rd. Let S Dm be a draw of a random dataset S
(Xm: vm)} and let H' = fx (w,>(w,x)) (w,x): [|w/l+ < ||w'll A w E argmax|jull min:e(m) min Us (u, x²) be a hypothesis class of maximizers of the robust margin. Then, for any 8 > 0, with probability at least 1 8 over the draw of the random dataset S. for all h E Hi,, it holds:
(max;
||]]| log(2d) 2d) + +e|[w*|]]
3/
log 2/8
L.,001h) (h)
2/m
(7)
max;
|x|||||| [|llz|/w**
1=1l ||2 +
el
w lnd max + 2.00 + /
log 2/6
2.
2/m
2m
The proof appears in Appendix B and follows from standard arguments based on the properties of the ramp loss and standard Rademacher complexity bounds. Notice that eq. (7) depends on the various norms of w' and so consider specific cases in order to probe its behaviour in different

---

regimes. In particular, we assume that all the entries of the vectors are normalized to be (1). We call vector E IR "dense" when it satisfies ||z|| (dd) and || @(vā), while we call it "k-sparse" if ||z|| (kk) and ||z|| @(vk) for l < d. Let us also specialize to p co. We
enumerate the cases:
Dense, Dense: both the ground truth vector w and the samples x (with probability 1) are dense, then the bounds evaluate to θ (vm (dylog d ed) and θ ( (d+ +d)) for r -= 1 and r 2, respectively. In particular, for O, the r = 2 bound is smaller only by logarithmic factor, and as e increases the bounds should behave the same. So, we expect an ls regularization to yield smaller generalization error for = 0, while for larger e, fz and f regularization should perform roughly similarly.
2. S-Sparse, Dense: If the ground truth vector is k-sparse and the samples are dense, then the bounds yield +
- (kvloog + ek)) and θ vm (VayT++ eVivd) for r 1 and vm
2, respectively. For k O(1). & regularization is expected to generalize better than l already for c = O. As e increases, & regularized solutions should continue generalizing worse, the "worst-case" dimension-depennden term makes its appearance.
3. Dense, k-Sparse: If w is dense and the samples x are k-sparse, then we get and r 2, respectively. The r = bounds provides more favorable guarantees in this case, even for > O.
θ
m (dylog + -dd) and θ v (L/kV + ed)) for
4. k-Sparse, k-Sparse: If both w' and are k-sparse, then we have + ( A (Avloo ckt) (m + eVRva) for and r 2, respectively. For e 0, & and &2 regularization should behave similarly, but, as increases, l regularization starts "paying" the "worst-case" cimeesioonddeeeddent term, making the & solution more appealing.
and + (k
Notice how the "price" of robustness especially manifests itself in Case 4, where our input is "embedded" in a k-dimensional space: the bounds are very similar for e = 0, but as soon as e becomes positive, the extra penalty of le solutions over grows with dimension. Moreover, Case 3 highlights that an & regularization is not always optimal for foo perturbations. To summarize, we see that the optimal choice of regularization depends not only the choice of norm p and the value of e, but also on the sparsity of the data-generating process (see also Table for summary). In particular, in order for the dimension-dependen term to appear in the bound, the model w itself needs to be sparse.
3 Implicit Biases in Robust ERM
In the previous section, saw that the way we choose constrain hypothesis class can significantly affect the robust generalization error. In this section, we connect this with the implicit bias of optimization during robust ERM and demonstrate cases where the implicit regularization is either working in favor of robust generalization or against it. The term implicit bias refers to the tendency of optimization methods to infuse their solutions with properties that were not explicitly "encoded" in the loss function. It usually describes the asymptotic behavior of the algorithm. We study two ways that an implicit bias can affect robustness in robust ERM: through the optimization algorithm and through the parameterization of the model.
3.1 Price of Implicit Bias from the Optimization Algorithm
In this section, we study the implicit bias of robust ERM in linear models with steepest descent, family of algorithms which generalizes gradient descent to other than the Fuclidean geometries. We focus on minimizing the worst-case exponential loss, which has the same asymptotic properties as the logistic or cross-entropy loss (see e.g. [Telgarsky] 2013 Soudry et al. 2018 Lyu and Li 2020
m
m
Ls(h)= = [s(w)=
max x1
exp(-N) x))
exp( - Di (w, x:) + +el|ww wellwll=-). (8)
|
11 Se
5

---

The above corresponds to choosing ((u) with some definitions about the margin and the separability of dataset.
exp (-u) in the definition of eq. 3
We first proceed
Definition 3.1. We call ep ma-mar of a dataset Wh the quantity max #0 minge [m]]
W: (w.x.)
Definition 3.2. dataset {x, y4 ) (e.p)-linearly separable if max minig[m]
2e (w(x) ||
e.
Geometrically, the mp-margin of a dataset captures the largest possible lp-distance of a decision boundary their closest data point x; (see Lemma C.8 for completeness). Requiring separability is natural starting point for understanding training methods that succeed in fitting their training data and
has been widely adopted in prior work (Soudry et al. 2018 Li et al. 2020 Lyu and Li 2020)..
Steepest Descent (Normalized) steepest descent is an optimization method which updates the variables with vector which has unit norm, for some choice of norm, and aligns maximally with minus the gradient of the objective function [Boyd and Vandenberghe 2014). Formally, the update for normalized steepest descent with respect norm ||-]| for loss Ls [w() is given by:
Wi+1 = W. + n.Aw, where Aw; satisfies
Aw; E argmin (u, VLs(w.)).
||
Unnormalized steepest descent, simply steepest descent, further scales the magnitude of the update by Ls (we) where ||+I|+ denotes the dual norm of ||-|I. The case ||-Il = I1-112 corresponds to familiar gradient descent. We will be interested in understanding the steepest descent trajectory, when
minimizing Ls from eq. (8), in the limit of infinitesimal stepsize, i.c. steepest flow dynamics:
dw
dt E VEERR :
argmin (u,g) E OT. uER*:|uu|[[llll
(10)
Notice that loss Ls is not differentiable everywhere (due to the norm in the exponent), but we consider subgradients θL.g in analysis. We are ready state result for the asymptotic behavior of steepest flow in minimizing the worst-case exponential loss.
Theorem 3.3. For any (c. limeerryyy separable dataset and any initialization Wo, consider steep- est flow with respect to the E, norm, r 2 1, on the worst-case exponential loss Ls(w) = E max xxill exp(-Vs y; (w, (w,x))). Then, the iterates we satisfy:
Vi (W,, x() max min min 50000 |x]-xxllp |eell
Yi (w.x.)
lim min min
(11)
w
[x] -xiiill
||w/|-
Theorem 3.3 can be seen as a generalization of the results Gunasekar et al. 2018a Sa to robust ERM (for any lp perturbation norm), modulo continuous time analysis. The choice of analyzing continuous-time dynamics was made to avoid many technical issues related to the non-differentiabiiiy of the norm, which do not affectt the asymptotic behavior of the algorithm. Li et al. [2020) studied the implicit bias of gradient descent in robust ERM, and showed that it converges to the minimum & solution that classifies the training points robustly, which agrees with the special case of r = 2 in Theorem 3.3 For the proof, we need to lower bound the margin at all times with a quantity that asymptotically goes to the maximum margin. This requires duality lemma that relates the (sub) gradient of the loss with the maximum margin, and generalizes previous results that only apply to either gradient descent, the unperturbed loss, but
both. The proof appears in Appendix Remark 3.4. The right hand side of eq. (TT) is equivalent to:
min |/] s.t.
min yi (w, x 2 1, Vi E [m]] |
(12)
Thus, the solution converges, in direction, the hyperplane with the smallest E, norm which classifies the training points correctly (and robustly). As result, we can leverage Proposition 2.2 to reason about the robust generalization of the solution returned by steepest descent. An equivalent viewpoint of (12). first observed by Li et al. (2000) about a version of this result for gradient descent (r = 2), is the following:
min || ||- + A(e, m)]lllllll
s.t. yi (w,x,) x.) 2 1, Vi E [m],
(13)

---

for some X(e, m) > O. Thus, the problem can be understood as performing norm minimization for a norm which a linear combination of the algorithm norm and the dual of the perturbation norm p". The coefficient of the latter increases with which, hereby, means that the bias induced from the perturbation starts to dominate over the bias of the algorithm with increasing c.
In light of Section 2 and Proposition 2.2 we see that the implications of this result are twofold. First, on the negative side, Theorem 3.3 implies that robust ERM with gradient descent (42) can harm the robust generalization error p oc. For instance, as we saw in Cases 2 and 4 Section 2.2 gradient descent will suffer dimension dependent statistical overheads. On the positive side, Theorem 3.3 supplies us with an algorithm that can achieve the desired regularization. In Cases 2 and this would correspond to steepest descent with respect to r 1. In general, we have the following corollary: Corollary 3.5. Minimizing the loss of eq. ( with steepest flow with respect to the lp. norm (on (e, p) separable data) convergences minimum lp. norm solution that classifies all the points correctly.
The notable case of steepest descent w.r.t. the l norm is called coordinate descent. It amounts to updating at each step only the coordinate that corresponds to the largest absolute value of the gradient (Appendix D). In Section 4.1 we demonstrate how robust ERM w.r.t. &o perturbations with coordinate descent, can enjoy much smaller robust generalization error than gradient descent.
Finally, although the perturbation magnitude e did not influence the conversation so far terms of the choice of the algorithm, it is important to note that, as e increases, the max-margin solution will look similar for any choice of norm. In fact, in the limiting case of the largest possible that does not violate the separability assumption, all max-margin separators are the same see Lemma C.7 type of implicit bias will cease to be important for generalization.
so the
3.2 Price of Implicit Bias from Parameterization
We reasoned in the previous section that robust ERM with gradient descent over the class of linear functions of the form fün (x; w) (w, x) can result in excessive (robust) test error for fox pertur- bations. We now demonstrate how the same algorithm, but applied to a different architecture, can induce much more robust models. In particular, consider the following architecture:
fdlag (x; u) = (u, - -
u [u+.u]] I 2d
R
(14)
which consists of reparamcterization of fun- In terms of expressive power, the two architectures are the same. However, optimizing them can result in very different predictors. In fact, this class of homogeneous models, known diagonal linear networks, have been the subject of case studies before for understanding feature learning in deep networks, because, whilst linear in the input, they can exhibit non-trivial behaviors of feature learning (Woodworth et al. 2020]. In order study the implicit bias of robust ERM with gradient descent on fdiag. we leverage a result by [Lyu and Zhu 2022) which shows that, under certain conditions, the implicit bias of gradient flow based robust ERM for homogeneous networks, is towards solutions with small & norm.
Theorem 3.6 (Paraphrased Theorem 5 in [Lyu and Zhu )022). Consider gradient flow minimizing a worst-case exponential loss T.s () (u)(
ET max [x.-x e v. (x((), , for a homogeneous, locally Lipschitz, network (x; IP - R. and assume that for all times > 0 and for each point
x; the perturbation argmax [xx (x e (x(aa)) is scale invariant and that the loss gets minimized,
i.e. Ls(u) 20200 0. Then, converges in direction to KKT point of the following optimization problem:
s.t.
min Se
y (x 2 1, Vi E [m]]
(15)
||x]
As we show, faing satisfies the conditions of Theorem 3.6 and, thus, we get the following description of its asymptotic behavior.
Corollary 3.7. Consider gradient flow on the worst-case exponential loss Ls(u) =
m Ei= max x(]la e- v and assume that Ls(u) + 0. Then, u converges in di-
1
rection a KKT point of the following optimization problem:
1
min
(1|u+
112
|u
s.t. min 311 (u² u2, xx) 2 1, Vi [mm] (16)
E. u_
EBC
2
Sx
7

---

However, the optimization problem of eq. (66) which is over R²d is nothing but disguised 1 minimization problem, when viewed in the prediction (R*) space. Proposition 3.8. Problem
166 has the same optimal value as the following constrained opt. problem:
min WERd
[wll s.f.
min 1x4-xx1lpe
Yi (w, x4) 2 1, Vi E [m]]
(17)
The proofs appear in Appendix C.4 These results suggest that the bias of gradient-descent based robust ERM over diagonal networks is towards minimum & solutions, which as we argued in the previous section can have very different robust error compared to &2 solutions, which are returned by gradient-descent based robust ERM over linear models. We verify this in the simulations of Section 4.1
Remark 3.9. Technically, Corollary 3.7 only proves convergence first order (KKT) point, so we cannot conclude equívalence with the minimum of the & problem in eq. 17 Yet, we believe that global optimality, under the condition of (c, p) separability, can be proven by extending the techniques of [Moroshko et al. 2020) in robust ERM.
Experiments
In this section, we explore with simulations how the implicit bias of optimization in robust ERM is affecting the (robust) generalization of the models. Appendix F contains full experimental details.
4.1 Linear models
Setup We compare different steepest descent methods in minimizing a worst-case loss with either linear models diagonal neural networks synthetic data, and study their robust generalization error. In accordance with Section 2.2] we consider distributions that come from a "teacher" w* with y = sgn((w" x)) that can have sparse or dense x, w'. We denote by kw and kx the expected number of non-zero entries of the ground truth w and the samples x, respectively. We train linear models funm (x; w) = (w, x) with steepest descent with respect to either the l (coordinate descent CD) or the & norm (gradient descent GD), and diagonal neural networks fdiag (x; u4, u+) = (u² 15--u- x²,x) with gradient descent (diag- -di-g-) We consider &oo perturbations. We design the and we obtain the value of following experiment: first, we fit the training data with CD for 27 This supplies us with an upper the lo margin of the dataset (denoted as e*) (') at the end of training bound on the value of for our robust ERM experiments, i.e. we know there exists linear model with 100% robust train accuracy for e less than or equal to this e* margin. We then perform robust ERM with (full batch) ED/CD/diag-net- for multiple values of dataset size m (and draws of the dataset), and aggregate the results.
for various values of e less than e*. We repeat the above
Results We plot the (robust) generalization gap of the three learning algorithms versus the dataset size for (kw, (5112, 512) (Dense, Dense) and (kw, )(4, 512) (4-Sparse, Dense) in Figures 1 (bottom) and 2 (left), respectively. In each figure, we show the performance of the methods both in ERM (no perturbations during training) and robust ERM. The evaluation is w.r.t. the used in training. For both distributions, we observe a sigmificant change in the relative performance of the methods, when we pass from ERM to robust ERM. For data with a sparse teacher (Figure 2), CD and diag-net-CD already outperform
in terms of generalization when implementing ERM, as a result of their bias towards minimum & (sparse solutions). However, in agreement with the bounds of Section 2.2] the interval between the algorithms grows when performing robust ERM as result of their different biases. In the case of Dense, Dense data (Figure D the effect of robust ERM is more dramatic, as the algorithms generalize similarly when implementing ERM, yet their gap between their robust generalization in robust ERM exceeds 20% in the case of few training data! Notice that the bounds in Section 2.2 were less optimistic than the experiments show for the performance of CD and diag-net ne in this case. Plots with other distributions appear in Figure 5
To get a fine-grained understanding of the interactions between the hyperparameters of the learning problem, we measure the average difference of (robust) generalization gaps between GD and CD. In par- ticular, for each different combination of sparsities (kw, kxx) and perturbation c, we summarize curves
RRnninn this algorithm to convergence is guaranteed to result in the largest possible foo separator of the (x.ww]
training data (Gunasekar et al. 2018a. Recall that the Lo -marin maXw340 millg[m]]] y/ [[w]]]
8

---

(d
ky
kw O(d)
Ky Ø (dvd)
80
Generaliztioo Gap
Perturbation 2
4
20
26
27
2
2
logd
Zlogd
vd
loga
Zlogd
vd
Rusust ERM (d= 512,
Kw 4. 512)
ky e(
kw @llogd
80
Robest Generalizatonn Gap
Perturbation +/
40
+
20
2
27
2
2
logd
2logd
vd
logd
2logd
vd
ky
CD GD
diag Blg-nnat-GD
10%
15%
20%
Figure 2: Left: Binary classification of data coming from sparse teacher w* and dense x, with (bottom) or without (top) & perturbations of the input in R2 using linear models. We plot the (robust) generalization gap. i.e., (robust) train minus (robust) test accuracy. of different learning algorithms versus the training size m. For robust ERM, is set to I of the largest permissible value The gap between the methods grows when pass from ERM to robust ERM. Right: Average benefit of CD over GD (in terms of generalization gap) for different values of teacher sparsity lww, data sparsity ky and magnitude of fx perturbation e.
of the form of Figure 2 (left) into number, by calculating: 210 1 (GD(m) (D)) dm. The results shown Figure 2 (right). Notice that, argued in Section 2.2 there cases with e > 0 where CD does not outperform GD (kw = (dd), kx = (log d)), because the learning problem much more "skewed" towards dense solutions. We also observe that when goes from to S the edge of CD over GD grows. Past certain threshold of the methods will start perform the same, since for e* the algorithms return the same solution (Lemma C.7p. See also Appendix and Figure for the average difference of "clean" generalization gaps between GD and CD.
4.2 Neural networks
Our discussion has focused so far on linear (with respect to the input) models, where closed form solution for the worst-case loss allowed us to obtain precise answers for the connection between generalization and optimization bias in robust ERM. Such characterization for general models is
too optimistic at this point, because, even for kernelized model f(x; w) (w, ((x)). it not clear how to compute the right notion of margin that arises from min - (w, o(x')) without making further assumptions about o(-). As such, it is difficult reason that one set of optimization choices will lead to better suited implicit bias than another. We assess, however, experimentally, what effect (if any) the choice of the optimization algorithm has on the robustness of non-linear model. To this end, we train neural networks with two optimization algorithms, gradient descent (GD) and sign (gradient) descent (SD) for various values of perturbation magnitude e, focusing on loo perturbations. SD corresponds to steepest descent with respect to the loo norm and is expected to obtain minimum with very different properties than the obtained with GD (Appendix D). In practice, found it easier to train neural networks with SD than with any other steepest descent algorithm (besides CD).
Fully Connected NNs We first focus on ReLU networks with hidden layer without bias term: f(x) = Σ ( (W,x), where ou) = max(0, u) is applied elementwise. For this class of homogeneous networks, we expect very different implicit biases when performing (robust) ERM with GD versus SD (see Appendix D for details). In Figure we plot the accuracy of models trained on random subsets of MNIST [LeCun et al. 1998) with "standard" ERM (e = 0) and robust ERM (e 0.2). We observe that in ERM (top), the choice of the algorithm does not affect the generalization

---

ERM m= 800.
Performance Gap
Accuracy
90-
0.4
%
100
10a
Perturbation
10a
0.3
Robust ERM - mm250 0.2
100
Robust Accuracy
70
85
10a
10a
10a
102
10
100
250
10,000
Epachs
#train points
GD train
GD test
SD train
50 test
2%
6%
Figure 3: Left: Comparison of two optimization algorithms, gradient descent and sign gradient descent, in ERM and robust ERM on subset of MNIST (digits vs 7) with hidden layer ReLU nets. Train and test accuracy correspond to the magnitude of perturbation used during training. We observe that in robust ERM the gap between the generalization of the two algorithms increases. Right: Gap in (robust) test accuracy (with respect to the used in training) of CNNs trained with GD and SD (GD accuracy minus SD accuracy) on subsets of MNIST (all classes) for various of e and m.
error much. But, for 0.2 (bottom), SD significantly outperforms CD (4.11% mean difference over random seeds), even though both algorithms reach 100% robust train accuracy. Notably, in this case, robust ERM with SD not only achieves smaller robust generalization error, but also avoids robust overfitting during training, contrast to GD. It is plausible that robust overfitting, which gets observed during the late phase of training |Rice al. 2020 ). is due to (or attenuated by) the implicit bias of an algorithm kicking in late during robust ERM. This bias can either aid or harm the robust generalization of the model and perhaps this is why the two algorithms exhibit different behavior. It would be interesting for future work to further study this connection. See Appendix for plots with different values of and m.
Convolutional NNs Departing from the homogeneous setting, where the implicit bias of robust ERM known or can be "guessed", we now train convolutional neural networks (with bias terms). As result, we do not have direct control over which biases our optimization choices will elicit, changing the optimization algorithm should still yield biases towards minima with different properties. In Figure we plot the mean difference (over 3 random seeds) between the generalization of the converged models. We see that the harder the problem is (fewer samples m, request for larger robustness c), the bigger the price of implicit bias becomes. Note that for this architecture it turns out that the implicit bias GD is better "aligned" with our learning problem and GD generalizes better than SD, despite facing the opposite situation in homogeneous networks. This should not be entirely surprising, since we saw already in linear models that reparameterization can drastically change the induced bias of the same algorithm.
Conclusion
In this work, we studied from the perspective learning theory the issue of the large generalization gap when training robust models and identified the implicit bias of optimization as a contributing factor. Our findings seem to suggest that optimizing models for robust generalization challenging because it is tricky to do capacity control "right" in robust machine learning. The experiments of 4 seem suggest searching different first-order optimization algorithms (besides gradient descent) for robust ERM (adversarial training) promising avenue for future work.
Section
10

---

Acknowledgments. NT and JK acknowledge support through the NSF under award 1922658. Supported in part by the NSF-Simons Funded Collaboration on the Mathematics of Deep Learning (htps://deepfoundtiios ai/), the NSF TRIPOD Institute on Data Economics Algorithms and Learning (IDEAL) and an NSE-IIS award. Part of this work was done while NT was visiting the Toyota Technological Institute of Chicago (TTIC) during the winter of 2024, and NT would like to thank everyone at TTIC for their hospitality, which enabled this work. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise.
References
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alchh-Buuc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7411-7422, 2019.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 283. PMLR, 2018
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine PMLR, 2020.
Learning Research, pages
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 10077-10094. PMLR, 25 Apr 2023.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normaaizze margin bounds for neural networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6240-6249, 2017.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numer., 30:203-248, 2021.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný, editors, Machine Learning and Knowledge Discovery in Databases- European Conference, ECML. PKDD) 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190 of Lecture Notes in Computer Science, pages 387-402. Springer, 2013.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014.
Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya P. Razenshteyn. Adversarial examples from computational constraints. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, 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 -30- PMLR, 2019.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 39-57. IEEE Computer Society, 2017.

---

Earl A. Coddington and Norman Levinson. Theory of Ordinary Differential Equations. McGraw-Hil Book Company, 1955.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3):273-297, 1995.
Corinna Cortes, Mehryar Mohri, and Ananda Theertha Suresh. Relative deviation margin bounds. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 22311131. PMLR, 2021.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag. Edoardo Debenedetti, Nicolas Flammar- ion, Mung Chiang. Prateek Mittal, and Matthias Hein. RobustBench: a standardized adversarial robustness benchmark. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Edoardo Debenedetti, Zishen Wan, Maksym Andriushchenko, Vikash Sehwag, Kshitij Bhardwaj, and Bhavya Kailkhura. Scaling compute is not all you need for adversarial robustness. CoRR, 2023,
Fartash Faghri, Cristina Nader Vasconcelos, David J. Fleet, Fabian Pedregosa, and Nicolas Le Roux. Bridging the gap between adversarial robustness and optimization bias. CoRR, abs/2102.08868,, 2021.
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bias Bisa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 1186-1199 195, 2018.
Dylan J. Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Hypothesis set stability and generalization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 6726-6736. 2019.
Spencer Frei, Gal Vardi, Peter L. Bartlett, and Nathan Srebro. The double-edged sword of implicit bias: Generalization vs. robustness in relu networks. CoRR, abs/2303.001aaaao 01665, 2023. doi: 10.48550/ ARX1V.2303.01556. https://////d org/ 10. 40..55055aaxii 2303.01455
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian J. Goodfellow. Adversarial spheres. In 6th International Conference on Learning Representutions, ICIR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Workshop Track Proceedings, 2018
Ian J. Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Suriya Gunasekar, Blake E. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach. CA, USA, pages 6151-6153 2017.
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssn, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1827-1836. PMLR, 2018a.
12

---

Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks, In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicold Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 9482-9491, 2018b.
Andrew Iyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, Adversarial examples are not bugs, they are features. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Ach--Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 125-136, 2019.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019a.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772-1798, PMLR, 25 28 Jun 2019b.
Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel, editors, Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017, pages 2021-2031. Association for Computational Linguistics, 2017.
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the "wenty-Secone Annual Conference Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 793-800. Curran Associates, Inc., 2008.
V. Koltchinskii and D. Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Trans. Inf. Theory, 47(5):1902-199 2001.
Anders Krogh and John A. Hertz. A simple weight decay can improve generalization. In John E. Moody, Stephen Jose Hanson, and Richard Lippmann, editors, Advances in Neural Information Processing Systems 4, (NIPS Conference, Denver, Colorado, USA, December 2-5, 1991], J. pages 950-957. Morgan Kaufmann, 1991.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings, 2017a
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning scale. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017b.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEFE, 86(1 0-2277-23224 1998.
Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training separable data. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
13

---

Bochen Lyu and Zhanxing Zhu. Implicit bias of adversarial training for deep neural networks. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In Sth International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 36-30, 2020, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018.
David A. McAllester. Some pac-bayesian theorems. In Peter L. Bartlett and Yishay Mansour, editors, Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 1998, Madison, Wisconsin, USA, July 24-26, 1998, pages 230 0300-234.440 ACM, 1998.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 978-0-262-01825-8.
Edward Moroshko, Blake E. Woodworth, Suriya Gunasekar, Jason D. Lec, Nati Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florin Balcan, and Hsuan-Tiee Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Walced Mustafa, Yunwen Lei, and Marius Kloft. On the generalization analysis of adversarial learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 16174-16196. PMLR, 17-23 Jul 2022.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee, Nathan Srebro, and Daniel Soudry. Lexi- cographic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, 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 4683-4692, PMLR, 2019.
Preetum Nakkiran. Adversarial robustness may be at odds with simplicity. CoRR, abs//900/ 90030 2019. URL.attp://arxix http://rxxx..oorrbb/rsas wtt./ab/////11000053333
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-hayesian approach to spectrally- normalized margin bounds for neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018
Andrew Y. Ng. Feature selection, 11 vs. 12 regularization, and rotational invariance. In Proceedings of the Twenty-Firs International Conference Machine Learning, ICML '04, page 78, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1 1581 138385.
Nicolas Papernot, Patrick D. McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Anan- thram Swami. The limitations of deep learning adversarial settings. In IEEE European Symposiun on Security and Privacy, EuroS&P 2016, Saarbrücken, Germany, March 21-24, 2016, pages 372-387. IEEE, 2016.
Leslie Rice, Eric Wong, and J. Zico Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Viruual Event, volume 119 of Proceedings of Machine Learning Research, pages 8093-8104. PMLR. 2020.
14

---

Cynthia Rudin, Corinna Cortes, Mehryar Mohri, and Robert E. Schapire. Margin Margin-based ranking meets boosting in the middle. In Peter Auer and Ron Meir, editors, Learning Theory, 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005, Proceedings, volume 3559 of Lecture Notes Computer Science, pages 63-78. Springer, 2005.
Robert E. Schapire, Yoav Freund, Peter Barlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In Douglas H. Fisher, editor, Proceedings of the Fourteenth International Conference on Machine Learning (ICML 1997), Nashville, Tennessee. USA, July 8- 8-12, 1997, pages 322-330, 1997.
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In 7th International Conference on Learning Representations, ICLR 20/9, New Orleans, LA, USA, May 6-9, 2019, 2019a.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor. and Tom Goldstein. Adversarial training for free! In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3353-3364, 2019b.
Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputingg 307:195-220 204, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. J. Mach. Learn. Res., 19:70:1-70:57, 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Benjamin Taskar, Carlos Guestrin, and Daphne Koller. Max-margin markov networks. In Sebastian Thrun, Lawrence K. Saul, and Bernhard Schölkopf, editors, Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada], pages 25-32. MIT Press, 2003.
Matus Telgarsky. Margins, shrinkage, and boosting. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 307-315, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Nikolaos Tsilivis and Julia Kempe. What the neural tangent kernel tell us about adversarial robustness? In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In 7th International Conference on Learning Represen- tations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978- 978-0-471-03000
Gal Vardi. On the implicit bias in deep-learning algorithms. Commun. ACM, 66(6):86-93, 2023.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Gradient methods provably converge to non-robust networks. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
15

---

Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages (6246-36260) PMLR, 2023.
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Blake E. Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 3635-3673. PMLR, 2020.
Dong Yin, Kannan Ramchandran, and Peter L.. Bartlett. Rademacher complexity for adversarially robust generalization. In Kamalika Chaudhuri and Ruslan 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 7085-7094. PMLR, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Dinghuai Zhang, Tianyuan Zhang. Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 227-238, 2019a
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1472-7482 PMLR, 2019b.
Andy Zou, Zifan Wang. J. Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks on aligned language models. CoRR, abs/2307. 15043, 2023.
16

---

A Related work
Most relevant our work Yin et al. [2019] Awasthi al. [020 derived generalization bounds
for adversarially robust classification for linear models and simple neural networks, based on the
notion of Rademacher Complexity [Koltchinskii and Panchenko| 2002]. and form the starting point of our work (Section 2) Gunasekar et al. [2018a] studied the implicit bias of steepest descent in ERM for linear models, while Li et al. (020) analyzed the implicit bias of gradient descent in robust ERM. Theorem 3.3 can be seen as a generalization of these results. In Section 3.2 we analyze robust ERM with gradient descent in diagonal neural networks, which were introduced in [Woodworth et al., 2020] as model of feature learning in deep neural networks. The work of Faghri et al. [2021] discusses the connection between optimization bias and adversarial robustness, yet with a very different focus than ours; the authors identify conditions where "standard" ERM produces maximally robust classifiers, and, leveraging results on the implicit bias of CNNs [Gunasekar et al. 2018b]. they design a new adversarial attack that operates in the frequency domain.
Adversarial Robustness Our discussion is focused on so-called white-box robustness (where an adversary has access any information about the model)- see (Papernot al. 2016 for taxonomy of threat models. Adversarial examples in machine learning were first studied in (Biggio et al.) 2013) for simple models and in (Szegedy et al.) [014] for deep neural networks deployed in image classification tasks. The adversarial vulnerability of neural networks is ubiquitous (Papernot et al.. 2016 and it has been observed in many settings and several modalities (see, for instance, [Kurakin ct al. 2017a Jia and Liang, 2017 Zou et al. (003]). ). The reasons for that still remain unclear the past have entertained hypotheses such as high dimensionality of input space Fawzi et al. 2018 Gilmer et al. 22018,) Shafahi et al., 2019a], presence of spurious features in natural data [layas et al. 2019 T sipras et al. 2019 Tsilivis and Kempe, 2022). limited model complexity
explanations
Nakkiran 2019), fundamental computational limits of learning algorithms [Bubeck et al.. 2019].
and the implicit bias of standard (non-robust) algorithms (Frei et al. 2023 Vardi et al.) [2022] Many
empirical methods for defending neural networks have been proposed. but most of them failed to conclusively solve the issue [Carlini and Wagner) 2017 Athalye et al., 2018). The only mechanism that can be adapted to any threat model and has passed the test of time is Adversarial Training (Madry) ctt al. 2018 Goodfellow et al.) 2015 Kurakin et al. 201 7b Shaham et al. 2018), i.e., robust ERM. For neural network training, this translates to calculating at each step ad adversarial examples with (projected) gradient ascent (or some variant), and then updating the weights with gradient descent (using the gradient of the loss evaluated on improving this method, either computationally by reducing the amount of gradient calculations (Shafahi et al., 2019b] Zhang et al. [2019a] Wong et al. 2020). or statistically by modifying the loss function /Zhang et al. 2019b | Awasthi et al. [023]. A common pitfall of all these methods is large (robust) generalization gap [Croce et al. 2021 and (robust) overfitting during training (Rice et al., 2020]: towards the end of training, the robust test error increases even though the robust training error continues to decrease. Vast amounts of synthetic training data have been shown to help both accounts, alleviating the need for early stopping during training [Wang et al. 2023
the adversarial points). There have been many attempts
-bagin- Generalization bounds The idea of (confidence) margin has been central in the development of many machine learning methods [Vapnik] 1998] Taskar et al.] 2003 Rudin et al. 2005) and it has been used in several contexts for justifying their empirical success [Cortes and
Vapnik 1995 Schapire et al. 1997 Koltchinskii and Panchenko 2002). In linear models and kernel methods, is closely related the notion of geometric margin, and -aseen- generalization bounds can explain the strong generalization performance in high-dimensions [Vapnik] 1998 Mohri ct al. 2012 Shalev-Shwarz and Ben- sen-David 2014).. For neural networks. they are still the object of active research [Bartlett et al. 2017 Neyshabur et al.) [0188] Long and Sedghi, 20200 Cortes et al. 2021]. For these kind of bounds, the Rademacher complexity of the hypothesis class plays a central role [Koltchinskii 2001). Rademacher complexity-yppe analyses have been shown to subsume other similar frameworks Kakade et al.) 2008]] (Foster al. 2019], such as the PAC-Bayes one [McAllester]
1998), and in many cases they can provide the finest known guarantees. YYn et al. [209) and and/Awasthi ct al. 22200] recently derived margin-based bounds for adversarially robust classification see also
Mustafa et al. 2022 for non-additive perturbations.
Implicit Bias of Optimization Algorithms The implicit bias (or regularization) of optimization algorithms refers to the tendency of gradient methods to induce properties to the solution that were
17

---

not explicitly specified. It is believed to be beneficial for generalization in learning Neyshaaur et al.
2015]. The implicit bias of gradient descent towards margin maximization/norm minimization has
been studied in many learning setups including matrix factorization [Arora et al. 2019 Gunasekar
jet al. 2017]. learning with linear models [Soudry et al. 2018 Ji and Telgarsky| (209b), deep linear
{ and Telgarsky 2019a] and convolutional networks [uunasekar et al., [208bb) and homogeneous
models Lyu and Li. 2020 Nacson et al. 2019]. Telgarsky [2013] and Gunasekar et al. [2018a]
have analyzed implicit biases beyond li-like margin maximization for other optimization algorithms; namely Adaboost and Steepest (and Mirror) Descent, respectively. See Verdi 2023] for compre-
hensive survey of the area. The importance of sparsity (min-f1 solutions) in binary classification
has been studied in [gg 2004]. In the context of adversarial training. Li et al. [220)] analyzed the
implicit bias of optimizing worst-case loss with gradient descent in linear models, and Lyu and Zhu
2022] extended these results to deep models.
B Generalization Bounds for Robust Interpolators
In this Section, we provide the proof of Proposition 2.2 which we now restate for convenience.
Proposition B.1. (Generalization bound for robust interpolators) Consider a distribution DD over Rd x {+1} with P(x.))>DD [y = sgn((w*,x)) xx),, Vx': ||x' -x S = 1 for some w E Rd. Let S D be draw of a random dataset S {(x1, (111,81)..... (Xm: vmm) and let
Hi = f- (w,x) ||w/lr S l|w*ll, A w (rgg mingg(m] min Ui (u, xi) } be a hypothesis class of maximizers of the robust margin. Then, for any 8 > 0, with probability at least 1 - 8 over the draw of the random dataset S. for all h E Hy, it holds:
max;
||x:|loo||"*|| 1/ + +ellw"lli)
) + 3/
log 2/6 2m
r -1
LD,01(M) 5
vm
(18)
max; ||x]||||| cl c||w" maxx ft - 2.0 + 3/
log 2/6
2.
m
Proof. First, notice that Hi S Hr. so, by the definition of the Rademacher complexity, it holds: Rs(H,) < (H,)). Thus, from Theorem 2.1 we have for all h H' and for p > 0 with probability
1-6: 8:
(b)h)) < (h))) + As((H))) + +3\ log 2/5
(19)
2m
Observe that the ramp loss (u) = min max 1 - })), >> 0 is upper bound on the 0-1 loss, thus readily get bound for the 0-1 robust risk:
2 p
2/6
LD.01 (h) S Ls(h) + As RM, - -3/
(20)
2m
Now, let us specialize the ramp loss for p = (a stronger version of this Proposition can be obtained for a that depends on the data see, for instance, the techniques in Theorem 5.9 in [Mohri et al. 2012). ). Then, the bound becomes:
log 2/5 2m
max min(1, max(0, 1 ys (w, x()) 22 (H.) + 3/ Lo (b) S m || Xillsse
(21)
But, notice that for all h H. and their corresponding 1 EEe max Se min(1, max 1 ye (w, x()) is O, since:
w, the empirical loss
31 (w,x²)
argmax min min y1 (w, argmax min min w:llwil (6(m] Sx-xillsse
werd iE(m) [|x] -xllxillsse w
argmax weR' w
||w/
(22)
mince(m)) min [x (wno))
argmin wER w
||w]|r.
-in i (w.x') Wel(m
18

---

h
H2
H1
oo
Figure 4: An illustration of the model selection problem we are facing in Section 2 We depict hypothesis classes which correspond to Hr = {x+> (w, x) ||w]], S W] for r 1, 2, oo (notice that here, for illustration purposes, we keep W constant and not dependent on r). Increasing the
order r of H, can decrease the approximation error of the class, but might increase the complexity captured by the worst-case Rademacher Complexity term of eq. (6).
Note that the set solutions is not empty, since w satisfies the constraints with probability result, for all h E Hy we obtain:
log 2/8
Lp (h) < 2 Rig (H,, + +31
(23)
2m
Combining this with the upper bound of the adversarial Rademacher complexity of eq. (6) together
with the standard Rademacher complexity bounds for 1,2 [akade al. 2008
O
maxic [m]) [xc, o0 Wi
1,
Rg(H) =
mm
(24)
max (m] 1x
r= 2.
we obtain the result.
x
Sparse
Dense
w
Sparse
E, & similar as e + O, lj better as 0
4 better as e + 0
Dense
& better 0,
f, l2 similar - 0,
Table 1:
summary of the expected generalization behavior for the various distributions of Sec- tion 2.2 e denotes the strength of foo perturbations and é,, &2 denote the type of regularization
applidd to the solution.
C Implicit Biases in Robust ERM
C.1 Robust ERM over Linear Models with Steepest Flow
First, we provide the proof of Theorem 3.3 Recall that we are interested analyzing the implicit bias of steepest descent algorithms with infinitesimal step size when minimizing worst case loss.
The steepest flow update with respect norm ||-|| written follows:
dw dt
E :
argmin lu.g).e. g OLs S.
(25)
uER:: jull lil..
where recall 0T.g is the set of subgradients of Ls.
We restate Theorem 3.3
19

---

Theorem C.1. For any (e.p)-linearly separable dataset and any initialization Wo, steepest flow with respect the & norm,
the worst-case exponential loss Lg(w) E mxx Sillsse exp(-y- Yo (w,x,) x()) satisfies:
Vi (Wr, x()
(w, x() ||
lim min min 1-00 -
min min wy0
(26)
[wlll
|x -x--xill S
Proof. Throughout the proof, we suppress the dependence of w on time, Let us define the maximum, worst-case, margin:
min (w, x()
2 max min w=0 iE(m) [x
(27)
||
We use the subscript r", because T/m maximizes distance with respect to the e,-- norm. Recall that the loss function is given as:
m
Ls(w) =
max exp(-Mi (W, x() = Σ x
exp(-Mi (w, x1) + fc/lwllp-).
(28)
By the definition of the loss function, we have for any > 0:
Ls(w)= Σ exp(-yı (w.x.) + +lllll)>
2 max exp(-M (w,x)) + <llwllp-).
(29)
(E[m]
Thus, we obtain the following relation between the loss and the current margin:
min Y/ (w,x;) cl|w|pp
log [s()))
(30)
EE mm
so the goal will to lower bound the RHS. For that we need the following Lemma, which consists of the core of the proof and quantifies the relation between maximum margin and loss (sub) gradients. This Lemma generalizes Lemma C. in (Li al. 2020) that applies to gradient descent. We will overload notation and denote by O any subgradient of
Lemma C.2. For any w Rd, holds:
3pp < |0Ls(w)]l--
(31)
Ls(w)
Proof. Let u, be vector that attains 7r, i.c ü, is worst-case e,,, maximum margin separator:
Yi (w, x()
ü E argmax min min ws0 (E(m) x<)B((x) ||w||r
(32)
Then, have (since Ls is convex, the "chain rule" holds):
(ū,,,- -OLs,)) =
Upt y: =0|lw|lp> e ue tww.))+tllllll
(33)
up. (ū,. y: E (Ü,- (lo
tell))
|u,- ||-
But, by the definition of the dual norm and of the subgradient, we have ((w,,
s
[ Iby |||||||lplll = ||ū ll.,, so eq. (33) becomes:
(ū..- -Ls(ww)
u e 21 nwwwxx)+elllll..
(34)
which by rearranging can be written as:
ü
TT. (w)
Jra (w))
(35)
i ||
Finally, again, by the definition of the dual norm, we get the desired result:
|0Ls(w)ll 2 Tr- Ls(w).
(36)
0
20

---

In light of this Lemma, we can lower bound the derivative of the RHS of (30) as follows:
d log
1 dLs
Ls
dt
T.s
dt
dw
aL.s
(Chain rule)
Lg
dt
(37)
|
l|r.
dw
(Def. of steepest flow)
Ls
dw
2 7/--
(Lemma
dt
Thus, eq. 30 becomes:
Vi (w, x:)
e||w/ll 112-
dw ds
||,
ds
min KE m
7/.
(from Eq. (37
||
1,.0 cs
diw ds
2 7pm
[w/l+ 1|
(38)
1/w
woll
-/--
|w|l-
||
W
Wo
7/m
[w|r
||
since Ls 0 ( dLLs (ct < 0- see Lemma C.3 and Ls is bounded from below) and hence it must be
|w] + 00.
Lemma C.3. For any convex T,, the steepest flow of eq. 25 satisfes
dL
dt S 0 and dw dt [uERd:ju|Slllll
argmin
(u,g")
E argmin
|glll
> O.
(39)
geats
Proof.
Since L is convex, the "chain rule holds", that is, for all g OL we have:
dL
dw
g:
(40)
dt
dt
First, apply this to the element of ÔL, g, that corresponds to de of dual norm, we have:
dw
then, by the definition of S and that
dL
dw
(41)
dt
dt
Now, apply the "chain rule" for g" argmingeos l|g]].:
dL
g" dw
dw
2 - 1gg
(42)
dt
dt
dt
Equating dl from
get
/dw
Ig" ||-.
C.2 Existence of Steepest Descent Flows
In this section, we prove that C steepest descent flows exist for certain norms when the initialization has sufficiently small robust risk (see Theorem C.ooeemmC.]lbloooe This criterion applies to r-norms with r E (1, but not r = 1 or Co.
Lemma C.4. If the norm || is strictly convex and x * O, then there unique minimizer to + xu, over the ball BM (0) {u: ||||| I M) for any M 0.
21

---

Proof. We'll show this statement via proof by contrapositive.
Let W1, Ug be any two minimizers of (u, x) over (0). Then because this function is linear, U2 cannot be in the interior of (ar Due to the convexity of the ball Bw the linear combination fu, + (1 - u) is not in the interior of the ball B (0), and thus the norm ||-] is not strictly convex.
This result implies that whenever the norm ||-|| is strictly convex, the function P P:R. (0) + R defined by
P(x)
argmax (u, x)
(43)
|| s||||]
is well-defined.
This observation together with classical results from ODE theory can be leveraged to proved the existence well behaved steepest descent flows. See Theorem 1.2 [ooddington and Levinson [955] pages 6 and 19] for Peano's existence theorem:
Theorem C.5 (Peano's existence theorem). Consider the ODE
x (t) f(t,x(t))
with initial condition x(T) = 5. If f
Rd + Rd is continuous on a rectangle containing (T, E). then there is C solution for | 7| S for some >> O.
This result states that if the map f is sufficiently well-behaved, then there is a solution to the ODE for sufficiently small time. Below, we prove that there exists steepest descent flow for all times by "stitching together" small time intervals for which there exists local solutions. We also require the initial point satisfy certain condition so that we avoid the singularity zero in the map P.
Theorem C.6. Let ||-I| be a strictly convex norm for which the function defined by (43) continuous. Then if the initial point wo satisfies Ls (Wo) < (0) then there exists C steepest descent for the equation
dw dt
P(VLs(w(())-
Proof. Theorem
C.5 proves the existence of a C. local solution for small times Now let
sup(s ((s) + 0, or there exists a C² solution for all s}
For contradiction, we will assume that < co. First, notice that
a (s(((()) - -P (VLs(w((t)) vLs(w(t)) -
dt
Thus (s(w(T)) < Ls(wo)) (s(w(0)), and consequently, w(T) * 0. Therefore, Peano's existence theorem again implies the existence of local solution starting from w(T). Thus the solution can be extended past time T, which contradicts the definition of T.
One can show that if [|-1| the r-norm for E (1, oo), then the corresponding function P defined by 43
is
P(x) = |x| sign(x)|x
and this function is continuous in the domain Rdd (0]-
Consequently, there exists a steepest descent flow for the r-norm for r (1, so long as the initialization satisfies Ls (woo)) (O).
C.3 Equivalence of max-margin solutions
Lemma C.7. Let {(x,, v.) be a dataset with Ep margin equal to e. Any hyperplane that v)) separates {(x) Rd ||x] xillp & ,.'},v))" is an l, max-margin separator for any
22

---

This result informs us that any choice of algorithm in robust ERM (w.r. to Ep perturbations) for equal the ? margin of the dataset will produce the same solutions.
We provide the proof of Lemma C.7 First, one can calculate the margin of a point x with respect to a linear separator w:
Lemma C.8. The Ep margin of linear hyperplane w datapoint (x, y) is y x)xx) w/lp-
Proof. We want to find the largest e for which (w, x + ch) 2 0 for all | S 1. for all h with ||b||p I 1 Taking an infimum over results in
(w, x) - c||w//p- 2 0
and thus c = (w, x)/l|w/l>-
Next, this lemma allows one calculate the margin of ball around a point. We denote by BP the lp ball around x, i.c. (x)x) = {x' : ||x' - -xlpp S e). Lemma C.9. The l--margin of the set (x) with label y
</|w|pp-
yw
w Ir.
Proof. We want to find the largest constant for which
y(w (x + h1 + h2)) 2 0
h, (0) and h2 E B (0). Taking an infimum over all possible h, and h2 results
yw < [w|lpp cl| w// 2 0
Therefore, the largest such possible is
yw X El w//-----
This result immediately implies Lemma C.7
Proof of Lemma C.7 Let w be the 4, max margin hyperplane separating the ((BP(x)) (())))))))))) 1 If
the l--mate t--arginn of the dataset is e, then Lemma C.8 implies that
y/w*
x El [|lwllpp"
min kE(1,m)
[ I|.
and therefore Lemma C.9
implies that the e, max-margin hyperplane has margin On the other
hand, any separating hyperplane for {[BB((x y:) bm has separation margin that is at worst zero. Therefore, any separating hyperplane is an e, max-margin hyperplane.
C.4
Robust ERM over Diagonal Networks
We first show Corollary 3.7
Proof. A diagonal neural network falag (x; u) is 2-homogencous, since for any c > 0, holds:
faiag (x: cu) = ((cu)) )2 (cu_)² xx) = c² (u u² x).
(44)
Furthermore, for any x, the optimal perturbation is scale invariant as is: -u, u2), which is scale invariant, i.e.,
argmin 18 Se (u. u² x +) sign((ou,) (ou )2) sugn(u? u2) for any a 0. Thus, fann satisfies the condi-
tions of Theorem 3.6
D
23

---

Now, we provide the proof of Proposition 3.8, which states that Eg minimization in parameter space equivalent & minimization predictor space for robust ERM in diagonal networks.
Proof. Let us recall the two optimization problems:
u4 ERd u ER (1lu+ 112 -uuull12 l12)
min
(45)
min y/ {u, xu,xx,) 2 1, Vi [m],
x x St
and
min 2 ||/]
(46)
s.t. min Yi (w, 2 1, Vi E [m].
||x] Se
We will show that the two problems share the same optimal value OPT. Let (ū+, ū_),, w be optimal solutions of 45) and (46). respectively, with corresponding values OPTA, OPTB.
First, we show that OPTB OPTA Let u - then satisfy the constraints of (46) and:
|
u
U44
ū= ت+ + أー
$
1
(u+.) 11 ,) 2 (u+.. + و)²
(47)
4
j=l
1
[
12 + - 13 OPTΛ.
2
As w is feasible point of 46). it is OPTB
w 1 and we deduce OPTs S O
Now, we prove the reverse relation. We decompose w to its positive and negative part, w u. 2² where, observe, the supports (set of indices with non-zero values) of û û_ do not overlap. Then, (ū+, ú_) satisfy the constraints of (45) and, furthermore:
(11- + | 112)
w < OPTB.
(48)
Since (Ū., ú_) is feasible point of (45 we deduce that OPT S OPT
D Cases of Steepest Descent & Implicit Bias
Coordinate Descent In coordinate descent, at each step we only update the coordinate with the largest absolute value of the gradient. Formally, its update is given by:
aL(w.) Ow,[1] e, i argmax
aC(w,)
Aw, E conv
(49)
Ow:h7
jE[d]
where e;, E [d], denotes the standard basis and conv (-) stands for the convex hull. Coordinate descent has long been studied for its connection with the & regularized exponential loss and Adaboost. corresponds to Steepest Descent with respect the norm, and at each step holds: |/w/]
[| In our experiments, we found it difficult to run robust ERM with coordinate descent for large values of perturbation e, both in linear models and neural networks. Also, it is computationally challenging to scale coordinate descent to large models, since only one coordinate gets updated at a time. These are the main reasons why we chose to experiment with Sign (Gradient) Descent in Section 4.2
24

---

ERM (d = 512, Kw 512, 2, K2
Robust ERM (d 512, E= Ki 512. 4)
Generalizze Lenerraiizttin Gap
Generalizz Ceneralization Gap
80
Robust
20
20
2
2
2
m
ERM (d' 512, 0, Kw 4, ky
Robust ERM (d' 512, 41 Kw 4. K.
Leneralization Gap
Robust Generalization Gap
m
2
27
2
Figure 5: Binary classification of data coming from dense teacher w and sparse data x (top) and from a sparse w* and sparse data x (bottom). We compare performance of different algorithms with (right) without (left) f.x: perturbations of the input in IRd using linear models. We plot the (robust) generalization gap, i.e., (robust) train minus (robust) test accuracy, of different learning algorithms versus the training size m. For robust ERM, accordance to the bounds of Section 2.2 it can still be the case that l solutions will generalize better in robust ERM, due the significant advantage of them ERM.
to be & of the largest permissible value e*. In
Sign (Gradient) Descent In Sign (Gradient) Descent, we only use the sign of the gradient to update the iterates, i.e.
Aw, -iggn((((w.)))
(50)
corresponds to steepest descent with respect the fox norm. connection with popular adaptive optimizers has made it an interesting algorithm to study for deep learning applications.
Implicit bias in homogeneous networks From the results of [Lyu and Li 2020]. we know that, for homogeneous networks, gradient descent converges in direction to KKT point of maximum margin optimization problem defined by the &2 norm. For steepest descent, on the other hand, there is such characterization, yet expect similar result hold; namely, we expect running ERM with steepest descent to converge in direction to a point that has some relation to the maximum margin optimization problem defined by the norm of the algorithm. By making a leap of faith, we expect something similar to hold for robust ERM. Since the promotion of a margin in one norm can have very different properties from the promotion of margin in different norm, we expect robust ERM with gradient descent and sign descent to yield solutions with different properties.
E
Additional Experiments
Linear models We plot (robust) generalization gaps vs dataset size m for distributions with (kw, kx) equal to (512, 4) (Dense, Spurse) and (ky, kx) equal to (4, 4) (Sparse, Sparse) on the top and the bottom of Figure 5 respectively. In accordance to the bounds of Section 2.2 it can still be the case that & solutions will generalize better robust ERM, due to the significant advantage of them in ERM. In Figure 6 we produce heatmaps similar to those of Figure but the benefit of CD over CD measured with respect to "clean" generalization = 0), no matter what value of was used during training. In particular, for each combination of data/weight sparsity and perturbation used at training, we compute clean generalization gaps of and GD solutions for various values of dataset size m.
2 (CD(m) CD(m)) dm, whereas in We then aggregate the results over m and compute 210 I
Section 4.1 the curves GD(m), CD(m) referred the robust error (w.r.t. the value of used during training). We observe that there cases such as the Dense, Dense one with kw lx 512
25

---

Standard Generalization
K = ((d)
kw = @(v
Perturbation
logd
Zlogd
vi
d
logd
2logd
va
d
kw ((2logd)
Kw @(logd)
Perturbations
logd
2logd
.d
logd
2logd
vd
Kx
Kx
0%
5%
10%
15%
20%
Figure 6: Average benefit, i.c. 2 Z (GD(m) CD(m)) dm, of CD over GD (in terms "clean" generalization gap) for different values of teacher sparsity kww, data sparsity lxx and magnitude of perturbation used during training (evaluation here is always with respect 0 "standard" generalization). The dimension is fixed be 512.
2
that for 0 (in particular equal to e* bottom right corner in top left subplot), GD generalizes better than CD in terms of clean error, even though it is the other way around for robustness see Figure Figure [ (bottom right). This suggests that even if nail the optimization bias in robust ERM, we might still incur a tradeoff between robustness and accuracy [Tsipras et al. 2019]. However, this need not always be the case; for example for Sparse, Dense data, such tradeoff is observed.
Fully-Connected Neural Networks In Figure 7 we plot (robust) accuracy during training in ERM and robust ERM 0.2, 0.3) for I hidden layer ReLU networks trained subset of 100 images (randomly drawn in each seed) of digits 2 and 7 from the MNIST dataset. We observe that the gap between the performance of gradient descent and steepest descent larger in robust ERM than in ERM.
Convolutional Neural Networks In Figure we plot the (robust) train and test accuracy during training for various combinations of dataset size and perturbation magnitude. The main observation, summarized also in Figure (left) in the main text, that when there are little available data m, the implicit bias in robust ERM affects generalization more than in "standard" ERM (row-wise comparison in the Figure). Notice that the artifact of the light-ish bottom right corner in Figure (non- trivial gap between GD and SD for 10, 000 and 0) is due the fact that SD becomes unstable at that time near convergence. Reducing the learning rate would have allievated this "anomaly".
Experimental details
In this Section, we provide more details about our experimental setup. All experiments are im- plemented in PyTorch and were run either multiple CPUs (experiments with linear models) or
26

---

GPUs. Estimated GPU hours: 200. Link to github repository: price- www-iimsmttteeeeeeeeeeeeeeeeeeee bias/tree/main
https: https://githus: https//ggghuub...css111222222
F.1 Experiments with synthetic data
Accuracy m-100
We consider the following distributions:
1. Dense, Dense: We sample points x; ~ NO, Ia), [m]] and ground truth vector w ~ (0, La) that la- bels each of the m points with y/1 sgn((w",x:))
Accurary
90
85
80
75
Robust ERM 0.2
100
2. k-Sparse, Dense: We sample points
Robust Accuracy
95
x, ~ (-1,0,+13,7 E [m], with corresponding probabilities (22
85
(so expected number of non- zero entries is k) and ground truth vector w ~ (O, La) that labels each of the m points with y/
5. }
80
75
Robust z
Robuct Accuracy
95
90
85
3. Dense, k-Sparse: Same as before, but now X dense and w is k--paare (with high probability).
80
75 10'
10 Epochs
10a
4. k-Spurse, k- k-Sparse: We sample points x; ~ NO, Ia), i E (m]) and ground truth vector w (- +1} with corresponding probabilities 22. 1-
test
train
tast
Figure 7: Accuracy during training in ERM (top) and robust ERM for c = 0.2 (center) and 0.3 (bottom). Setting: hidden layer ReI.U networks trained on subset of MNIST. Mean over 3 ran- dom seeds randomness affects initialization and draw of random dataset. The gap between the gen- cralization of the algorithms is more significant in robust ERM.
3. k) (so expected number of non- zero entries is k) that labels each of the m points with y, sgn((w" ((w x.)).
Linear models For the experiments with lin- ear models f(x; w) = (w,x), we train with the exponential loss and we an (adaptive) learning rate schedule TI min (B-c)² ((w,)
where 7 is finite upper bound (105 in experiments) and B is the largest for norm of the train data. This type of learning rate schedule can be derived by a discrete-time analysis of robust ERM over linear models (the direct analogue of Theorem 3.3). A similar learning rate schedule appears in the works of Gunasekar et al. (201a)].. Lyu and Li [2020]. To allow a fair comparison between the two algorithms, we stop their execution when they reach the same training loss value value) (10-5), We start from the all-zero, w = O, initialization.
Diagonal neural networks For the experiments with the diagonal linear network fx; w) = (w, x). with w u² u2, we use constant, small, learning rate x 10 and we adopt the same stopping criterion as with the "vanilla" linear models. We initialize u+, u. with constant value of vza (where a is the initialization scale and d the input dimension) which has been standard in prior works with diagonal networks. We set a 10-3 to promote "feature" learning, i.e. to induce the implicit bias "faster" see [Woodworth et al.) 2020).
For all the runs with the various models/algorithms, we sample de independent points and use them as a test set (one draw per dimension, i.e. same test dataset across the different values of m and e). The maximum value of perturbation, e*, is estimated by running ERM with coordinate descent for 10s iterations. Notice that this results to a different e* for each different draw of the dataset. The robust test accuracy efficiently calculated, since the adversarial points can be calculated in closed form for linear models. Our experimental protocol tried to ensure that we reach 100% (robust) train accuracy in all runs. This true all cases but the distributions with sparse data, where we found that for
If the algorithm has not reached this value after 2 10t iterations, stop that epoch.
27

---

Accuracy- mukccisss Im-100, (=0]
Accuracy muliddass (m-100, 2m2.d)
Accuracy muliidass, (m-100, 2w2.4)
78
Ezeets
Eseehs
Eseehs
Accuracy wis.iissss Im- 250 e-
Accuraty mutiitiss Accuncy-mubitee
(5-250, c-2.3)
Accuracy muliitsse (5:250 (-d.4)
Escent
Eseehs
Esceht
Arcuwey- multi aas, in mm-100m 0000. 2-
Accuraty mul clnss (m 10000, c-0.31
Accuracy mulliiasss (m 10000, g-0-4)
kmd
Epeche
Esechs
Esochs
Figure 8: Training curves of CNNs trained on subsets of MNIST for various combinations of dataset size m and perturbation magnitude e.
training datasets of cardinality 2d, the margin of the dataset was small and, thus, convergence was very slow. In these cases, the robust train accuracy approached 100%, but it was not exactly equal to it.
F.2 Experiments with neural networks
In all the experiments with the various values of and m, we train with 3 random seeds which correspond to different set of samples drawn from the full dataset and a different initialization.
Fully Connected Neural Networks We run GD and SD with the same set of hyperparameters constant learning rate equal to 10-5, batch size equal to the whole available data (the amount varies across different experiments), and, when e >> O, we estimate robustness by calculating perturbations with (projected) gradient descent (PGD). We use 10 iterations of PGD with step size = 5. The initialization of the networks is scaled down by a factor of 10 to promote feature learning and faster margin maximization. We use the exponential loss.
Convolutional Neural Networks We use standard architecture from Madry al. 2018 consist- ing of convolutional, max max-pooling and fully connected layers. The fully connected layers contain biases, the network is not homogeneous. We start from PyTorch' 's default initialization. We used a constant learning rate equal to 0.1 for GD and equal to 0.0001 for SD (SD would diverge during training with larger learning rates that we tried). In Figure 3 (right) in the main text, we report the difference between accuracies obtained after convergence of train error to O. In order to standardize the evaluation of the two algorithms, the reporting time corresponds to the first epoch hitting certain train loss threshold, i.c. 10-3, For more challenging training regimes (i.e. large e), this threshold was set larger (10-1), as we found it difficult optimize very small train loss values. In the
experiments with CNNs, we used the cross entropy loss during training. When > O, we use 10 iterations of PGD with step size a S.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We theoretically reason for the effect of implicit bias of robust ERM in the robustness of linear models. We experimentally study this effect in neural networks.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We are very explicit that out theoretical results hold for linear models. In Section 4.2 we discuss why it is not straightfoward reason about nonlinear models.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: All assumptions are clearly stated in the theorems. The proofs appear in the Appendix. Any Lemmata that useful for the main theorems are proven there.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide a comprehensive description of our experimental setup in Section F We describe our data distributions (for the experiments with synthetic data), our models and our algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
30

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
github repository linked.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //nips fiiaps.cc/publie wwtppbbiccgguueeeeeooooooccpcped
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Everything is described in detail in Section F (hyperparameters, reasons they were chosen this way etc).
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Figures that compare the performance of different algorithms show the mean value and the standard deviation over random seeds. The seeds control draw of the dataset/iniiialization We use numpy for calculating the error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments were run on both CPUs and GPUs, and a description exists in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The endgoal of our line of research train safer and robust models.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not think that it is appropriate to discuss the societal impact of our work in a mainly theoretical paper, risks misdirecting the attention reader.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Data are synthetic and/or publicly available online.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the creators of the dataset that we use (MNIST).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "0G0BJl8oyM", "reviewer": "Reviewer_ey2u", "summary": "This paper explores a linear classification scenario, investigating the factors that contribute to the gap between empirical adversarial risk and expected adversarial risk. Furthermore, they discuss which type of regularization should be applied in different cases. There are also simulations results to support their points.", "questions": "See weakness.", "limitations": "No negative social impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper is well-written with a clear structure. Motivations are well-explained on why the authors study the problem and the contributions of this study are well discussed. The analysis for the theoretical results are helpful in understanding. Overall, it is easy to follow the logic and flow of the paper.\n\n2.Theoretical results are solid and well-organized. The authors made the theoretical settings clear.\n\n3.Empirical results support the theoretical findings.", "weaknesses": "1.In Theorem 2.1, it is not clear whether the constant $\\rho$ has influences on other constants shown in the theorem.\n\n2.While these results mainly focus on the gap between empirical adversarial risk and expected adversarial risk, maybe the discussions about their influences on expected risk and empirical adversarial risk are lacked. \n\n3.As Theorem 3.3 focuses on steepest gradient dynamics on linear model, and Theorem 3.6 is about gradient flow on diagonal model, from my side, it is better to add a result about steepest gradient dynamics on diagonal model to make the analysis more sufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your critical and positive evaluation of our work. We respond to your questions:\n\n1. > In Theorem 2.1, it is not clear whether the constant $\\rho$ has influences on other constants shown in the theorem.\n    \n    Thank you for the comment. The empirical margin $\\hat{\\rho}$ appears in the statement of Proposition 2.2 due to a typo, and it does not affect the bound in eq. 7, nor does it influence any constants as presented there. In fact, it is not used in the proof in the Appendix. We can obtain more refined, data-dependent versions of this bound by leveraging the empirical margin $\\hat{\\rho}$, but they do not offer any insights related to our discussion in Section 2, and we opted not to include such a result for the sake of brevity, as it could have misdirected the focus. See also our remark in lines 692-693 in the proof in the Appendix, where we address this issue and point the interested reader to a standard reference that discusses the role of $\\hat{\\rho}$ in generalization bounds. We removed the constant from the statement in lines 127-128, as well as from line 147, where it also appeared due to a typo. Thank you!\n\n\n2. > While these results mainly focus on the gap between empirical adversarial risk and expected adversarial risk, maybe the discussions about their influences on expected risk and empirical adversarial risk are lacked.\n\n    Thank you for this very interesting suggestion (we assume that you meant to say \"expected risk and empirical risk\", instead of \"expected risk and empirical adversarial risk\")! In short, our search for robust predictors can actually harm the standard generalization error (error measured without perturbations), **if** the type of the perturbation is not \"aligned\" with the type of data. For example, in the case of *Dense, Dense* data in pg. 4, we expect from the generalization bounds to see a tradeoff between robustness and accuracy. The reason is that small $\\ell_2$ norm solutions are preferred for standard generalization, while small $\\ell_1$ solutions are better for robustness. This can also be observed in the experiments. We measure the standard generalization error ($\\epsilon=0$, regardless of the value of $\\epsilon$ used during training) and we produce a figure similar to Figure 2, consisting of heatmaps with the average difference between the performance of gradient descent (GD) and coordinate descent (CD). The figure can be accessed through the following link: https://ibb.co/sw7TWMD. Indeed, we observe that, for example, when $k_{\\mathcal{X}}=k_{\\mathcal{W}}=d$ (*Dense, Dense*) and we train for large perturbations, $\\epsilon = \\frac{\\epsilon^\\star}{2}$ (bottom right corner in top left subplot), GD generalizes better than CD in terms of standard generalization error. If we contrast this with the same datapoint in Figure 2 (where we measure the robust error), we see that there is a tradeoff between robustness and accuracy, since CD has better robust generalization. However, this is not always the case; for example for *Sparse, Dense* data, no such tradeoff is observed. This provides a more nuanced understanding of this well documented tradeoff [1] and suggests that the implicit bias of optimization in robust ERM is at the heart of this tradeoff as well. The focus of the paper was on robust generalization, but we agree with you that a discussion of standard generalization could be interesting in this context, space permitting. We will include the above results in the experiments section and add some discussion in Section 2 after Proposition 2.2. Thank you!\n    \n3. > As Theorem 3.3 focuses on steepest gradient dynamics on linear model, and Theorem 3.6 is about gradient flow on diagonal model, from my side, it is better to add a result about steepest gradient dynamics on diagonal model to make the analysis more sufficient.\n\n    The reason we opted to include results for gradient flow is essentially the non-smoothness of the robust loss for general $\\ell_p$ perturbations, which complicates the technical arguments. In fact, as far as we understand, many proofs that have appeared in prior works concerning the implicit bias of gradient descent in robust ERM contain unjustified steps and non-rigorous parts and it is unclear how to rectify them, without many additional simplifying assumptions. Take, for instance, the proof of Theorem 3.1 in [2], which is about the implicit bias of gradient descent applied on the robust loss with linear models. The usage of Taylor's Theorem, as well as the bound on the sharpness of the Hessian on pg. 12 appear to be wrong and it is technically non-trivial to sidestep these challenges which are due to the non-smoothness of the loss. While providing rates of convergence is very interesting in its own right, such results do not affect our conclusions on the importance of implicit bias in the robust generalization of models. \n    \n    \nWe would like to thank you once again for reviewing our work and helping us improve its presentation, especially with regard to weakness no.2. Please let us know if you have any more questions. If there are no outstanding concerns, we would kindly ask you to consider raising your score which would substantially help in reaching a reviewer consensus. Thank you.\n\n[1]. Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. Robustness may be at odds with accuracy.\n\n[2]. Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data.", "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": "", "extra_scores": {}}, {"review_id": "wPHobZHZTS", "reviewer": "Reviewer_mpQX", "summary": "In this paper, the authors study the issue of large generalization gap with Robust ERM objective, they connect this with the implicit bias of optimization (including architecture and the optimization algorithm). The findings suggest that optimizing models for robust generalization is challenging since it is hard to do the right capacity control for robust machine learning.", "questions": "See weakness", "limitations": "See weakness", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper has in-depth investigations into how does the choice of regularization norm affect the generalization ability of the model w.r.t. sparsity of data, optimization algorithm and choice of architecture\n- The authors validate their findings in both linear models and NN", "weaknesses": "- The theory studies might be still too limited", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing & positively assessing our work and for highlighting its strengths. We address your only concern:\n\n> The theory studies might be still too limited\n\nThis paper is the first to consider the connection between the implicit bias of optimization in adversarial training/robust ERM and robust generalization and it is also the first that identifies implicit bias as a main source of many challenges in robust machine learning (such as the large generalization gap, robustness/accuracy tradeoff, etc.). As a result, we believe it is natural that we began our theoretical analysis with the simplest models that permit this. Please note that stronger theoretical results would have required tight generalization bounds for more complicated classes of models (such as neural networks) and this is a central question in deep learning theory, even in the absence of adversarial perturbations - see, for instance, [1]. It could be interesting to derive a more general result for the case of one hidden layer ReLU neural networks, where a tight (robust) generalization bound exists (Theorem 10 in [2]). However, obtaining a characterization of the implicit bias of robust ERM with various optimization algorithms (in *predictor space*) is highly non-trivial for this class of models and would require many new techniques and generalization of previous results on ERM from e.g. the work of Savarese et al. [3]. We are actively working in this direction for a follow-up study.\n**Furthermore**, our experimental results on neural networks suggest that the phenomena that we identify are more general and we are happy that you recognized this in your evaluation of the strengths of this work. We would argue that the theoretical part of our study is not limited (since it is rich in new ideas) and we would be happy to listen to any suggestions that you might have on directions that might be worth developing further.\n\n[1]. Spectrally-normalized margin bounds for neural networks. Peter Bartlett, Dylan J. Foster, Matus Telgarsky.\n\n[2]. Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks. Pranjal Awasthi, Natalie Frank, Mehryar Mohri.\n\n[3]. How do infinite width bounded norm networks look in function space? Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro.", "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": "", "extra_scores": {}}, {"review_id": "g0j6swtF9J", "reviewer": "Reviewer_Pp2c", "summary": "The paper studies the implicit bias of robust Empirical Risk Minimization (ERM) and its connection with robust generalization. In regularized classification, the authors discuss the choice of regularization for a given perturbation set to improve robust generalization. In the unregularized setting, they study the implicit bias of steepest descent when applying it to the worst-case exponential loss in scenarios where the data is separable. They investigate two architectures: linear models and diagonal neural networks.", "questions": "Could the authors elaborate on the technical challenges they faced in proving their results, especially the result of implicit bias in linear models?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written, and its contributions are well-explained.\n 2. The difference between the convergence of Gradient Descent in linear models and diagonal neural networks with $\\ell_{\\infty}$ perturbations is a very interesting result.", "weaknesses": "In my opinion, a weakness of the paper is that while the authors engage in an interesting discussion in the technical sections, the results presented in the paper are not very insightful on their own:\n\n1. The result presented in Section 2 is directly derived from Theorem 2.1, which is borrowed from prior works, and Rademacher Complexity.\n 2. As the authors mention, the result of implicit bias in linear models is not surprising, and its proof is based on techniques from prior works.\n3. The result of implicit bias in diagonal neural networks can be seen as a paraphrased theorem from prior work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our work and help us improve it. We first reply to some of your points regarding the weaknesses of this paper:\n\n> As the authors mention, the result of implicit bias in linear models is not surprising, and its proof is based on techniques from prior works.\n\nWhile it is true that we can anticipate such a result for the implicit bias of steepest descent in robust ERM, we argue that the main novelty lies in asking the question in the first place (\"*What is the effect of implicit bias of robust ERM in robust generalization?*\") and in its connection with generalization bounds. There are no prior works that study these questions. Furthermore, please note that the proof is not a simple extension of previous results and it is not based directly on the techniques of [1] - see also our response to your question below.\n\n> The result of implicit bias in diagonal neural networks can be seen as a paraphrased theorem from prior work.\n\nWe respectfully disagree. We leverage a result from prior work about robust ERM (Theorem 3.6) which characterizes the implicit bias of gradient descent for homogeneous networks in *parameter space*, while Corollary 3.7 and Proposition 3.8 establish the implicit bias of robust ERM in *function/predictor space*. This result is the first result of this kind for robust ERM. We are also confused about your previous point, since in Strength no.2 you complimented this result.\n\nResponding to your question, \n\n> Could the authors elaborate on the technical challenges they faced in proving their results, especially the result of implicit bias in linear models?\n\nThe optimization results are not trivial, since existing results for ERM, such as the ones found in [1], cannot be directly extended for the robust objective. In particular, Lemma 10 in pg. 18 in [1] cannot be generalized and this was a starting challenge that we faced. Furthermore, previous results on the implicit bias of gradient descent in robust ERM with linear models contain inconsistencies and unjustified steps [2]; the usage of Taylor's Theorem, as well as the bound on the sharpness of the Hessian in pg. 12 in that paper, appear to be wrong and it is technically non-trivial to sidestep these challenges which are due to the non-smoothness of the loss. As a result, we chose to analyze steepest flow for the robust objective, which has not been defined, let alone analyzed before. Particularly, Lemma C.2 uses a completely different idea than [1] and, since it is a general result about steepest descent/flow, it is interesting and beautiful in its own right.\n\nMore generally, we would like to defend the contributions of our paper (objecting to your score: \"poor\") by summarizing the most important ones:\n1. We connect the implicit bias of optimization in robust ERM with the robust generalization error, and we show how and why implicit bias is more significant in robust ERM than in stardard ERM (this is where the term \"price\" comes from).\n2. We paint a conceptual picture for the challenges faced in robust machine learning, which is rooted in foundational ideas of learning theory.\n3. We rectify a misconception from prior work [3, 4] that asserted that regularization via the dual norm is always beneficial for robust generalization.\n4. We provide rigorous results for linear models and diagonal neural networks against general $\\ell_p$ adversarial perturbations.\n5. We provide extensive experiments with synthetic data that validate the theoretical claims.\n6. We provide several experiments with neural networks in image classification settings with gradient descent and sign gradient descent, and experimentally identify and establish a new connection between robust generalization gap and optimization geometry.\n\nWe believe that the price of implicit bias in robust generalization is a new interesting phenomenon in robust machine learning and we believe there are many avenues for future work which can be inspired by this work. \n\nWe hope that succintly summarizing the contributions of our paper, while also elaborating on some technical challenges that we faced by anwering your question could make you reconsider your evaluation of our work. We would be happy to include some discussion on the technical challenges, if you think this would benefit the paper. Thank you very much!\n\n\n[1]. Characterizing Implicit Bias in Terms of Optimization Geometry. Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro.\n\n[2]. Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data.\n\n[3]. Rademacher Complexity for Adversarially Robust Generalization. Dong Yin, Kannan Ramchandran, Peter Bartlett.\n\n[4]. Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks. Pranjal Awasthi, Natalie Frank, Mehryar Mohri.", "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": "", "extra_scores": {}}, {"review_id": "e5f0pKt5bZ", "reviewer": "Reviewer_ZNCk", "summary": "This paper studies the generalization gap of robust empirical risk minimization for linear regression. The paper shows that the choice optimization algorithm or architecture affects the generalization gap of the trained linear model. In particular, a steepest descent algorithm w.r.t. $l_p$ norm finds the minimum $l_p$ norm interpolating solution on linearly separable data; a reparametrization of the linear model into a two-layer diagonal linear network has a bias toward minimum $l_1$ norm solution.", "questions": "See Weakness", "limitations": "See Weakness", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Connections between implicit bias (of optimization algorithm and of architecture) and adversarial robustness.\n2. Interesting discussion on the optimal regularization for robust ERM w.r.t. $l_\\infty$.\n3. Experiments are through and well presented.", "weaknesses": "1. The message in this paper is delivered but the supporting argument is rather incomplete: \n* Section 2.1 highlights the need for an optimal regularization given specific data assumption and threat model, but the discussion is primarily for $l_\\infty$ threat model. \n* Section 3.2 discusses how a diagonal linear network has a bias toward minimum $l_1$ solution, but the connection is not formal (the author acknowledges it in Remark 3.9).\n2. The technical contribution is minor in my opinion. The ERM counterparts of the results in Section 3 are well-known and extensively studied, and extending them to robust ERM is more or less straightforward.\n\nMinor comments:\n1. Corollary 3.5 refers to equation (8), which has $p^*$ as the conjugate of $p$, yet the corollary itself contains another $p^*$, it is confusing whether they are the same $p^*$.\n2. Referring steepest descent w.r.t. $l_1$ as \"coordinate descent\" is confusing. Generally, coordinate descent chooses the coordinate to be updated in a cyclic or random order. I understand there is a variation of CD that picks the coordinate with the largest gradient component, but plainly using CD may let the reader think of the more standard CD algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our paper and for your positive evaluation of our work. \nFirst, let us correct a small mistake on your summary of our work (since reviews might become public in the future and readers might get confused):\n> This paper studies the generalization gap of robust empirical risk minimization for linear regression.\n\nWe do not study regression problems, but classification with linear (as a function of the input) models. Experiments contain results with non-linear models.\n\n\nWe address your questions:\n\n\n> Section 2.1 highlights the need for an optimal regularization given specific data assumption and threat model, but the discussion is primarily for $\\ell_\\infty$ threat model.\n\nIndeed, we chose to focus on the $\\ell_\\infty$ case in Section 2, since (a) this type has received much attention in practical applications and (b) it illustrates clearly the main message of our paper. Gradient descent is well positioned for $\\ell_2$ perturbations in linear models, so there is not much value to study this case in detail from a generalization perspective. Please note that it has often been the case for theoretical studies on robustness in the past to only focus on one type of perturbation [1, 2]. In Section 3, however, our optimization results cover a general case of $\\ell_p$ perturbations. Finally, in the experiments of Section 4.2 where we consider different classes of non-linear networks, we effectively study different kinds of threat models (since different feature extractors map $\\ell_\\infty$ perturbations to different spaces).\n\n> Section 3.2 discusses how a diagonal linear network has a bias toward minimum $\\ell_1$ solution, but the connection is not formal (the author acknowledges it in Remark 3.9).\n\nWe would like to clarify that Corollary 3.7 and Proposition 3.8 and their corrresponding proofs in the Appendix are formal and rigorous. However, as you point out, we can only show that we get convergence to a stationary point in Corollary 3.7. As it is often the case in results in this area (see for instance [3]), a full characterization of a limiting point as local optimum is elusive, so we often end up with characterization as first-order stationary points. It is unclear whether we can obtain stronger results here due to the non-smoothness of the adversarial objective, yet we are optimistic about it and we hope that future work can address this.\n\n> The technical contribution is minor in my opinion. The ERM counterparts of the results in Section 3 are well-known and extensively studied, and extending them to robust ERM is more or less straightforward.\n\nThe optimization results are not trivial, since existing results for ERM, such as the ones found in [4], cannot be directly extended for the robust objective. In particular, Lemma 10 in pg. 18 in [4] cannot be generalized and this was a starting challenge that we faced. Furthermore, previous results on the implicit bias of gradient descent in robust ERM with linear models contain inconsistencies and unjustified steps [5]; the usage of Taylor's Theorem, as well as the bound on the sharpness of the Hessian in pg. 12 in that paper, appear to be wrong and it is technically non-trivial to sidestep these challenges which are due to the non-smoothness of the loss. As a result, we chose to analyze steepest flow for the robust objective, which has not been defined, let alone analyzed before. Particularly, Lemma C.2 uses a completely different idea than [4] and, since it is a general result about steepest descent/flow, it is interesting and beautiful in its own right.\n\n> Corollary 3.5 refers to equation (8), which has $p^\\star$ as the conjugate of $p$, yet the corollary itself contains another $p^\\star$, it is confusing whether they are the same $p^\\star$.\n\nThank you for this comment. They are the same $p^\\star$. \n\n> Referring steepest descent w.r.t.  as \"coordinate descent\" is confusing. Generally, coordinate descent chooses the coordinate to be updated in a cyclic or random order. I understand there is a variation of CD that picks the coordinate with the largest gradient component, but plainly using CD may let the reader think of the more standard CD algorithm.\n\nThank you for the suggestion. It is a matter of definitions and conventions. We followed the language of *Convex Optimization,\nStephen Boyd and Lieven Vandenberghe* [6] (Section 9.4.2), which is one of the main references in Convex Optimization. We will add a note in the main text and in the appendix, stating that the algorithm should not be confused with other variations of CD. Thank you!\n\nPlease let us know if our response addressed your concerns and we hope that you would consider raising your score if this is the case. Thank you!\n\n\n[1]. The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks. Spencer Frei, Gal Vardi, Peter L. Bartlett, Nathan Srebro.\n\n[2]. Rademacher Complexity for Adversarially Robust Generalization. Dong Yin, Kannan Ramchandran, Peter Bartlett.\n\n[3]. Gradient Descent Maximizes the Margin of Homogeneous Neural Networks. Kaifeng Lyu, Jian Li.\n\n[4]. Characterizing Implicit Bias in Terms of Optimization Geometry. Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro.\n\n[5]. Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data.\n\n[6]. Convex Optimization. Stephen Boyd and Lieven Vandenberghe.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies how the implicit bias of optimization in robust empirical risk minimization (robust ERM) influences robust generalization under adversarial perturbations. It identifies two key factors affecting robustness: the optimization algorithm and the model architecture. The study is supported by simulations with synthetic data and experiments with deep neural networks. The reviewers were satisfied with the responses provided during the rebuttal and found the paper interesting. The authors are encouraged to incorporate the comments and feedback received to strengthen their work.
Decision: Accept (poster)