Improved Sample Complexities for Deep Neural Networks and Robust Classification via an All-Layer Margin
Authors: Colin Wei
Tengyu Ma
Venue:  (2020)
Keywords: deep learning theory
generalization bounds
adversarially robust generalization
data-dependent generalization bounds

Abstract: For linear classifiers, the relationship between (normalized) output margin and generalization is captured in a clear and simple bound – a large output margin implies good generalization. Unfortunately, for deep models, this relationship is less clear: existing analyses of the output margin give complicated bounds which sometimes depend exponentially on depth. In this work, we propose to instead analyze a new notion of margin, which we call the “all-layer margin.” Our analysis reveals that the all-layer margin has a clear and direct relationship with generalization for deep models. This enables the following concrete applications of the all-layer margin: 1) by analyzing the all-layer margin, we obtain tighter generalization bounds for neural nets which depend on Jacobian and hidden layer norms and remove the exponential dependency on depth 2) our neural net results easily translate to the adversarially robust setting, giving the first direct analysis of robust test error for deep networks, and 3) we present a theoretically inspired training algorithm for increasing the all-layer margin. Our algorithm improves both clean and adversarially robust test performance over strong baselines in practice.

Published as a conference paper at ICLR 2020
IMPROVED SAMPLE COMPLEXITIES FOR DEEP NET- WORKS AND ROBUST CLASSIFICATION VIA AN ALL- LAYER MARGIN
Colin Wei Stanford University colinee@@ttaffrdd.cdl
Tengyu Ma
Stanford University
tengyuma@st aaammmsstaffrdd.c..m
ABSTRACT
For linear classifiers, the relationship between (normalized) output margin and generalization is captured in clear and simple bound large output margin implies good generalization. Unfortunately, for deep models, this relationship is less clear: existing analyses of the output margin give complicated bounds which sometimes depend exponentially on depth. In this work, we propose to instead an- alyze new notion of margin, which we call the "all-layer margin." Our analysis reveals that the all-layer margin has clear and direct relationship with general- ization for deep models. This enables the following concrete applications of the all-layer margin: 1) by analyzing the all-layer margin, we obtain tighter general- ization bounds for neural nets which depend on Jacobian and hidden layer norms and remove the exponential dependency translate to the adversarially robust setting, giving the first direct analysis of robust test error for deep networks, and 3) present a theoretically inspired training al- gorithm for increasing the all-layer margin. Our algorithm improves both clean and adversarially robust test performance over strong baselines in practice.
depth 2) our neural net results easily
INTRODUCTION
The most popular classification objectives for deep learning, such as cross entropy loss, encourage larger output margin the gap between predictions the true label and and next most confident la- bel. These objectives have been popular long before deep learning was prevalent, and there a long line of work showing they enjoy strong statistical guarantees for linear and kernel methods (Bartlett and Mendelson, 2002; Koltchinskii et al., 2002; Hofmann et al., 2008; Kakade et al., 2009). These guarantees have been used explain the successes of popular algorithms such SVM (Boser al., 1992; Cortes and Vapnik, 1995).
For linear classifiers, the relationship between output margin and generalization is simple and direct generalization error is controlled by the output margins normalized by the classifier norm. Con- cretely, suppose we have n training data points each with norm 1, and let 74 be the output margin on the i-th example. With high probability, if the classifier perfectly fits the training data, we obtain'
Σ classifier norm
Test classification error 5
+ low order terms
(1.1)
n
For deeper models, the relationship between output margin and generalization is unfortunately less clear and interpretable. Known bounds for deep nets normalize the output margin by a quantity that either scales exponentially in depth or depends complex properties of the network (Neyshabur et al., 2015; Bartlett et al., 2017: Neyshabur et al., 2017b; Golowich et al., 2017: Nagarajan and Kolter, 2019; Wei and Ma, 2019). This is evidently more complicated than the linear case in (1.1). These complications arise because for deep nets, it is unclear how to properly normalize the output
'This is stronger version of the classical textbook bound which involves the min margin on the training examples. We present this stronger version hecause motivates our work better. It can be derived from the results of Srehro al. (2010).

---

Published as a conference paper at ICLR 2020
margin. In this work, we remedy this issue by proposing new notion of margin, called "all-layer margin", which we use to obtain simple guarantees like (1.1) for deep models. Let m, be the all- layer margin for the i-th example. We can simply normalize it by the sum of the complexities of the weights (often measured by the norms or the covering number) and obtain a bound of the following form:
Σ sum of the complexities of each layer)
Test error 5
- low order terms
(1.2)
m
As the name suggests, the all-layer margin considers all layers of the network simultaneously. unlike the output margin which only considers the last layer. We note that the definition of the all-layer margin is the key insight for deriving (1.2) given the definition, the rest of the proof follows naturally with standard tools. (Please see equation (2.2) for a formal definition of the margin, and Theorem 2.1 for a formal version of bound (1.2).) To further highlight the good statistical properties of the all-layer margin, we present three of its concrete applications in this paper.
1. By relating all-layer margin to ouiput margin and other quantities, we obtain improved gener- alization bounds for neural nets. In Section 3, we derive an analytic lower bound on the all-layer margin for neural nets with smooth activations which depends on the output margin normalized by other data-dependent quantities. By substituting this lower bound into (1.2), we obtain a gen- eralization bound in Theorem 3.1 which avoids the exponential depth dependency and has tighter data-dependent guarantees than (Nagarajan and Kolter, 2019; Wei and Ma, 2019) in several ways. First, their bounds use the same normalizing quantity for each example, whereas our bounds are tighter and more natural because we use different normalizer for each training example - the local Lipschitzness for that particular example. Second, bound depends the empirical distribution of some complexity measure computed for each training example. When these complexities are small for each training example, we can obtain convergence rates faster than 1/vn. We provide more thorough comparison to prior work in Section 3.
Furthermore, for relu networks, we give tighter generalization bound which removes the depen- dency on inverse pre-activations suffered by (Nagarajan and Kolter, 2019), which they showed to be large empirically (see Section B.)). The techniques of (Wei and Ma, 2019) could not remove this dependency because they relied on smooth activations.
2. We extend our tools to give generalization bounds for adversarially robust classification error which are analogous to our bounds in the standard setting. In Section 4, we provide a natural ex- tension of our all-layer margin to adversarially robust classification. This allows us to translate our neural net generalization bound, Theorem 3.1, directly to adversarially robust classification (see Theorem 4. The resulting bound takes a very similar form as our generalization bound for clean accuracy it simply replaces the data-dependent quantities in Theorem 3.1 with their worst-case values in the adversarial neighborhood of the training example. As a result, also avoids explicit exponential dependencies on depth. As our bound is the first direct analysis of the robust test error, it presents a marked improvement over existing work which analyze loose relaxations of the adver- sarial error (Khim and Loh, 2018; Yin al., 2018). Finally, our analysis of generalization for the clean setting translates directly to the adversarial setting with almost no additional steps. This is an additional advantage of our all-layer margin definition.
3. We design a training algorithm that encourages a larger all-layer margin and demonstrate that improves empirical performance over strong baselines. In Section 5, we apply our regularizer to WideResNet models (Zagoruyko and Komodakis, 2016) trained on the CIFAR datasets and demon- strate improved generalization performance for both clean and adversarially robust classification. We hope that these promising empirical results can inspire researchers to develop new methods for optimizing the all-layer margin and related quantities.
1.1 ADDITIONAL RELATED WORK
Zhang et al. (2016); Neyshabur et al. (2017a) note that deep learning often exhibits statistical prop- erties that are counterintuitive to conventional wisdom. This has prompted a variety of new perspec- tives for studying generalization in deep learning, such as implicit algorithmic regularization (Gu- nasekar et al., 2017; Li et al., 2017; Soudry et al., 2018; Gunasekar et al., 2018), new analyses of interpolating classifiers (Belkin al., 2018; Liang and Rakhlin, 2018; Hastie al., 2019; Bartlett
2

---

Published as a conference paper at ICLR 2020
et al., 2019), and the noise and stability of SGD (Hardt et al., 2015; Keskar et al., 2016; Chaudhari et al., 2016). In this work, we adopt a different perspective for analyzing generalization by studying novel definition of margin for deep models which differs from the well-studied notion of output margin. We hope that our generalization bounds can inspire the design of new regularizers tailored towards deep learning. Classical results have hounded generalization error in terms of the model's output margin and the complexity of its prediction (Bartlett and Mendelson, 2002; Koltchinskii et al., 2002), but for deep models this complexity grows exponentially in depth (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2017b; Golowich et al., 2017). Long and Sedghi (2019) prove bounds for convolutional networks which scale with the number of parameters and their distance from initialization. Recently, Nagarajan and Kolter (2019); Wei and Ma (2019) derived complexity measures terms of hidden layer and Jacobian norms which avoid the exponential dependence on depch, but their proofs require complicated techniques for controlling the complexity of the output margin. Neyshabur et al. (2017a); Arora et al. (2018) also provide complexity measures related to the data-dependent stability of the network, but the resulting bounds only apply to a randomized or compressed version of the original classifier. We provide a simple framework which derives such bounds for the original classifier. Novak et al. (2018); Javadi et al. (2019) study stability-related complexity measures empirically.
A recent line of work establishes rigorous equivalences between logistic loss and output margin maximization. Soudry et al. (2018); Ji and Telgarsky (2018) 8) show that gradient descent implicitly maximizes the margin for linearly separable data, and Lyu and Li (2019) prove gradient descent con- verges to a stationary point of the max-margin formulation for deep homogeneous networks. Other works show global minimizers of regularized logistic loss are equivalent to margin maximizers, in linear cases (Rosset et al., 2004) and for deep networks (Wei et al., 2018: Nacson et al., 2019). A number of empirical works also suggest alternatives to the logistic loss which optimize variants of the output margin (Sun et al., 2014; Wen et al., 2016; Liu; Liang et al., 2017: Cao et al., 2019). The neural net margin at intermediate and input layers has also been studied. Elsayed et al. (2018) de- sign an algorithm to maximize a notion of margin intermediate layers of the network, and Jiang et al. (2018) demonstrate that the generalization gap of popular architectures can empirically be predicted using statistics of intermediate margin distributions. Verma al. (2018) propose a regu- larization technique which they empirically show improves the structure of the decision boundary at intermediate layers. Sokolić et al. (2017) provide generalization bounds based the input margin of the neural net, but these bounds depend exponentially on the dimension of the data manifold. These papers study margins defined for individual network layers, whereas our all-layer margin simultaneously considers all layers. This distinction is crucial for deriving our statistical guarantees.
A number of recent works provide negative results for adversarially robust generalization (Tsipras et al., 2018: Montasser et al., 2019; Yin et al., 2018; Raghunathan et al., 2019). We provide pos- itive results stating that adversarial test accuracy can be good if the adversarial all-layer margin is large on the training data. Schmidt et al. (2018) demonstrate that more data may be required for generalization on adversarial inputs than on clean data. Montasser et al. (2019) provide impossiblity results for robust PAC learning with proper learning rules, even for finite VC dimension hypothesis classes. Zhang et al. (2019) consider the trade-off between the robust error and clean error. Farnia et al. (2018) analyze generalization for specific adversarial attacks and obtain bounds depending exponentially on depth. Yin et al. (2018); Khim and Loh (2018) give adversarially robust general- ization bounds by upper bounding the robust loss via transformed/relaxed loss function, and the bounds depend on the product of weight matrix norms. Yin et al. (2018) also show that the product of norms is inevitable if we go through the standard tools of Rademacher complexity and the out- put margin. Our adversarial all-layer margin circumvents this lower bound because it considers all layers of the network rather than just the output.
1.2 NOTATION
We use the notation {a:)k=1 to refer to a sequence of l elements indexed by i. We will use o to denote function composition: f g(x) = =f(())). Now for function classes F,G. define Fog & (fog:: E F.g E 9). We use Dn to denote the partial derivative operator with respect to variable h, and thus for a function f(,, h2), use Dr. [h,, h2) to denote the partial derivative of f with respect to h; evaluated at (h,, h2)). We will use || to denote some norm. For function f mapping between normed spaces Dj, Do with norms ||r, Ilo. respectively,
3

---

Published as a conference paper at ICLR 2020
define llfllop _ supxer, | which generalizes the operator norm for linear operators. Let [] I denote the Frobenius norms and the sum of the absolute values of the entries of M, respectively. For some set S (often a class of functions), we Net (1(,,,,,, S) be the covering number of S in the metric induced by norm || || with resolution For function class F, let No F) denote the covering number of F in the metric (f. sup, llf(x) f(=)ll- For a function f and We bound generalization for a test distribution P given a set of n training samples, P. _ {( B:) where x E Do denotes inputs and y [7] is an integer label. We will also use Pa to denote the uniform distribution on these training samples. For a classifier F Do + R', we use the convention that ()) F(z)y is its predicted label on input I. Define the 0-1 prediction loss la.1 (F(x), to output I when F incorrectly classifies and otherwise.
[f
distribution P. we use the notation [I))).., - ([==)(]f(=)
WARMUP: SIMPLIFIED ALL-LAYER MARGIN AND ITS GUARANTEES
Popular loss functions for classification, such logistic and hinge loss, attempt to increase the output margin of a classifier by penalizing predictions that are too close to the decision boundary. Formally, consider the multi-class classification setting with classifier F Do + R', where I denotes the number of labels. We define the output margin example (a, v) by ((F(z))) & max F(x), - +y }.
For shallow models such linear and kernel methods, the output margin maximization objective enjoys good statistical guarantees (Kakade et al., 2009; Hofmann et al., 2008). For deep networks, the statistical properties of this objective are less clear: until recently, statistical guarantees depend- ing on the output margin also suffered an exponential dependency on depth (Bartlett et al., 2017; Neyshabur et al., 2017b). Recent work removed these dependencies but require technically involved proofs and result in complicated bounds depending on numerous properties of the training data (Na- garajan and Kolter, 2019; Wei and Ma, 2019).
In this section, we introduce a new objective with better statistical guarantees for deep models (The- orem 2.1) and outline the steps for proving these guarantees. Our objective is based on maximizing notion of margin which measures the stability of classifier to simultaneous perturbations at all layers. Suppose that the classifier F(x)= = f& .... o fi (x) is computed by composing functions fu...., fi. and let ....... ō, denote perturbations intended to be applied at each hidden layer. We recursively define the perturbed network output Fxx (1.....5p))) by
(1 6) = (x) + 51 ||=||2
he(x, 5) fe(h.-1 8)) + 6 || (2r, 8)[[2
(2.1)
F(z, 6) (2,
The all-layer margin will now be defined the minimum norm of ó required to make the classifier misclassify the input. Formally, for classifier F. input æ, and label y, we define
min
1
mr(#, v) A
(2.2)
subject to arg max F(x,
+
Note that the constraint that F(z, 8) misclassifies Furthermore, mp is strictly positive if and only if the unperturbed prediction F(x) correct. Here multiplying 6, by the previous layer norm [| (2r, 8)ll2 is important and intuitively balances the relative scale of the perturbations at each layer. We note that the definition above is simplified to convey the main intuition behind our results to obtain the tightest possible bounds, in Sections 3 and 4, we use the slightly more general m defined in Section A.
is equivalent to enforcing (F(x),)) < 0.
Prior works have studied, both empirically and theoretically, the margin of network with respect to single perturbations at an intermediate or input layer (Sokolić et al., 2017: Novak et al., 2018; Elsayed et al., 2018; Jiang et al., 2018). Our all-rayer margin is better tailored towards handling the compositionality of deep networks because considers simultancous perturbations to all layers, which is crucial for achieving its statistical guarantees.
4

---

Published as a conference paper at ICLR 2020
Fi} be the class of compositions of functions from function classes FI.....Fkk We bound the population classification error for F E F based on the distribution of mr on the training data and the sum of the complexities of each layer, mea- sured via covering numbers. For simplicity, we assume the covering number of each layer scales as M in Fi) & [CP/22] for some complexity Ci which is common for many function classes.
Formally, let F -
o.......
Theorem 2.1 (Simplified version of Theorem A.1). In the above setting, with probability 1 1-6 8-8 over the draw of the training data, all classifiers F F which achieve training error 0 satisfy
C. Vn
Ep((o
E BLN
2 + log"
mF y)
where ç & O [og]1//)++ogn is low-order term.
In other words, generalization is controlled by the sum of the complexities of the layers and the quadratic mean of 1/mp the training set. Theorem A.1 generalizes this statement to provide bounds which depend on the g-th moment of 1/mF for any integer > 0 and converge at rates faster than I/V For neural nets, C, scales with weight matrix norms and 1/mF can be upper bounded by a polynomial in the Jacobian and hidden layer norms and output margin, allowing us to avoid an exponential dependency on depth when these quantities are well-behaver on the training data.
We will break down the proof of Theorem 2.1 into two simple parts. The first part hinges on showing that my has low complexity which scales with the sum of the complexities at each layer. The second part relates mp the 0-1 loss using the simple fact that m (2. y) is nonzero if and only if F correctly classifies
Lemma 2.1 (Complexity Decomposition Lemma). Let m o F = {mp: F FJ denote the family of all-layer margins of function compositions F. Then
[ (
Nog
>> log N1g (ct,
Log
(2.3)
The covering number of an individual layer commonly scales as log (h S [c/ In this case, for all O, we obtain log (c, (E)
Lemma 2.1 shows that the complexity of mF scales linearly in depth for any choice of layers F,- In sharp contrast, lower bounds show that the complexity of the output margin scales exponentially in depth via product of Lipschitz constants of all the layers (Bartlett et al., 2017; Golowich al., 2017). Our proof only relies on basic properties of mp, indicating that my is naturally better- equipped to handle the compositionality of F. particular, we prove Lemma 2. by leveraging a uniform Lipschitz property of mp. This uniform Lipschitz property does not hold for prior defi- nitions of margin and reflects the key insight in our definition it arises only because our margin depends simultaneous perturbations to all layers.
Claim 2.1. For any two compositions F = fa ....o fi and f = Frs .... o Fa and any v), we have (mp(x,)) 3) m v)1 S v Et llfe R.
Proof sketch. Let 5* be the optimal choice of in the definition of my (x, y). We will construct 8 such that [|0]|2 < |15 112 E, llf F llep and > (x(x 8), y) = 0 as follows: define 3, - 6, + A;
for A, A (Z,6-1(Z,6"1 F. 1(x.5')) where h is defined as in (2.1) with respect to the classi- | (=.0"
fier F. Note that by our definition of || llpp we have ||Ai|2 Σ [| fallop- Now is possi- F(x, In particular, 8 is satisfies the misclassifica- tion constraint the all-layer margin objective for F. Thus, follows that mz(x,y) < ||01|2 S
ble to check inductively that F(x,
||5*||2 + || S mF(F.)) u) + v Eg 1I. R.ppp where the last inequality followed from |A S
5

---

Published as a conference paper at ICLR 2020
I15s - Billop. With the same reasoning,we we obtain mp v) S mp(a,y) + v., lI.. - fi fillop so (mr(e, v) ---mmpp(,1) w)1 v E: II Tullap
Given Claim 2.1, Lemma 2.1 follows simply by composing 6--covers of Fg. We prove a more general version in Section A (see Lemmas A.I and A.3.)
The second part of the proof of Theorem 2.1 is to upper bound the 0-1 test enror by the test error of some smooth surrogate loss o m.. result by Srebro al. (2010) shows that generic smooth losses & enjoy faster O(n ") covergence rates if the empirical loss is low. We straightforwardly combine Lemma 1 with their results to obtain the following generalization bound for mp:
Lemma 2.2. Suppose that is a 3-smooth loss function taking values [0, 1]. Then in the setting of Theorem 2.1, we have with probability 1 for all F EEE F:F:
3 Ep (((((((( = Er, (e(mm((mmm v)) +c (,, log2n log(1/6) + log log
(2.4)
2
for some universal constant > 0.
To complete the proof of Theorem 2.1, we will choose & my which upper bounds the 0-1 loss such that the right hand side of (2.4) gives the desired bound. In Section A, we formalize the proof plan presented here and also define a slightly more general version of m. used to derive the bounds presented in the following Sections and 4.
Connection to (normalized) output margin Finally, we check that when F is linear classifier, mp recovers the standard output margin. Thus, we can view the all-layer margin as an extension of the output margin to deeper classifiers.
Example 2.1. In the binary classification setting with a linear classifier F(z) = w x where the data x has norm 1, we have mr(a, v) max yw x=] = (F(x),
For deeper models, the all-layer margin can be roughty bounded by quantity which normalizes the output margin by Jacobian and hidden layer norms. We formalize this in Lemma 3.1 and use this to prove our main generalization bound for neural nets, Theorem 3.1.
GENERALIZATION GUARANTEES FOR NEURAL NETWORKS
Although the layer margin is likely difficult compute exactly, we can analytically lower bound it for neural nets with smooth activations. In this section, we obtain a generalization bound that depends on computable quantities by substituting this lower bound into Theorem 2.1. Our bound considers the Jacobian norms, hidden layer norms, and output margin on the training data, and avoids the exponential depth dependency when these quantities are well-behaved, as is the case in practice (Arora et al., 2018; Nagarajan and Kolter, 2019; Wei and Ma, 2019). Prior work (Nagarajan and Kolter, 2019; Wei and Ma, 2019) avoided the exponential depth dependency by considering these same quantities but required complicated proof frameworks. We obtain simpler proof with tighter dependencies on these quantities by analyzing the all-layer margin.
The neural net classifier F will be parameterized by r weight matrices (W and compute F(x) Wir (W(1)zz) ...) for smooth activation c. Let d be the largest layer dimension. We model this neural net by a composition of = 2r layers alternating between matrix multiplications and applications of and the subscript in parenthesis (s) to emphasize the different indexing system between weight matrices and all the layers. We will let (()) (() denote the || ||z norm of the layer preceding the i-th matrix multiplication evaluated on input x, and kij-i(z)) will denote the ||. llop norm the Jacobian of the j-th layer with respect to the 1-th layer evaluated on x. The following theorem bounds the generalization error of the network and is derived by lower bounding the all- allerayer margin in terms the quantitics (sg (r), (F(()))))))))))
Theorem 3.1. Assume that the activation 6 has a n'g -g-Liischitz derivative. Fix reference matrices (Aty, Big ha and any integer q > O. With probability 1 8 over the draw of the training sample

---

Published as a conference paper at ICLR 2020
Pay all neural nets F which achieve training error 0 satisfy
34/(x+2)
Ex I1
2/3 La(Pn) (i)
2/3
2/3
q glog² n
Eplco- o F] = SOO
+
(3.1)
n2/
where NN (3) captures local Lipschitz constant of perturbations layer and is defined by
((1-1(())6x-1-2((1) + (2,)))
KN (())
az, y)
(3.2)
((F(x).
for a secondary term (2) (r, v) given by
8/6- (1)
Ky 2y Ng)+y(
(io) v)
(z)
fmi
18122-15''
-1 (1)
(
Σ
ky-)())
1S ("
Here the second and third summations above over the choices of j.J satisfying the con- straints specified in the summation. We define a(s) by ((s) - min| VallW(o A (I
Brolll.i//oog d + poly(n and Ç (logm+tog(1/))+> +1) is a low-order term.
For example, when q = from (3.1) we obtain the following bound which depends on the second moment of (3) and features the familiar 1/ l/vn convergence rate in the training set size.
Eplca o F Er, Bp, 22) 1/3 (
3/2
log"
E
NN For larger 4, we obtain a faster convergence rate in but the dependency on (a() gets larger. We will outline proof sketch which obtains variant of Theorem 3.1 with slightly worse polynomial NN and (()). For simplicity we defer the proof the full Theorem 3.1 to Sections B and C. First, we need to slightly redefine mF so that perturbations are only applied at linear layers
dependency on (i)
(formally, fix 62 = 0 for the even-indexed activation layers, and let 6وg) - 82i-1 index perturbations the i-th linear layer). It is possible check that Lemma 2.1 still holds since activation layers correspond to a singleton function class {ø} with log covering number O. Thus, the conclusion of Theorem 2.1 also applies for this definition of mp. Now the following lemma relates this all-layer margin to the output margin and Jacobian and hidden layer norms, showing that mr(r, v) can be lower bounded terms of (1 y))-
Lemma 3.1. In the setting above, we have the lower bound mF(x, v) [1
Directly plugging the above lower bound into Theorem 2.1 and choosing Czi 0. Czi-1 O(3) would give variant of Theorem 3.1 that obtains different polynomial in NN (())* a(()-
Heuristic derivation of Lemma 3.1 We compute the derivative of F(x, 8) with respect to 8(g) D&.,, F(x, 5) D 12 (xx,))(lh2-2) l) We abused notation to let Den (x.5) F(x, 5) denote the derivative of F with respect to the 2i - 1-th perturbed layer evaluated on input (), By definitions Kjmis 8()) and the fact that the output margin I-Lipschitz, we obtain ( (F(z, 6). s=lol S D 1( F(x, 0)lppp///g-2222 ()ll (1)-1-2(1))((-1(())) With the first order approximation (F((1,)) 8). (F(()),)) + Σ, Do (F((x))) (el.)))lo).. v)1o=00()) around 8 0, we obtain
(F(x, xx(())) Σ (20))122()))
The right hand side is nonnegative whenever ||0||2 S 1[ Is 7(((),,)
which would imply that m 8) 2 (10=-11-2((0))6--00))0 However, this conclusion is imprecise and
7(f())v)

---

Published as a conference paper at ICLR 2020
non-rigorous because of the first order approximation to make the argument rigorous, also control the smoothness of the network around x in terms of the interlayer Jacobians, ultimately resulting in the bound of Lemma 3.1. We remark that the quantities K(t) are not the only expressions with which we could lower bound mf(r,)) v). Rather, the role of (())
NNN is to emphasize the key term
66 -)(=)))---=((())) which measures the first order stability of the network perturbation 6() and (((()))))
relates the all-layer margin to the output margin. As highlighted above, if this term small, mp will be large so long as the network is sufficiently smooth around (Ir, y), as captured by e0aa (z, v).
Comparison existing bounds We can informally compare Theorem 3.1 to the existing bounds of (Nagarajan and Kolter, 2019; Wei and Ma, 2019) as follows. First, the leading term #Gs (1)1)))))0-1122(1) of NN (() depends on three quantities all evaluated on the same training example, whereas the analogous quantity in the bounds of (Nagarajan and Kolter, 2019; Wei and Ma, 2019)
(((()))))
appears as maxp, "(F()))) maxp, (4) maxp, 11--1t-)) where each maximum is taken " over the entire training set. As we have | ( (P.) S. maxp, (3) (z. y). the term (|* I| (P..)) in our bound can be much smaller than its counterpart in the bounds of (Nagarajan and Kolter, 2019;
Wei and Ma, 2019). An interpretation of the parameter q is that we obtain fast (close to 1 con- vergence rates if the model fits every training example perfeetly with large all-layer margin, could have slower convergence rates with better dependence on the all-layer margin distribution. is unclear whether the techniques in other papers can achieve convergence rates faster than O(1/ because their proofs require the simultaneous convergence of multiple data-dependent quantities, whereas we bound everything using the single quantity mp.
Additionally, we compare the dependence on the weight matrix norms relative to n (as the degree of in our bound can vary). For simplicitly, assume that the reference matrices A(e) are set to 0. Our dependence on the weight matrix norms relative to the training set size is, up to logarithmic 24/(1+2)
[min( Vallt (s)llm.))W Vi
,which always matches or improves on the dependency obtained by PAC-Bayes methods such as (Neyshabur et al., 2017b; Nagarajan and Kolter, 2019). Wei and Ma (2019) obtain the dependency (IW(o "lla, where (W 1|2, is the sum of the || l|2 norms of the rows of W(D)- This dependency on W(e) is always smaller than ours. Finally, we note that Theorem 2.1 already gives tighter (but harder to compute) generalization guarantees for relu networks directly in terms of mp. Existing work contains a term which depends on inverse pre-activations shown to be large in practice (Nagarajan and Kolter, 2019), whereas m avoids this dependency and is potentially much smaller. We explicitly state the bound in Section B.I.
factors,
vn
4 GENERALIZATION GUARANTEES FOR ROBUST CLASSIFICATION
In this section, we apply our tools to obtain generalization bounds for adversarially robust clas- sification. Prior works rely on relaxations of the adversarial loss to bound adversarially robust generalization for neural nets (Khim and Loh, 2018; Yin et al., 2018). These relaxations are not tight and in the case of (Yin et al., 2018). 8), only hold for neural nets with one hidden layer. To the best of our knowledge, our work is the first to directly bound generalization of the robust classi- fication error for any network. Our bounds are formulated in terms of data-dependent properties in the adversarial neighborhood of the training data and avoid explicit exponential dependencies in depth. Let Badvy (xx denote the set of possible perturbations to the point (typically some norm ball around r). We would like to bound generalization of the adversarial classification loss gadv defined
by eady (F(x),v) A max,' (x)) fo-1 (F(x', y)- We prove the following bound which essentially replaces all data-dependent quantities in Theorem 3.1 with their adversarial counterparts.
Theorem 4.1. Assume that the activation 6 has a w'g- -Lipschitz derivative. Fix reference matrices (A Bi and any integer q > O. With probability 1 8 over the draw of the training sample Pa, all neural nets F which achieve robust training error 0 satisfy
2/3) 30/ (a(2))
q glogg
(E, |l
2/3 (P.)
Ep.cat gady 5
+6
n9/ (2+2)
8

---

Published as a conference paper at ICLR 2020
where rady is defined by (()) (z, 3) defined the same as in Theorem 3.1.
max,'eB"(()) (1) N la',"0 v) for ni() in (3.2), and agj) S are
Designing regularizers for robust classification based on the bound in Theorem 4.1 is a promising direction for future work. To prove Theorem 4.1, we simply define natural extension to our all- layer margin, and the remaining steps follow in direct analogy to the clean classification setting. We define the adversarial all-layer margin as the smallest all-layer margin on the perturbed inputs: mi (xr, y) A minz'' mr(x, v). We note that mf (a, y) is nonzero if and only if F correctly classifies all adversarial perturbations of z. Furthermore, the adversarial all-layer margin also satis- fies the uniform Lipschitz property in Claim 2.1. Thus, the remainder of the proof of Theorem 4.1 follows the same steps laid out in Section 2. As before, we note that Theorem 4. requires m to be the more general all all-layer margin defined in Section A. We provide the full proofs in Section E.
5 EMPIRICAL APPLICATION OF THE ALL-LAYER MARGIN
Inspired by the good statistical properties of the all-layer margin, we design an algorithm which encourages larger all all-layer margin during training. Letting denote the standard cross entropy loss used in training and @ the parameters of the network, consider the following objective:
G (;0,), ((Fe(z, 5).9) - 2
(5.1)
This objective can be interpreted as applying the Lagrange multiplier method to a softmax re- laxation of the constraint maxy' F(x, o1....,5g)b # y in the objective for all-layer margin. If G(8, 2; xr y) is large, this signifies the existence of some 8 with small norm for which Fe (z: 5) suffers large loss, indicating that mF, is likely small. This motivates the following training ob- jective over θ: L(O)= A Ep, [max, G(6, O; y)]. Define &e, E arg max; G(,, θ x, y). From Danskin's Theorem, if G(ō, O; x. y) is continuously differentiable', then we have that the quantity -Ep, [VeG(6)
O x. y) will be descent direction in @ for the objective L(O) (see Corollary A.2 of (Madry et al., 2017) for the derivation of a similar statement). Although the exact value 5ā.ng is hard to obtain, we can use a substitute 80,2.y found via several gradient ascent steps in 6. This inspires the following all-layer margin optimization (AMO) algorithm: we find perturbations ó for each example in the batch via gradient ascent steps on G(ô, O;z,y) v). For each example in the batch, we then compute the perturbed loss (Fe ,e.x,)) and update θ with its negative gradient with respect to these perturbed losses. This method is formally outlined in the PERTURBEDUPDATE procedure of Algorithm 1.3
We use Algorithm 1 to train a WideResNet architecture (Zagoruyko and Komodakis, 2016) on CIFARIO and CIFAR100 in variety of settings. For all of our experiments use / 1. Upetturb = 0.01, and we apply perturbations following conv layers in the WideResNet basic blocks. In Table we report the best validation error achieved during a single run of training, demonstrating that our algorithm indeed leads to improved generalization over the strong WideResNet baseline for a variety of settings. Additional parameter settings and experiments for the feedforward VGG (Si- monyan and Zisserman, 2014) architecture are in Section F.I. In addition, in Section F.I, we show that dropout, another regularization method which perturbs each hidden layer, does not offer the same improvement as AMO.
Inspired by our robust generalization bound, we also apply AMO to robust classification by extend- ing the robust training algorithm of (Madry et al., 2017). Madry et al. (2017) adversarially perturb the training input via several steps of projected gradient descent (PGD) and train using the loss com- robust AMO algorithm initializes perturbations g
puted on this perturbed input. At each update, to 0 for every training example in the batch. The updates to these 8 are performed simultaneously with PGD updates for the adversarial perturbations with the same update rule as Algorithm 1.
If we use relu network. G(8, θ æ, y) is technically not continuously differentiable, but the algorithm that we derive still works empirically for relu nets.
We note a slight difference with our theory: in the FORWARDPERTURS function, we perform the update f 5)= f (z, 6)) (f)--e1z, 8)) ررر rather than scaling by the previous layer norm this allows the perturbation to also account for the scaling of layer j.

---

Published as a conference paper at ICLR 2020
Algorithm 1 All-layer Margin Optimization (AMO)
procedure PRRTUURBBDDUDDDATGimmiiiaaa
= (i Wi) current parameters +)
Initialize 6; 0 for i = ......b.
for 8 = 1, ,,....f do
for all (zt, 91) B: do
Update d; < (1 Uperturb 2) + Iperturb V8 <(FORWADDEETTURROO; oú, θ), yi)
Set update 9 Ve 8 E, El FORWARDPERTURBGEY 6;, θ), v.)] Update O - θ 7g + VeR(e)).
> R is regularizer, i.e. weight decay.
function FORWARDPERTURBEE. 6, θ)
> The net has layers fi(: (),;))..... fr(:; O) with intended perturbations 8(1) 8(r)
Initialize + a.
for j .....,r do
Update 4 (h; 9)
Update < h+ + [1|]80).
return h
Table 1: Validation error CIFAR for standard training vs. AMO (Algorithm 1).
Dataset
Arch.
Setting
Standard SGD
AMO
Baseline
4.15%
3.42%
WRN16-10
No data augmentation
9.59%
6.74%
20% random labels
9.43%
6.72%
CIFAR-10
Baseline
3.82%
3.00%
WRN28-10
No data augmentation 20% random labels
8.28%
6.47%
8.17%
6.01 %
Bascline
20.12%
19.14%
WRN16-10
No data augmentation
31.94%
26.09%
CIFAR-100
Bascline
18.85%
17.78%
WRN28-10
No data augmentation
30.04%
24.67 %
In Table 2, we report best validation performance for robust AMO and the baseline method of (Madry et al., 2017) CIFARIO. Our results demonstrate that our robust AMO algorithm can also offer improvements in the robust accuracy. We provide parameter settings Section F.2.
CONCLUSION
Many popular objectives in deep learning are based on maximizing a notion of output margin, but unfortunately it is difficult to obtain good statistical guarantees by analyzing this output margin. In this paper, we design a new all-layer margin which attains strong statistical guarantees for deep models. Our proofs for these guarantees follow very naturally from our definition of the margin. We apply the all-layer margin in several ways: 1) we obtain tighter data-dependent generalization bounds for neural nets 2) for adversarially robust classification, we directly bound the robust gen- cralization error in terms of local Lipschitzness around the perturbed training examples, and 3) we design new algorithm to encourage larger all-layer margins and demonstrate improved perfor- mance on real data in both clean and adversarially robust classification settings. We hope that our results prompt further study maximizing all-layer margin as new objective for deep learning.
Table 2: Robust validation error CIFAR-I0 for standard robust training (Madry al., 2017) robust AMO. The attack model is 50 steps of PGD with 10 random restarts using for perturbations with radius 8.
Arch. WedeResNeet6610 Ne12
(Madry et al., 2017)
Robust AMO
48.75%
45.94% %
45.47%
42.38 %
10

---

Published as a conference paper at ICLR 2020
7 ACKNOWLEDGEMENTS
CW acknowledges support from an NSF Graduate Research Fellowship. The work is also partially supported by SDSI and SAIL.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv:/802.05296, 2018.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(N0)):4334422222222 2002.
Peter I.
Bartlett, Dylan J Foster, and Matus Telgarsky. Speccrally-noommaiized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249, 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. arXiv preprint arXiv: 1906. / 1.000, 2019.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. arXiv preprint arXiv: 1802:0100 2018.
Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pages 152. ACM, 1992.
Olivier Bousquet. Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms. 2002.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning Imbalanced Datasets with Biaibl-Disttibutin-Aaaaaa Margin Loss. arXiv e-prints, art, wrXiv:1906.07413, Jun 2019.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. arXiv preprint arXiv:1611.01836 2016.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-297, 1995.
Richard M Dudley. The sizes of compact subsets of hilbert space and continuity of gaussian pro- cesses. Journal of Functional Analysis, (3):2900-30,, 1967.
Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In Advances in neural information processing systems, pages 342-852, 2018
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, and Dimitris Tsipras. Robustness (python li- brary), 2019. URL https: /ttthub.ttttt//gg// wtt.ccoo///////. wttp///aaddyaaabbbbutttteee
Farzan Farnia, Jesse M Zhang, and David Tse. Generalizable adversarial training via spectral nor- malization. arXiv preprint 111100811 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint ar 2017.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159, 2017.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, pages 9461-9471, 2018.
11

---

Published as a conference paper at ICLR 2020
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint 159.0:150, 2015.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 085600 2019.
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learn- ing. The annals of statistics, pages 1171-1220, 2008.
Hamid Javadi, Randall Balestriero, and Richard Baraniuk. hessian based complexity measure for deep networks. arXiv preprint 12XXv::905.11633 2019.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300 2018.
Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. arXiv preprint arXiv: 2018.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in neural information processing systems, pages 793-800, 2009.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 04886, 2016.
Justin Khim and Po-Ling Loh. Adversarial risk bounds for binary classification via function trans- formation. arXiv preprint arXiv:1810.09511 2018.
Vladimir Koltchinskii, Dmitry Panchenko, et al. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. arXiv preprint arXiv: arXiv:1712.09903: 2017.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can gener- alize. arXiv preprint 1808 0000000.0087....0000 2018
Xuezhi Liang, Xiaobo Wang. Zhen Lei, Shengeai Liao, and Stan Li. Soft-margin softmax for deep classification. In International Conference on Neural Information Processing, pages 413- 421. Springer, 2017.
Weiyang Liu. Large-margin softmax loss for convolutional neural networks.
Philip M Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. arXiv preprint arXiv: 1905. /2600, 2019.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06088 2017.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly learnable, but only improperly. arXiv preprint /902.0 2019.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth--ensitive margins in homogeneous and non-homogeneous deep models. arXiv preprint arXiv: /90 /00.00325...5 2019.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv: /3344, 2019.
12

---

Published as a conference paper at ICLR 2020
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-
5956, 2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:/707.0955: 0..54,9 2017b.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: empirical study. arXiv preprint arXiv: 1802.08760 2018.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprini arXiv: (90.00290..0032, 2019.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Boosting regularized path maximum margin classifier. Journal of Machine Learning Research, 5(Aug):9411 973, 2004.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. In Advances in Neural Information Processing Systems, pages 50266, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265 0204442266686000 2017.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19 (1):2822-22) 2878, 2018.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss. arXiv preprint arXiv: 1009.3896, 2010.
Yi Sun, Yuheng Chen, Xiaogang Wang, and Xiaoou Tang. Deep learning face representation by joint eieetification-veriiicnaa 1988-1996, 2014.
In Advances in neural information processing systems, pages
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustmess may be at odds with accuracy. arXiv preprint I80. 12152, 2018
Vikas Verma, Alex Lamb, Christopher Beckham, Aaron Courville, Ioannis Mitliagkis, and Yoshua Bengio. Manifold mixup: Encouraging meaningful on-manifold interpolation regularizer. star, 1050:13, 2018.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. arXiv preprint arXiv: / /905.09688 2019.
Colin Wei, Jason D. Lee, Qiang Liu, and Tengyu Ma. Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel. arXiv e-prints, art. arXiv:1810.05369 Oct 2018.
Yandong Wen, Kaipeng Zhang, Zhifeng Li, and Yu Qiao. A discriminative feature learning approach for deep face recognition. In European conference on computer vision, pages 499-515. Springer, 2016.
Dong Yin, Kannan Ramchandran, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. arXiv preprint arXiv: 1810. 11944, 2018
Sergey Zagoruyko and Nikos Komodakis. 16Xiv:1605.07116, 2016.
Wide residual networks.
arXiv preprint
13

---

Published as a conference paper at ICLR 2020
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pages 7472-7482, 2019.
14

---

Published as a conference paper at ICLR 2020
A GENERALIZED ALL-LAYER MARGIN AND MISSING PROOFS FOR SECTION 2
In this section, we provide proofs for Section 2 in more general and rigorous setting. We first formally introduce the setting, which considers functions composed of layers which map between arbitrary normed spaces.
Recall that denotes our classifier from Section 2 computed via the composition fk o.... o f1, For convenience, overload notation and also let it refer to the sequence of functions {fi.... ./..... f& }- Recall that FF denotes the class of all compositions of layers Fk,..., Fi, where we let functions in F; map domains 1 to D; We will fix Dr - TR', the space of predictions for classes. Each space equipped with norm || (our theory allows the norm be different for every but for simplicity we use the same symbol || for all layers).
As in Section we will use F(r, 5) to denote the classifier output perturbed by 6. It will be useful to define additional notation for the perturbed function between layers i and j, denoted by (h, o), recursively as follows:
5h fi(h) + &,llil,, and (h, f5=,(f (f)- 6)) + 5,11ff-1- 8)1l
where we choose /: (h, 6) 2 h. Note that F(x, 5) 2 fR- (I, d), and the notation (ar, 6) from Section 2 is equivalent to fi-- (x, We will use the simplified notation fz-((z) _ fz- 0) when the perturbation 5 is all layers.
For given F, we now define the general all-layer margin mp : Do x [4] + R as follows:
min ||0
m y)
(A.1)
subject to > (F 8).8) S 0
The norm I|I I|I will have the following form:
||
where o, will be parameters chosen later to optimize the resulting bound, and || Ip de-
notes the standard en-norm. For F = (i....:Jk) we overload notation and write || Fill
[K(a))l llalllll.............. ; a wwl. llopp)))lp
This more general definition of mp will be useful for obtaining Theorems 3.1 and 4.1. Note that by setting a, 1 for all i and p 2, recover the simpler my defined in Section 2.
As before, it will be convenient for the analysis to assume that the e-covering number of F; in operator norm scales with - We formally state this condition for general function classes and norms below:
Condition A.1 (c-2 covering condition). We say that a function class satisfies the - covering condition with respect to norm || with complexity C1-11 (G) for all e > O.
c2 11
(9)
log (og
2
Now we provide the analogue of Theorem 2.1 for the generalized all- all-layer margin:
Theorem A.1. Fix any integer > Suppose that all layer functions F, satisfy Condition A.l with operator norm || llop and complexity function Cl- (Fi). Let the all layer margin mp be defined as in (A.1). Then with probability å over the draw of the training data, all classifiers F which achieve training error 0 satisfy
29/(9+2)
we
(.(P.) Vn
3P(fo-(F(2)))
q glog*
where (F) & (E, a. 2p/lp 2pp/lo-2) Cl-lhe (FF)2// (p+2)/
is a complexity (in the sense of Con- dition A. for covering F in and ( A O 1og(1/6)+logn is a low-order term.
15

---

Published as a conference paper at ICLR 2020
Note that this recovers Theorem 2.1 when a; 1 for all and p 2. The proof of Theorem A.1 mirrors the plan laid out in Section 2. As before, the first step of the proof is showing that my has low complexity measured by covering numbers.
Lemma A.1. Define m _ ((x, v) ~ m=(x,y) FFF.. Then
(e, m m S MiHn(e,FF
As in Section 2, we prove Lemma A.1 by bounding the error between my and my in terms of the noom of the difference between F and F.
Claim A.1. For any z, E Do x [1] and function sequences (foli F (i. we have (m v) mp( v) S F Fll-
Proof. Suppose that 8* optimizes equation (A.1) used to define mr (3r, y)- Now the notation hg - (1=1(1,6*), Define 8 as follows:
8 = 62 + 1:0 - -1:(h;
11;:111
We first argue via induction that J:x- (x, (I, l1q.. As the base case, we trivially have so-- (z, 8) hg-
x
[1 -i(fi- + - (xx,
-((ht-)) - 8,1111111
(by the inductive hypothesis)
= f((h-11)+ + 07 (0z fi(h;_1) -
||-1l||
(definition of ō)
|
= -(((h/-1) + + 6/114@2111
h4
(definition of gt)
Thus, we must have F(x, Fxx, 8*) follows that ((F(x, 8). S 0 as well. Furthermore, by triangle inequality
|| ||6* ||| 11 5lll
(A.2)
[/ -. )lI
Now we note that as
< IIʃ= Tillop it follows that
[4
8 8*ll < [|a F llopp....... awllfe - fallop)llo = FI Flll
Thus, using (A.2) and the definition of m we have
m y) < || s mp( + || F
where we relied on the fact that || mp y). Using the same reasoning, we also obtain the inequality mz(x,y) S m y) + F - Fll Combining gives [mf(r,)) v) - m (x( <
F Fll
Lemma A.I now directly follows.
Proof of Lemma A.I. As Claim A.I holds for any choice of (x, y) E Do x [4] follows that if f covers F in norm ||| I|I. then m F will be cover for m o F in the functional oc norm.
We state the generalized version of Lemma 2.2. The statement below is straightforward application of our covering number bound in Lemma A.1 with theory in (Srebro et al., 2010); for minor technical reasons translate their result to covering numbers and reprove it in Section A.I.
16

---

Published as a conference paper at ICLR 2020
Lemma A.2 (Straightforward adaptation from (Srebro et al., 2010)). Suppose that E is B B-smooth loss function taking values in [0, 11. Furthermore suppose that F satisfies Condition A.I with respect norm and complexity C1I-1 (F). Then with probability 1 1 for all F E F,
[3C (F) log" (F)
log(1/6) + log log n
[p(e(mr(r w) - 2 Pr ((mm((( v))l +e
n
for some universal constant c O.
The final ingredient is showing that when each individual layer F; satisfies Condition A. in operator norm, the class of compositions satisfies Condition A.1 with respect norm ||I III-
Lemma A.3. Suppose that each F; satisfies Condition A.I with norm llop and complexity Ci-lb (F)). Define the complexity measure CiI-1((F) by
(p+2)/2g
CII-I(F) -
Σ 2p/()+2)
11-1bo (F,))
(A.3)
Then we have
CP (F) 2
log N1 (i
<
which by definition implies that Ff satisfies Condition A.I with norm I|I || and complexity C1I-11 (F).
Proof. Let F/ be an 6-cover of F; in the operator norm Illl We will first show that F a {Frc.... ...... F F F.) is (age)- -coeer of F in I|| IlI- To this, for any F (fa...., f1) E F, let
F E F, be the cover element for fi, and define F' & Fi.....f). Then we have
F Fll flsalllfi fellop Heille
- [ase:) llp
as desired. Furthermore, we note that log f S E:
c (Fi)
by Condition A.1. Now we will
choose
4= = (=ICii-n(FF) (FF) (F)))((()--2(003
11op (FF)2/(0+2)) a; -p/(o+2)
We first verify that this gives an e-cover of F
|||=
1/p
|arei =e (G1-1(5)- (010)))22/(0)))))))) Σ Cll-lin (Fi (2n/(022) (20042)
Mp+2))
1/p
= (F) -2/()+2)))
Σ Gl (F,) (2p///22)))))) a 20/(o+2)
= =ci 22(p+22(())) - C11-1 (F))2/6422 =6
9g (F)
Next, we check that the covering number is bounded by
Ci (Fi)
Σ, C. (F.) (F C1 (FF) 4/(pp+) 20/(0+2)
?
Ex (F)(((()1/(++2)) 1le (Fx 2p/))/1112)) 2 2p/(2+2)
(n (F))
(F)
17

---

Published as a conference paper at ICLR 2020
Finally, prove Theorem A.1 (and result, Theorem 2.1). This will hinge applying Lemma A.2 with the correct choice of smooth loss.
Proof of Theorems A.I and 2.1. Define (m(m) & 1 2 min Piz-wio.n22/333 2 m) 0.5). By Claim A.2, this loss is 3 smooth and for m2(2,)) v) 0 satisfies
(o(mF(xx,) - (Bmmp(z,)) (V
c2v/
for universal constants C1, We additionally have (F()),)),)) y) I (a(mp(a, v)). Because of Lemma A.3, the conditions of Lemma A.2 are satisfied, and applying Lemma A.2 with smooth loss la gives with probability 1 - 6, for all F E F with training error 0
E (( X Er(3) log(1/6) + log logn
where (B) is defined by
BC ||-1
(F) log" n
Er( 2
Σ
c2v9
T1
V3mF(1,
n
(2.8)EP,
and Ci (F=) is defined as in Lemma A.3. Choosing 3 to minimize the above expression would give the desired bound however, such a post-hoc analysis cannot be performed because the optimal / depends on the training data, and the loss class has be fixed before the training data drawn.
Instead, we utilize the standard technique union bounding over a grid of in log-scale. Let & Ci--[( (F)poo(())))- denote the minimum choice of 3 in this grid, and select in this grid all choices of | in the form E2 for j 2 0. For given choice of 3, we assign it failure probability 2 such that by design Σ 8 8. Thus, applying Lemma A.2 for each choice of B with
8 5
corresponding failure probability 8, we note with probability 1 6,
(F)()) v)1 S BF(3) log(1/6) + log (3/g) log logn
holds for all 3 and F F.
Now for fixed F E F, let Br denote the optimizer of (B). We claim either there some choice of 3 with
(3) + 1og(1/6) + log(3/5) log log < Er(3)) log n + log(1/8)
(A.4)
n
or (p(()) 2 1, in which case the generalization guarantees of Theorem A.1 for this F anyways trivially hold. To see this, we note that there is 3 in the grid such that 3 E [sp. 2 + E). Then
1 Σ "
c2v9
435 |1-11 () log"
Er(3)
poly(n
(3tmr(1.))
"
(2.9)EP,
4EF(37) + p)
Furthermore, note that if B3 > poly(n)g, then Er(3)) 2 1. This allows to only consider poly(n),, giving (A.4).
Thus, with probability 1 - 5, for all F' F, we have
log n + log(1/5)
Ep((o. < Ex(87) +0
n
(1(
2/(4+2)
n mF La(
remains to observe that setting 31 = θ
(F)) log
gives us the theorem
statement.
18

---

Published as a conference paper at ICLR 2020
Claim A.2. For 3 > O, define the loss function (m(m) & minn Ptz-Nio.1n2///3
m) 0.5). Then Eg satisfies the following properties:
1. For all m I. (g(m) [0, 1}, and for m S O, [g(m) =
2. The function Eg is 01 3.8-mmooth for some constant сi independent of B.
3. For any integer 0 and 0, {p(m) S 3al-m for some constant 02 independent of
q.
Proof. The first property follows directly from the construction of Lg. For the second property, first note that
d= Pr (2/V B 2 m) m,33/2 dm Z~N(0.1)
exp( (=p(-m??3/2)
2
Now first note that at m = 0, the above quantity evaluates to O, and thus lg has a second derivative everywhere (as m is the only point where the function switches). Furthermore, max,, my mVB exx((=m2pm Thus, the above expression is upper bounded by V2n
maxy y/ exp(-yy// /2) I c' for some constant c' independent of B. 8 c', giving the second property.
For the third property, we note that for m > 0, (m) = 2 Przz-N(o.1) (2/V33/////// 2 m). As the q-th moment of Gaussian random variable with variance 1 is upper bounded by q²/2cg for all g and some 02 independent of q, Markov's inequality gives the desired result.
A.1 PROOF OF LEMMA A.2
The proof is straightforward application of Lemma 1 and conversion of (Srebro al., 2010) from the language of Rademacher complexity to covering numbers.
Proof of Lemma A.2. We can follow the proof of Theorem in (Srebro et al., 2010), with the only difference that replace their Rademacher complexity term with our complexity function Cii-1 (FF) For completeness, we outline the steps here.
Define H(1) (h LomoF: Ep, [h] S #J to be the class of functions in o with empirical
loss at most μr. Define (()) & (F) log n. By Claim A.3, the following holds for all p:: vn
Σ [oth(zn 8.)
E,
sup NEH())
(b())
Now using the same steps as (Srebro et al., 2010) (which relies applying Theorem 6.1 of (Bous- quet, 2002)), we obtain for all F e J, with probability 1
Ep(f mp] < Ep. mF] 106r,
48 -log 1/5 log logn) Ep, mpl(Srt + (log 1/5 + log log n))
4
(A.5)
n
n
where r is the largest solution of (()) = We now plug in r x Boog nci (F) and use the fact that /oi02 $ (c, + 02) for any c, 02 > 0 to simplify the square root term in A.5.
n
[3C] f. (oglog") log(1/8) + log log n
Ep(e mF] < Er, komr)++
for some universal constant
Claim A.3. In the setting above, for all > O, we have
Eahh(anB (HHI(F) 480y
ES
sup NEM(U)
log
Vn
where {0 i...d. Rademacher random variables.
19

---

Published as a conference paper at ICLR 2020
Proof. First, by Dudley's Theorem (Dudley, 1967), have
Bgg
sup hEH(P)
Σ
inf
a
1
Vlog H(mi)de
as0
vn
Now by Claim A.4, we obtain
488p C (F)
Eg
sup hEM((N)
Eosh(as, Bi)
I inf
+
1
de
(by Claim A.4)
asu
vn Ja
E2
(F) e12
v488
I inf as0
a
de
Vn
Jalv
4883
(A.6)
We obtained the last line via change variables to = e/V488k. Now we substitute a (11)8 and note that the integrand 0 fo (1)1(FFFF get
Vm
E
sup kgH())
Eo,h(zs.01) $
(F-n())488))
1+
S ad)
Vn
log
Vn
The following claim applies Lemma A.1 in order to bound the covering number of H()) in terms of (1))((). Claim A.4. In the setting of Lemma A.2, we have the covering number bound
(J)
log (e <
48,3
62
Proof. As o m o F the composition of a B-smooth loss with the function class m o F, by equation (22) of (Srebro et al., 2010) have
log log.Nz((P.) ((()) s log 4831, m F)
s log.Ni.1 (88 s 48,3 (T) ?
(by Lemma A.1)
(as F satisfies Condition A.1)
B PROOFS FOR NEURAL NET GENERALIZATION
This section will derive the generalization bounds for neural nets in Theorem 3.1 by invoking the more general results in Section C. Theorem 3.1 applies to all neural nets, but to obtain it, we first need bound generalization for neural nets with fixed norm bounds on their weights (this is a standard step in deriving generalization bounds). The lemma below states the analogue of Theorem 3.1, for all neural nets satisfying fixed norm bounds on their weights.
Lemma B.1. In the neural network setting, suppose that the activation à has K'y Lipsschch deriva- live. For parameters {aig)= meant be norm constraints for the weights, define the class of neural nets with bounded weight norms with respect reference matrices {A(s B as follows:
F F (0 F(x) min Wal A lto. I
Bio B1o S S0() ViJ
20

---

Published as a conference paper at ICLR 2020
Then with probability 1 5, for any 0 and for all F E F. we have
Ep (F()))((()),)))
(rlog n (
10g(1/8)
2 1r, 1..1 (F)))
"
+ (1-Ep,loonF((2) 2/102))))))))) ( log (0-2)
EgIlmty lI (S.) )2/3
n
where Sn, denotes the subset of examples classified correctly by F and ne is defined as in (3.2).
Proof. We will identify the class of neural nets with matrix norm bounds fa Vi with sequence of function families
F - (h + Wh: W E Rdxd .iin .min(v]]lv [Va] - A IW - B(ylla)) Vlg $ sa))
F2i 2 ( + {(h)
and let F F2y-1 Fi denote all possible parameterizations of neural nets with norm bounds {ar))== Let || llp be defined with respect to Euclidean norm ||.1/2 on the input and output spaces, which coincides with matrix operator norm for linear operators. We first claim that
( 2
log log.Ni--lle (2. S
This is because can construct two covers: for { H Wh: VallW S a(s) and one for {h + Wh: 1WIli.///oo S a each of which has log size bounded by 2(e2)) by Lemma B.2 and Claim B.2. Now we offset the first cover by the linear operator A(a) and the second by (()) and take the union of the two, obtaining an c-cover for F2 in operator norm. Furthermore, log.Niiill, F2i) = 0 simply because F2i the singleton function.
Thus, F2, satisfy Condition A.1 with norm _lopp and complexity functions Cil-1la (F2i-1) S (()) and Cj- (Fx)) = 0, so we can apply Theorem C.1. It remains to ar- gue that (2, y) as defined for Theorem C.I using standard Euclidean norm || - lla is equivalent to (()) (z. y) defined in (3.2). To see this, we note that functions in F have O-Liischitzz derivative, leading those terms with coefficient of K2zj1 cancel in the definition of KC] (z,, v)- There 1-1 correspondence between the remaining terms of ( y) and NNNN
N.NN
((() (z, y). so (x. v) into Theorem C.1 in place of ( y). Furthermore, as we have Ci-l1 (F2s) 0, the corresponding terms disappear in the bound of Theorem C.I, finally giving the desired result.
we can substitute (,,
Now we obtain Theorem 3.1 by union bounding Lemma B.1 over choices {a
Proof of Theorem 3.1. We will use the standard technique of applying Lemma B.1 over many choices of {a and union bounding over the failure probability. Choose poly(n-1) and consider grid of }ā } with a()) ' for 2 1. We apply Lemma B.1 with for all possible norm bounds } in the grid, using failure probability = 6/[[I /() for given choice of ). By union bound, with probability E 1 8, the bound of Lemma B.1 holds simul- taneously for all choices of { In particular, for the neural net F with parameters (W there
choice of { satisfying
min (VdllW - - loo I Brelllaa S م S 2 min ( W - Agllmo [[ - BBoll,,1 (ilh..yooogg log +
for all i. The application of Lemma B.1 for this choice of âيج) gives us the desired generalization bound.
21

---

Published as a conference paper at ICLR 2020
B.1 GENERALIZATION BOUND FOR RELU NETWORKS
In the case where Φ is the relu activation, we can no longer lower bound the all-layer margin mF(2, y) using the techniques in Section C, which rely smoothness. However, can still ob- tain a generalization bound in terms of the distribution of 1 //mp(z,) y) on the training data. We can expect (/, 3) be small in practice because relu networks typically exhibit stability to per- turbations. Prior bounds for relu nets suffer from some source of looseness: the bounds of (Bartlett al., 2017: Neyshabur al., 2017b) depended on the product of weight norms divided by margin, and the bounds of (Nagarajan and Kolter, 2019) depended on the inverse of the pre-activations, ob- served to be large in practice. Our bound avoids these dependencies, and in fact, it is possible to upper bound our dependency on 1/m= (z, y) in terms of both these quantities.
For this setting, we choose a fixed III |II defined as follows: i corresponds to a linear layer in the network, set a; L, and for corresponding to activation layers, set a; (in other words, only allow perturbations after linear layers). We remark that we could use alternative definitions of III but because we do not have a closed-form lower bound my, the tradeoff between these formulations is unclear.
Theorem B.1. In the neural network setting, suppose that o is any activation (such as the relu function) and my is defined using I|I -1- I|| as described above. Fix any integer > 0. Then with probability 5. for all relu networks F parameterized by weight matrices (W Vi that achieve training error O, we have
(3)
24/(x+2)
(Ei (()
Eplco-1 F] so
log² n
me
PP())) V'i
+
log(1 (1o211004r log n+ t Exlono)
where a()) is defined as in Theorem 3.1, and & O term.
is a low-order
a
The proof follows via direct application of Theorem A.I and the same arguments Lemma B.1 relating matrix norms to covering numbers. We remark that in the case of relu networks, we can upper bound m via quantity depending on the inverse pre-activations that mirrors the bound of Nagarajan and Kolter (2019). However, as mentioned earlier, this is a pessimistic upper bound as Nagarajan and Kolter (2019) show that the inverse preactivations can be quite large in practice.
B.2 MATRIX COVERING LEMMAS
In this section we present our spectral norm cover for the weight matrices, which used in Section to prove our neural net generalization bounds. Lemma B.2, Let Mio(B) denote the set of di x d2 matrices with Frobenius norm bounded by B, i.e.
(I) & {M& E Rd.xdd |M S B}
Then letting d f max(d1, d2) denote the larger dimension, for all >> 0, we have
36dB² log(9d)
log (e, Mrno (B)) S
Proof. The idea for this proof is that since the cover is in spectral norm, we only need cover the top d' A [ singular vectors of matrices M E M.
First, it suffices to work with square matrices, as a spectral norm cover of max(d1, d2) x max d2) matrices will also yield cover of dj x d2 matrices in spectral norm (as we can extend a dj x d2 matrices to larger square matrix by adding rows or columns with all 0). Thus, letting d A max(di ,2)). we will cover Min ()) defined with respect to x d matrices.
Let d' 19B2/<2 We first work in the case when d' < d. Let i be cu Frobenius norm cover of d x d' matrices with Frobenius norm bound d' Let D be the cover of d' x d matrices with Frobenius
22

---

Published as a conference paper at ICLR 2020
norm bound B in Frobenius with resolution ev. We construct M for Mao (B) as follows: take all possible combinations of matrices Ü, V from U1 V, and add UV to M. First note that by Claim B.I, we have
log M S dd' (log(3d' + log(3B/ev))
Now analyze the cover resolution of M: for M M, first let trunca (M) be the truncation of M to its d' largest singular values. Note that as M has at most singular values with absolute value greater than c/3, JM trunca (M))l Σ c/3. Furthermore, let USV trunca (M) be the SVD decomposition of this truncation, where U RRxde ||U||m S d' and SV E Rdd xd |I Il S B. Let U E l satisfy I1Ü - Uno I cu. and V E v satisfy IIV -VV I cv. Let M UV. Then
we obtain
|| - M lop I M trunc, (M) + [trunc./(M] M lo
S s/33 + |USV - USp |iÜSV UV
S + c B + evdd
Thus, setting cu c/3B, cv c/3d", then get c-cover of M with log cover size [9dB² [22 B2(2) As d' S d, this simplifies to [36d log(9d)/<2).
Now when d' 2 d, we simply take a Frobenius norm cover of d x d matrices with Frobenius norm bound B, which by Claim B.1 has log size at most d log(3B/c [36dB² (og())(() where the inequality followed because 9B² /c² 2 d.
Combining both cases, we get for all >
36dB² log(9d)
log Vig 1hp (c, (B) -
62
The following claims are straightforward and follow from standard covering number bounds for I 1/2 and || 1 balls.
Claim B.1. Let (B) denote the class of d1 d2 matrices with Frobenius norm bounded by B. Then for 0 < E < B, loggoN Nin Iloo (e, Mno B)) I di d2 log(3B/e).
Claim B.2. Let MillIla (B) denote the class of d1 x d2 matrices with the & norm of its entries bounded by B. Then log Wit (c,M (B)) < 5| B² B²/ log 10d.
C GENERALIZATION BOUND FOR SMOOTH FUNCTION COMPOSITIONS
In this section, we present the bound for general smooth function compositions used prove Theo- rem 3.1.
We will work the same general setting as Section Let (z_,(x, 8) denote the i-to-j Jacobian evaluated at fi-1-1 (z, 6), i.c. Jz 6) A ( (hff)=((h.))l===f----
We will additionally define general notation for hidden layer and Jacobian norms which coincides with our notation for
neural nets. Let (xx) A [|/+=((=)] and sa(x: ||ز||| As the function Dfs-i outputs opera-
tors mapping D;-1 to Dy, we can additionally define (z))(x) |D 1z)loo with Kjej+i (x:) A
Let KY be an upper bound on the Lipschitz constant of Difi= measured in operator norm:
[DD Dfii-(h + 1)p k6llv/]|
23

---

Published as a conference paper at ICLR 2020
Now define the value K (z, y), which can be thought of as a Lipschitz constant for perturbation 5, in the definition of mp, as follows:
(1)))+1(z)
(z, A (2x)
(F(()))
85())
+ (x))
16
(z)+
1 Sk =max fi+1jz
Kjttit1 م (x)
+ 8
Σ JiShSh
Kij + (x)
(C.1)
For this general setting, the following theorem implies that for any integer > 0, if F classifies all training examples correctly, then its error converges at a rate that scales with n n and the products [[r]] Cill (Fi).
Theorem C.1. Let F {fr o... f f. E Fit denote class of compositions of functions from
families (Fi) each of which satisfies Condition A. with operator norm ||. llop and complexity
Cip-lep (Fi). For any choice of integer q >> O, with probubility 1 - 5 for all F E F the following bound holds:
Eo (F()..))
h +og(1+
$
(Bp, [fo-1 (F(() +0
n
(1(1 n2
logg 4/(0+2)
012
+ (Ln (F(x) 0
2/3 Σ | I. (5..) Clill (F.) (F,)
where Sn denotes the subset of training examples correctly classified by F and ny is defined in (C.1). In particular, if classifies all training samples correctly, ie. |Sa] n, with probability 8 we huve
log?n n
8/le+2)
2/3 Σ |K 11 (.,,,, (F,) (1
3g/(a+2)
Epllon(F(z). Eq
+
where _ (
logon loggntoo is low order term
To prove this theorem, we will plug the following lower bound on me into Lemma A.2 with the appropriate choice of smooth loss f, and pick the optimal choice of {as H for the resulting bound. We remark that we could also use Theorem A.1 as our starting point, but this would still require optimizing over Ke
Lemma C.1 (General version of Lemma 3.1). In the setting of Theorem C.I, where each layer F; is a class of smooth functions, (F)(,, v) > 0, we have
mp y) 2 (x, /aal
We prove Lemma C.1 in Section D by formalizing the intuition outlined in Section 3. With Lemma C. in hand, we can prove Theorem C.I. This proof will follow the same outline as the proof of Theorem A.1. The primary difference is that we optimize over & values of as whereas Theorem A.I only optimized over the smoothness 8.
Proof of Theorem C.I. We use la with 8 1 defined in Claim A.2 as a surrogate loss for the 0-1 loss. Since Claim A.2 gives las (F()).)) y) I 1 y)), by Lemma A.2 it follows that Ep(ea. (F v) Eplla_1(mm(( v))]
(f. n log(1/8) + log log
3 Ep. (o x)) +
<
2
n
n
(C.2)
24

---

Published as a conference paper at ICLR 2020
Now first note that for misclassified pair, (m=1(m v)) lo-1 (Fz)( 1. For cor- rectly classified examples, we also have the bound (m= 4)) 2 my(2.0) for constant 02 independent of q- Thus, it follows that
[o2g)a/2
Ep, ( v)) S (f,
1
Σ
(c2g)9/²
mr y)
(2,9)ES,
Plugging this into (C.2), get with probability 1 1- for all F.F.
E log(1/6) + log log
Ep, 1 (mr (z, y))l - Bp, (co.1 (F(x))))) (
(C.3)
n
where defined by
(c2g)
+ (F) log" n
E
(C.4)
mF (z, 8)8
n
(..
Thus, it suffices upper bound Il (a, v) ()) (11-1) for the choice of a, p used define mp. We will set p q/ [g 1) and
By Lemma C.I, we have mp y)
>
union bound (C.3) over choices of a.
First, for particular choice of a and = a/(a 1), we apply our lower bound on m v) to simplify (C.4) as follows:
(F) log"n
E
Σ
(c2g) (1
+
(s,
39-2
(22g)
Σ (=)
Σ
24/(3q
(, (F,)2 (3/
log n
a2
+
a
n
1=1
(x,9)ES,
(C.5)
For convenience, we use EF(a) to denote (C.5) as function of a. Note that ny depends on F. Now let at denote the minimizer of (a)) As do not know the exact value of az before the training data is drawn, we cannot simply plug the exact value of a into (C.5). Instead, we will apply similar union bound the proof of Theorem A.1, although this union bound is slightly more complicated because we optimize over k quantities simultancously.
We & to denote the lower limit -1
ag in Cil-ley (Fi)) "poly(k -i "n Now we consider a grid of {ā.) where ă has entries of the form
search over a, setting &
a; = -,22 for any j 2 0. For given choice of a, we assign it failure probability
(C.6)
2
where 8 the target failure probability after union bounding. First, note that
8 8
Σ
it 5
3120
J+20
Therefore, with probability 8, get that (C.2) holds for mr defined with respect every ā.
In particular, with probability 1 o, for all F E F and ā in the grid,
E Er((o
< Ep, (m
3 p. (F.
Fr(()) + Es log((2: + log(1/5) + log log
S 2
n
(C.7)
C111 = 0. then we simply set a; = oc, which is equivalent to restricting the perturbations used in computing my to layers where C1-1., (F.))
25

---

Published as a conference paper at ICLR 2020
where the last term obtained by subsituting (C.6) for the failure probability. Now we claim that there is some choice of â in the grid such that either
(a(ā) + E,
log(1/5) + log log S <9Ep(at)) +0
( k (llo(i)) + +ogg(1/))
(C.8)
or EF(aT) Z 1 (in which case it is trivial to obtain generalization error bounded by Er(a)))
To this, first consider ā in grid such that ã; E [arr, 20 + Ex]- By construction of our grid of a, such choice always exists. Then we have
Ep (ā)
2
02
(224)1/2 n
(2 y)9
+
Σ
a,
220/130-21
20/(39
C1 (F.)
log n
(x.))ESn
(c2g)
(2,
i=1
(Z.
(34-2)/2
Σ
(3 2) 1-11np (F.)2o/ (30
log n + poly(n (1)
+ 99
api
The first term obtained because ã; a and the second via the upper bound ã; S 20rp, + E Thus, for some choice of ā in the grid, we have Ex(@) < 9E, (at) + poly(n Furthermore, if ore. >> c CiI-Ii (F for some constant c, we note that (p(a)p 2 1 thus, it suffices only consider aip I (Fi) 'n. In particular, only need consider ã; where log(28,/5:) S log kn. Finally, we note that bound, Combining these facts gives (C.8).
assume WLOG that & S n otherwise (C.8) would give trivial
Thus, it follows that for all F F.
(F(() Er, (F((()) +0 (Fr(at)+ k llog + log(1/6)
(C.9)
n
(020)4/2
El n6 (x()))))) 1/0 =
Finally, we can apply Lemma C.2 using
[5_]] 1/9 || [ntlle, and b, (11.1,p
(F,, log n
to get
Er(a $
| n
2/(0+2)
log 4/(x+2)
|| Σ
2/3 Lo(S.., (1
39/(9+2)
n
Substituting into (C.9) gives the desired bound.
Lemma C.2. For coefficients (zi) (be) O and integer q O, define
(34 2)/9
E(a) A Σ 29/0 +
Σ
23/ 22)
aj
with minimizer a" and minimum value E*. Then
3g/la+2)
E* 2
(2,b,))218
26

---

Published as a conference paper at ICLR 2020
Proof. Choose {as ) follows (we obtained this by solving for for which V.E(a) 0):
2-2g 0रत
02
Bq
bj
Σ
2
2/30///
For this particular choice of compute
2u
477
=
! 2
2/24
222/3002 2/3
2
2/332/3
2-
9+3
q
Σ
2/332/13 2/3
Σ
2/3 2/3 b,
39
q
9+2
Σ
2/3/2/3 2/3
2/3
2
Likewise, we can also compute
(34 2//9
(34-2)/4
0.0+2]
Σ a (2a01))))//000 20/133)22
20/130
Σ
(x)b;)2/3
Σ (2,b))2/3
2
q 4tz
Σ (2:b,) 2233
=
2
Σ (2.be)) (2,b:)2/3 2/3
2
Finally, we note that (3) (1) 2/(+22)
(2)
442 < 2, obtain
34/(x
E S E(a) 22
Σ (2.6)))/3
D LOWER BOUNDING mE FOR SMOOTH LAYERS
In this section, we prove Lemma C.I, which states that when the function F is a composition of functions with Lipschitz derivative, we will be able to lower bound mF(x,, y) in terms of the inter- mediate Jacobians and layer norms evaluated at z. To prove Lemma C.1, we rely on tools developed by (Wei and Ma, 2019) which control the change in the output of a composition of functions all the intermediate Jacobians are bounded.
First, we define the soft indicator 1 ge as follows:
{ 2 z/t
if St t if < 2 $ 2t 2f S
1 se())
We also define the ramp loss T₁ follows:
if 2
(2)()=
z/p
if <
0
if<00
Using the techniques of (Wei and Ma, 2019), we work with an "augmented" indicator which lower bounds the indicator that the prediction is correct, 1 5), 2 0j. We define this augmented
27

---

Published as a conference paper at ICLR 2020
indicator by
I(6;2, - (1)
II 1Sick-1
II ISiSss
1sy (j llpp))
(D.1)
for nonnegative parameters (4, Tj-i which we will later choose to be the margin, hidden layer norm, and Jacobian norms the unperturbed input. Because the augmented indicator I(,; y) conditions on small Jacobian and hidden layer norms, it will turn out to be Kद (z, y) -Liisshciit in the perturbation og. Furthermore, by construction, the value the augmented indicator Z(Ø; z, y) will equal 1 when 5 = 0, and we will also have
((r(F(x,)),)) 2 0J I(6;,,)) 21 E (..
This immediately gives lower bound the perturbation level required create negative margin. The lemma below formally bounds the Lipschitz constant of ([); x, y) in å,.
Lemma D.1. For nonnegative parameters fú, Tj-is P. with TJ= = for any j and Tj+J'' = 0 for j S j + define the function I(ô; x,
in (D.1). Then in the setting of Lemma C.r. given i E [k], for all choices of 8g and v, if o = 0 for j > i, we have
I(6, + v, 1,
I [(6 8 x. 8) R11l2|1
for R, defined follows:
Ri 4-11
8The-4+1
87
Σ
16 Ty' 16 3n+-/4117 11
T/
1ShS $k max(((+1.jf)
+8 8
$251511
(D.2)
We prove Lemma D.I in Section D.I. With Lemma D.I, can formalize the proof of Lemma C.I.
Proof of Lemma C.I. We will apply Lemma D.I. using t, s1xx), P >(F(z), y). Ts+i (x))(x). First, note that for this choice of parameters, the Lipschitz constant & of Lemma D.1 evaluates to (T, v). Thus, it follows that for all 6,
I(0; x, v) - I(ō; x. v)
s Σ [I 8. 0, 0,6 0;2, I(6 .,.,,,,,,.. 8,2ر = 0,
Σ (1,
(D.3)
Furthermore, by the definition I(6; x, y). have
[ (F(,, (), 8). v) 2 0) 2 I():
Finally, by our choice of the parameters used to define I(6; x. y), we also have I(0; 2, v) 2 1. Combining everything with (D.3), we get
(F(F(z, 2 of 2 I( 2 I(0;0,y) - Σ K2 (),
2 1 - [1[ (z. v) -
(since || |lp/(p-1) and Ipp are dual norms)
|1 (2. v)/ (x)l:)/)////)=ll//llo-lll)
Thus, for any 8, if ||| < 1K 3/ then ( (), 6), 2 0] > 0, which in turn implies (F((, 0),v) 0. It follows by definition of m that m v) [e | -1
28

---

Published as a conference paper at ICLR 2020
D.1 PROOF OF LEMMA D.1
To see the core idea of the proof, consider differentiating Z(ő; x, with respect to d; (ignoring for the moment that the soft indicators are technically differentiable). Let the terms A.....y ... Ag represent the different indicators which the product ((;; is comprised of. Then by the product rule for differentiation, we would have
Ds,I(6;z,,)) w)
Σ
II () 5'
Now the idea is that for every j. the product Iy Ay (6; contains an indicator that Ds,A, A,,A, x,; y) is bounded this stated formally by Lemmas D.3, D.4, and D.5. Informally, this allows to bound ||,, y)ll by the desired Lipschitz constant Rg.
To formally prove this statement for the case of non-differentiable functions (as the soft-indicators se are non-differentiable), it will be convenient to introduce the following notion of product- Lipschitzness: for functions A1 Dr + R+ and A2 Dj + RR, where D, is some normed space, we say that function A₁ 7-product-Lipschine w.r.t. A2 if there exists some c, C' such that for any ||||| I and r E D,, we have
|1 + A1())\A2(z) & F|RM| + C|||/|1
We use the following fact that the product of functions which are product-Lipschhnn with respect to one another fact Lipschitz. We provide the proof in Section D.2.
functions Lemma D.2. Let A Ag Dí [0, 1] be set of Linctinss such that A, is Ty-product- Lipschitz w.r.t I1 jttt A₃ for all i. Then the product II. A; is E; Tiplipcci
Now we proceed to formalize the intuition of product-rule differentiation presented above, by show- ing that the individual terms in I(Ō; 2., y) product-Lipschitz with respect the other terms. For the following three lemmas, we require the technical assumption that for any fixed choice of x, 8_i. the functions J (zx, 8), " 8) are worst-case Lipschitz in 8; measured in || |l. lop respectively, with Lipschitz constant C", Our proof of Lemma D.I, however, can easily circumvent this assumption. The proofs of the following three lemmas are given Section D.2.
Lemma D.3. Choose i,j with k -1 2 j > i. Then after we fix any choice of I, 5. the function Lst, (1ff)-(zzz 8)11 is 47 i -product-Lipschitz in ó, with respect to 1ss, en (11lJJ--sst1 o)llo)) s4 ((15)==-11,,)))).
1,
Lemma D.4. Choose i S k. Then after we fix any choice of x, 8, the func- tion (2, 0),)). is
47k 4 prod-ctttt---iishhhiii in 8, with respect to (1l (1 8l)))
1 1 (l]Jkest1 (1,))) 1 (1l
Lemma D.5. Choose i, 1. with jn 2 f2. ji Set product-Lipschits constant 7 as follows:
7= 8 ( + t-1 Ey (ia siish -1
Tí Then for any fixed choice of α satisfying dy t-product-lapschiit Sty (1J (lppp)
0 for j >
i, the func-
tion 1 1smn i2 [1J ())lpp)
in 8, with respect to Here note that have
1sh- (1ff--11 8) Hiss'sss T--1-ja
ifi 1 +1.
Given the described steps, we will now complete the proof of Lemma D.I.
Proof of Lemma D.I. We first assume that the conditions Lemmas D.3, D.4, D.5 regarding C'- worst-case Lipschitzness hold. We note that [(,; x) is product which contains all the functions appearing in Lemmas D.3, D.4, and D.5. Thus, Claim D.I allows us to conclude that each term in [(;; xr, y) is product-Lipschin with respect to the product of the remaining terms. As these lemmas also account for all the terms in ((;; x, y), we can thus apply Lemma D.2, where each A, is set to be term in the product for I(8; v)- Therefore, bound the Lipschitz constant in ô; of I(8: x, y), sum the product-Lipschie
constants given by Lemmas D.3, D.4, and D.5. This gives that Z(8; x, y) is -ipsccic in o, for R; defined in (D.2).
29

---

Published as a conference paper at ICLR 2020
Now to remove the C' worst-case Lipschitzness assumption, D.6 of (Wei and Ma, 2019) to note that such Lipschitz constants exist if we restrict ò to some compact set, and thus conclude the lemma statement for 6; restricted to this compact set. Now simply choose this compact set sufficiently large to include both ó; and d; + v.
follow the reasoning of Claim
D.2 PROOFS FOR PRODUCT-L.ISSCHEEE LEMMAS
Proof of Lemma D.2. As each A, is Lipschitz and there are a finite number functions, there exists C" such that any possible product A;, ..- A,, is C' L'-siischi Furthermore, by the definition of product-L.ipschig there are c, C. > such that for any ||||| S c. x E D,, and 1 S S q, we have
(AA(+ + +) A(()) II A,(x) & 74 | + C/|u1|2 8
Now note that
A, (a +V) II 9
II A +z) A(x) Σ
II
A,(00) (1) (D.4)
1=1+1
Now for any we have
u) A, II (x
II A,(x)
/=1
s=++1
$1(A,(+ A A,(x) ('||l j=++1
II A,(a)
(as I[ A5 is C'-Lipschitz)
$ $|A(+ A A,(x) c'|[lll)
jti
We used the fact that IT Az(x) I Now we have |A(( + v) A,(x) [ Az(x) s
T||l/|| + C| and |A(x + v) C((x)|(*||b| c |ul2 as A, is C'-Lipschitz, so
i-1
9 II /=
(A.(z +) Ax(x)) II
A₂ + v)
s (C+ +*
j=1
Plugging this back into (D.4) and applying triangle inequality, we get
II A,(x +) - II A,(a)) s ||l||
Σ -. a(C + (3)lul])
Σ, 4z Define the constant C" A min(c, ( }. For any and all satisfying ||l||| C", have
I[ A, - v) - II [+)) < 2|| Σ 7
(D.5)
Now for any x; y Dj, wish show II, A:(y) II, A, (x 2 vll E, 7, To this end, we divide x into segments of length at most C and apply (D.5) on each segment.
Define (15) = x + j ---يl (u x) for = 1,..., |||= vll/C"J Then as || - x0-1) < C",
C"
we have III, (x()) II, A,x0--)) < -| z0 11 Σ, 74. Furthermore, we note that the sum of all the segment lengths equals |yy I||. Thus, can this inequality over pairs
(ar, (())), (2)))................ .., (x('ll=-vil/C") y) and apply triangle inequality to get
II At(y) II A(xx)) < 2||x vll Σ 7r
desired.
30

---

Published as a conference paper at ICLR 2020
Proof of Lemma D.3. For convenience, define
A(x, 6) - STj an1 (1Jje (z, (lop)) ((1,
We first note that D (2r, 8), the partial derivative of fzr- with respect to ö; is given by Jjt-it (2, 1- 6]| by Claim D.2. As Uj=i+1(z; 5). 1 6)ll are both worst-case Lipschitz in & with some Lipsehitz constant C", can apply Claim H.4 of (Wei and Ma, 2019) to obtain:
(, 8; + +) - fz, (,, 6:)11 (J (x, 8) + C² /2|2I)))
for any and some Lipschitz constant C Thus, by the 17" Lipschitz-ness of the indicator 1g we have
[L,,, 1 8-i, 0, + 1)l) - 1 (
| (1, 6, + v) - 1 s-i, 8:)1
< A(x, 8)
tj
(1:8s 1x, llpp + C21/2|1|I|l1
A(x, 6)
t2
< A(x, 8) (11 (z,
01ll-1ii----111 8)1l + C" /2
1/
Now by definition of A(x. 8), we get that the right hand side equals O if ||],-s+ (2r, 8opp 2 27z--41 or 1 d)ll 2 -4 Thus, the right hand side must be bounded by
4T
||a| + C" /2||u11
t
which gives product-Lippschitnnss with constant
Proof of Lemma D.4. This proof follows in an identical manner to that of Lemma D.3. The only additional step using the fact that 7(h, y) I-Lipschitz h, so the composition (p(T(h, u)) is l Lipschitz in h.
Proof of Lemma D.5. Let C' be an upper bound on the Lipschitz constant in ó, of all the functions -=((,, (z, 8). As we assumed that each f, has -iisshicctttz Jacobian, such an upper bound exists. J
We first argue that
JJ (x.8_ 8, 8, vv (1, 6.]1lop
||0/||
Σ
(1 81pp C2/2||/|]
(D.6)
(1|5)-1++11 (z. 8) (alloppllf---i (z, 8)1 C" (" (z, 8)1lop)
for some Lipschitz constant C". The proof this statement is nearly identical to the proof Claim D.3 in (Wei and Ma, 2019), only sketch it here and point out the differences. We rely on the expansion
(z,
- (15 Jize-is
(2,
which follows from the chain rule. Now we note that we can compute the change in single term Jpe-3 (x. 8) from perturbing 5; as follows:
J (x. 8 8_1, + v) (z 5 54) = DD (h, (h, (e - DaSs (h, ln= (166_,)))
31

---

Published as a conference paper at ICLR 2020
Note that when j' > i, by assumption by 0, so Dnffs-s(hh0) (aff((h). Thus, as fy has Ky Lipschitz derivative, we get
( v) Jy (2, (2,1
$ kyllffy---12,,0,0000 +v -1- 8 8.)
(since the derivative of fy is kly ky--Lipschtzz) < x1y(1 d.)llo + C" /2|2|||||||l/ (by Claim H.4 (Wei and Ma, 2019))
1 <kg - 6) apl 1-11-1 6) C" /2/|/|))]]//
We obtained the last line via Claim D.2. We note that the cases when j' > i contribute the terms under the summation in (D.6).
When j'
have Dafie (h, (h,)) 6) Dafi(h) + D for any h, [|Dafies 5,, 8_1)
DiSici (h, 5, + v, 6 llopp
D op I ||el|. As this holds for any h, it follows that ( 8- 6; v) (I, d- di)llop op ||||. This term results in the last quantity in (D.6).
Finally, when j' < i, we have J 01, +v) J (5, as J does not depend on 84.
To see how (D.6) follows, we would apply the above bounds in telescoping sum over indices j' ranging from ma i) to J1. For more detailed derivation, refer the steps in Claim D.3 of (Wei and Ma, 2019).
Now for convenience define
A(x, 6) - 1s, (1
II
Isyr (1) 8)
SS""
Note that any of the bounds set by the indicators in A(x, 8) are violated, then A(x, = and thus
6- (1)l = 1 5 (1IJ 8-i, 04 + ))pppp 15 (I) و
In the other case, we have ||/- (x, 5)1l s 24 and |J 0) llop S 2Ty'e3", in which case (D.6) can be bounded by
(x, 8 d-i, 8z v) Jjs J (x, b
$ 84:-1
Σ
Ky -
|||||
j'aaax (ja.(t)))))
+ Ji 1-44 ||
C" ||||
for some C that is independent of x, 6, v. Thus, by Lipschitz-ness of -T (-) and the triangle inequality, we have
1 S (x,
5-,, )lppp [
s (D.7)
8 (Tn-catte- + 4-1 2 22 -y
|M
T3
This gives the desired result.
1] be functions where A is F-product-Lipschitz w.r.t Ag Then A is also F-product Lipschitz w.E.. Az
Claim D.I. Let A A2, As - [0,
+
Proof. This statement follows from the definition of product-LLipschiznnss and the fact that |1 + v) A1(v)) S [1 + (1))
since As(x) 1.
Claim D.2. The partial derivative of fie-1 with respect to variable dg evaluated at x, can be computed as
32

---

Published as a conference paper at ICLR 2020
Proof. By definition, f (x, 8) fg-etilfie1(2 (0,,,)),), Thus, note that (2, only depends on 6, through fi-1 6). so by chain rule we have
Ds. (1,5)-1(210) Difs+ ++1 (h,
fi- (2,, Jn-it1 (z, Ps (s 1 8)) + 8. 8)1l]
Jseitt (z, ( 6)
In the second line, we invoked the definition of Jj+i+1 (x,
Claim D.3. We have the expansion
J)-1(z,6) = J)t5(228) (. (2,)
Proof. This a result of the chain rule, but for completeness we state the proof here. We have
DaSs-i(h, Dat, Pn15(()-1-(hhh5)-- Di
(0,6)
(by chain rule)
(D.8)
Thus, plugging in h = fi (x, 8), we gel
(z, DnJjei 8) 1== DnSj (000
DD'
Dw (h', (a
= (2, 1)
Now we can apply identical steps expand 12, 8), giving the desired result.
E PROOFS FOR ADVERSARIALLY ROBUST CLASSIFICATION
In this section, derive the generalization bounds for adversarial classification presented in Sec- tion 4. Recall the adversarial all-layer margin m (x, & min (B"h mp(z', v) defined in Section 4. In this section, we will use the general definition of m. in (A.1).
We will sketch the proof of Theorem E.1 using the steps those laid out in Sections 2 and A. We will rely on the following general analogue of Theorem C. with the exact same proof, but with Ry (defined in Section C) replaced by nadv (I. y) & maxx'eB=(()) Ho (a', y) everywhere:
Theorem E.1. Ler F = {fk ....o fi fo E Fi} denote class of compositions of functions from families (Fi) each of which satisfies Condition A.l with operator norm || llop and complexity
Cii-lop (Fi). For any choice of integer q > O, with probubility 1 - ō for all E F the following
bound holds:
[alyy (F(x),
3
h kloonn + log(1/8)
Ep,, (F +0
2
n
3a 412
( n
log² कスス
+ +(1 E1, pady (F(x) O
Σ llc udy 12/3 Ly(S Cl (F.)2/3
where Sudv denotes the subxet of training examples correctly classified by F with respect to adver- sarial perturbations. In particular, F classifies all training samples with adversarial error O, i.e. we have
SSaty = n, with probability 1
Ep (edd (F(x). log² 4/(9+2)
3g/(9
|| Σ
2/3 L,(W ( (1, (F/)
+
n
where Ç _ 0 klogn+log(11/b is low order term.
33

---

Published as a conference paper at ICLR 2020
Given Theorem E.I, Theorem 4.1 follows with the same proof as the proof of Theorem 3.1 given in Section B. To prove Theorem E.1, we first have the following analogue Lemma A.1 bounding the covering number of malv F. Lemma E.1. Define mdv F - (1x, v) + mp (r, FEFF Then
(c, ndv o FF S (in((e,FF
This lemma allows to invoke Lemma A.2 smooth loss composed with m F, did for the clean classification setting. The lemma is proven the exact same way as Lemma A.1, given the Lipschitz-ness of m below:
Claim E.1. For any 2, E Do [1] and function sequences F Wii (fit have
|m (z, v) m F (x, 8)l I F Fl.
(x, Proof. Let x BBdd (z) be such that mf (x,y) v) ( 2) By Claim A.I, have
adv m (x, S ( ,9) S m (lrx"")))) .9) + F|| FlI m adv (x. y) + || - Flll
We can apply the reverse reasoning also obtain mi (2,, v) S m adv (z, v) F FIll Combining the two gives the desired result.
Next, we lower bound mp adv when each function in F is smooth.
Lemma E.2. In the setting of Lemma C.I, let net (xr, y) max (6 y). Then if
pady (F()..) = 0, we have 0-1
adv F (z, v) [K (x, (a.
Proof. By definition and Lemma C.I, we have
adv (x, 3)
min mF(a', y) 2 min xx)
Hx (Int(x',))/aa w/)/a:///m // 1/(o-1)
(x)
max, [a 3)/ / /
(max (x', u) i=1 (lp/(-11)
To finish the proof of Theorem E.I, we use 6-=1 (m (xz v)) as an upper bound for eady (F(x), y) and follow the steps of Theorem C.1 to optimize over the choice of {ar) As these steps are iden- tical to Theorem C.I. omit them here. With Theorem E.1 in hand, conclude Theorem 4.1 using the same proof as Theorem 3.1.
F ADDITIONAL EXPERIMENTAL DETAILS
F.1 ADDITIONAL DETAILS FOR CLEAN CLASSIFICATION SETTING
For the experiments presented in Table the other hyperparameters besides and Tpertur are set to their defaults for WideResNet architectures. Our code is inspired by the following PyTorch WideResNet implementation: https:// httpp::///ttubbs WideReaNet-pyteen
comm/ttrnall// and we the default hyperparameters in this implementation. Al- though we tried a larger choice of t, the number of updates to the perturbations 6, our results did not depend much on
34

---

Published as a conference paper at ICLR 2020
Table 3: Validation error on CIFAR-I0 for VGG-19 architecture trained with standard SGD and AMO.
Arch.
Standard SGD
AMO 5.06%
VGG-19
5.66%
Table 4: Validation error on CIFAR for models trained with dropout vs. AMO. We tuned the dropout probability p and display the best-performing value.
Dataset
Arch.
Tuned Dropout
AMO
WRNI6-10 10
4.04% (p=0.1)
3.42%
CIFAR-10
WRN28-10
3.52% 0.10.1)
3.00%
WRN16-10
19.57%
0.1).
19.14%
CIFAR-100
WRN28-10
18.77% (p 0.2)
17.78%
In Table 3, we demonstrate that our AMO algorithm can also improve performance for conventional feedforward architectures such VGG (Simonyan and Zisserman, 2014). We report the best vali- dation error on the clean classification setting. For both methods, we train VGG-19 for 350 epochs using weight decay 0.0005 and an initial learning rate of 0.05 annealing by a factor of 0.1 the 150-th and 250-th epochs. For the AMO algorithm, we optimize perturbations for t = 1 steps and use learning rate 7/penurh 0.01.
In Table 4, we demonstrate that our AMO algorithm can offer improvements over dropout, which also regularization method based on perturbing the hidden layers. This demonstrates the value of regularizing stability with respect to worst-case perturbations rather than random perturbations. For the combinations of CIFAR dataset and WideResNet architecture, we tuned the level of dropout and display the best tuned results with the dropout probability in Table 4. We use the same hyperparameter settings as described above.
F.2 ADDITIONAL DETAILS FOR ROBUST AMO
Our implementation based on the robustness library by (Engstrom et al., 2019)5. For both meth- ods, we produce the perturbations during training using 10 steps of PGD with fx perturbations with radius c 8. We update the adversarially perturbed training inputs with a step size of in pixel space. During evaluation,
use 50 steps of PGD with 10 random restarts and perturbation radius e = For all models, we train for 150 epochs using SGD with a learning rate decay 0.1 at the 50th, 100th, and 150th epochs. For the baseline models, we use a weight decay of 5e-4, initial learning rate of 0.1, and batch size of 128.
For both models trained with robust AMO, the perturbations d have step size of 6.4c-3, and shrink the norm of by a factor of 0.92 every iteration. For the WideResNet16 model trained with robust AMO, use batch size of 128 with initial learning rate of 0.1 and weight decay 5e-4. For the WideResNet28 model trained using robust AMO, we use a batch size of 64 (chosen so that the vectors fit in GPU memory) with initial learning rate of 0.707 (chosen keep the covariance of the gradient update the same with the decreased batch size). We use weight decay 2e-4. We chose these parameters by tuning.
'https:/ http://tttthub..oom/./////aaaaaa
35


Reviews:
[{"review_id": "rye0FNG0tB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new generalization bound for deep neural networks and develops a regularizer which optimize quantities related to the bound and improve generalization error on competitive baselines. The paper treats deep neural network as a composition of functions (i.e. the layers) and introduces a new complexity measure, all layer margins, which depends on norm-based perturbation simultaneously applied to all the hidden layers of the neural networks. The all-layer margin can be seen as a generalization of the popular margin definition in SVM’s. Similarly, a generalization bound can be derived based on such all layer margins. The paper also shows that the bound has nice properties that improve upon some short-comings of previous efforts and compare favorably in terms of tightness. The paper also shows that this bound can be adapted to adversarial robustness of the deep model. Finally, a practical algorithm is proposed to optimize the approximation of the all-layer margin and improve upon the baseline models (i.e. trained with only cross-entropy) in a non-trivial manner.\n\nI really like the paper! Jiang et al. 19 showed a surprisingly strong correlation between the margins at the hidden layers and generalization, which begs the question whether a generalization bound can be proven based on these perturbations. This paper shows that it is indeed the case with a much more sophisticated yet intuitive definition of margin that depends all hidden layers at the same time. Other than the nice theoretical properties outlined in the paper, the most exciting property of the all layer margin is that it can be directly optimized which the paper shows at the end. On the technical front, I have carefully read section 2 and Appendix A and read the other proofs at a coarser granularity. Barring some small notational errors, I did not find major errors in the derivation since standard techniques are used after the definition of the all layer margin. For the algorithm, while I have some questions about the thoroughness and accuracy of the approximation the results are quite compelling.\n\nI think this paper should be accepted as I consider generalization to be one of the most important topics in deep learning and the paper is a valuable contribution both for theory and practices. In addition, the paper is relatively easy to follow for a topic so technically involved. \n\nBarring my endorsement, I have some small complaints and questions:\n    1. The notation for summation in the definition of \\psi is quite difficult to parse. It would be good to either adopt a more explicit notation or have some extra clarification.\n\n    2. The symbol for function F and the symbol for function class \\mathcal{F} are sometimes mixed. For example, in lemma 2.1, the m_F on LHS should be m \\circ \\mathcal{F}.\n\n    3. I am a little confused on the role of section 3 since, like the paper states, the bound in section 3 is always looser than section 2. Is this bound just for comparison with previous work or provide a tractable upper bound? If so this should be discussed.\n\n    4. In lemma B.1, why are there 2 reference matrices and how should they be chosen?\n\n    5. Condition A.1 assumes the function classes of each layer have some kind of bounded complexity. In a feedforward neural network, a single \\mathcal{F}_i is just a linear operator which has pretty small complexity, but how about networks with residual connections? Is this assumption still reasonable? Likewise, since the proposed AMO is applied to residual networks, I want to hear the authors thought on this.\n\n    6. Following the previous point, perhaps it would be nice to have some experiments on conventional feedforward networks and applied the proposed algorithm to all layers instead of skipping the contents of the residual block.\n\n    7. Can the bound be accurately approximated? To me this seems almost combinatorially hard. If so, do the authors expect it to be non-vacuous? Given the results of Jiang et al., it seems that it is plausible to obtain fairly tight bound conditioned on the data and architecture.\n\n    8. Adversarial robustness is a highly active and empirical-results-driven field, so some experiments on the defense against adversarial attack would greatly strengthen the theoretical results. Otherwise it’s hard to gauge how useful it is.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkxnszbmqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a bound on the generalization error of a deep network in terms of margin at each layer of the network.  The starting premise is that extending the existing margin generalization bounds to deep networks worsen exponentially with the depth of the\nnetwork. Recent work which removed that exponential dependency is\nclaimed to require a more involved proof and complicated dependence on\ninput.  The paper provides a new bound that is simpler\nand tighter.\n\nA second contribution is to extend their bounds to robust classifier.\nSince their bounds depend on instance-specific margins, the extension\nto the robust case is straightforward. They just need to relax the\nmargin to the robustness boundary of the input. \n\nFinally, they present a new algorithm motivated by their bounds, that\nmaximized margin on all layers.  They show that the resultant network has much lower error than standard training.\n\nThe paper is well-presented and in spite of being theoretical is very nicely developed so that the main contributions come out clearly to non-specialists too.  \n\nA few minor comments:\nThe inner min in Equation 2.2 seems to be a typo.\n\nIn Theorem 2.1, there is typo around the definition of \\xi.\nBelow thoerem 2.1, the phrase \"depend on the q-th moment\" has 'q' undefined.\n\nTypo \"is has a\" in Theorem 3.1\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "H1lRC3iCYH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a novel and interesting way to measure the margin in the context of deep networks that removes the exponential dependency of depth in the corresponding generalization bounds. The key idea is to stabilize not only with respect to the input perturbations (which most existing works do and end up obtaining an exponential dependency), but simultaneous perturbations at every layer. It also shown that these ideas readily can be extended to provide bounds in the adversarial classification case. Finally, preliminary positive results on benchmarks showing how such an all-layer margin can be maximized during training are presented.\n\nMajor comments:\n1. I really like the fresh idea of simultaneous perturbations based analysis. Though it is clear that the proposed all-layer margin is upper bounded by margins with single perturbation, it is indeed non-trivial and insightful to understand that the same alleviates the exponential dependency of depth. More specifically, I think claim 2.1 is the the most insightful result, though simple to prove in hindsight. It would greatly help the readers if simple figures are used to explain this insightful result in the final manuscript. \n\n2. I think overall the paper was a pleasure to read especially with the way simplified analysis is presented in the main paper while postponing details to the Appendix.  It will be great if theorem 3.1 can further be simplified in notation and details just to present the main result that linear dependency is achieved via the lower bound for all-layer margin and to show improvement over existing bounds.\n\nMinor comments:\n1. Though results in sec5 are encouraging it would have been nice if it is shown that narrow and deep architectures benefit from such a regularization. As per the authors of WRN, the optimal architectures are not very deep.\n\n2. Though linear dependency is a useful step, it does not still reflect the observation in practice that in many applications deep networks generalize better than the shallow ones. Any comments towards this might help.\n\n3. There seem to be some typos: second min in (2.2) etc.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklNuffTtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves generalization bounds for Neural networks in terms of all layer margins. All layer margins are the smallest relative perturbations  of outputs of each layer, that result in misclassification. This new quantity allows to show generalization bounds that scales as sum of complexities of each layer and inversely scales with the all layer margin. The resulting bound does not have an explicit exponential dependence on depth, unlike some earlier bounds in terms of output margin.\n\nThe paper makes strong claims in the abstract and introduction that the analysis removes exponential dependency of capacity on depth. However I don’t think this is possible in the worst case. The exponential dependency is now hidden in the all layer margin (please correct me if I am mistaken). Note that the bound could still be interesting if this quantity is small for real world networks of interest. However the paper currently lacks this discussion. The paper need to make it clear that the bound only avoids explicit exponential dependence on depth. This brings me to another major drawback of the all layer margin. \n\nThis quantity is not computable as it requires solving a min-max problem, to find the best perturbation for each data point. So we cannot easily test if real networks that generalize well do have smaller all layer margin. The paper provides a lower bound for this quantity in terms of layer norms, network Jacobian norms, and output margin - which can be large. While all layer margin is certainly interesting from analysis perspective, as it allows to show bounds that are relatively cleaner, and behaves well with composition functions, it is not clear to me that it doesn’t decrease exponentially for deeper networks. A discussion on this can help the paper. \n\nThis paper is along the recent line of work on data dependent generalization bounds by Nagarajan  & Kolter 2019, Wei & Ma 2019.  Note that these earlier papers also prove generalization bounds that also do not have explicit exponential dependence on depth. This point also needs to be made clearer. \n\nGiven the adversarial nature of the definition of the all layer margin, the same framework is used to show a robust generalization bound, which is nice. However, the bound again depends on a hard to compute quantity - \\kapp^{adv}, making it less clear about the utility of such a bound.\n\nFinally the paper presents experiments, where to encourage higher all layer margin, the paper relies on min max gradient updates, similar to adversarial training, and shows better performance with this. I am curious if authors experiments with dropout, as it also adds “perturbations” to the output activations of each layer, and if the gains are orthogonal to dropout. Also how does the performance of AMO compared with  adversarial training methods (PGD) with small \\epsilon? The experiments currently are lacking to compare AMO with existing techniques.\n\nOverall I believe the paper needs to be rewritten with correctly stated contributions and need a more nuanced discussion of the benefits and drawbacks of the all layer margin and the  corresponding generalization bounds. \n\n** Post response comments **\nAuthors have clarified some of my earlier concerns. But the paper still requires rewriting to properly emphasize that it does not avoid exponential dependence on depth, but rather avoids an explicit dependence. Also there needs to be discussion about the computability of  \\kapp^{adv}. Finally adding experiments with dropout should make it more clear about the advantages of the proposed training method. Because the current draft does not address these yet, I am leaving my score at 3. My actual rating is more on the borderline (5), but the current system does not allow such scores. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This works presents a new and interesting notion of margin for deep neural networks (that incorporates representation at all layers). It then develops generalization bounds based on the introduced margin. The reviewers pointed some concerns, including some notation issues, complexity in case of residual networks, removal of exponential dependence on depth,  and dependence on a hard to compute quantity - \kapp^{adv}. Some of these concerns were addressed by the authors. At the end, most of the reviewers find the notion of all-layer margin introduced in this paper a very novel and promising idea for characterizing generalization in deep networks. Agreeing with reviewers, I recommend accept. However, I request the authors to accommodate remaining comments /concerns raised by R1 in the final version of your paper. In particular, in your response to R1 you mentioned for one case you saw improvement even with dropout, but that is not mentioned in the revision; Please include related details in the draft.

Decision: Accept (Poster)