Title: IMPROVED SAMPLE COMPLEXITIES FOR DEEP NET-WORKS AND ROBUST CLASSIFICATION VIA AN ALL-LAYER MARGIN

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.

1. INTRODUCTION:

The most popular classification objectives for deep learning, such as cross entropy loss, encourage a larger output margin -the gap between predictions on the true label and and next most confident label. These objectives have been popular long before deep learning was prevalent, and there is 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 to explain the successes of popular algorithms such as SVM (Boser et 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. Concretely, suppose we have n training data points each with norm 1, and let γ i be the output margin on the i-th example. With high probability, if the classifier perfectly fits the training data, we obtain1 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 on 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 margin. In this work, we remedy this issue by proposing a new notion of margin, called "all-layer margin", which we use to obtain simple guarantees like (1.1) for deep models. Let m i be the alllayer 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:

Test error

1 n n i=1

sum of the complexities of each layer m i 2 + low order terms (1.2)

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 output margin and other quantities, we obtain improved generalization 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 generalization 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 a different normalizer for each training example -the local Lipschitzness for that particular example. Second, our bound depends on 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/ √ n. We provide a more thorough comparison to prior work in Section 3. Furthermore, for relu networks, we give a tighter generalization bound which removes the dependency on inverse pre-activations suffered by (Nagarajan and Kolter, 2019) , which they showed to be large empirically (see Section B.1). 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 extension 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.1). 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, it 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 adversarial error (Khim and Loh, 2018; Yin et 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 it 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 demonstrate 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 properties that are counterintuitive to conventional wisdom. This has prompted a variety of new perspectives for studying generalization in deep learning, such as implicit or algorithmic regularization (Gunasekar et al., 2017; Li et al., 2017; Soudry et al., 2018; Gunasekar et al., 2018) , new analyses of interpolating classifiers (Belkin et al., 2018; Liang and Rakhlin, 2018; Hastie et al., 2019; Bartlett 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 a 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 bounded 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 in terms of hidden layer and Jacobian norms which avoid the exponential dependence on depth, 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) show that gradient descent implicitly maximizes the margin for linearly separable data, and Lyu and Li (2019) prove gradient descent converges 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) design an algorithm to maximize a notion of margin at 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 et al. (2018) propose a regularization technique which they empirically show improves the structure of the decision boundary at intermediate layers. Sokolić et al. (2017) provide generalization bounds based on 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 positive 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 generalization bounds by upper bounding the robust loss via a 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 output 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 i } k i=1 to refer to a sequence of k elements a i indexed by i. We will use

• to denote function composition: f • g(x) = f (g(x)). Now for function classes F, G, define F • G {f • g : f ∈ F, g ∈ G}.

We use D h to denote the partial derivative operator with respect to variable h, and thus for a function f (h 1 , h 2 ), we use D hi f (h 1 , h 2 ) to denote the partial derivative of f with respect to h i evaluated at (h 1 , h 2 ). We will use • to denote some norm. For a function f mapping between normed spaces

D I , D O with norms • I , • O , respectively, define f op sup x∈D I f (x) O

x I , which generalizes the operator norm for linear operators. Let M fro , M 1,1 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 let N • ( , S) be the covering number of S in the metric induced by norm • with resolution . For a function class F, let N ∞ ( , F) denote the covering number of F in the metric d ∞ (f, f ) = sup x f (x) -f (x) . For a function f and distribution P , we use the notation f Lq(P ) (E x∼P [|f (x)| q ]) 1/q . We bound generalization for a test distribution P given a set of n training samples, P n {(x i , y i )} n i=1 where x ∈ D 0 denotes inputs and y ∈ [l] is an integer label. We will also use P n to denote the uniform distribution on these training samples. For a classifier F : D 0 → R l , we use the convention that max y ∈[l] F (x) y is its predicted label on input x. Define the 0-1 prediction loss 0-1 (F (x), y) to output 1 when F incorrectly classifies x and 0 otherwise.

2. WARMUP: SIMPLIFIED ALL-LAYER MARGIN AND ITS GUARANTEES:

Popular loss functions for classification, such as 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 a classifier F : D 0 → R l , where l denotes the number of labels. We define the output margin on example (x, y) by γ(F (x), y) max {0, F (x) y -max y =y F (x) y }.

For shallow models such as 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 depending 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 (Nagarajan and Kolter, 2019; Wei and Ma, 2019) .

In this section, we introduce a new objective with better statistical guarantees for deep models (Theorem 2.1) and outline the steps for proving these guarantees. Our objective is based on maximizing a notion of margin which measures the stability of a classifier to simultaneous perturbations at all layers. Suppose that the classifier

F (x) = f k • • • • • f 1 (x)

is computed by composing k functions f k , . . . , f 1 , and let δ k , . . . , δ 1 denote perturbations intended to be applied at each hidden layer. We recursively define the perturbed network output F (x, δ 1 , . . . , δ k ) by

h 1 (x, δ) = f 1 (x) + δ 1 x 2 h i (x, δ) = f i (h i-1 (x, δ)) + δ i h i-1 (x, δ) 2 F (x, δ) = h k (x, δ) (2.1)

The all-layer margin will now be defined as the minimum norm of δ required to make the classifier misclassify the input. Formally, for classifier F , input x, and label y, we define

m F (x, y) min δ1,...,δ k k i=1 δ i 2 2 subject to arg max y F (x, δ 1 , . . . , δ k ) y = y (2.2)

Note that the constraint that F (x, δ) misclassifies x is equivalent to enforcing γ(F (x), y) ≤ 0. Furthermore, m F is strictly positive if and only if the unperturbed prediction F (x) is correct. Here multiplying δ i by the previous layer norm h i-1 (x, δ) 2 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 F defined in Section A.

Prior works have studied, both empirically and theoretically, the margin of a 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-layer margin is better tailored towards handling the compositionality of deep networks because it considers simultaneous perturbations to all layers, which is crucial for achieving its statistical guarantees.

Formally, let F {f k • • • • • f 1 : f i ∈ F i }

be the class of compositions of functions from function classes F 1 , . . . , F k . We bound the population classification error for F ∈ F based on the distribution of m F on the training data and the sum of the complexities of each layer, measured via covering numbers. For simplicity, we assume the covering number of each layer scales as log N • op ( , F i ) ≤ C 2 i / 2 for some complexity C i , which is common for many function classes. Theorem 2.1 (Simplified version of Theorem A.1). In the above setting, with probability 1 -δ over the draw of the training data, all classifiers F ∈ F which achieve training error 0 satisfy

E P [ 0-1 (F (x), y)] i C i √ n E (x,y)∼Pn 1 m F (x, y) 2 log 2 n + ζ where ζ O log(1/δ)+log n n is a low-order term.

In other words, generalization is controlled by the sum of the complexities of the layers and the quadratic mean of 1/m F on the training set. Theorem A.1 generalizes this statement to provide bounds which depend on the q-th moment of 1/m F for any integer q > 0 and converge at rates faster than 1/ √ n. For neural nets, C i scales with weight matrix norms and 1/m F 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-behaved 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 m F has low complexity which scales with the sum of the complexities at each layer. The second part relates m F to the 0-1 loss using the simple fact that m F (x, y) is nonzero if and only if F correctly classifies x. Lemma 2.1 (Complexity Decomposition Lemma). Let m • F = {m F : F ∈ F} denote the family of all-layer margins of function compositions in F. Then

log N ∞   i 2 i , m • F   ≤ i log N • op ( i , F i ) (2.3)

The covering number of an individual layer commonly scales as log

N • op ( i , F i ) ≤ C 2 i / 2 i . In this case, for all > 0, we obtain log N ∞ ( , m • F) ≤ ( i Ci) 2 2 .

Lemma 2.1 shows that the complexity of m F scales linearly in depth for any choice of layers F i .

In sharp contrast, lower bounds show that the complexity of the output margin scales exponentially in depth via a product of Lipschitz constants of all the layers (Bartlett et al., 2017; Golowich et al., 2017) . Our proof only relies on basic properties of m F , indicating that m F is naturally betterequipped to handle the compositionality of F. In particular, we prove Lemma 2.1 by leveraging a uniform Lipschitz property of m F . This uniform Lipschitz property does not hold for prior definitions of margin and reflects the key insight in our definition -it arises only because our margin depends on simultaneous perturbations to all layers.

Claim 2.1. For any two compositions

F = f k • • • • • f 1 and F = f k • • • • • f 1 and any (x, y), we have |m F (x, y) -m F (x, y)| ≤ k i=1 f i -f i 2 op .

Proof sketch. Let δ be the optimal choice of δ in the definition of m F (x, y). We will construct δ such that δ 2 ≤ δ 2 + i f i -f i 2 op and γ( F (x, δ), y) = 0 as follows: define

δ i δ i + ∆ i for ∆ i fi(hi-1(x,δ ))-fi(hi-1(x,δ )) hi-1(x,δ ) 2

, where h is defined as in (2.1) with respect to the classifier F . Note that by our definition of • op , we have

∆ i 2 ≤ f i -f i op . Now it is possi- ble to check inductively that F (x, δ) = F (x, δ ).

In particular, δ is satisfies the misclassification constraint in the all-layer margin objective for F . Thus, it follows that m F (x, y) ≤ δ 2 ≤

δ 2 + ∆ 2 ≤ m F (x, y) + i f i -f i 2

op , where the last inequality followed from

∆ i 2 ≤ f i -f i op .

With the same reasoning,we obtain m F (x, y) ≤ m F (x, y)

+ i f i -f i 2 op , so |m F (x, y) -m F (x, y)| ≤ i f i -f i 2 op .

Given Claim 2.1, Lemma 2.1 follows simply by composing i -covers of F i . We prove a more general version in Section A (see Lemmas A.1 and A.3.) The second part of the proof of Theorem 2.1 is to upper bound the 0-1 test error by the test error of some smooth surrogate loss • m F . A result by Srebro et al. (2010) shows that generic smooth losses enjoy faster O(n -1 ) covergence rates if the empirical loss is low. We straightforwardly combine Lemma 2.1 with their results to obtain the following generalization bound for • m F : Lemma 2.2. Suppose that is a β-smooth loss function taking values in [0, 1]. Then in the setting of Theorem 2.1, we have with probability 1 -δ for all F ∈ F:

E P [ (m F (x, y))] ≤ 3 2 E Pn [ (m F (x, y))] + c β( i C i ) 2 log 2 n n + log(1/δ) + log log n n (2.4)

for some universal constant c > 0.

To complete the proof of Theorem 2.1, we will choose • m F 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 F used to derive the bounds presented in the following Sections 3 and 4.

Connection to (normalized) output margin Finally, we check that when F is a linear classifier, m F 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 (x) = w x where the data x has norm 1, we have m F (x, y) = max{0, yw x} = γ(F (x), y).

For deeper models, the all-layer margin can be roughly bounded by a 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.

3. GENERALIZATION GUARANTEES FOR NEURAL NETWORKS:

Although the all-layer margin is likely difficult to 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 a 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 (i) } and compute

F (x) = W (r) φ(• • • φ(W (1) x) • • • ) for smooth activation φ.

Let d be the largest layer dimension. We model this neural net by a composition of k = 2r -1 layers alternating between matrix multiplications and applications of φ and use the subscript in parenthesis (i) to emphasize the different indexing system between weight matrices and all the layers. We will let s (i) (x) denote the • 2 norm of the layer preceding the i-th matrix multiplication evaluated on input x, and κ j←i (x) will denote the • op norm of the Jacobian of the j-th layer with respect to the i -1-th layer evaluated on x. The following theorem bounds the generalization error of the network and is derived by lower bounding the all-layer margin in terms the quantities s (i) (x), κ j←i (x), γ(F (x), y).

Theorem 3.1. Assume that the activation φ has a κ φ -Lipschitz derivative. Fix reference matrices {A (i) , B (i) } k i=1 and any integer q > 0. With probability 1 -δ over the draw of the training sample P n , all neural nets F which achieve training error 0 satisfy

E P [ 0-1 • F ] ≤ O    i κ NN (i) 2/3 Lq(Pn) a 2/3 (i) 3q/(q+2) q log 2 n n q/(q+2)    + ζ (3.1)

where κ NN (i) captures a local Lipschitz constant of perturbations at layer i and is defined by

κ NN (i) (x, y) s (i-1) (x)κ 2r-1←2i (x) γ(F (x), y) + ψ (i) (x, y) (3.2)

for a secondary term ψ (i) (x, y) given by

ψ (i) (x, y) r-1 j=i s (i-1) (x)κ2j←2i(x) s (j) (x) + 1≤j≤2i-1≤j ≤2r-1 κ j ←2i (x)κ2i-2←j(x) κ j ←j (x) + 1≤j≤j ≤2r-1 j j =max{2i,j},j even κ φ κ j ←j +1 (x)κ j -1←2i (x)κ j -1←j (x)s (i-1) (x) κ j ←j (x)

Here the second and third summations above are over the choices of j, j satisfying the constraints specified in the summation. We define

a (i) by a (i) min{ √ d W (i) -A (i) fro , W (i) - B (i) 1,1 } √ log d + poly(n -1 ) and ζ r log n+log(1/δ)+ i log(a (i) +1) n

is a low-order term.

For example, when q = 2, from (3.1) we obtain the following bound which depends on the second moment of κ NN (i) and features the familiar 1/ √ n convergence rate in the training set size.

E P [ 0-1 • F ] i E Pn (κ NN (i) ) 2 1/3 (a (i) ) 2/3 3/2 log 2 n √ n + ξ

For larger q, we obtain a faster convergence rate in n, but the dependency on κ NN (i) gets larger. We will outline a proof sketch which obtains a variant of Theorem 3.1 with a slightly worse polynomial dependency on κ NN (i) and a (i) . For simplicity we defer the proof of the full Theorem 3.1 to Sections B and C. First, we need to slightly redefine m F so that perturbations are only applied at linear layers (formally, fix δ 2i = 0 for the even-indexed activation layers, and let δ (i) δ 2i-1 index perturbations to the i-th linear layer). It is possible to check that Lemma 2.1 still holds since activation layers correspond to a singleton function class {φ} with log covering number 0. Thus, the conclusion of Theorem 2.1 also applies for this definition of m F . Now the following lemma relates this all-layer margin to the output margin and Jacobian and hidden layer norms, showing that m F (x, y) can be lower bounded in terms of {κ NN (i) (x, y)}. Lemma 3.1. In the setting above, we have the lower bound m F (x, y) ≥

1 {κ NN (i) (x,y)} r i=1 2 .

Directly plugging the above lower bound into Theorem 2.1 and choosing

C 2i = 0, C 2i-1 = a (i) would give a variant of Theorem 3.1 that obtains a different polynomial in κ NN (i) , a (i) .

Heuristic derivation of Lemma 3.1 We compute the derivative of F (x, δ) with respect to δ (i) :

D δ (i) F (x, δ) = D h2i-1(x,δ) F (x, δ) h 2i-2 (x, δ) 2 . We abused notation to let D h2i-1(x,δ) F (x, δ)

denote the derivative of F with respect to the 2i -1-th perturbed layer evaluated on input (x, δ). By definitions of κ j←i , s (i) and the fact that the output margin is 1-Lipschitz, we obtain

D δ (i) γ(F (x, δ), y)| δ=0 2 ≤ D h2i-1(x,δ) F (x, 0) op h 2i-2 (x, 0) 2 = κ 2r-1←2i (x)s (i-1) (x). With the first order approximation γ(F (x, δ), y) ≈ γ(F (x), y) + i D δ (i) γ(F (x, δ), y)| δ=0 δ (i) around δ = 0, we obtain γ(F (x, δ), y) ≥ γ(F (x), y) - i κ 2r-1←2i (x)s (i-1) (x) δ (i) 2

The right hand side is nonnegative whenever

δ 2 ≤ γ(F (x),y) {κ2r-1←2i(x)s (i-1) (x)} r i=1 2 , which would imply that m F (x, y) ≥ γ(F (x),y) {κ2r-1←2i(x)s (i-1) (x)} r i=1 2 .

However, this conclusion is imprecise and non-rigorous because of the first order approximation -to make the argument rigorous, we 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 κ NN (i) are not the only expressions with which we could lower bound m F (x, y). Rather, the role of κ NN (i) is to emphasize the key term

s (i-1) (x)κ2r-1←2i(x) γ(F (x),y)

, which measures the first order stability of the network to perturbation δ (i) and relates the all-layer margin to the output margin. As highlighted above, if this term is small, m F will be large so long as the network is sufficiently smooth around (x, y), as captured by ψ (i) (x, y).

Comparison to 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

s (i-1) (x)κ2r-1←2i(x) γ(F (x),y)

of κ NN (i) 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 max Pn

1 γ(F (x),y) •max Pn s (i-1) (x)•max Pn κ 2r-1←2i (x)

, where each maximum is taken over the entire training set. As we have κ NN (i) Lq(Pn) ≤ max Pn κ NN (i) (x, y), the term κ NN (i) Lq(Pn) 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 n -1 ) convergence rates if the model fits every training example perfectly with large all-layer margin, or we could have slower convergence rates with better dependence on the all-layer margin distribution. It is unclear whether the techniques in other papers can achieve convergence rates faster than O(1/ √ n) because their proofs require the simultaneous convergence of multiple data-dependent quantities, whereas we bound everything using the single quantity m F .

Additionally, we compare the dependence on the weight matrix norms relative to n (as the degree of n in our bound can vary). For simplicitly, assume that the reference matrices A (i) are set to 0. Our dependence on the weight matrix norms relative to the training set size is, up to logarithmic factors,

min{ √ d W (i) fro, W (i) 1,1} √ n 2q/(q+2)

, 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

W (i) 2,1 √ n

, where W (i) 2,1 is the sum of the • 2 norms of the rows of W (i) . This dependency on W (i) 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 m F . Existing work contains a term which depends on inverse pre-activations shown to be large in practice (Nagarajan and Kolter, 2019) , whereas m F avoids this dependency and is potentially much smaller. We explicitly state the bound in Section B.1.

4. GENERALIZATION GUARANTEES FOR ROBUST CLASSIFICATION:

In this section, we apply our tools to obtain generalization bounds for adversarially robust classification. 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) , 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 classification 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 B adv (x) denote the set of possible perturbations to the point x (typically some norm ball around x). We would like to bound generalization of the adversarial classification loss adv 0-1 defined by adv 0-1 (F (x), y) max x ∈B adv (x) 0-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 φ has a κ φ -Lipschitz derivative. Fix reference matrices {A (i) , B (i) } k i=1 and any integer q > 0. With probability 1 -δ over the draw of the training sample P n , all neural nets F which achieve robust training error 0 satisfy

E P [ adv 0-1 • F ] ≤ O    q log 2 n i κ adv (i) 2/3 Lq(Pn) a 2/3 (i) 3q/(q+2) n q/(q+2)    + ζ where κ adv (i) is defined by κ adv (i) (x, y) max x ∈B adv (x) κ NN (i) (x , y) for κ NN (i) in (3.

2), and a (i) , ζ are defined the same as in Theorem 3.1.

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 a natural extension to our alllayer 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: m adv F (x, y) min x ∈B adv (x) m F (x, y). We note that m adv F (x, y) is nonzero if and only if F correctly classifies all adversarial perturbations of x. Furthermore, the adversarial all-layer margin also satisfies 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.1 requires m F to be the more general 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 a larger 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(δ, Θ; x, y) (F Θ (x, δ), y) -λ δ 2 2 (5.1)

This objective can be interpreted as applying the Lagrange multiplier method to a softmax relaxation of the constraint max y F (x, δ 1 , . . . , δ k ) y = y in the objective for all-layer margin. If G(δ, Θ; x, y) is large, this signifies the existence of some δ with small norm for which F Θ (x, δ) suffers large loss, indicating that m FΘ is likely small. This motivates the following training objective over Θ:

L(Θ) E Pn [max δ G(δ, Θ; x, y)]. Define δ Θ,x,y ∈ arg max δ G(δ, Θ; x, y). From Danskin's Theorem, if G(δ, Θ; x, y) is continuously differentiable 2 ,

then we have that the quantity -E Pn [∇ Θ G(δ Θ,x,y , Θ; x, y)] will be a descent direction in Θ for the objective L(Θ) (see Corollary A.2 of (Madry et al., 2017) for the derivation of a similar statement). Although the exact value δ Θ,x,y is hard to obtain, we can use a substitute δΘ,x,y found via several gradient ascent steps in δ. 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(δ, Θ; x, y). For each example in the batch, we then compute the perturbed loss (F Θ (x, δΘ,x,y )) and update Θ with its negative gradient with respect to these perturbed losses. This method is formally outlined in the PERTURBEDUPDATE procedure of Algorithm 1. 3We use Algorithm 1 to train a WideResNet architecture (Zagoruyko and Komodakis, 2016 ) on CIFAR10 and CIFAR100 in a variety of settings. For all of our experiments we use t = 1, η perturb = 0.01, and we apply perturbations following conv layers in the WideResNet basic blocks.

In Table 1 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 (Simonyan and Zisserman, 2014) architecture are in Section F.1. In addition, in Section F.1, 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 extending 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 computed on this perturbed input. At each update, our robust AMO algorithm initializes perturbations δ to 0 for every training example in the batch. The updates to these δ are performed simultaneously with PGD updates for the adversarial perturbations with the same update rule as Algorithm 1.

Algorithm 1 All-layer Margin Optimization (AMO)

procedure PERTURBEDUPDATE(minibatch B = {(x i , y i )} b i=1 , current parameters Θ) Initialize δ i = 0 for i = 1, . . . , b. for s = 1, . . . , t do for all (x i , y i ) ∈ B: do Update δ i ← (1 -η perturb λ)δ i + η perturb ∇ δ (FORWARDPERTURB(x i , δ i , Θ), y i ) Set update g = ∇ Θ 1 b i ( FORWARDPERTURB(x i , δ i , Θ), y i ) . Update Θ ← Θ -η(g + ∇ Θ R(Θ)).

R is a regularizer, i.e. weight decay.

function FORWARDPERTURB(x, δ, Θ)

The net has layers f 1 (•; Θ), . . . , f r (•; Θ), aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaawith intended perturbations δ (1) , . . . , δ (r) .

Initialize h ← x. In Table 2 , we report best validation performance for robust AMO and the baseline method of (Madry et al., 2017) on CIFAR10. Our results demonstrate that our robust AMO algorithm can also offer improvements in the robust accuracy. We provide parameter settings in Section F.2.

for j = 1, . . . , r do Update h ← f j (h; Θ). Update h ← h + h δ (j) . return h

6. 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 generalization error in terms of local Lipschitzness around the perturbed training examples, and 3) we design a new algorithm to encourage larger all-layer margins and demonstrate improved performance on real data in both clean and adversarially robust classification settings. We hope that our results prompt further study on maximizing all-layer margin as a new objective for deep learning. A GENERALIZED ALL-LAYER MARGIN AND MISSING PROOFS FOR SECTION 2

In this section, we provide proofs for Section 2 in a 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 F denotes our classifier from Section 2 computed via the composition

f k • • • • • f 1 ,

For convenience, we overload notation and also let it refer to the sequence of functions {f 1 , . . . , f k }.

Recall that F denotes the class of all compositions of layers F k , . . . , F 1 , where we let functions in F i map domains D i-1 to D i . We will fix D k R l , the space of predictions for l classes. Each space is equipped with norm • (our theory allows the norm to be different for every i, but for simplicity we use the same symbol • for all layers).

As in Section 2, we will use F (x, δ) to denote the classifier output perturbed by δ. It will be useful to define additional notation for the perturbed function between layers i and j, denoted by f j←i (h, δ), recursively as follows:

f i←i (h, δ) f i (h) + δ i h , and f j←i (h, δ) f j←j (f j-1←i (h, δ)) + δ j f j-1←i (h, δ)

where we choose f i-1←i (h, δ) h. Note that F (x, δ) f k←1 (x, δ), and the notation h i (x, δ) from Section 2 is equivalent to f i←1 (x, δ). We will use the simplified notation f j←i (x) f j←i (x, 0) when the perturbation δ is 0 at all layers.

For a given F , we now define the general all-layer margin m F :

D 0 × [l] → R as follows: m F (x, y) min |||δ||| subject to γ(F (x, δ), y) ≤ 0 (A.1)

The norm ||| • ||| will have the following form:

|||δ||| = (α 1 δ 1 , . . . , α k δ k ) p

where α i ≥ 0 will be parameters chosen later to optimize the resulting bound, and • p denotes the standard p -norm. For F = {f 1 , . . . , f k }, we overload notation and write

|||F ||| = (α 1 f 1 op , . . . , α k f k op ) p .

This more general definition of m F will be useful for obtaining Theorems 3.1 and 4.1. Note that by setting α i = 1 for all i and p = 2, we recover the simpler m F defined in Section 2.

As before, it will be convenient for the analysis to assume that the -covering number of F i in operator norm scales with -2 . We formally state this condition for general function classes and norms below: Condition A.1 ( -2 covering condition). We say that a function class G satisfies the -2 covering condition with respect to norm

• with complexity C • (G) if for all > 0, log N • ( , G) ≤ C 2 • (G) 2

Now we provide the analogue of Theorem 2.1 for the generalized all-layer margin: Theorem A.1. Fix any integer q > 0. Suppose that all layer functions F i satisfy Condition A.1 with operator norm • op and complexity function C • op (F i ). Let the all layer margin m F be defined as in (A.1). Then with probability 1 -δ over the draw of the training data, all classifiers F ∈ F which achieve training error 0 satisfy

E P [ 0-1 (F (x), y)]    1 m F Lq(Pn) C |||•||| (F) √ n    2q/(q+2) q log 2 n + ζ where C |||•||| (F) i α 2p/(p+2) i C • op (F i ) 2p/(p+2) (p+2)/2p

is a complexity (in the sense of Condition A.1) for covering F in ||| • ||| and ζ O log(1/δ)+log n n is a low-order term.

Note that this recovers Theorem 2.1 when α i = 1 for all i 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 m F has low complexity as measured by covering numbers.

Lemma A.1. Define m • F {(x, y) → m F (x, y) : F ∈ F}. Then N ∞ ( , m • F) ≤ N |||•||| ( , F)

As in Section 2, we prove Lemma A.1 by bounding the error between m F and m F in terms of the ||| • |||-norm of the difference between F and F .

Claim A.1. For any x, y ∈ D 0 × [l], and function sequences

F = {f i } k i=1 , F = { f i } k i=1 , we have |m F (x, y) -m F (x, y)| ≤ |||F -F |||.

Proof. Suppose that δ optimizes equation (A.1) used to define m F (x, y). Now we use the notation h i f i←1 (x, δ ). Define δ as follows:

δ i δ i + f i (h i-1 ) -f i (h i-1 ) h i-1

We first argue via induction that f i←1 (x, δ) = h i . As the base case, we trivially have

f 0←1 (x, δ) = x = h 0 . f i←1 (x, δ) = f i ( f i-1←1 (x, δ)) + δ i f i-1←1 (x, δ) = f i (h i-1 ) + δ i h i-1

(by the inductive hypothesis)

= f i (h i-1 ) + δ i + f i (h i-1 ) -f i (h i-1 ) h i-1 h i-1 (definition of δ) = f i (h i-1 ) + δ i h i-1 = h i (definition of g i )

Thus, we must have F (x, δ) = F (x, δ ), so it follows that γ( F (x, δ), y) ≤ 0 as well. Furthermore, by triangle inequality

||| δ||| ≤ |||δ ||| + ||| δ -δ ||| (A.2)

Now we note that as

fi(h i-1 )-fi(h i-1 ) h i-1 ≤ f i -f i op , it follows that ||| δ -δ ||| ≤ (α 1 f 1 -f 1 op , . . . , α k f k -f k op ) p = |||F -F |||

Thus, using (A.2) and the definition of m F , we have

m F (x, y) ≤ ||| δ||| ≤ m F (x, y) + |||F -F |||

where we relied on the fact that |||δ ||| = m F (x, y). Using the same reasoning, we also obtain the inequality m

F (x, y) ≤ m F (x, y) + |||F -F |||. Combining gives |m F (x, y) -m F (x, y)| ≤ |||F -F |||.

Lemma A.1 now directly follows. 

Proof of Lemma:

C |||•||| (F) i α 2p/(p+2) i C • op (F i ) 2p/(p+2) (p+2)/2p (A.3)

Then we have Proof. Let F i be an i -cover of F i in the operator norm • op . We will first show that

log N |||•||| ( , F) ≤ C 2 |||•||| (F)

F { F k •• • •• F 1 : F i ∈ F i } is a {α i i } k i=1 p -cover of F in ||| • |||.

To see this, for any F = (f k , . . . , f 1 ) ∈ F, let f i ∈ F i be the cover element for f i , and define F ( f k , . . . , f 1 ). Then we have

||| F -F ||| = {α i f i -f i op } k i=1 p ≤ {α i i } k i=1 p

as desired. Furthermore, we note that log | F| ≤ i C 2

• op (Fi)

2 i

by Condition A.1. Now we will

choose i = C |||•||| (F) -2/(p+2) C • op (F i ) 2/(p+2) α -p/(p+2) i

We first verify that this gives an -cover of F in ||| • |||:

{α i i } k i=1 p = C |||•||| (F) -2p/(p+2) i C • op (F i ) 2p/(p+2) α p-p 2 /(p+2) i 1/p = C |||•||| (F) -2/(p+2) i C • op (F i ) 2p/(p+2) α 2p/(p+2) i 1/p = C |||•||| (F) -2/(p+2) C |||•||| (F) 2/(p+2) =

Next, we check that the covering number is bounded by

C 2 |||•||| (F ) 2 : i C 2 • op (F i ) 2 i ≤     i C 2 • op (F i ) 2 C |||•||| (F) 4/(p+2) C • op (F i ) -4/(p+2) α 2p/(p+2) i 2     = i C |||•||| (F) 4/(p+2) C • op (F i ) 2p/(p+2) α 2p/(p+2) i 2 = C |||•||| (F) 4/(p+2) C |||•||| (F) 2p/(p+2) 2 = C |||•||| (F) 2 2

Finally, we prove Theorem A.1 (and as a result, Theorem 2.1). This will hinge on applying Lemma A.2 with the correct choice of smooth loss.

Proof of Theorems A.1 and 2.1. Define β (m) 1 + 2 min{0, Pr Z∼N (0,1) (Z/ √ β ≥ m) -0.5}. By Claim A.2, this loss is c 1 β smooth and for m F (x, y) > 0 satisfies

β (m F (x, y)) ≤ c 2 √ q √ βm F (x, y)

q for universal constants c 1 , c 2 . We additionally have 0-1 (F (x), y) ≤ β (m F (x, y)). Because of Lemma A.3, the conditions of Lemma A.2 are satisfied, and applying Lemma A.2 with smooth loss β gives with probability 1 -δ, for all F ∈ F with training error 0

E P [ 0-1 (F (x), y)] ẼF (β) + log(1/δ) + log log n n

where ẼF (β) is defined by

ẼF (β) 1 n (x,y)∈Pn c 2 √ q √ βm F (x, y) q + βC 2 |||•||| (F) log 2 n n and C 2 |||•||| (F)

is defined as in Lemma A.3. Choosing β 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 to be fixed before the training data is drawn.

Instead, we utilize the standard technique of union bounding over a grid of β in log-scale. Let ξ C 2 |||•||| (F)poly(n -1 ) denote the minimum choice of β in this grid, and select in this grid all choices of β in the form ξ2 j for j ≥ 0. For a given choice of β, we assign it failure probability δ = δ 2 β/ξ , such that by design δ = δ. Thus, applying Lemma A.2 for each choice of β with corresponding failure probability δ, we note with probability 1 -δ,

E P [ 0-1 (F (x), y)] ẼF ( β) + log(1/δ) + log( β/ξ) + log log n n

holds for all β and F ∈ F.

Now for fixed F ∈ F, let β F denote the optimizer of ẼF (β). We claim either there is some choice of β with

ẼF ( β) + log(1/δ) + log( β/ξ) + log log n n ẼF (β F ) + O log n + log(1/δ) n (A.4)

or ẼF (β F ) 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 β in the grid such that β ∈

[β F , 2β F + ξ]. Then ẼF ( β) ≤ 1 n (x,y)∈Pn c 2 √ q β F m F (x, y) q + 4β F C 2 |||•||| (F) log 2 n n + poly(n -1 ) ≤ 4 ẼF (β F ) + poly(n -1 )

Furthermore, we note that if β F > poly(n)ξ, then ẼF (β F ) 1. This allows to only consider β < poly(n)ξ, giving (A.4).

Thus, with probability 1 -δ, for all F ∈ F, we have

E P [ 0-1 (F (x), y)] ẼF (β F ) + O log n + log(1/δ) n It remains to observe that setting β F = Θ   q n 1 m F q Lq (Pn) C |||•||| (F ) 2 log 2 n 2/(q+2) 

 gives us the theorem statement.

Claim A.2. For β > 0, define the loss function β (m) 1 + 2 min{0, Pr Z∼N (0,1) (Z/ √ β ≥ m) -0.5}. Then β satisfies the following properties:

1. For all m ∈ R, β (m) ∈ [0, 1], and for m ≤ 0, β (m) = 1.

2. The function β is c 1 β-smooth for some constant c 1 independent of β.

3. For any integer q > 0 and m > 0, β (m) ≤ q q/2 c q 2 β q/2 m q for some constant c 2 independent of q.

Proof. The first property follows directly from the construction of β . For the second property, we first note that d 2 dm 2 Pr Z∼N (0,1)

(Z/ β ≥ m) = mβ 3/2 √ 2π exp(-m 2 β/2)

Now first note that at m = 0, the above quantity evaluates to 0, and thus β has a second derivative everywhere (as m = 0 is the only point where the function switches). Furthermore, max m m √ β exp(-m 2 β/2) = max y y exp(-y 2 /2) ≤ c for some constant c independent of β. Thus, the above expression is upper bounded by β √ 2π c , giving the second property. For the third property, we note that for m > 0, β (m) = 2 Pr Z∼N (0,1) (Z/ √ β ≥ m). As the q-th moment of a Gaussian random variable with variance 1 is upper bounded by q q/2 c q 2 for all q and some c 2 independent of q, Markov's inequality gives the desired result.

A.1 PROOF OF LEMMA A.2:

The proof is a straightforward application of Lemma A.1 and conversion of (Srebro et al., 2010) from the language of Rademacher complexity to covering numbers.

Proof of Lemma A.2. We can follow the proof of Theorem 1 in (Srebro et al., 2010) , with the only difference that we replace their Rademacher complexity term with our complexity function C |||•||| (F). For completeness, we outline the steps here. 

C |||•||| (F ) √ 48βµ √ n

log n. By Claim A.3, the following holds for all µ:

E σ sup h∈H(µ) i σ i h(x i , y i ) ≤ ψ(µ)

Now using the same steps as (Srebro et al., 2010) (which relies on applying Theorem 6.1 of (Bousquet, 2002)), we obtain for all F ∈ F, with probability 1 -δ

E P [ • m F ] ≤ E Pn [ • m F ] + 106r n + 48 n (log 1/δ + log log n) + E Pn [ • m F ](8r n + 4 n (log 1/δ + log log n)) (A.5)

where r n is the largest solution of ψ(µ) = µ. We now plug in r n

β log 2 nC 2 |||•||| (F ) n

and use the fact that √ c 1 c 2 ≤ (c 1 + c 2 )/2 for any c 1 , c 2 > 0 to simplify the square root term in A.5.

E P [ • m F ] ≤ 3 2 E Pn [ • m F ] + c βC 2 |||•||| (F) log 2 n n + log(1/δ) + log log n n

for some universal constant c.

Claim A.3. In the setting above, for all µ > 0, we have

E σ sup h∈H(µ) i σ i h(x i , y i ) ≤ C |||•||| (F) √ 48βµ √ n log n

where {σ i } n i=1 are i.i.d. Rademacher random variables.

Proof. First, by Dudley's Theorem (Dudley, 1967) , we have

E σ sup h∈H(µ) i σ i h(x i , y i ) ≤ inf α>0 α + 1 √ n ∞ α log N L2(Pn) ( , H(µ))d

Now by Claim A.4, we obtain

E σ sup h∈H(µ) i σ i h(x i , y i ) ≤ inf α>0   α + 1 √ n ∞ α 48βµ C 2 |||•||| (F) 2 d   (by Claim A.4) ≤ inf α>0   α + √ 48βµ √ n ∞ α/ √ 48βµ C 2 |||•||| (F) 2 d   (A.6)

We obtained the last line via change of variables to = / √ 48βµ. Now we substitute α =

C |||•||| (F ) √ 48βµ √ n

and note that the integrand is

0 for > C |||•||| (F) to get E σ sup h∈H(µ) i σ i h(x i , y i ) ≤ C |||•||| (F) √ 48βµ √ n 1 + C |||•||| (F ) C |||•||| (F )/ √ n 1 d ≤ C |||•||| (F) √ 48βµ √ n log n

The following claim applies Lemma A.1 in order to bound the covering number of H(µ) in terms of

C |||•||| (F).

Claim A.4. In the setting of Lemma A.2, we have the covering number bound

EQUATION

Proof. As • m • F is the composition of a β-smooth loss with the function class m • F, by equation ( 22) of (Srebro et al., 2010) we have

log N L2(Pn) ( , H(µ)) ≤ log N ∞ ( / 48βµ, m • F) ≤ log N |||•||| ( / 48βµ, F) (by Lemma A.1) ≤ 48βµ C |||•||| (F) 2 (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 to 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 a κ φ -Lipschitz derivative. For parameters {a (i) } r i=1 meant to be norm constraints for the weights, define the class of neural nets with bounded weight norms with respect to reference matrices {A (i) , B (i) } as follows:

F {x → F (x) : min{ √ d W (i) -A (i) fro , W (i) -B (i) 1,1 } log d ≤ a (i) ∀i}

Then with probability 1 -δ, for any q > 0 and for all F ∈ F, we have

E P [ 0-1 (F (x), y)] ≤ 3 2 E Pn [ 0-1 (F (x), y)] + O r log n + log(1/δ) n + (1 -E Pn [ 0-1 (F (x), y)]) 2/(q+2) O   q log 2 n n q (q+2) i ( κ NN (i) Lq(Sn) a (i) ) 2/3 3q (q+2)  

where S n denotes the subset of examples classified correctly by F and κ NN (i) is defined as in (3.2).

Proof. We will identify the class of neural nets with matrix norm bounds {a (i) } r i=1 with a sequence of function families

F 2i-1 {h → W h : W ∈ R d×d , min{ √ d W -A (i) F , W -B (i) 1,1 } log d ≤ a (i) } F 2i {h → φ(h)} and let F F 2r-1 • • • • • F 1 denote

all possible parameterizations of neural nets with norm bounds {a (i) } r i=1 . Let • op be defined with respect to Euclidean norm • 2 on the input and output spaces, which coincides with matrix operator norm for linear operators. We first claim that

log N • op ( , F 2i-1 ) a (i) 2 2

This is because we can construct two covers: one for {h → W h :

√ d W F / √ log d ≤ a (i) }, and one for {h → W h : W 1,1 / √ log d ≤ a (i) }

, each of which has log size bounded by O( a (i) 2 / 2 ) by Lemma B.2 and Claim B.2. Now we offset the first cover by the linear operator A (i) and the second by B (i) and take the union of the two, obtaining an -cover for F 2i-1 in operator norm. Furthermore, log N • op ( , F 2i ) = 0 simply because F 2i is the singleton function.

Thus, F 2i-1 , F 2i satisfy Condition A.1 with norm

• op and complexity functions

C • op (F 2i-1 )

a (i) and C • op (F 2i ) = 0, so we can apply Theorem C.1. It remains to argue that κ 2i-1 (x, y) as defined for Theorem C.1 using standard Euclidean norm • 2 is equivalent to κ NN (i) (x, y) defined in (3.2). To see this, we note that functions in F 2j-1 have 0-Lipschitz derivative, leading those terms with a coefficient of κ 2j-1 to cancel in the definition of κ i (x, y). There is a 1-1 correspondence between the remaining terms of κ 2i-1 (x, y) and κ NN (i) (x, y), so we can substitute κ NN (i) (x, y) into Theorem C.1 in place of κ 2i-1 (x, y). Furthermore, as we have C • op (F 2i ) = 0, the corresponding terms disappear in the bound of Theorem C.1, finally giving the desired result. Now we obtain Theorem 3.1 by union bounding Lemma B.1 over choices of {a (i) } r i=1 .

Proof of Theorem 3.1. We will use the standard technique of applying Lemma B.1 over many choices of {a (i) }, and union bounding over the failure probability. Choose ξ = poly(n -1 ) and consider a grid of { α (i) } with a (i) = ξ2 ji for j i ≥ 1. We apply Lemma B.1 with for all possible norm bounds { α (i) } in the grid, using failure probability δ = δ/( i a (i) /ξ) for a given choice of { α (i) }. By union bound, with probability 1 -δ = 1 -δ, the bound of Lemma B.1 holds simultaneously for all choices of { α (i) }. In particular, for the neural net F with parameters

{W (i) }, there is a choice of { α (i) } satisfying min{ √ d W (i) -A (i) fro, W (i) -B (i) 1,1} log d ≤ a (i) ≤ 2 min{ √ d W (i) -A (i) fro, W (i) -B (i) 1,1} log d + ξ

for all i. The application of Lemma B.1 for this choice of α (i) gives us the desired generalization bound.

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 m F (x, y) using the techniques in Section C, which rely on smoothness. However, we can still obtain a generalization bound in terms of the distribution of 1/m F (x, y) on the training data. We can expect 1/m F (x, y) to be small in practice because relu networks typically exhibit stability to perturbations. Prior bounds for relu nets suffer from some source of looseness: the bounds of (Bartlett et al., 2017; Neyshabur et 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, observed to be large in practice. Our bound avoids these dependencies, and in fact, it is possible to upper bound our dependency on 1/m F (x, y) in terms of both these quantities.

For this setting, we choose a fixed ||| • ||| defined as follows: if i corresponds to a linear layer in the network, set α i = 1, and for i corresponding to activation layers, set α i = ∞ (in other words, we only allow perturbations after linear layers). We remark that we could use alternative definitions of ||| • |||, but because we do not have a closed-form lower bound on m F , the tradeoff between these formulations is unclear. Theorem B.1. In the neural network setting, suppose that φ is any activation (such as the relu function) and m F is defined using ||| • ||| as described above. Fix any integer q > 0. Then with probability 1 -δ, for all relu networks F parameterized by weight matrices {W (i) } r i=1 that achieve training error 0, we have

E P [ 0-1 • F ] ≤ O     log 2 n    1 m F Lq(Pn) i a (i) √ n    2q/(q+2)     + ζ

where a (i) is defined as in Theorem 3.1, and

ζ O log(1/δ)+r log n+ i (a (i) +1) n

is a low-order term.

The proof follows via direct application of Theorem A.1 and the same arguments as Lemma B.1 relating matrix norms to covering numbers. We remark that in the case of relu networks, we can upper bound 1 m F (x,y) via a 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 is used in Section B to prove our neural net generalization bounds. Lemma B.2. Let M fro (B) denote the set of d 1 × d 2 matrices with Frobenius norm bounded by B, i.e.

EQUATION

Proof. The idea for this proof is that since the cover is in spectral norm, we only need to cover the top d B 2 / 2 singular vectors of matrices M ∈ M.

First, it suffices to work with square matrices, as a spectral norm cover of max{d 1 , d 2 } × max{d 1 , d 2 } matrices will also yield a cover of d 1 × d 2 matrices in spectral norm (as we can extend a d 1 × d 2 matrices to a larger square matrix by adding rows or columns with all 0). Thus, letting d max{d 1 , d 2 }, we will cover M fro (B) defined with respect to d × d matrices.

Let d 9B 2 / 2 . We first work in the case when d ≤ d. Let U be a U Frobenius norm cover of d × d matrices with Frobenius norm bound d . Let V be the cover of d × d matrices with Frobenius norm bound B in Frobenius norm with resolution V . We construct a cover M for M fro (B) as follows: take all possible combinations of matrices U , V from U, V, and add U V to M. First note that by Claim B.1, we have

log | M| ≤ dd (log(3d / U ) + log(3B/ V ))

Now we analyze the cover resolution of M: for M ∈ M, first let trunc d (M ) be the truncation of M to its d largest singular values. Note that as M has at most d singular values with absolute value greater than /3, Mtrunc d (M ) op ≤ /3. Furthermore, let U SV = trunc d (M ) be the SVD decomposition of this truncation, where

U ∈ R d×d , U fro ≤ d and SV ∈ R d ×d , SV fro ≤ B. Let U ∈ U satisfy U -U fro ≤ U , and V ∈ V satisfy V -SV fro ≤ V . Let M = U V . Then we obtain M -M op ≤ M -trunc d (M ) op + trunc d (M ) -M op ≤ /3 + U SV -U SV op + U SV -U V op ≤ + U B + V d

Thus, setting U = /3B, V = /3d , then we get a -cover of M with log cover size 9dB 2 / 2 (log 81d 2 B 2 / 2 ). As d ≤ d, this simplifies to 36dB 2 log(9d)/ 2 . Now when d ≥ d, we simply take a Frobenius norm cover of d × d matrices with Frobenius norm bound B, which by Claim B.1 has log size at most d 2 log(3B/ ) ≤ 36dB 2 log(9d)/ 2 , where the inequality followed because 9B 2 / 2 ≥ d.

Combining both cases, we get for all > 0, log

N • op ( , M fro (B)) ≤ 36dB 2 log(9d) 2

The following claims are straightforward and follow from standard covering number bounds for 

C GENERALIZATION BOUND FOR SMOOTH FUNCTION COMPOSITIONS:

In this section, we present the bound for general smooth function compositions used to prove Theorem 3.1.

We will work in the same general setting as Section A. Let J j←i (x, δ) denote the i-to-j Jacobian evaluated at f i-1←1 (x, δ), i.e. J j←i (x, δ) D h f j←i (h, δ)| h=fi-1←1(x,δ) . We will additionally define general notation for hidden layer and Jacobian norms which coincides with our notation for neural nets. Let s i (x) f i←1 (x) and s 0 (x)

x . As the function Df j←i outputs operators mapping D i-1 to D j , we can additionally define κ j←i (x)

Df j←i • f i-1←1 (x) op , with κ j←j+1 (x) 1.

Let κ i be an upper bound on the Lipschitz constant of Df i←i measured in operator norm:

Df i←i (h) -Df i←i (h + ν) op ≤ κ i ν

Now we define the value κ i (x, y), which can be thought of as a Lipschitz constant for perturbation δ i in the definition of m F , as follows:

EQUATION

κ j κ j -1←i+1 (x)κ j1←j +1 (x)κ j -1←j2 (x) κ j1←j2 (x)   + 8 j2≤i≤j1 κ j1←i+1 (x)κ i-1←j2 (x) κ j1←j2 (x)

(C.1) For this general setting, the following theorem implies that for any integer q > 0, if F classifies all training examples correctly, then its error converges at a rate that scales with n -q/(q+2) and the products

κ i Lq(Pn) C • op (F i ). Theorem C.1. Let F = {f k • • • • • f 1 : f i ∈ F i } denote a class of compositions of functions from k families {F i } k i=1

, each of which satisfies Condition A.1 with operator norm • op and complexity C • op (F i ). For any choice of integer q > 0, with probability 1 -δ for all F ∈ F the following bound holds: In particular, if F classifies all training samples correctly, i.e. |S n | = n, with probability 1 -δ we have

E P [ 0-1 (F (x), y)] ≤ 3 2 (E Pn [ 0-1 (F (x), y)]) + O k log n + log(1/δ) n + (1 -E Pn [ 0-1 (F (x), y)]) 2 q+2 O   q log 2 n n q/(q+2) i κ i 2/3 Lq(Sn) C • op (F i ) 2/3

E P [ 0-1 (F (x), y)] q log 2 n n q/(q+2) i κ i 2/3 Lq(Sn) C • op (F i ) 2/3 3q/(q+2) + ζ where ζ O k log n+log(1/δ)

n is a low order term.

To prove this theorem, we will plug the following lower bound on m F into Lemma A.2 with the appropriate choice of smooth loss , and pick the optimal choice of {α i } k i=1 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 {α i } k i=1 . Lemma C.1 (General version of Lemma 3.1). In the setting of Theorem C.1, where each layer F i is a class of smooth functions, if γ(F (x), y) > 0, we have

m F (x, y) ≥ {κ i (x, y)/α i } k i=1 -1 p/(p-1)

We prove Lemma C.1 in Section D by formalizing the intuition outlined in Section 3. With Lemma C.1 in hand, we can prove Theorem C.1. This proof will follow the same outline as the proof of Theorem A.1. The primary difference is that we optimize over k values of α i , whereas Theorem A.1 only optimized over the smoothness β.

Proof of Theorem C.1. We use β with β = 1 defined in Claim A.2 as a surrogate loss for the 0-1 loss. Since Claim A.2 gives 0-1 (F (x), y) ≤ β=1 (m F (x, y)), by Lemma A.2 it follows that

E P [ 0-1 (F (x), y)] ≤ E P [ β=1 (m F (x, y))] ≤ 3 2 E Pn [ β=1 (m F (x, y))] + c 1 C 2 |||•||| (F) log 2 n n + log(1/δ) + log log n n (C.2)

Now we first note that for a misclassified pair, β=1 (m F (x, y)) = 0-1 (F (x), y) = 1. For cor-

rectly classified examples, we also have the bound β=1 (m F (x, y)) ≤ (c2q) q/2 m F (x,y) q for constant c 2 independent of q. Thus, it follows that

E Pn [ β=1 (m F (x, y))] ≤ E Pn [ 0-1 (F (x), y)] + 1 n (x,y)∈Sn (c 2 q) q/2 m F (x, y) q

Plugging this into (C.2), we get with probability 1 -δ for all F ∈ F,

E Pn [ β=1 (m F (x, y))] ≤ 3 2 E Pn [ 0-1 (F (x), y)] + O E + log(1/δ) + log log n n (C.3)

where E is defined by

E = 1 n (x,y)∈Sn (c 2 q) q/2 m F (x, y) q + C 2 |||•||| (F) log 2 n n (C.4)

Thus, it suffices to upper bound E. By Lemma C.1, we have m F (x, y) ≥ {κ i (x, y)/α i } k i=1 -1 p/(p-1) for the choice of α, p used to define m F . We will set p = q/(q -1) and union bound (C.3) over choices of α.

First, for a particular choice of α and p = q/(q -1), we apply our lower bound on m F (x, y) to simplify (C.4) as follows:

E ≤ 1 n (x,y)∈Sn (c 2 q) q/2 (κ i (x, y)/α i ) k i=1 q q + C 2 |||•||| (F) log 2 n n ≤ k i=1 α -q i   (c 2 q) q/2 n (x,y)∈Sn κ i (x, y) q   + i α 2q/(3q-2) i C • op (F i ) 2q/(3q-2) 3q-2 q log 2 n n (C.5)

For convenience, we use ẼF (α) to denote (C.5) as a function of α. Note that κ i depends on F . Now let α F denote the minimizer of ẼF (α). As we do not know the exact value of α F before the training data is drawn, we cannot simply plug the exact value of α F into (C.5). Instead, we will apply a similar union bound as the proof of Theorem A.1, although this union bound is slightly more complicated because we optimize over k quantities simultaneously.

We use ξ i to denote the lower limit on α i in our search over α, setting

ξ i = C • op (F i ) -1 poly(k -1 n -1

).4 Now we consider a grid of { α i } k i=1 , where α has entries of the form α i = ξ i 2 j for any j ≥ 0. For a given choice of α, we assign it failure probability

δ = δ i 2 α i /ξ (C.6)

where δ is the target failure probability after union bounding. First, note that

δ = δ j1≥0 • • • j k ≥0 1 2 j1+•••+j k +k ≤ δ

Therefore, with probability 1 -δ, we get that (C.2) holds for m F defined with respect to every α. In particular, with probability 1 -δ, for all F ∈ F and α in the grid,

E P [ 0-1 (F (x), y)] ≤ E Pn [ β=1 (m F (x, y))] ≤ 3 2 E Pn [ 0-1 (F (x), y)] + O ẼF ( α) + i log(2 α i /ξ i ) + log(1/δ) + log log n n (C.7)

where the last term was obtained by subsituting (C.6) for the failure probability. Now we claim that there is some choice of α in the grid such that either

ẼF ( α) + i log(2 α i /ξ i ) + log(1/δ) + log log n n ≤ 9 ẼF (α F ) + O k log(n) + log(1/δ) n (C.8)

or ẼF (α F ) 1 (in which case it is trivial to obtain generalization error bounded by ẼF (α F )).

To see this, we first consider α in our grid such that

α i ∈ [α F,i , 2α F,i + ξ i ]

. By construction of our grid of α, such a choice always exists. Then we have

ẼF ( α) = k i=1 α -q i   (c 2 q) q/2 n (x,y)∈Sn κ i (x, y) q   + i α 2q/(3q-2) i C • op (F i ) 2q/(3q-2) 3q-2 q log 2 n n ≤ k i=1 α F,i -q   (c 2 q) q/2 n (x,y)∈Sn κ i (x, y) q   + 9 i α F,i 2q/(3q-2) C • op (F i ) 2q/(3q-2) (3q-2)/q log 2 n n + poly(n -1 )

The first term we obtained because α i ≥ α F,i , and the second via the upper bound α i ≤ 2α F,i + ξ i . Thus, for some choice of α in the grid, we have ẼF

( α) ≤ 9 ẼF (α F ) + poly(n -1 ). Furthermore, if α F > c • C • op (F i ) -1 n for some constant c, we note that ẼF (α F ) 1 -thus, it suffices to only consider α F ≤ c • C • op (F i ) -1 n.

In particular, we only need to consider α i where log(2 α i /ξ i ) log kn. Finally, we note that we can assume WLOG that k n otherwise (C.8) would give a trivial bound. Combining these facts gives (C.8).

Thus, it follows that for all F ∈ F,

E P [ 0-1 (F (x), y)] ≤ 3 2 E Pn [ 0-1 (F (x), y)] + O ẼF (α F ) + k log n + log(1/δ) n (C.9)

Finally, we can apply Lemma C.2 using z i = (c2q) q/2 n (x,y)∈Sn κ i (x, y) q

1/q = |Sn| n 1/q κ i Lq(Sn) and b i = C • op (Fi) log n √ n to get ẼF (α F ) |S n | n 2/(q+2) q log 2 n n q/(q+2) i κ i 2/3 Lq(Sn) C • op (F i ) 2/3 3q/(q+2)

Substituting into (C.9) gives the desired bound.

Lemma C.2. For coefficients {z i } k i=1 , {b i } k i=1 > 0 and integer q > 0, define

E(α) i z q i /α q i + i α 2q/(3q-2) i b 2q/(3q-2) i (3q-2)/q

with minimizer α and minimum value E . Then

E ≤ 2 i (z i b i ) 2/3 3q/(q+2)

Proof. Choose {α i } k i=1 as follows (we obtained this by solving for α for which ∇ α E(α) = 0):

α i = q 2 1 (q+2) z 3q-2 3q i b -2 3q i i z 2/3 i b 2/3 i 2-2q q(q+2)

For this particular choice of α, we can compute

i z q i /α q i = q 2 -q q+2 i z q i z -q+2/3 i b 2/3 i i z 2/3 i b 2/3 i 2q-2 q+2 = q 2 -q q+2 i z 2/3 i b 2/3 i i z 2/3 i b 2/3 i 2q-2 q+2 = q 2 -q q+2 i z 2/3 i b 2/3 i 3q q+2

Likewise, we can also compute

i α 2q/(3q-2) i b 2q/(3q-2) i (3q-2)/q = q 2 2 q+2 i (z i b i ) 2/3 (3q-2)/q i (z i b i ) 2/3 4-4q q(q+2) = q 2 2 q+2 i (z i b i ) 2/3 3q 2 +4q-4+4-4q q(q+2) = q 2 2 q+2 i (z i b i ) 2/3 3q q+2

Finally, we note that q 2 2/(q+2) + q 2 -q q+2 ≤ 2, so we obtain

E ≤ E(α) ≤ 2 i (z i b i ) 2/3 3q/(q+2) D LOWER BOUNDING m F FOR SMOOTH LAYERS

In this section, we prove Lemma C.1, which states that when the function F is a composition of functions with Lipschitz derivative, we will be able to lower bound m F (x, y) in terms of the intermediate Jacobians and layer norms evaluated at x. 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 if all the intermediate Jacobians are bounded.

First, we define the soft indicator 1 ≤t as follows:

1 ≤t (z) = 1 if z ≤ t 2 -z/t if t ≤ z ≤ 2t 0 if 2t ≤ z

We also define the ramp loss T ρ as follows:

T ρ (z) = 1 if z ≥ ρ z/ρ if 0 ≤ z < ρ 0 if z < 0

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[γ(F (x, δ), y) ≥ 0]. We define this augmented indicator by

I(δ; x, y) T ρ (γ(f k←1 (x, δ), y)) 1≤i≤k-1 1 ≤ti ( f i←1 (x, δ) ) 1≤i≤j≤k 1 ≤τj←i ( J j←i (x, δ) op ) (D.1)

for nonnegative parameters ρ, t i , τ j←i which we will later choose to be the margin, hidden layer norm, and Jacobian norms at the unperturbed input. Because the augmented indicator I(δ; x, y) conditions on small Jacobian and hidden layer norms, it will turn out to be κ i (x, y)-Lipschitz in the perturbation δ i . Furthermore, by construction, the value of the augmented indicator I(δ; x, y) will equal 1 when δ = 0, and we will also have

1[γ(F (x, δ), y) ≥ 0] ≥ I(δ; x, y) ≥ 1 - i κ i (x, y) δ i

This immediately gives a lower bound on the perturbation level required to create a negative margin.

The lemma below formally bounds the Lipschitz constant of I(δ; x, y) in δ i . Lemma D.1. For nonnegative parameters t i , τ j←i , ρ, with τ j←j+1 = 1 for any j and τ j←j = 0 for j ≤ j + 2, define the function I(δ; x, y) as in (D.1). Then in the setting of Lemma C.1, for a given i ∈ [k], for all choices of δ i and ν, if δ j = 0 for j > i, we have

|I(δ i + ν, δ -i ; x, y) -I(δ i , δ -i ; x, y)| ≤ κi ν

for κi defined as follows:

κi ti-1   8τ k←i+1 ρ + k-1 j=i 8τj←i+1 tj + 1≤j 2 ≤j 1 ≤k j 1 j =max{i+1,j 2 } 16κ j τ j -1←i+1 τ j 1 ←j +1 τ j -1←j 2 τj 1 ←j 2   + 8 j 2 ≤i≤j 1 τj 1 ←i+1τi-1←j 2 τj 1 ←j 2 (D.2)

We prove Lemma D.1 in Section D.1. With Lemma D.1, we can formalize the proof of Lemma C.1.

Proof of Lemma C.1. We will apply Lemma D.1, using t i = s i (x), ρ = γ(F (x), y), τ j←i = κ j←i (x). First, note that for this choice of parameters, the Lipschitz constant κi of Lemma D.1 evaluates to κ i (x, y). Thus, it follows that for all δ, |I(0; x, y) -I(δ; x, y)|

≤ i |I(δ 1 , . . . , δ i-1 , δ i = 0, δ j>i = 0; x, y) -I(δ 1 , . . . , δ i , δ j>i = 0; x, y)| ≤ i κ i (x, y) δ i (D.3)

Furthermore, by the definition of I(δ; x, y), we have

1[γ(F (x, δ), y) ≥ 0] ≥ I(δ; x, y)

Finally, by our choice of the parameters used to define I(δ; x, y), we also have I(0; x, y) ≥ 1.

Combining everything with (D.3), we get

1[γ(F (x, δ), y) ≥ 0] ≥ I(δ; x, y) ≥ I(0; x, y) - i κ i (x, y) δ i ≥ 1 -{κ i (x, y)/α i } k i=1 p/(p-1) {α i δ i } k i=1 p (since • p/(p-1) and • p are dual norms) = 1 -{κ i (x, y)/α i } k i=1 p/(p-1) |||δ||| Thus, for any δ, if |||δ||| < {κ i (x, y)/α i } k i=1 -1 p/(p-1) , then 1[γ(F (x, δ), y) ≥ 0] > 0, which in turn implies γ(F (x, δ), y) ≥ 0. It follows by definition of m F (x, y) that m F (x, y) ≥ {κ i (x, y)/α i } k i=1 -1 p/(p-1) .

Now to remove the C worst-case Lipschitzness assumption, we can follow the reasoning of Claim D.6 of (Wei and Ma, 2019) to note that such Lipschitz constants exist if we restrict δ i to some compact set, and thus conclude the lemma statement for δ i restricted to this compact set. Now we simply choose this compact set sufficiently large to include both δ i and δ i + ν.

D.2 PROOFS FOR PRODUCT-LIPSCHITZ LEMMAS:

Proof of Lemma D.2. As each A i is Lipschitz and there are a finite number of functions, there exists C such that any possible product

A i1 A i2 • • • A ij is C -Lipschitz.

Furthermore, by the definition of product-Lipschitz, there are c, C > 0 such that for any ν ≤ c, x ∈ D I , and 1 ≤ i ≤ q, we have

|(A i (x + ν) -A i (x))| j =i A j (x) ≤ τi ν + C ν 2

Now we note that

i A i (x + ν) - i A i (x) = i   i-1 j=1 A j (x + ν) q j=i+1 A j (x)   (A i (x + ν) -A i (x)) (D.4)

Now for any i, we have

|(A i (x + ν) -A i (x)) i-1 j=1 A j (x + ν) q j=i+1 A j (x)| ≤ |(A i (x + ν) -A i (x))|( i-1 j=1 A j (x) + C ν ) q j=i+1 j (x) (as i-1 j=1 A j is C -Lipschitz) ≤ |A i (x + ν) -A i (x)|( j =i A j (x) + C ν )

We used the fact that q j=i+1 A j (x) ≤ 1. Now we have |A i (x + ν) -A i (x)| j =i A j (x) ≤ τi ν + C ν 2 , and |A i (x + ν) -A i (x)|C ν ≤ C 2 ν 2 as A i is C -Lipschitz, so

|(A i (x + ν) -A i (x)) i-1 j=1 A j (x + ν) q j=i+1 A j (x)| ≤ τi ν + (C + C 2 ) ν 2

Plugging this back into (D.4) and applying triangle inequality, we get

| i A i (x + ν) - i A i (x)| ≤ ν i τi + q(C + C 2 ) ν

Define the constant C min{c, i τi q(C+C 2 ) }. For any x and all ν satisfying ν ≤ C , we have

| i A i (x + ν) - i A i (x)| ≤ 2 ν i τi (D.5)

Now for any x, y ∈ D I , we wish to show | i A i (y)i A i (x)| ≤ 2 x -y i τi . To this end, we divide x -y into segments of length at most C and apply (D.5) on each segment. Define x (j) = x + j C

x-y (y -x) for j = 1, . . . , x -y /C . Then as x (j) -x (j-1) ≤ C , we have | i A i (x (j) )i A i (x (j-1) )| ≤ x (j) -x (j-1) i τi . Furthermore, we note that the sum of all the segment lengths equals y -x . Thus, we can sum this inequality over pairs (x, x (1) ), . . . , (x ( x-y /C ) , y) and apply triangle inequality to get Proof. By definition, f j←1 (x, δ) = f j←i+1 (f i←1 (x, δ), δ). Thus, we note that f j←1 (x, δ) only depends on δ i through f i←1 (x, δ), so by chain rule we have D δi f j←1 (x, δ) = D h f j←i+1 (h, δ)| h=fi←1(x,δ) D δi f i←1 (x, δ) = J j←i+1 (x, δ)D δi [f i (f i-1←1 (x, δ)) + δ i f i-1←1 (x, δ) ] = J j←i+1 (x, δ) f i-1←1 (x, δ)

In the second line, we invoked the definition of J j←i+1 (x, δ).

Claim D.3. We have the expansion

J j←i (x, δ) = J j←j (x, δ) • • • J i←i (x, δ)

Proof. This is a result of the chain rule, but for completeness we state the proof here. We have

D h f j←i (h, δ) = D h f j (f j-1←i (h, δ), δ) = D h f j←j (h , δ)| h =fj-1←i(h,δ) D h f j-1←i (h, δ)

(by chain rule) (D.8) Thus, plugging in h = f i-1←1 (x, δ), we get

J j←i (x, δ) = D h f j←i (h, δ)| h=fi-1←1(x,δ) = D h f j←j (h , δ)| h =fj-1←i(fi-1←1(x,δ),δ) D h f j-1←i (h, δ)| h=fi-1←1(x,δ) = D h f j←j (h , δ)| h =fj-1←1(x,δ) J j-1←i (x, δ) = J j←j (x, δ)J j-1←i (x, δ)

Now we can apply identical steps to expand J j-1←i (x, δ), giving the desired result.

E PROOFS FOR ADVERSARIALLY ROBUST CLASSIFICATION:

In this section, we derive the generalization bounds for adversarial classification presented in Section 4. Recall the adversarial all-layer margin m adv F (x, y) min x ∈B adv (x) m F (x , y) defined in Section 4. In this section, we will use the general definition of m F in (A.1).

We will sketch the proof of Theorem E.1 using the same steps as those laid out in Sections 2 and A. We will rely on the following general analogue of Theorem C.1 with the exact same proof, but with κ i (defined in Section C) replaced by κ adv i (x, y) max x ∈B adv (x) κ i (x , y) everywhere:

Theorem E.1. Let F = {f k • • • • • f 1 : f i ∈ F i }

denote a class of compositions of functions from k families {F i } k i=1 , each of which satisfies Condition A.1 with operator norm • op and complexity C • op (F i ). For any choice of integer q > 0, with probability 1 -δ for all F ∈ F the following bound holds: In Table 3 , we demonstrate that our AMO algorithm can also improve performance for conventional feedforward architectures such as VGG (Simonyan and Zisserman, 2014) . We report the best validation 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 at the 150-th and 250-th epochs. For the AMO algorithm, we optimize perturbations δ for t = 1 steps and use learning rate η perturb = 0.01.

In Table 4 , we demonstrate that our AMO algorithm can offer improvements over dropout, which is also a 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 p in Table 4 . We use the same hyperparameter settings as described above.

F.2 ADDITIONAL DETAILS FOR ROBUST AMO:

Our implementation is based on the robustness library by (Engstrom et al., 2019) 5 . For both methods, we produce the perturbations during training using 10 steps of PGD with ∞ perturbations with radius = 8. We update the adversarially perturbed training inputs with a step size of 2 in pixel space. During evaluation, we use 50 steps of PGD with 10 random restarts and perturbation radius = 8. For all models, we train for 150 epochs using SGD with a learning rate decay of 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 δ have a step size of 6.4e-3, and we shrink the norm of δ by a factor of 0.92 every iteration. For the WideResNet16 model trained with robust AMO, we use a 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 to 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.

:

This is a stronger version of the classical textbook bound which involves the min margin on the training examples. We present this stronger version because it motivates our work better. It can be derived from the results ofSrebro et al. (2010).

If we use a relu network, G(δ, Θ; x, 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 FORWARDPERTURB function, we perform the update fj←1(x, δ) = fj(fj-1←1(x, δ)) + fj(fj-1←1(x, δ)) δj, rather than scaling δ by the previous layer normthis allows the perturbation to also account for the scaling of layer j.

If C • op (Fi) = 0, then we simply set αi = ∞, which is equivalent to restricting the perturbations used in computing mF to layers where C • op (Fi) > 0.

https://github.com/MadryLab/robustness

Figures and Tables:

which by definition implies that F satisfies Condition A.1 with norm ||| • ||| and complexity C |||•||| (F).

Define H(µ) = {h ∈ •m•F : E Pn [h] ≤ µ} to be the class of functions in •m•F with empirical loss at most µ. Define ψ(µ)

denotes the subset of training examples correctly classified by F and κ i is defined in (C.1).

| i A i (y)i A i (x)| ≤ 2 x -y i τi as desired.

n denotes the subset of training examples correctly classified by F with respect to adversarial perturbations. In particular, if F classifies all training samples with adversarial error 0, i.e.|S advn | = n, with probability 1 -δ we haveE P [ adv 0-1 (F (x), y)] q Lq(S adv n ) C • op (F i ) 2/3 3q/(q+2) + ζ where ζ O k log n+log(1/δ)n is a low order term.

Validation error on CIFAR for standard training vs. AMO (Algorithm 1).

Table content: <table><tr><td>Dataset</td><td>Arch.</td><td>Setting</td><td>Standard SGD</td><td>AMO</td></tr><tr><td/><td/><td>Baseline</td><td>4.15%</td><td>3.42%</td></tr><tr><td/><td>WRN16-10</td><td>No data augmentation</td><td>9.59%</td><td>6.74%</td></tr><tr><td>CIFAR-10</td><td/><td>20% random labels Baseline</td><td>9.43% 3.82%</td><td>6.72% 3.00%</td></tr><tr><td/><td>WRN28-10</td><td>No data augmentation</td><td>8.28%</td><td>6.47%</td></tr><tr><td/><td/><td>20% random labels</td><td>8.17%</td><td>6.01%</td></tr><tr><td>CIFAR-100</td><td>WRN16-10 WRN28-10</td><td>Baseline No data augmentation Baseline No data augmentation</td><td>20.12% 31.94% 18.85% 30.04%</td><td>19.14% 26.09% 17.78% 24.67%</td></tr></table>

Robust validation error on CIFAR-10 for standard robust training(Madry et al., 2017) vs. robust AMO. The attack model is 50 steps of PGD with 10 random restarts using ∞ perturbations with radius = 8.

Table content: <table><tr><td>Arch.</td><td colspan="2">(Madry et al., 2017) Robust AMO</td></tr><tr><td>WideResNet16-10</td><td>48.75%</td><td>45.94%</td></tr><tr><td>WideResNet28-10</td><td>45.47%</td><td>42.38%</td></tr></table>

Lemma A.2 (Straightforward adaptation from(Srebro et al., 2010)). Suppose that is a β-smooth loss function taking values in [0, 1]. Furthermore suppose that F satisfies Condition A.1 with respect to norm ||| • ||| and complexity C |||•||| (F). Then with probability 1 -δ, for all F ∈ F, The final ingredient is showing that when each individual layer F i satisfies Condition A.1 in operator norm, the class of compositions F satisfies Condition A.1 with respect to norm ||| • |||. Lemma A.3. Suppose that each F i satisfies Condition A.1 with norm • op and complexity C • op (F i ). Define the complexity measure C |||•||| (F) by

Table content: <table><tr><td>E P [ (m F (x, y))] ≤</td><td>3 2</td><td>E Pn [ (m F (x, y))] + c</td><td>βC 2 |||•||| (F) log 2 n n</td><td>+</td><td>log(1/δ) + log log n n</td></tr><tr><td colspan="3">for some universal constant c &gt; 0.</td><td/><td/><td/></tr></table>

• 2 and • 1 balls. Claim B.1. Let M fro (B) denote the class of d 1 × d 2 matrices with Frobenius norm bounded by B. Then for 0< < B, log N • fro ( , M fro (B)) ≤ d 1 d 2 log(3B/ ). Let M • 1,1 (B) denote the class of d 1 × d 2 matrices with the 1 norm of its entries bounded by B. Then log N • fro ( , M • 1,1 (B)) ≤ 5 B 2 / 2 log 10d.

Table content: <table><tr><td>Claim B.2.</td></tr></table>

Validation error on CIFAR-10 for VGG-19 architecture trained with standard SGD and AMO.

Table content: <table><tr><td>Arch.</td><td colspan="2">Standard SGD AMO</td></tr><tr><td>VGG-19</td><td>5.66%</td><td>5.06%</td></tr></table>

Validation error on CIFAR for models trained with dropout vs. AMO. We tuned the dropout probability p and display the best-performing value.

Table content: <table><tr><td>Dataset</td><td>Arch.</td><td>Tuned Dropout</td><td>AMO</td></tr><tr><td>CIFAR-10</td><td colspan="2">WRN16-10 4.04% (p = 0.1) WRN28-10 3.52% (p = 0.1)</td><td>3.42% 3.00%</td></tr><tr><td>CIFAR-100</td><td colspan="3">WRN16-10 19.57% (p = 0.1) 19.14% WRN28-10 18.77% (p = 0.2) 17.78%</td></tr></table>

Peer review (iclr2020):
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. Major comments: 1. 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. 2. 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. Minor comments: 1. 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. 2. 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. 3. There seem to be some typos: second min in (2.2) etc.