Title: ON THE MARGIN THEORY OF FEEDFORWARD NEURAL NETWORKS Anonymous

Abstract: Past works have shown that, somewhat surprisingly, over-parametrization can help generalization in neural networks. Towards explaining this phenomenon, we adopt a margin-based perspective. We establish: 1) for multi-layer feedforward relu networks, the global minimizer of a weakly-regularized cross-entropy loss has the maximum normalized margin among all networks, 2) as a result, increasing the over-parametrization improves the normalized margin and generalization error bounds for deep networks. In the case of two-layer networks, an infinite-width neural network enjoys the best generalization guarantees. The typical infinite feature methods are kernel methods; we compare the neural net margin with that of kernel methods and construct natural instances where kernel methods have much weaker generalization guarantees. We validate this gap between the two approaches empirically. Finally, this infinite-neuron viewpoint is also fruitful for analyzing optimization. We show that a perturbed gradient flow on infinite-size networks finds a global optimizer in polynomial time.

1. INTRODUCTION:

In deep learning, over-parametrization refers to the widely-adopted technique of using more parameters than necessary (Krizhevsky et al., 2012; Livni et al., 2014) . Both computationally and statistically, over-parametrization is crucial for learning neural nets. Controlled experiments demonstrate that over-parametrization eases optimization by smoothing the non-convex loss surface (Livni et al., 2014; Sagun et al., 2017) . Statistically, increasing model size without any regularization still improves generalization even after the model interpolates the data perfectly (Neyshabur et al., 2017b) . This is surprising given the conventional wisdom on the trade-off between model capacity and generalization.

In the absence of an explicit regularizer, algorithmic regularization is likely the key contributor to good generalization. Recent works have shown that gradient descent finds the minimum norm solution fitting the data for problems including logistic regression, linearized neural networks, and matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018b; Li et al., 2018; Gunasekar et al., 2018a; Ji & Telgarsky, 2018) . Many of these proofs require a delicate analysis of the algorithm's dynamics, and some are not fully rigorous due to assumptions on the iterates. To the best of our knowledge, it is an open question to prove analogous results for even two-layer relu networks. (For example, the technique of Li et al. (2018) on two-layer neural nets with quadratic activations still falls within the realm of linear algebraic tools, which apparently do not suffice for other activations.)

We propose a different route towards understanding generalization: making the regularization explicit. The motivations are: 1) with an explicit regularizer, we can analyze generalization without fully understanding optimization; 2) it is unknown whether gradient descent provides additional implicit regularization beyond what 2 regularization already offers; 3) on the other hand, with a sufficiently weak 2 regularizer, we can prove stronger results that apply to multi-layer relu networks. Additionally, explicit regularization is perhaps more relevant because 2 regularization is typically used in practice.

Concretely, we add a norm-based regularizer to the cross entropy loss of a multi-layer feedforward neural network with relu activations. We show that the global minimizer of the regularized objective achieves the maximum normalized margin among all the models with the same architecture, if the regularizer is sufficiently weak (Theorem 2.1). Informally, for models with norm 1 that perfectly classify the data, the margin is the smallest difference across all datapoints between the classifier score for the true label and the next best score. We are interested in normalized margin because its inverse bounds the generalization error (see recent work (Bartlett et al., 2017; Neyshabur et al., 2017a; 2018; Golowich et al., 2017) or Proposition 3.1). Our work explains why optimizing the training loss can lead to parameters with a large margin and thus, better generalization error (see Corollary 3.2). We further note that the maximum possible margin is non-decreasing in the width of the architecture, and therefore the generalization bound of Corollary 3.2 can only improve as the size of the network grows (see Theorem 3.3). Thus, even if the dataset is already separable, it could still be useful to increase the width to achieve larger margin and better generalization.

At a first glance, it might seem counterintuitive that decreasing the regularizer is the right approach. At a high level, we show that the regularizer only serves as a tiebreaker to steer the model towards choosing the largest normalized margin. Our proofs are simple, oblivious to the optimization procedure, and apply to any norm-based regularizer. We also show that an exact global minimum is unnecessary: if we approximate the minimum loss within a constant factor, we obtain the max-margin within a constant factor (Theorem 2.2).

To better understand the neural network max-margin, in Section 4 we compare the max-margin two-layer network obtained by optimizing both layers jointly to kernel methods corresponding to fixing random weights for the hidden layer and solving a 2-norm max-margin on the top layer. We design a simple data distribution (Figure 1 ) where neural net margin is large but the kernel margin is small. This translates to an Ω( √ d) factor gap between the generalization error bounds for the two approaches and demonstrates the power of neural nets compared to kernel methods. We experimentally confirm that a gap does indeed exist.

In the setting of two-layer networks, we also study how over-parametrization helps optimization. Prior works (Mei et al., 2018; Chizat & Bach, 2018; Sirignano & Spiliopoulos, 2018; Rotskoff & Vanden-Eijnden, 2018) show that gradient descent on two-layer networks becomes Wasserstein gradient flow over parameter distributions in the limit of infinite neurons. For this setting, we prove that perturbed Wasserstein gradient flow finds a global optimizer in polynomial time.

Finally, we empirically validate several claims made in this paper. First, we confirm that neural networks do generalize better than kernel methods. Second, we show that for two-layer networks, the test error decreases and margin increases as the hidden layer grows, as predicted by our theory.

1.1 ADDITIONAL RELATED WORK Zhang et al. (2016) and Neyshabur et al. (2017b) show that neural network generalization defies conventional explanations and requires new ones. Neyshabur et al. (2014) initiate the search for the "inductive bias" of neural networks towards solutions with good generalization. Recent papers (Hardt et al., 2015; Brutzkus et al., 2017; Chaudhari et al., 2016 ) study inductive bias through training time and sharpness of local minima. Neyshabur et al. (2015a) propose a new steepest descent algorithm in a geometry invariant to weight rescaling and show that this improves generalization. Morcos et al. (2018) relate generalization in deep nets to the number of "directions" in the neurons. Other papers (Gunasekar et al., 2017; Soudry et al., 2018; Nacson et al., 2018; Gunasekar et al., 2018b; Li et al., 2018; Gunasekar et al., 2018a) study implicit regularization towards a specific solution. Ma et al. (2017) show that implicit regularization can help gradient descent avoid overshooting optima. Rosset et al. (2004a; b) study logistic regression with a weak regularization and show convergence to the max margin solution. We adopt their techniques and extend their results.

A line of work initiated by Neyshabur et al. (2015b) has focused on deriving tighter norm-based Rademacher complexity bounds for deep neural networks (Bartlett et al., 2017; Neyshabur et al., 2017a; Golowich et al., 2017) and new compression based generalization properties (Arora et al., 2018b) . Dziugaite & Roy (2017) manage to compute non-vacuous generalization bounds from PAC-Bayes bounds. Neyshabur et al. (2018) investigate the Rademacher complexity of two-layer networks and propose a bound that is decreasing with the distance to initialization. Liang & Rakhlin (2018) and Belkin et al. (2018) study the generalization of kernel methods.

On the optimization side, Soudry & Carmon (2016) explain why over-parametrization can remove bad local minima. Safran & Shamir (2016) show that over-parametrization can improve the quality of the random initialization. Haeffele & Vidal (2015) , Nguyen & Hein (2017), and Venturi et al. (2018) show that for sufficiently overparametrized networks, all local minima are global, but do not show how to find these minima via gradient descent. Du & Lee (2018) show that for two-layer networks with quadratic activations, all second-order stationary points are global minimizers. Arora et al. (2018a) interpret over-parametrization as a means of implicit acceleration during optimization. Mei et al. (2018) , Chizat & Bach (2018), and Sirignano & Spiliopoulos (2018) take a distributional view of over-parametrized networks. Chizat & Bach (2018) show that Wasserstein gradient flow converges to global optimizers under structural assumptions. We extend this to a polynomial-time result.

1.2. NOTATION:

Let R denote the set of real numbers. We will use • to indicate a general norm, with • 1 , • 2 , • ∞ denoting the 1 , 2 , ∞ norms on finite dimensional vectors, respectively, and • F denoting the Frobenius norm on a matrix. In general, we use ¯on top of a symbol to denote a unit vector: when applicable, ū u/ u , where the norm • will be clear from context. Let S d-1 {ū ∈ R d : ū 2 = 1} be the unit sphere in d dimensions. Let L p (S d-1 ) be the space of functions on S d-1 for which the p-th power of the absolute value is Lebesgue integrable. For α ∈ L p (S d-1 ), we overload notation and write α p

S d-1 |α(ū)| p dū 1/p . Additionally, for α 1 ∈ L 1 (S d-1 ) and α 2 ∈ L ∞ (S d-1 ) or α 1 , α 2 ∈ L 2 (S d-1 ), we can define α 1 , α 2 S d-1 α 1 (ū)α 2 (ū)dū < ∞.

Furthermore, we will use Vol(S d-1 ) S d-1 1dū. Throughout this paper, we reserve the symbol X = [x 1 , . . . , x n ] to denote the collection of datapoints (as a matrix), and Y = [y 1 , . . . , y n ] to denote labels. We use d to denote the dimension of our data. We often use Θ to denote the parameters of a prediction function f , and f (Θ; x) to denote the prediction of f on datapoint x. We will use the notation , to mean less than or greater than up to a universal constant, respectively. Unless stated otherwise, O(•), Ω(•) denote some universal constant in upper and lower bounds, respectively. The notation poly denotes a universal constant-degree polynomial in the arguments.

2. WEAK REGULARIZER GUARANTEES MAX MARGIN SOLUTIONS:

In this section, we will show that when we add a weak regularizer to cross-entropy loss with a positive-homogeneous prediction function, the normalized margin of the optimum converges to some max-margin solution. As a concrete example, feedforward relu networks are positive-homogeneous.

Let l be the number of labels, so the i-th example has label y i ∈ [l]. We work with a family F of prediction functions f (Θ; •) : R d → R l that are a-positive-homogeneous in their parameters for some a > 0: f (cΘ; x) = c a f (Θ; x), ∀c > 0. We additionally require that f is continuous in Θ. For some general norm • , we study the λ-regularized cross-entropy loss L λ , defined as

L λ (Θ) n i=1 -log exp(f yi (Θ; x i )) l j=1 exp(f j (Θ; x i )) + λ Θ r (2.1)

for fixed r > 0. Let Θ λ ∈ arg min L λ (Θ). 1 We define the normalized margin of Θ λ as:

γ λ min i f yi ( Θλ ; x i ) -max j =yi f j ( Θλ ; x i ) (2.2)

Define the • -max normalized margin as

γ max Θ ≤1 min i f yi (Θ; x i ) -max j =yi f j (Θ; x i )

and let Θ be a parameter achieving this maximum. We show that with sufficiently small regularization level λ, the normalized margin γ λ approaches the maximum margin γ . Our theorem and proof are inspired by the result of Rosset et al. (2004a; b) , who analyze the special case when f is a linear predictor. In contrast, our result can be applied to non-linear f as long as f is homogeneous. Theorem 2.1. Assume the training data is separable by a network f (Θ ; •) ∈ F with an optimal normalized margin γ > 0. Then, the normalized margin of the global optimum of the weaklyregularized objective (equation 2.1) converges to γ as the strength of the regularizer goes to zero. Mathematically, let γ λ be defined in equation 2.2. Then

γ λ → γ as λ → 0

An intuitive explanation for our result is as follows: because of the homogeneity, the loss L(Θ λ ) roughly satisfies the following (for small λ, and ignoring problem parameters such as n):

L λ (Θ λ ) ≈ exp(-Θ λ a γ λ ) + λ Θ λ r

Thus, the loss selects parameters with larger margin, while the regularization favors parameters with a smaller norm. The full proof of the theorem is deferred to Section A.1.

Theorem 2.1 applies to feedforward relu networks and states that global minimizers of the weaklyregularized loss will obtain a maximum margin among all networks of the given architecture. By considering global minimizers, Theorem 2.1 provides a framework for directly analyzing generalization properties of the solution without considering details of the optimization algorithm. In Section 3 we leverage this framework and existing generalization bounds (Golowich et al., 2017) to provide a clean argument that over-parameterization can improve generalization.

We can also provide an analogue of Theorem 2.1 for the binary classification setting. For this setting, our prediction is now a single real output and we train using logistic loss. We provide formal definitions and results in Section A.2. Our study of the generalization properties of the max-margin (see Section 3 and Section 4) is based in this setting.

2.1. OPTIMIZATION ACCURACY:

Since L λ is typically hard to optimize exactly for neural nets, we study how accurately we need to optimize L λ to obtain a margin that approximates γ up to a constant. The following theorem shows that it suffices to find Θ achieving a constant factor multiplicative approximation of L λ (Θ λ ), where λ is some sufficiently small polynomial in n, l, γ . Though our theorem is stated for the general multi-class setting, it also applies for binary classification. We provide the proof in Section A.3.

Theorem 2.2. In the setting of Theorem 2.1, suppose that we choose

λ = exp(-(2 r/a -1) -a/r ) (γ ) r/a n c (l -1) c

for sufficiently large c (that only depends on r/a). For β ≤ 2, let Θ denote a β-approximate minimizer of L λ , so L λ (Θ ) ≤ βL λ (Θ λ ). Denote the normalized margin of Θ by γ . Then

γ ≥ γ 10 • β a/r .

3. GENERALIZATION PROPERTIES OF A MAXIMUM MARGIN NEURAL NETWORK:

In Section 2 we showed that optimizing a weakly-regularized logistic loss leads to the maximum normalized margin. We now study the direct implications of this result on the generalization properties of the solution. Specifically, we use existing Rademacher complexity bounds of Golowich et al. (2017) to present a generalization bound that depends on the network architecture only through the inverse 2 -normalized margin and depth of the network (see Proposition 3.1). Next, we combine this bound with Theorem 2.1 to conclude that parameters obtained by optimizing logistic loss with weak 2 -regularization will have a generalization bound that scales with the inverse of the maximum possible margin and depth. Finally, we note that the maximum possible margin can only increase as the size of the network grows, which suggests that increasing the size of the network improves the generalization of the solution (see Theorem 3.3).

We consider depth-K neural networks with 1-Lipschitz, 1-positive-homogeneous activation φ for K ≥ 2. Suppose that the collection of parameters Θ is given by matrices W 1 , . . . , W K . The K-layer network will compute a real-valued score

f (Θ; x) W K φ(W K-1 φ(• • • φ(W 1 x) • • • )) (3.1)

where we overload notation to let φ(•) denote the element-wise application of the activation φ. Let m i denote the size of the i-th hidden layer, so

W 1 ∈ R m1×d , W 2 ∈ R m2×m1 , • • • , W K ∈ R 1×m K-1 .

We will let M (m 1 , . . . , m K-1 ) denote the sequence of hidden layer sizes. We will focus on 2 -regularized loss. The weakly-regularized logistic loss of the depth-K architecture with hidden layer sizes M is therefore

L λ,M (Θ) 1 n n i=1 log(1 + exp(-y i f (Θ; x i ))) + λ Θ 2 F (3.2)

We note that f is K-homogeneous in Θ, so the results of Section 2 apply to L λ,M . 2 Following our conventions from Section 2, we denote the optimizer of L λ,M by Θ λ,M , the normalized margin of Θ λ,M by γ λ,M , the max-margin solution by Θ ,M , and the max-margin by γ ,M . Our notation emphasizes the architecture of the network. Since the classifier f now predicts a single real value, we need to redefine

γ λ,M min i y i f ( Θλ,M ; x i ) γ ,M max Θ 2≤1 min i y i f (Θ; x i )

When the data is not separable by a neural network with architecture M, we define γ ,M to be zero.

Recall that X = [x 1 , . . . , x n ] denotes the matrix with all the data points as columns, and Y = [y 1 , . . . , y n ] denotes the labels. We sample X and Y i.i.d. from the data generating distribution p data , which is supported on X × {-1, +1}. We can define the population 0-1 loss and training 0-1 loss of the network parametrized by Θ by

L(Θ) = Pr (x,y)∼p data [yf (Θ; x) ≤ 0]

Let C sup x∈X x 2 be an upper bound on the norm of a single datapoint. Proposition 3.1 shows that the generalization error only depends on the parameters through the inverse of the margin on the training data. We obtain Proposition 3.1 by applying Theorem 1 of Golowich et al. (2017) with the standard technique of using margin loss to bound classification error. There exist other generalization bounds which depend on the margin and some normalization (Neyshabur et al., 2015b; 2017a; Bartlett et al., 2017; Neyshabur et al., 2018) ; we choose the bounds of Golowich et al. (2017) because they fit well with 2 normalization. In the two-layer case K = 2, the bound below also follows from Neyshabur et al. (2015b) . Proposition 3.1. [Straightforward consequence of Golowich et al. (2017, Theorem 1) ] Suppose φ is 1-Lipschitz and 1-positive-homogeneous. For any depth-K network f (Θ; •) separating the data with normalized margin γ min i y i f ( Θ; x i ) > 0, with probability at least 1 -δ over the draw of X, Y ,

L(Θ) C γK (K-1)/2 √ n + (γ) (3.3)

where (γ)

log log 2 4C γ n + log(1/δ) n

. Note that (γ) is typically small, and thus the above bound mainly scales with

C γK (K-1)/2 √ n . 3

For completeness, we state the proof in Section C.1. By combining this bound with our Theorem 2.1 we can conclude that optimizing weakly-regularized logistic loss gives us generalization error bounds that depend on the maximum possible margin of a network with the given architecture. Corollary 3.2. In the setting of Proposition 3.1, with probability 1 -δ,

lim sup λ→0 L(Θ λ,M ) C γ ,M K (K-1)/2 √ n + (γ ,M ) (3.4)

where (γ) is defined as in Proposition 3.1. Above we implicitly assume γ ,M > 0, since otherwise the right hand side of the bound is vacuous.

2 Although Theorem 2.1 is written in the language of multi-class prediction where the classifier outputs l ≥ 2 scores, the results translate to single-output binary classification. See Section A.2.

3 Although the 1 K (K-1)/2 factor of equation 3.3 decreases with depth K, the margin γ will also tend to decrease as the constraint Θ F ≤ 1 becomes more stringent.

By applying Theorem 2.2 with Proposition 3.1, we can also conclude that optimizing L λ,M within a constant factor gives a margin, and therefore generalization bound, approximating the best possible.

One consequence of Corollary 3.2 is that optimizing weakly-regularized logistic loss results in the best possible generalization bound out of all models with the given architecture. This indicates that the widely used algorithm of optimizing deep networks with 2 -regularized logistic loss has an implicit bias towards solutions with good generalization.

Next, we observe that the maximum normalized margin is non-decreasing with the size of the architecture. Formally, for two depth-K architectures M = (m 1 , . . . , m K-1 ) and M = (m 1 , . . . , m K-1 ), we say M ≤ M if m i ≤ m i ∀i = 1, . . . K -1. Theorem 3.3 states that if M ≤ M , then the max-margin over networks with architecture M is at least the max-margin over networks with architecture M. Theorem 3.3. Recall that γ ,M denotes the maximum normalized margin of a network with architecture M. If M ≤ M , we have γ ,M ≤ γ ,M . As a important consequence, the generalization error bound of Corollary 3.2 for M is at least as good as that for M. This theorem is simple to prove and follows because we can directly implement any network of architecture M using one of architecture M , if M ≤ M . This can explain why additional overparameterization has been empirically observed to improve generalization in two-layer networks (Neyshabur et al., 2017b) : the margin does not decrease with a larger network size, and therefore Corollary 3.2 gives a better generalization bound. In Section 6, we provide empirical evidence that the test error decreases with larger network size while the margin is non-decreasing.

The phenomenon in Theorem 3.3 contrasts with standard 2 -normalized linear prediction. In this setting, adding more features increases the norm of the data, and therefore the generalization error bounds could also increase. On the other hand, Theorem 3.3 shows that adding more neurons (which can be viewed as learned features) can only improve the generalization of the max-margin solution.

4. NEURAL NET MAX-MARGIN VS. KERNEL METHODS:

We will continue our study of the max-margin neural network via comparison against kernel methods, a context in which margins have already been extensively studied. We show that two-layer networks can obtain a larger margin, and therefore better generalization guarantees, than kernel methods. Our comparison between the two methods is motivated by an equivalence between the 2 max-margin of an infinite-width two-layer network and the 1 -SVM (Zhu et al., 2004) over the lifted feature space defined by the activation function applied to all possible hidden units (Neyshabur et al., 2014; Rosset et al., 2007; Bengio et al., 2006) . The kernel method corresponds to the 2 -SVM in this same feature space, and is equivalent to fixing random hidden layer weights and solving an 2 -SVM over the top layer. In Theorem 4.3, we construct a distribution for which the generalization upper bounds for the 1 -SVM on this feature space are smaller than those for the 2 -SVM by a Ω( √ d) factor. Our work provides evidence that optimizing all layers of a network can be beneficial for generalization.

There have been works that compare 1 and 2 -regularized solutions in the context of feature selection and construct a feature space for which a generalization gap exists (e.g., see Ng ( 2004)). In contrast, we work in the fixed feature space of relu activations, which makes our construction particularly challenging.

We will use m to denote the width of the single hidden layer of the network. Following the convention from Section 3, we will use γ ,m to denote the maximum possible normalized margin of a two-layer network with hidden layer size m (note the emphasis on the size of the single hidden layer). The depth K = 2 case of Corollary 3.2 immediately implies that optimizing weakly-regularized 2 loss over width-m two-layer networks gives parameters whose generalization upper bounds depend on the hidden layer size only through 1/γ ,m . Furthermore, from Theorem 3.3 it immediately follows that

γ ,1 ≤ γ ,2 ≤ • • • ≤ γ ,∞

The work of Neyshabur et al. ( 2014) links γ ,m to the 1 SVM over a lifted space. Formally, we define a lifting function ϕ : R d → L ∞ (S d-1 ) mapping data to an infinite feature vector:

x ∈ R d → ϕ(x) ∈ L ∞ (S d-1 ) satisfying ϕ(x)[ū] = φ(ū x) (4.1)

where φ is the activation of Section 3. We look at the margin of linear functionals corresponding to α ∈ L 1 (S d-1 ) . The 1-norm SVM (Zhu et al., 2004) over the lifted feature ϕ(x) solves for the maximum margin:

γ 1 max α min i∈[n] y i α, ϕ(x i ) subject to α 1 ≤ 1 (4.2)

where we rely on the inner product and 1-norm defined in Section 1.2. This formulation is equivalent to a hard-margin optimization on "convex neural networks" (Bengio et al., 2006) . Bach (2017) 

γ 1 2 = γ ,n = • • • = γ ,∞ .

For completeness, we prove Proposition 4.1 in Section B, relying on the work of Tibshirani ( 2013) and Rosset et al. (2004a) . Importantly, the 1 -max margin on the lifted feature space is obtainable by optimizing a finite neural network. We compare this to the 2 margin attainable via kernel methods. Following the setup of equation 4.2, we define the kernel problem over α ∈ L2 (S d-1 ):

γ 2 max α min i∈[n] y i α, ϕ(x i ) subject to √ κ α 2 ≤ 1 (4.3)

where κ Vol(S d-1 ). (We scale α 2 by √ κ to make the lemma statement below cleaner.) First, γ 2 can be used to obtain a standard upper bound on the generalization error of the kernel SVM. Following the notation of Section 3, we will let L 2-svm denote the 0-1 population classification error for the optimizer of equation 4.3. Lemma 4.2. In the setting of Proposition 3.1, with probability at least 1-δ, the generalization error of the standard kernel SVM with relu feature (defined in equation 4.3) is bounded by

L 2-svm C γ 2 √ dn + 2 (4.4)

where

2 log max log 2 C √ dγ 2 ,2 n + log(1/δ)

n is typically a lower-order term.

The bound above follows from standard techniques (Bartlett & Mendelson, 2002) , and we provide a full proof in Section C.2. We construct a data distribution for which this lemma does not give a good bound for kernel methods, but Corollary 3.2 does imply good generalization for two-layer networks. Theorem 4.3. There exists a data distribution p data such that the 1 SVM with relu features has a good margin: γ 1 1 and with probability 1 -δ over the choice of i.i.d. samples from p data , obtains generalization error

L 1-svm d log n n + 1 where 1 log(1/δ) n

is typically a lower order term. Meanwhile, with high probability the 2 SVM has a small margin: γ 2 max log n n , 1/d and therefore the generalization upper bound from Lemma 4.2 is at least

Ω min 1, d log n n

In particular, the 2 bound is larger than the 1 bound by a Ω( √ d) factor.

Although Theorem 4.3 compares upper bounds, our construction highlights properties of distributions which result in better neural network generalization than kernel method generalization. Furthermore, in Section 6 we empirically validate the gap in generalization between the two methods.

We briefly overview the construction of p data here. The full proof is in Section D.1.

Proof sketch for Theorem 4.3. We base p data on the distribution D of examples (x, y) described below. Here e i is the i-th standard basis vector and we use x e i to represent the i-coordinate of x (since the subscript is reserved to index training examples).

EQUATION

       y = +1, x e 1 = +1, x e 2 = +1 w/ prob. 1/4 y = +1, x e 1 = -1, x e 2 = -1 w/ prob. 1/4 y = -1, x e 1 = +1, x e 2 = -1 w/ prob. 1/4 y = -1, x e 1 = -1, x e 2 = +1 w/ prob. 1/4

Figure 1 shows samples from D when there are 3 dimensions. From the visualization, it is clear that there is no linear separator for D. As Lemma D.1 shows, a relu network with four neurons can fit this relatively complicated decision boundary. On the other hand, for kernel methods, we prove that the symmetries in D induce cancellation in feature space. As a result, the features are less predictive of the true label and the margin will therefore be small. We formalize this argument in Section D.1.

Gap in regression setting::

We are able to prove an even larger Ω( n/d) gap between neural networks and kernel methods in the regression setting where we wish to interpolate continuous labels. Analogously to the classification setting, optimizing a regularized squared error loss on neural networks is equivalent to solving a minimum 1-norm regression problem (see Theorem D.5). Furthermore, kernel methods correspond to a minimum 2-norm problem. We construct distributions p data where the 1-norm solution will have a generalization error bound of O( d/n), whereas the 2norm solution will have a generalization error bound that is Ω(1) and thus vacuous. In Section D.2, we define the 1-norm and 2-norm regression problems. In Theorem D.10 we formalize our construction.

5. PERTURBED WASSERSTEIN GRADIENT FLOW FINDS GLOBAL OPTIMIZERS IN POLYNOMIAL TIME:

In the prior section, we studied the limiting behavior of the generalization of a two-layer network as its width goes to infinity. In this section, we will now study the limiting behavior of the optimization algorithm, gradient descent. Prior work (Mei et al., 2018; Chizat & Bach, 2018) has shown that as the hidden layer size grows to infinity, gradient descent for a finite neural network approaches the Wasserstein gradient flow over distributions of hidden units (defined in equation 5.1). Chizat & Bach (2018) assume the gradient flow converges, a non-trivial assumption since the space of distributions is infinite-dimensional, and given the assumption prove that Wasserstein gradient flow converges to a global optimizer in this setting, but do not specify a convergence rate. Mei et al. (2018) show global convergence for the infinite-neuron limit of stochastic Langevin dynamics, but also do not provide a convergence rate.

We show that a perturbed version of Wasserstein gradient flow converges in polynomial time. The informal take-away of this section is that a perturbed version of gradient descent converges in polynomial time on infinite-size neural networks (for the right notion of infinite-size.)

Formally, we optimize the following functional over distributions ρ on R d+1 :

L[ρ] R Φdρ + V dρ

where Φ : R d+1 → R k , R : R k → R, and V : R d+1 → R. In this work, we consider 2-homogeneous Φ and V . We will additionally require that R is convex and nonnegative and V is positive on the unit sphere. Finally, we need standard regularity assumptions on R, Φ, and V : Assumption 5.1 (Regularity conditions on Φ, R, V ). Φ and V are differentiable as well as upper bounded and Lipschitz on the unit sphere. R is Lipschitz and its Hessian has bounded operator norm.

We provide more details on the specific parameters (for boundedness, Lipschitzness, etc.) in Section E.1. We note that relu networks satisfy every condition but differentiability of Φ. 5 We can fit a neural network under our framework as follows:

Example 5.2 (Logistic loss for neural networks). We interpret ρ as a distribution over the parameters of the network. Let k n and Φ i (θ) wφ(u x i ) for θ = (w, u). In this case, Φdρ is a distributional neural network that computes an output for each of the n training examples (like a standard neural network, it also computes a weighted sum over hidden units). We can compute the distributional version of the regularized logistic loss in equation 3.2 by setting V (θ) λ θ 2 2 and R(a 1 , . . . , a n )

n i=1 log(1 + exp(-y i a i )). We will define L [ρ] : R d+1 → R with L [ρ](θ) R ( Φdρ), Φ(θ) + V (θ) and v[ρ](θ) -∇ θ L [ρ](θ). Informally, L [ρ]

is the gradient of L with respect to ρ, and v is the induced velocity field. For the standard Wasserstein gradient flow dynamics, ρ t evolves according to

d dt ρ t = -∇ • (v[ρ t ]ρ t ) (5.1)

where ∇• denotes the divergence of a vector field. For neural networks, these dynamics formally define continuous-time gradient descent when the hidden layer has infinite size (see Theorem 2.6 of Chizat & Bach (2018) , for instance).

We propose the following modification of the Wasserstein gradient flow dynamics:

d dt ρ t = -σρ t + σU d -∇ • (v[ρ t ]ρ t ) (5.2)

where U d is the uniform distribution on S d . In our perturbed dynamics, we add very small uniform noise over U d , which ensures that at all time-steps, there is sufficient mass in a descent direction for the algorithm to decrease the objective. For infinite-size neural networks, one can informally interpret this as re-initializing a very small fraction of the neurons at every step of gradient descent. We prove convergence to a global optimizer in time polynomial in 1/ , d, and the regularity parameters. Theorem 5.3 (Theorem E.4 with regularity parameters omitted). Suppose that Φ and V are 2homogeneous and the regularity conditions of Assumption 5.1 are satisfied. Also assume that from starting distribution ρ 0 , a solution to the dynamics in equation 5.2 exists. Define L inf ρ L[ρ]. Let > 0 be a desired error threshold and choose σ exp(-d log(1/ )poly(k, L[ρ 0 ] -L )) and t

d 2 4 poly(log(1/ ), k, L[ρ 0 ] -L ),

where the regularity parameters for Φ, V , and R are hidden in the poly(•). Then, perturbed Wasserstein gradient flow converges to an -approximate global minimum in t time:

min 0≤t≤t L[ρ t ] -L ≤ .

We provide a theorem statement that includes regularity parameters in Section E.1. We prove the theorem in Section E.2.

As a technical detail, Theorem 5.3 requires that a solution to the dynamics exists. We can remove this assumption by analyzing a discrete-time version of equation 5.2:

ρ t+1 ρ t + η(-σρ t + σU d -∇ • (v[ρ t ]ρ t )

) and additionally assuming Φ and V have Lipschitz gradients. In this setting, a polynomial time convergence result also holds. We state the result in Section E.3.

An implication of our Theorem 5.3 is that for infinite networks, we can optimize the weaklyregularized logistic loss in time polynomial in the problem parameters and λ -1 . By Theorem 2.2, we only require λ -1 = poly(n) to approximate the maximum margin within a constant factor. Thus, for infinite networks, we can approximate the max margin within a constant factor in polynomial time. 

6. SIMULATIONS:

We first compare the generalization of neural networks and kernel methods for classification and regression. In Figure 2 we plot the generalization error and predicted generalization upper bounds6 of a trained neural network against a 2 kernel method with relu features as we vary n. Our data comes from a synthetic distribution generated by a neural network with 6 hidden units; we provide a detailed setup in Section F.1. For classification we plot 0-1 error, whereas for regression we plot squared error. The variance in the neural network generalization bound for classification likely occured because we did not tune learning rate and training time, so the optimization failed to find the best margin. The plots show that two-layer networks clearly outperform kernel methods in test error as n grows. However, there seems to be looseness in the bounds: the kernel generalization bound appears to stay constant with n (as predicted by our theory for regression), but the test error decreases.

We also plot the dependence of the test error and margin on the hidden layer size in Figure 3 for synthetic data generated from a ground truth network with 10 hidden units and also MNIST. The plots indicate that test error is decreasing in hidden layer size while margin is increasing, as Theorem 3.3 predicts. We provide more details on the experimental setup in Section F.2.

In Section F.3, we verify the convergence of a simple neural network to the max-margin solution as regularization decreases. In Section F.4, we train modified WideResNet architectures on CIFAR10 and CIFAR100. Although ResNet is not homogeneous, we still report improvements in generalization from annealing the weight decay during training, versus staying at a fixed decay rate.

7. CONCLUSION:

We have made the case that maximizing margin is one of the inductive biases of relu networks obtained from optimizing weakly-regularized cross-entropy loss. Our framework allows us to directly analyze generalization properties of the network without considering the optimization algorithm used to obtain it. Using this perspective, we provide a simple explanation for why over-parametrization can improve generalization. It is a fascinating question for future work to characterize other generalization properties of the max-margin solution. On the optimization side, we make progress towards understanding over-parametrized gradient descent by analyzing infinite-size neural networks. A natural direction for future work is to apply our theory to optimize the margin of finite-sized neural networks.

A MISSING PROOFS IN SECTION 2:

We first show that L λ does indeed have a global minimizer. Claim A.1. In the setting of Theorems 2.1 and A.3, arg min Θ L λ (Θ) exists.

Proof. We will argue in the setting of Theorem 2.1 where L λ is the multi-class cross entropy loss, because the logistic loss case is analogous. We first note that L λ is continuous in Θ because f is continuous in Θ and the term inside the logarithm is always positive. Next, define b inf Θ L λ (Θ) > 0. Then we note that for Θ > (b/λ) 1/r M , we must have L λ (Θ) > b. It follows that inf Θ ≤M L λ (Θ) = inf Θ L λ (Θ). However, there must be a value Θ λ which attains inf Θ ≤M L λ (Θ), because {Θ : Θ ≤ M } is a compact set and L λ is continuous. Thus, inf Θ L λ (Θ) is attained by some Θ λ .

A.1 MISSING PROOFS FOR MULTI-CLASS SETTING:

Towards proving Theorem 2.1, we first show as we decrease λ, the norm of the solution Θ λ grows. Lemma A.2. In the setting of Theorem 2.1, as λ → 0, we have Θ λ → ∞.

To prove Theorem 2.1, we rely on the exponential scaling of the cross entropy: L λ can be lower bounded roughly by exp(-Θ λ γ λ ), but also has an upper bound that scales with exp(-Θ λ γ ). By Lemma A.2, we can take large Θ λ so the gap γ -γ λ vanishes. This proof technique is inspired by that of Rosset et al. (2004a) .

Proof of Theorem 2.1. For any M > 0 and Θ with γ Θ min i f ( Θ;

x i ) -max j =yi f ( Θ; x i ) , L λ (M Θ) = 1 n n i=1 -log exp(M a f yi (Θ; x i )) l j=1 exp(M a f j (Θ; x i )) + λM r Θ r (by the homogeneity of f ) = 1 n n i=1 -log 1 1 + j =yi exp(M a (f j (Θ; x i ) -f yi (Θ; x i ))) + λM r Θ r (A.1) ≤ log(1 + (l -1) exp(-M a γ Θ )) + λM r Θ r (A.2)

We can also apply

j =yi exp(M a (f j (Θ; x i ) -f yi (Θ; x i ))) ≥ max exp(M a (f j (Θ; x i ) - f yi (Θ; x i ))) = exp γ Θ in order to lower bound equation A.1 and obtain L λ (M Θ) ≥ 1 n log(1 + exp(-M a γ Θ )) + λM r Θ r (A.3)

Applying equation A.2 with M = Θ λ and Θ = Θ , noting that Θ ≤ 1, we have:

L λ (Θ Θ λ ) ≤ log(1 + (l -1) exp(-Θ λ a γ )) + λ Θ λ r (A.4)

Next we lower bound L λ (Θ λ ) by applying equation A.3,

L λ (Θ λ ) ≥ 1 n log(1 + exp(-Θ λ a γ λ )) + λ Θ λ r (A.5)

Combining equation A.4 and equation A.5 with the fact that L λ (Θ λ ) ≤ L λ (Θ Θ λ ) (by the global optimality of Θ λ ), we have

∀λ > 0, n log(1 + (l -1) exp(-Θ λ a γ )) ≥ log(1 + exp(-Θ λ a γ λ ))

Recall that by Lemma A.2, as λ → 0, we have Θ λ → ∞.

Therefore, exp(-Θ λ a γ ), exp(-Θ λ a γ λ ) → 0. Thus, we can apply Taylor expansion to the equation above with respect to exp(-Θ λ a γ ) and exp(-Θ λ a γ λ ).

If max{exp(-Θ λ a γ ), exp(-Θ λ a γ λ )} < 1, then we obtain n(l -1) exp(-Θ λ a γ ) ≥ exp(-Θ λ a γ λ ) -O(max{exp(-Θ λ a γ ) 2 , exp(-Θ λ a γ λ ) 2 })

We claim this implies that γ ≤ lim inf λ→0 γ λ . If not, we have lim inf λ→0 γ λ < γ , which implies that the equation above is violated with sufficiently large Θ λ ( Θ λ log(2( -1)n) 1/a would suffice). By Lemma A.2, Θ λ → ∞ as λ → 0 and therefore we get a contradiction.

Finally, we have γ λ ≤ γ by definition of γ . Hence, lim λ→0 γ λ exists and equals γ . Now we fill in the proof of Lemma A.2.

Proof of Lemma A.2. For the sake of contradiction, we assume that ∃C > 0 such that for any λ 0 > 0, there exists 0 < λ < λ 0 with Θ λ ≤ C. We will determine the choice of λ 0 later and pick λ such that Θ λ ≤ C. Then the logits (the prediction f j (Θ, x i ) before softmax) are bounded in absolute value by some constant (that depends on C), and therefore the loss function -log exp(fy i (Θ;xi)) l j=1 exp(fj (Θ;xi)) for every example is bounded from below by some constant D > 0 (depending on C but not λ.)

Let M = λ -1/(r+1) , we have that

0 < D ≤ L λ (Θ λ ) ≤ L λ (M Θ )

(by the optimality of Θ λ )

≤ -log 1 1 + (l -1) exp(-M a γ ) + λM r (by equation A.2) = log(1 + (l -1) exp(-λ -a/(r+1) γ )) + λ 1/(r+1) ≤ log(1 + (l -1) exp(-λ -a/(r+1) 0 γ )) + λ 1/(r+1) 0

Taking a sufficiently small λ 0 , we obtain a contradiction and complete the proof.

A.2 FULL BINARY CLASSIFICATION SETTING:

For completeness, we state and prove our max-margin results for the setting where we fit binary labels y i ∈ {-1, +1} (as opposed to indices in [l]) and redefining f (Θ; •) to assign a single real-valued score (as opposed to a score for each label). This lets us work with the simpler λ-regularized logistic loss:

L λ (Θ) 1 n n i=1 log(1 + exp(-y i f (Θ; x i ))) + λ Θ r

As before, let Θ λ ∈ arg min L λ (Θ), and define the normalized margin γ λ by γ λ min i y i f ( Θλ ; x i ).

Define the maximum possible normalized margin

γ max Θ ≤1 min i y i f (Θ; x i ) (A.6)

Theorem A.3. Assume γ > 0 in the binary classification setting with logistic loss. Then as λ → 0, γ λ → γ .

The proof follows via simple reduction to the multi-class case.

Proof of Theorem A.3. We prove this theorem via reduction to the multi-class case with l = 2. Construct f : R d → R 2 with f1 (Θ; x i ) = -1 2 f (Θ; x i ) and f2 (Θ; x i ) = 1 2 f (Θ; x i ). Define new labels ỹi = 1 if y i = -1 and ỹi = 2 if y i = 1. Now note that f ỹi (Θ; x i )-fj = ỹi (Θ; x i ) = y i f (Θ; x i ), so the multi-class margin for Θ under f is the same as binary margin for Θ under f . Furthermore, defining

Lλ (Θ) 1 n n i=1 -log exp( f ỹi (Θ; x i )) 2 j=1 exp( fj (Θ; x i )) + λ Θ r

we get that Lλ (Θ) = L λ (Θ), and in particular, Lλ and L λ have the same set of minimizers. Therefore we can apply Theorem 2.1 for the multi-class setting and conclude γ λ → γ in the binary classification setting.

A.3 MISSING PROOF FOR OPTIMIZATION ACCURACY:

Proof of Theorem 2.2. Choose B

1 γ log (l-1)(γ ) r/a λ 1/a

. We can upper bound L λ (Θ ) by computing

L λ (Θ ) ≤ βLλ(Θ λ ) ≤ βL λ (BΘ ) ≤ β log(1 + (l -1) exp(-B a γ )) + βλB r (by equation A.2) ≤ β(l -1) exp(-B a γ ) + βλB r (using log(1 + x) ≤ x) ≤ β λ (γ ) r/a + βλ 1 γ log (l -1)(γ ) r/a λ r/a ≤ β λ (γ ) r/a 1 + log (l -1)(γ ) r/a λ r/a L (U B)

Furthermore, it holds that Θ r ≤ L (U B) λ . Now we note that

L λ (Θ ) ≤ L (U B) ≤ 2β λ (γ ) r/a log (l -1)(γ ) r/a λ r/a ≤ 1 2n

for sufficiently large c depending only on a/r. Now using the fact that log(x) ≥ x 1+x ∀x ≥ -1, we additionally have the lower bound

L λ (Θ ) ≥ 1 n log(1 + exp(-γ Θ a )) ≥ 1 n exp(-γ Θ a ) 1+exp(-γ Θ a ) . Since L (U B) ≤ 1, we can rearrange to get γ ≥ -log nL λ (Θ ) 1-nL λ (Θ ) Θ a ≥ -log nL (U B) 1-nL (U B) Θ a ≥ -log(2nL (U B) ) Θ a

The middle inequality followed because x 1-x is increasing in x for 0 ≤ x < 1, and the last because

L (U B) ≤ 1 2n . Since -log 2nL (U B) > 0 we can also apply the bound Θ r ≤ L (U B) λ to get γ ≥ -λ a/r log 2nL (U B) (L (U B) ) a/r = -log 2nβ λ (γ ) r/a 1 + log (l-1)(γ ) r/a λ r/a β a/r γ 1 + log (l-1)(γ ) r/a λ r/a a/r (by definition of L (U B) ) ≥ γ β a/r           log( (γ ) r/a 2βnλ ) 1 + log (l-1)(γ ) r/a λ r/a a/r ♣ - log 1 + log (l-1)(γ ) r/a λ r/a 1 + log (l-1)(γ ) r/a λ r/a a/r ♥          

We will first bound ♣. First note that

log( (γ ) r/a 2βnλ ) log (l-1)(γ ) r/a λ = log (γ ) r/a λ -log 2βn log (γ ) r/a λ + log(l -1) ≥ log (γ ) r/a λ -log 2βn(l -1) log (γ ) r/a λ ≥ c -3 c (A.7)

where the last inequality follows from the fact that (γ ) r/a λ ≥ n c (l -1) c and β ≤ 2. Next, using the fact that log (γ ) r/a λ ≥ 1

(2 r/a -1) a/r , we note that

1 + log (l -1)(γ ) r/a λ -r/a a/r ≤ 1 + 1 (2 r/a -1) a/r -r/a a/r ≤ 2 (A.8)

Combining equation A.7 and equation A.8, we can conclude that

EQUATION

Finally, we note that if 1 + log (l-1)(γ ) r/a λ r/a is a sufficiently large constant that depends only on a/r (which can be achieved by choosing c sufficiently large), it will follow that ♥ ≤ 1 10 . Thus, if c ≥ 5, we can combine our bounds on ♣ and ♥ to get that γ ≥ γ 10β a/r B MISSING PROOF OF PROPOSITION 4.1 Proposition 4.1 follows simply from applying Corollary 1 of Neyshabur et al. ( 2014) to a hard-margin SVM problem. For completeness, we provide another proof here. The proof of Proposition 4.1 will consist of two steps: first, show that equation 4.2 has an optimal solution with sparsity n, and second, show that sparse solutions to equation 4.2 can be mapped to a neural network with the same margin, and vice versa. The following lemma and proof are based on Lemma 14 of Tibshirani (2013). For the proof of this lemma, we find it convenient to work with a minimum norm formulation which we show is equivalent to equation 4.2: Proof. Let opt denote the optimal objective for equation B.1. We note that α α 1 is feasible for equation 4.2 with objective 1 opt , and therefore γ 1 ≥ 1 opt . Furthermore,

min α α 1 subject to y i α, ϕ(x i ) ≥ 1 ∀i (B.1) Claim B.2. Let S ⊂ L 1 (S d-1 )

1 2γ 1 y i ū∈S d-1 α(ū)φ(ū x i )dū ≥ 1 ∀i, and so α γ 1 is feasible for equation B.1 with objective 1 γ 1 . Therefore, opt ≤ 1 γ 1 . As a result, it must hold that opt = 1 γ 1

, which means that α α 1 is optimal for equation 4. 

max λ∈R n λ 1 subject to n i=1 λ i y i φ(ū x i ) ≤ 1 ∀ū ∈ S d-1 λ i ≥ 0

For any primal optimal solution α and dual optimal solution λ , it must hold that

n i=1 λ i y i φ(ū x i ) = sign(α (ū)) ⇐⇒ α (ū) = 0 (B.2)

Proof. The dual form can be solved for by computation. By strong duality, equation B.2 must follow from the KKT conditions. Now define the mapping v : S d-1 → R n with v i (ū) y i φ(ū x i ). We will show a general result about linearly dependent v(ū) for ū ∈ supp(α ), after which we can reduce directly to the proof of Tibshirani (2013). Claim B.4. Let α be any optimal solution. Suppose that there exists S ⊆ supp(α ) such that {v(ū) : ū ∈ S} forms a linearly dependent set, i.e. Proof. Let λ be any dual optimal solution, then λ v(ū) = sign(α (ū)) ∀ū ∈ supp(α ) by Claim B.3. Thus, we apply λ to both sides of equation B.3 to get the desired statement.

Proof of Lemma B.1. The rest of the proof follows Lemma 14 in Tibshirani ( 2013). The lemma argues that if the conclusion of Claim B.4 holds and an optimal solution α has S ⊆ supp(α ) with {v(ū) : ū ∈ S} linearly dependent, we can construct a new α with α 1 = α 1 and supp(α ) ⊂ supp(α ) (where the inclusion is strict). Thus, if we consider an optimal α with minimal support, it must follow that {v(ū) : ū ∈ supp(α )} is a linearly independent set, and therefore |supp(α )| ≤ n.

We can now complete the proof of Proposition 4.1.

Proof of Proposition 4.1. For ease of notation, we will parametrize a two-layer network with m units by top layer weights w 1 , . . . , w m ∈ R and bottom layer weights u 1 , . . . , u m ∈ R d . As before, we use Θ to refer to the collection of parameters, so the network computes the real-valued function

f (Θ; x) = m j=1 w j φ(u j x)

Note that we simply renamed the variables from the parametrization of equation 3.1.

We first apply Lemma B.1 to conclude that equation 4.2 admits a n-sparse optimal solution α .

Because of sparsity, we can now abuse notation and treat α as a real-valued function such that ū∈supp(α ) |α (ū)| ≤ 1. We construct Θ corresponding to a two-layer network with m ≥ n hidden units and normalized margin at least γ 1 2 . For clarity, we let W correspond to the top layer weights and U correspond to the bottom layer weights. For every ū ∈ supp(α), we let Θ have a corresponding hidden unit j with (w j , u

j ) = sign(α (ū)) |α (ū)| 2 , |α (ū)| 2

ū , and set the remaining hidden units to 0. This is possible because m ≥ n. Now

f (Θ; x) = m j=1 w j φ(u j x) = 1 2 ū∈supp(α ) α (ū)φ(ū x) Furthermore, Θ 2 2 = m j=1 w 2 j + u j 2 2 = ū∈supp(α) |α (ū)| 2 + |α (ū)| 2 ū 2 2 = ū∈supp(α) |α (ū)| ≤ 1

Thus it follows that Θ has normalized margin at least γ 1 /2, so γ ,m ≥ γ 1 /2.

To conclude, we show that γ ,m ≤ γ 1 /2. Let Θ ,m denote the parameters obtaining optimal m-unit margin γ ,m with hidden units (w ,m j , u ,m j

) for j ∈ [m]. We can construct α to put a scaled delta mass of 2w ,m j u ,m j 2 on ū ,m j for j ∈ [m]. It follows that α 1 = m j=1 2|w ,m j | u ,m j 2 ≤ m j=1 w ,m j 2 + u ,m j 2 2 = Θ ,m 2 2 ≤ 1 Furthermore, S d-1 α(ū)φ(ū x) = 2 m j=1 w ,m j u ,m j 2 φ((ū ,m j ) x) = 2 m j=1 w ,m j φ(u ,m j x) = 2f (Θ ,m ; x)

Thus, α is a feasible solution to equation 4.2 with objective value at least 2γ ,m . Therefore, γ 1 ≥ 2γ ,m , so γ ,m = γ 1 /2.

C RADEMACHER COMPLEXITY AND GENERALIZATION ERROR:

We prove the generalization error bounds stated in Proposition 3.1 and Lemma 4.2 via Rademacher complexity and margin theory.

Assume that our data X, Y are drawn i.i.d. from ground truth distribution p data supported on X × Y.

For some hypothesis class F of real-valued functions, we define the empirical Rademacher complexity R(F) as follows:

R(F) 1 n E i sup f ∈F n i=1 i f (x i )

where i are independent Rademacher random variables.

For a classifier f , following the notation of Section 3 we will use L(f ) Pr (x,y)∼p data (yf (x) ≤ 0) to denote the population 0-1 loss of the classifier f . The following classical theorem (Koltchinskii et al., 2002) , (Kakade et al., 2009) bounds generalization error in terms of the Rademacher complexity and margin loss.

Theorem C.1 (Theorem 2 of Kakade et al. ( 2009)). Let (x i , y i ) n i=1 be drawn iid from p data . We work in the binary classification setting, so Y = {-1, 1}. Assume that for all f ∈ F, we have sup x∈X f (x) ≤ C. Then with probability at least 1 -δ over the random draws of the data, for every γ > 0 and f ∈ F,

L(f ) ≤ 1 n n i=1 1(y i f (x i ) < γ) + 4 R(F) γ + log log 2 4C γ n + log(1/δ) 2n

C.1 PROOF OF PROPOSITION 3.1

We will prove Proposition 3.1 by applying the Rademacher complexity bounds of Golowich et al. (2017) with Theorem C.1.

First, we show the following lemma bounding the generalization of neural networks whose weight matrices have bounded Frobenius norms. Lemma C.2. Define the hypothesis class F K over depth-K neural networks by

F K = f (Θ; •) : W j F ≤ 1 √ K ∀j Let C sup x∈X x 2 .

Recall that L(Θ) denotes the 0-1 population loss L(f (Θ; •)). Then for any f (Θ; •) ∈ F K classifying the training data correctly with unnormalized margin γ Θ min i y i f (Θ; x i ) > 0, with probability at least 1 -δ,

L(Θ) C γ Θ K (K-1)/2 √ n + log log 2 4C γΘ n + log(1/δ) n (C.1)

Note the dependence on the unnormalized margin rather than the normalized margin.

Proof. We first claim that sup f (Θ;

•)∈F K sup x∈X f (Θ; x) ≤ C. To see this, for any f (Θ; •) ∈ F K , f (Θ; x) = W K φ(• • • φ(W 1 x) • • • ) ≤ W K F φ(W K-1 φ(• • • φ(W 1 x) • • • ) 2 ≤ W K F W K-1 φ(• • • φ(W 1 x) • • • ) 2 (since φ is 1-Lipschitz and φ(0) = 0, so φ performs a contraction) < x 2 ≤ C

(repeatedly applying this argument and using W j F < 1) Furthermore, by Theorem 1 of Golowich et al. (2017) , R(F K ) has upper bound

R(F K ) C K (K-1)/2 √ n

Thus, we can apply Theorem C.1 to conclude that for all f (Θ; •) ∈ F K and all γ > 0, with probability

1 -δ, L(Θ) 1 n n i=1 1(y i f (Θ; x i ) < γ) + C γK (K-1)/2 √ n + log log 2 4C γ n + log(1/δ) n

In particular, by definition choosing γ = γ Θ makes the first term on the LHS vanish and gives the statement of the lemma.

Proof of Proposition 3.1. Given parameters Θ = (W 1 , . . . , W K ), we first construct parameters Θ = ( W1 , . . . , WK ) such that f ( Θ; •) and f ( Θ; •) compute the same function, and

W1 2 F = W2 2 F = • • • = WK 2 F ≤ 1 K .

To do this, we set

Wj = ( K k=1 W k F ) 1/k W j F Θ F W j By construction Wj 2 F = ( K k=1 W k 2 F ) 1/k Θ 2 F = ( K k=1 W k 2 F ) 1/k K k=1 W k 2 F ≤ 1 k (by the AM-GM inequality)

Furthermore, we also have

f ( Θ; x) = WK φ(• • • φ( W1 x) • • • ) = K j=1 ( K k=1 W k F ) 1/k W j F Θ F W K φ(• • • φ(W 1 x) • • • ) (by the homogeneity of φ) = 1 Θ K F f (Θ; x) = f Θ Θ F ; x (since f is K-homogeneous in Θ) = f ( Θ; x)

Now we note that by construction, L(Θ) = L( Θ). Now f ( Θ; •) must also classify the training data perfectly, has unnormalized margin γ, and furthermore f ( Θ; •) ∈ F K . As a result, Lemma C.2 allows us to conclude the desired statement.

To conclude Corollary 3.2, we apply the above on Θ λ,M and use Theorem A.3.

C.2 PROOF OF KERNEL GENERALIZATION BOUNDS:

Let F 2,φ B denote the class of 2 -bounded linear functionals in lifted feature space:

F 2,φ B {x → α, ϕ(x) : α ∈ L 2 (S d-1

), α 2 ≤ B}. We abuse notation and write α ∈ F 2,φ B to indicate a linear functional from F 2,φ B . As before, we will use L(α) to indicate the 0-1 population loss of the classifier x → α, ϕ(x) and let C sup x∈X x 2 be an upper bound on the norm of the data. We focus on analyzing the Rademacher complexity R(F 2,φ B ), mirroring derivations done in the past (Bartlett & Mendelson, 2002) . We include our derivations here for completeness.

Lemma C.3. R(F 2,φ B ) ≤ 1 n B n i=1 ϕ(x i ) 2 2 .

Proof. We write

R(F 2,φ B ) = 1 n E i sup α∈F 2,φ B α, n i=1 i ϕ(x i ) ≤ 1 n E i sup α∈F 2,φ B α 2 n i=1 i ϕ(x i ) 2 ≤ 1 n B • E i n i=1 i ϕ(x i ) 2 ≤ 1 n B E i   n i=1 i ϕ(x i ) 2 2   (via Jensen's inequality) ≤ 1 n B E i   n i=1 n j=1 i j ϕ(x i ), ϕ(x i )   ≤ 1 n B n i=1 ϕ(x i ) 2 2

(terms where i = j cancel out)

As an example, we can apply this bound to relu features:

Corollary C.4. Suppose that φ is the relu activation. Let κ Vol(S d-1 ). Then R(F 2,φ B ) B X F √ κ n √ d ≤ BC √ κ √ dn . Proof. We first show that ϕ(x i ) 2 2 = Θ κ d x i 2 2 . We can compute ϕ(x i ) 2 2 = Vol(S d-1 )E ū∼S d-1 [relu(ū x i ) 2 ] = κ d E ū∼S d-1 [relu( √ dū x i ) 2 ] = κ d 1 M 2 E u∼N (0,I d×d ) [relu(u T x i ) 2 ] (M 2 is the second moment of N (0, 1)) = Θ κ d x i 2 2 (C.2)

where the last line uses the computation provided in Lemma A.1 by Du et al. (2017) . Now we plug this into Lemma C.3 to get the desired bound.

We will now prove Lemma 4.2. 

to get with probability 1 -δ, L 2 -svm = L( √ κα 2 ) ≤ 4 R(F 2,φ 1 ) √ κγ 2 + log log 2 n + log(1/δ) 2n C γ 2 √ dn + log max log 2 C √ dγ 2 , 2 n + log(1/δ) n (applying Corollary C.4)

By bullet 3 and equation above, we complete the proof with triangle inequality:

n i=1 W i 2 ≤ E n i=1 W i 2 + nκ log 2 n nκ log 2 n + √ κn/d

Therefore, it suffices to prove bullets 1, 2 and 3. Note that 2 is a direct corollary of 1 so we will only prove 1 and 3. We start with 3:

By the definition of the 2 norm in L 2 (S d-1 ) and the independence of (x i , y i )'s, we can rewrite

E n i=1 W i 2 2 = κ • n 2 E ū∼S d-1 E (x,y)∼D ϕ(x)[ū] • y 2 (D.1) Let ū = (ū 1 , . . . , ūd ) and ū-2 = (ū 3 , . . . , ūd ) ∈ R d-2 , and define τ ū-2 2 . Let x -2 = (x e 3 , . . . , x e d ). Note that ϕ(x)[ū]y = y[ū 1 • x e 1 + ū2 • x e 2 + ū -2 x -2 ] and ū -2 x -2 has distribution ū-2 2 • N (0, 1) = τ • N (0, 1). Let z = ū -2 x -2 /τ ,

and therefore z has standard normal distribution. With this change of the variables, by the definition of the distribution D, we have

E (x,y)∼D ϕ(x)[ū] • y = 1 4 E z∼N (0,1) [(ū 1 + ū2 + τ z) + ] + 1 4 E z∼N (0,1) [(-ū 1 -ū2 + τ z) + ] - 1 4 E z∼N (0,1) [(ū 1 -ū2 + τ z) + ] - 1 4 E z∼N (0,1) [(+ū 1 -ū2 + τ z) + ]

By claim D.4, and the 1-homogeneity of relu, we can simplify the above equation to

E (x,y)∼D ϕ(x)[ū] • y = 1 4 τ • 2c 1 + O(min{|ū 1 + ū2 |/τ, |ū 1 + ū2 | 2 /τ 2 }) - τ 4 2c 1 -O(min{|ū 1 -ū2 |/τ, |ū 1 -ū2 | 2 /τ 2 }) min{|ū 1 | + |ū 2 |, (|ū 1 | + |ū 2 |) 2 /τ } It follows that E ū∼S d-1 E (x,y)∼D ϕ(x)[ū] • y 2 E ū min{(|ū 1 | + |ū 2 |) 2 , (|ū 1 | + |ū 2 |) 4 / ū-2 2 2 } E ū (|ū 1 | + |ū 2 |) 2 • 1[ ū-2 2 ≤ 1/2] + E ū (|ū 1 | + |ū 2 |) 4 / ū-2 2 2 • 1[ ū-2 2 ≥ 1/2] exp(- √ d) + E ū (|ū 1 | + |ū 2 |) 4 1/d 2 (D.

2) Combining equation D.1 and equation D.2 we complete the proof of bullet 3. Next we prove bullet 1. Note that ϕ(x)[ū]y is bounded by

|ū 1 | + |ū 2 | + ū -2 x -2 2 . Therefore, conditioned on x i 2 d log n W i 2 2 ≤ E ū∼S d-1 (|ū 1 | + |ū 2 | + ū -2 x -2 2 ) 2 E ū∼S d-1 |ū 1 | 2 + E ū∼S d-1 |ū 2 | 2 + E ū∼S d-1 ū -2 x -2 2 2 1/d + x -2 2 2 /d log n

Hence we complete the proof.

Claim D.4. Let Z ∼ N (0, 1) and a ∈ R. Then, there exists a universal constant c 1 and c 2 such that

|E [(a + Z) + + (-a + Z) + ] -2c 1 | ≤ c 2 min{|a|, a 2 }.

Proof. Without loss of generality we can assume a ≥ 0. Then,

E [(a + Z) + + (-a + Z) + ] = E [(a + Z)1[Z ≥ -a]] + E [(Z -a)1[Z ≥ a]] = E [a • 1[Z ≥ -a]] + E [Z • 1[Z ≥ -a]] -E [a • 1[Z ≥ a]] + E [Z • 1[Z ≥ a]] = E [a1[-a ≤ Z ≤ a]] + 2 E [Z • 1[Z ≥ a]]

(by

E [Z • 1[-a ≤ Z ≤ a]] = 0) = E [a1[-a ≤ Z ≤ a]] + 2 E [Z • 1[Z ≥ 0]] -2 E [Z • 1[a ≥ Z ≥ 0]] = 2c 1 + O(min{a, a 2 })

where the last equality uses the fact that c

1 E [Z • 1[Z ≥ 0]] and E [a1[-a ≤ Z ≤ a]] ≤ aE [1[-a ≤ Z ≤ a]] a min{1, a}.

Now we will prove Theorem 4.3.:

Proof of Theorem 4.3. To circumvent the technical issue of bounded support in Proposition 3.1 and Lemma 4.2, we construct p data to be a slightly modified version of D: perform rejection sampling of (x, y) ∼ D until we obtain a sample with x 2 2 d log n. Since this occurs with very high probability, the high probability result of Lemma D.3 still translates to p data . Now apply Lemma D.2 to conclude that γ 2 log n √ n + 1 d . Furthermore, Lemma D.1 allows us to conclude that γ 1 1. We can therefore apply Proposition 3.1, and conclude that with probability 1 -δ,

L 1-svm d log n n + log log(d log n) n + log(1/δ) n Furthermore, plugging γ 2 into the bound of Lemma 4.2 gives us min 1, d log n n + log log(dn) n + log(1/δ) n D.2 REGRESSION

We will first define the 1-norm and 2-norm regression problems. The regression equivalent of equation 4.2 for α ∈ L 1 (S d-1 ) is as follows: where α ∈ L 2 (S d-1 ).

α 1 ∈ arg min

We will briefly motivate our study of the regression setting by connecting the minimum 1-norm solution to neural networks. To compare, in the classification setting, optimizing the weakly regularized loss over neural networks is equivalent to solving the 1 SVM. In the regression setting, solving the weakly regularized squared error loss is equivalent is equivalent to finding the minimum 1-norm solution that fits the datapoints exactly. Theorem D.5. Let f (Θ; •) be some two-layer neural network with m ≥ n hidden units parametrized by Θ, as in Section 4. Define the λ-regularized squared error loss Θ) . Suppose that equation D.3 is feasible with optimal solution α 1 . Then as λ → 0, L λ,m (Θ λ,m ) → 0 and Θ λ,m 2 2 → 2 α 1 1 .

EQUATION

Proof. We can see that equation D.3 will have a n-sparse solution α using the same reasoning as the proof of Lemma B.1. Furthermore, following the proof of Proposition 4.1, the function x → α , ϕ(x) is implementable by a neural network Θ ,m with Θ ,m 2 2 = 2 α 1 = 2 α 1 1 . Following the same reasoning as before, we can also conclude that Θ ,m is an optimal solution for:

min Θ Θ 2 2 subject to f (Θ; x i ) = y i (D.5) Now we note that λ Θ λ,m 2 2 ≤ L λ,m (Θ λ,m ) ≤ L λ,m (Θ ,m ) = λ Θ ,m 2

2 , so as λ → 0, and also Θ λ,m 2 ≤ Θ ,m 2 . Now assume for the sake of contradiction that ∃B with Θ λ,m 2 ≤ B < Θ ,m 2 for arbitrarily small λ. We define

r min Θ 1 n n i=1 (f (Θ; x i ) -y i ) 2 subject to Θ 2 ≤ B

Note that r > 0 since Θ ,m is optimal for equation D.5. However, L λ,m ≥ r for arbitrarily small λ, a contradiction. Thus, lim λ→0 Θ ,m 2 2 = Θ ,m 2 2 .

We proceed to provide similar generalization bounds as the classification setting. This time, our bounds depend on the norms of the solution rather than the margin. Let f φ (α; •) x → α, ϕ(x) (for ϕ(x) defined in equation 4.1). Following the convention in Section C.2, define hypothesis class

F 1,φ B {f φ (α; •) : α ∈ L 1 (S d-1

), α 1 ≤ B} of linear functionals bounded by B in 1-norm. As before, define F 2,φ B and let R(F) denote the empirical Rademacher complexity of hypothesis class F.

We will first derive a Rademacher complexity bound for

F 1,φ B . Claim D.6. R(F 1,φ B ) ≤ 1 n BE i n i=1 i ϕ(x i ) ∞ .

Proof. We write

R(F 1,φ B ) = 1 n E i sup α∈F 1,φ B α, n i=1 i ϕ(x i ) ≤ 1 n E i sup α∈F 1,φ B α 1 n i=1 i ϕ(x i ) ∞ ≤ 1 n B • E i n i=1 i ϕ(x i ) ∞

We will now complete the bound on R(F 1,φ B ) for Lipschitz activations φ with φ(0) = 0. Claim D.7. Suppose that our activation φ is M -Lipschitz and φ(0

) = 0.Then R(F 1,φ B ) ≤ 3BM n i=1 x i 2 2 n

Proof. We will show that

E i n i=1 i ϕ(x i ) ∞ ≤ 3M n i=1 x i 2 2

from which the statement of the lemma follows via Claim D.6. Fix any ū ∈ S d-1 . Then we get the decomposition

E i sup ū∈S d-1 n i=1 i φ(ū x i ) ≤ E i n i=1 i φ(ū x i ) + E i sup ū∈S d-1 n i=1 i φ(ū x i ) -inf ū∈S d-1 n i=1 i φ(ū x i ) (D.6)

We can bound the first term as

E i n i=1 i φ(ū x i ) ≤ E i   n i=1 i φ(ū x i ) 2   ≤ n i=1 φ(ū x i ) 2 ≤ M n i=1 (ū x i ) 2 (since φ is Lipschitz and φ(0) = 0) ≤ M n i=1 x i 2 2 (D.7)

We note that the second term of equation D.6 can be bounded by

E i sup ū∈S d-1 n i=1 i φ(ū x i ) -inf ū∈S d-1 n i=1 i φ(ū x i ) ≤ E i sup ū∈S d-1 n i=1 i φ(ū x i ) -inf ū∈S d-1 n i=1 i φ(ū x i )

This follows from the general fact that the difference between the supremum and infimum of the absolute value of a quantity is bounded by the difference the supremum and the infimum. Furthermore, by symmetry of the Rademacher random variables,

E i sup ū∈S d-1 n i=1 i φ(ū x i ) -inf ū∈S d-1 n i=1 i φ(ū x i ) ≤ 2E i sup ū∈S d-1 n i=1 i φ(ū x i ) (D.8)

This simply gives an empirical Rademacher complexity of the hypothesis class F {x → φ(ū x) : ū ∈ S d-1 } scaled by n. By the Lipschitz contraction property of Rademacher complexity, using the fact that φ is M -Lipschitz, we can therefore bound equation D.8 by

2E i sup ū∈S d-1 n i=1 i φ(ū x i ) ≤ 2M n i=1

x i 2 2 (D.9)

Plugging equation D.7 and equation D.9 back into equation D.6 gives the desired bound.

The following is a generalization bound based on the 1-norm: Lemma D.8. Let l(•; y) : R → [-c, c] be a bounded M -Lipschitz loss function. Assume that φ is a 1-Lipschitz activation with φ(0) = 0. Let (x i , y i ) n i=1 be drawn i.i.d from p data . Then with probability at least 1 -δ over the dataset, every α ∈ L 1 (S d-1 ) satisfies

EQUATION

Proof. Our starting point is Theorem 1 of Kakade et al. (2009) , which states that with probability 1 -δ, for any fixed hypothesis class F and f ∈ F,

E (x,y)∼p data [l(f (x); y)] ≤ 1 n n i=1 l(f (x i ); y i ) + 2M R(F) + c log(1/δ) n (D.10)

We define B j 2 j X F for j ≥ 0. We note that by Claim D.7, R(F 1,φ Bj ) ≤ 3 2 j n . and apply the above on F 1,φ Bj using δ j δ 2 j+1 . Then using a union bound, with probability 1 -∞ j=0 δ j = 1 -δ, for all j ≥ 0 and f φ (α;

•) ∈ F 1,φ Bj E (x,y)∼p data [l(f φ (α; x); y)] ≤ 1 n n i=1 l(f φ (α; x i ); y i ) + 2M R(F 1,φ Bj ) + c log(1/δ j ) n ≤ 1 n n i=1 l(f φ (α; x i ); y i ) + 6M 2 j n + c log(1/δ) + log(2 j+1

) n

Now for every α with α 1 < 1 X F , we use the inequality for F 1,φ B0 , and for every other α, we apply the inequality corresponding to F 1,φ Bj+1 , where 2 j ≤ α 1 X F ≤ 2 j+1 . This gives the desired statement.

We can also provide the same generalization error bound for the 2-norm and relu features: Lemma D.9. In the setting of Lemma D.8, choose φ to be the relu activation. Then with probability 1 -δ, every α ∈ L 2 (S d-1 ) satisfies

EQUATION

Proof. We proceed the same way as in the proof of Lemma D.8. We define B j as before, and this

time have R(F 2,φ Bj ) √ κ2 j n √

d from Corollary C.4. Thus, again union bounding over all j, equation equation D.10 gives with probability 1 -δ, for all j ≥ 0 and f

φ (α; •) ∈ F 2,φ Bj E (x,y)∼p data [l(f φ (α; x); y)] 1 n n i=1 l(f φ (α; x i ); y i ) + M √ κ2 j n √ d + c log(1/δ) + log(2 j+1

) n

Now we assign the α to different j as before to obtain the statement in the lemma.

Note that if l is some bounded loss such that l(y; y) = 0 (for example, truncated squared error), for α 1 and α 2 the loss terms over the datapoints (in the bounds of Lemmas D.8 and D.9) vanish. For loss l, define

L 1-reg E x,y∼p data [l(f φ (α 1 ; x); y)] L 2-reg E x,y∼p data [l(f φ (α 2 ; x); y)]

Next, we will define the kernel matrix K with K ij = ϕ(x i ), ϕ(x j ) . Now we are ready to state and prove the formal theorem describing the gap between the 1-norm solution and 2-norm solution.

Theorem D.10. Recall the definitions of α 1 and α 2 in equation D.3 and equation D.4. For any activation φ with the property that K is full rank for any X with no repeated datapoints, there exists a distribution p data such that with probability 1,

α 1 1 ≤ 1

On the other hand,

EQUATION

2 ] = n κ For i.i.d samples from this choice of p data , if l is bounded (l(•; y) : R → [-1, 1]), 0 on correct predictions (l(y; y) = 0), and 1-Lipschitz, then with probability 1 -δ,

L 1-reg d n + log(1/δ) + log n n

Meanwhile, in the case that α 2 2 2 ≥ n κ , the upper bound on L 2 -reg from Lemma D.9 is Ω(1) and in particular does not decrease with n.

We will first show that for any dataset X, there is a distribution over Y such that the expectation of α 2 2 is large. When it is clear from context, y will denote the vector corresponding to Y . Lemma D.11. There is a distribution A over L 1 (S d-1 ) such that for any dataset X with y

i ϕ(x i ), β for β ∼ A, E β [ α 2 2 2 ] ≥ n κ and with probability 1, α 1 1 ≤ 1

We note the order of the quantifiers in Lemma D.11: the distribution A must not depend on the dataset X. We first provide a simple closed-form expression for α 2 2 2 . Claim D.12. If K is full rank, then α 2 2 2 = y K -1 y.

Proof. This follows by taking the dual of equation D.4.

Proof of Lemma D.11. We sample β ∼ A as follows: first sample ū ∼ S d-1 uniformly. Then set β to have a delta mass of 1 at ū and be 0 everywhere else. Define the vector v

ū [φ(ū x 1 ) • • • φ(ū x n )];

then it follows that we set our labels y to v ū. It is immediately clear that α 1 1 ≤ β 1 ≤ 1.

To lower bound:

E β [ α 2 2 2 ], from Claim D.12 we get E β∼A [ α 2 2 2 ] = E ū∼S d-1 [v ū K -1 v ū] = E ū∼S d-1 [traceK -1 (v ūv ū )] = trace(K -1 E ū∼S d-1 [v ūv ū ] = 1 κ trace(K -1 K) (by definition of K) = n κ

Proof of Theorem D.10. We note that since the distribution A of Lemma D.11 does not depend on the dataset X, it must follow that

EQUATION

2 ] = n κ Thus, there exists β such that if we sample X i.i.d. from the standard normal and set y i = ϕ(x i ), β , the expectation of α 2 2 2 is at least n κ . We choose p data corresponding to this β , with x sampled from the standard normal. Now it is clear that p data will satisfy the norm conditions of Theorem D.10.

For the generalization bounds, with high probability X F = Θ( √ nd) as x is sampled from the standard normal distribution. Thus, Lemma D.8 immediately gives the desired generalization error bounds for L 1-reg . On the other hand, if α 2 2 ≥ n κ , then the bound of Lemma D.9 is at least

√ κ α 2 2 X F n √ d ≥ Ω(1) E MISSING PROOFS IN SECTION 5 E.1 DETAILED SETUP

We first write our regularity assumptions on Φ, R, and V in more detail:

Lemma E.11. Let h : R d+1 → R that is 2-homogeneous, with ∇h( θ) ≤ M ∀ θ ∈ S d and |h( θ)| ≤ B ∀ θ ∈ S d . Then ∀0 ≤ t ≤ t , we have d dt hdρ ≤ σB(W 2 + 1) + M W - d dt L[ρ t ] + σB L (W 2 + 1) 1/2 (E.2)

Proof. Let Q(t) hdρ t . We can compute:

Q (t) = h(θ) dρ t dt (θ)dθ = h(θ)(-σρ t (θ) -∇ • (v[ρ t ](θ)ρ t (θ)))dθ + σ hdU d = -σ h( θ) θ 2 2 ρ t (θ)dθ + σ hdU d -h(θ)∇ • (v[ρ t ](θ)ρ t (θ))dθ (E.3)

Note that the first two terms are bounded by σB(W 2 + 1) by the assumptions for the lemma. For the third term, we have from Lemma E.5:

h(θ)∇ • (v[ρ t ](θ)ρ t (θ))dθ = |E θ∼ρt [ ∇h(θ), v[ρ t ](θ) ]| ≤ E θ∼ρt [ ∇h(θ) 2 2 ]E θ∼ρt [ v[ρ t ](θ) 2 2 ] (by Cauchy-Schwarz) ≤ E θ∼ρt [ ∇h( θ) 2 2 θ 2 2 ]E θ∼ρt [ v[ρ t ](θ) 2 2 ] (by homogeneity of ∇h) ≤ M W E θ∼ρt [ v[ρ t ](θ) 2 2 ]

(since h is Lipschitz on the sphere)

≤ M W - d dt L[ρ t ] + σB L (W 2 + 1) 1/2

(by Corollary E.8)

Plugging this into equation E.3, we get that

|Q (t)| ≤ σB(W 2 + 1) + M W - d dt L[ρ t ] + σB L (W 2 + 1) 1/2

We apply this result to bound the change in L [ρ t ] over time in terms of the change of the objective value. For clarity, we write the bound in terms of c 1 that is some polynomial in the problem constants.

Lemma E.12. Define Q(t) Φdρ t . For every θ ∈ S d and 0

≤ t ≤ t + l ≤ t , ∃c 1 poly(k, C R , B Φ , M Φ , B L ) such that |L [ρ t ]( θ) -L [ρ t+l ]( θ)| ≤ C R B Φ t+l t Q (t) 1 (E.4) ≤ σlc 1 (W 2 + 1) + c 1 W √ l(L[ρ t ] -L[ρ t+l ] + σlc 1 (W 2 + 1)) 1/2 (E.5) Proof. Recall that L [ρ t ]( θ) = ∇R( Φdρ t ), Φ( θ) + V ( θ). Differentiating with respect to t, d dt L [ρ t ]( θ) = d dt ∇R Φdρ t , Φ( θ) = Φ( θ) ∇ 2 R(Q(t))Q (t) ≤ C R B Φ Q (t) 2 ≤ C R B Φ Q (t) 1 (E.6)

Proof. We have h(θ + α θ) = ( θ 2 + α) 2 h( θ). Differentiating both sides with respect to α and evaluating the derivative at 0, we get θ ∇h(θ) = 2 θ 2 h( θ), as desired.

We state the lemma claiming that our objective will decrease if

L [ρ t ]( θ) 0 for some θ ∈ S d . Lemma E.16. Choose l ≥ log(W 2 /σ) + 2d log 2c2 τ τ -σ + 1

If K -τ t * is nonempty for some t * satisfying t * + l ≤ t , then after l steps, we will have

L[ρ t * +l ] ≤ L[ρ t * ] - (τ /4 -σlc 1 (W 2 + 1)) 2 lc 2 1 W 2 + σlc 1 (W 2 + 1) (E.8)

We will first show that a descent direction in L [ρ t ] will remain for the next l time steps. In the notation of Lemma E.12, define z

(s) C R B Φ t * +s t * Q (t) 1 dt. Note that from Lemma E.12, for all θ ∈ S d we have |L [ρ t * +s ]( θ) -L [ρ t * ]( θ)| ≤ z(s)

. Thus, the following holds: Claim E.17. For all s ≤ l, K

-τ +z(s) t * +s is nonempty. Proof. By assumption, ∃ θ with θ ∈ K -τ t * . Then L [ρ t * +s ]( θ) ≤ L [ρ t * ]( θ) + z(s) ≤ -τ + z(s), so K -τ +z(s) t * +s is nonempty. Let T s K -τ /2+z(s) t * +s for 0 ≤ s ≤ l.

We now argue that this set T s does not shrink as t increases. Proof. From the assumption z(l) ≤ τ 4 , it holds that T s ⊆ K -τ /4 t * +s ∀s ≤ k. Since T s is defined as a sublevel set, v[ρ t * +s ]( θ) points inwards on the boundary of T s for all θ ∈ T s , and by 1-homogeneity of the gradient, the same must hold for all u ∈ Ts . Now consider any particle θ ∈ Ts . We have that θ flows to θ + v[ρ t * +s ](θ)ds at time t * + s + ds. Furthermore, since the gradient points inwards from the boundary, it also follows that u + v[ρ t * +s ](θ)ds ∈ Ts . Now we compute )ds (E.9)

E.3 DISCRETE-TIME OPTIMIZATION:

To circumvent the technical issue of existence of a solution to the continuous-time dynamics, we also note that polynomial time convergence holds for discrete-time updates.

Theorem E.21. Along with Assumptions E.1, E.2, E.3 additionally assume that ∇Φ i and ∇V are C Φ and C V -Lipschitz, respectively. Let ρ t evolve according to the following discrete-time update:

ρ t+1 ρ t + η(-σρ t + σU d -∇ • (v[ρ t ]ρ t ))

There exists a choice of

σ exp(-d log(1/ )poly(k, M V , M R , b V , B V , C R , B Φ , C Φ , C V , L[ρ 0 ] -L[ρ ])) η poly(k, M V , M R , b V , B V , C R , B Φ , C Φ , C V , L[ρ 0 ] -L[ρ ]) t d 2 4 poly(k, M V , M R , b V , B V , C R , B Φ , C Φ , C V , L[ρ 0 ] -L[ρ ])

such that min 0≤t≤t L[ρ t ] -L ≤ .

The proof follows from a standard conversion of the continuous-time proof of Theorem E.4 to discrete time, and we omit it here for simplicity.

F ADDITIONAL MATERIAL ON EXPERIMENTS:

F.1 DETAILED SETUP FOR FIGURE 2 EXPERIMENT Our ground truth comes from a random neural network with 6 hidden units, and during training we use a network with as many hidden units as examples. For classification, we used rejection sampling to obtain datapoints with unnormalized margin of at least 0.1 on the ground truth network. We use a fixed dimension of d = 20. For all experiments, we train the network for 20000 steps with λ = 10 -8 and average over 100 trials for each plot point.

F.2 DETAILED SETUP FOR FIGURE 3 EXPERIMENT:

The left side of Figure 3 shows the experimental results for synthetic data generated from a ground truth network with 10 hidden units, input dimension d = 20, and a ground truth unnormalized margin of at least 0.01. We train for 80000 steps with learning rate 0.1 and λ = 10 -5 , using two-layer networks with 2 i hidden units for i ranging from 4 to 10. We perform 20 trials per hidden layer size and plot the average over trials where the training error hit 0. (At a hidden layer size of 2 7 or greater, all trials fit the training data perfectly.) The right side of Figure 3 demonstrates the same experiment, but performed on MNIST with hidden layer sizes of 2 i for i ranging from 6 to 15. We train for 600 epochs using a learning rate of 0.01 and λ = 10 -6 and use a single trial per plot point. For MNIST, all trials fit the training data perfectly. The MNIST experiments are more noisy because we run one trial per plot point for MNIST, but the same trend of decreasing test error and increasing margin still holds.

F.3 VERIFYING CONVERGENCE TO THE MAX-MARGIN:

We verify the normalized margin convergence on a two-layer networks with one-dimensional input.

A single hidden unit computes the following: x → a j relu(w j x + b j ). We add • 2 2 -regularization to a, w, and b and compare the resulting normalized margin to that of an approximate solution of the 1 SVM problem with features relu(wx i + b) for w 2 + b 2 = 1. Writing this feature vector is intractable, so we solve an approximate version by choosing 1000 evenly spaced values of (w, b). Our theory predicts that with decreasing regularization, the margin of the neural network converges to the 1 SVM objective. In Figure 4 , we plot this margin convergence and visualize the final networks and ground truth labels. The network margin approaches the ideal one as λ → 0, and the visualization shows that the network and 1 SVM functions are extremely similar. Table 1 : Test error on CIFAR10 and CIFAR100 for initial λ = 0.0005.

F.4 EXPERIMENTS ON CIFAR10 AND CIFAR100:

We train a modified WideResNet architecture (Zagoruyko & Komodakis, 2016) on CIFAR10 and CIFAR100. Our theory does not entirely apply because the identity mapping prevents ResNet architectures from being homogeneous, but our experiments show that reducing weight decay can still help generalization error in this setting. Because batchnorm can cause the regularizer to have different effects (van Laarhoven, 2017), we remove batchnorm layers and train a 16 layer deep WideResNet. We again compare a network trained with weight decayed annealing to one trained without annealing.

We used a fixed learning rate schedule that starts at 0.1 and decreases by a factor of 0.2 at epochs 60, 120, and 160. For CIFAR10, we use an initial weight decay of 0.0002 and decrease the weight decay by 0.2 at epoch 60, and then by 0.5 at epochs 90, 120, 140, 160. For CIFAR100, we initialize weight decay at 0.0005 and decrease it by 0.2 at epochs 60, 120, and 160. We tried different parameters for the initial weight decay and chose the ones that worked best for the model without annealing. We also tried using small weight decays at initialization, but these models failed to generalize well -we believe this is due to an optimization issue where the algorithm fails to find a true global minimum of the regularized loss. We believe that annealing the weight decay directs the optimization algorithm closer towards the global minima for small λ.

Table 1 shows the test error achieved by models with and without annealing. We see that the simple change of annealing weight decay can decrease the test error for this architecture.

:

We formally show that L λ has a minimizer in Claim A.1 of Section A.

is due the the relation that every unit-norm parameter Θ corresponds to an α in the lifted space with α = 2.

The relu activation is non-differentiable at 0 and hence the gradient flow is not well-defined.Chizat & Bach (2018) acknowledge this same difficulty with relu.

We compute the leading term that is linear in the norm or inverse margin from the bounds in Proposition 3.1 and Lemmas 4.2, D.8, and D.9.

sup x∈X ϕ(x) 2 √ κγ 2

d log(1/ ) ) in O( d log 1 ) time. Therefore, a total of O( d 2 4 log 2 (1/ )) time is sufficient to obtain accuracy.

Figures and Tables:

also study optimization and generalization of convex neural networks. Using results from Rosset et al. (2007); Neyshabur et al. (2014); Bengio et al. (2006), our Theorem 2.1 implies that optimizing weaklyregularized logistic loss over two-layer networks is equivalent to solving equation 4.2 when the size of the hidden layer is at least n + 1, where n is the number of training examples. Proposition 4.1 essentially restates this with the minor improvement that this equivalence 4 also holds when the size of the hidden layer is n. Proposition 4.1. Let γ 1 be defined in equation 4.2. Then

Figure 1: A visualization of 60 sampled points from D in 3 dimensions. Red points denote negative examples and blue points denote positive examples.

Figure 2: Comparing neural networks and kernel methods. Left: Classification. Right: Regression.

Figure 3: Dependence of margin and test error on hidden layer size. Left: Synthetic. Right: MNIST.

Let supp(α) {ū : |α(ū)| > 0}. There exists an optimal solution α to equation 4.2 with |supp(α )| ≤ n.

be the set of optimizers for equation 4.2, and let S ⊂ L 1 (S d-1 ) be the set of optimizers for equation B.1. If equation B.1 is feasible, for any α ∈ S, α γ 1 ∈ S , and for any α ∈ S , α α 1 ∈ S.

equation B.1, as desired. First, note that if equation B.1 is not feasible, then γ 1 = 0 and equation 4.2 has a trivial sparse solution, the all zeros function. Thus, it suffices to show that an optimal solution to equation B.1 exists that is n-sparse, since by Lemma B.2 equation B.1 and equation 4.2 have equivalent solutions up to a scaling. We begin by taking the dual of equation B.1. Claim B.3. The dual of equation B.1 has form

ū∈S c ūv(ū) = 0 (B.3) for coefficients c. Then ū∈S c ū sign(α (ū)) = 0.

Claim E.18. For all s > s, T s ⊇ T s .Proof. From equation E.6 and the definition of z(s),|L [ρ t+s ]( θ) -L [ρ t+s ]( θ)| ≤ z(s ) -z(s). It follows that for θ ∈ T s L [ρ t+s ]( θ) ≤ L [ρ t+s ]( θ) + z(s ) -z(s) ≤ -τ /2 + z(s) -z(s) + z(s ) (by definition of T s ) ≤ -τ /2 + z(s )which means that θ ∈ T s . Now we show that the weight of the particles in T s grows very fast if z(k) is small.Claim E.19. Suppose that z(l) ≤ τ /4. Let Ts = {θ ∈ R d+1 : θ ∈ T s }. Define N (s)Ts θ 2 dρ t * +s and β exp(-2d log 2c2 τ ). Then N (s) ≥ (τ -σ)N (s) + σβ.

Figure 4: Neural network with input dimension 1. Left: Normalized margin as we decrease λ. Right: Visualization of the normalized functions computed by the neural network and 1 SVM solution for λ ≈ 10 -14 . Method CIFAR10 CIFAR100 Weight decay annealing 5.86 26.22 Fixed weight decay 6.01 27.00

Proof of Lemma 4.2. From equation C.2, we first obtain sup x∈X ϕ(x) 2

Table content: <table><tr><td>optimizer for equation 4.3 by α 2 . Note that Since √ κα 2 has unnormalized margin √</td><td>C κ d . Denote the 1 , and furthermore L(α 2 ) = L( κα 2 ∈ F 2,φ √ κα 2 ). κγ 2 , we apply Theorem C.1 on margin √ √ κγ 2 and</td></tr><tr><td>hypothesis class F 2,φ 1</td><td/></tr></table>

Peer review (iclr2019):
 UPDATE: after revisions and discussion. There seems to be some interesting results presented in this paper which I think would be good to have discussed at the conference. This is conditional on further revisions of the work by the authors. This paper studies margin theory for neural nets. 1. First it is shown that margin of the solution to regularized problem approaches max margin solution. 2. Then a bound is given for using approximate solution to above optimization problem instead of exact one. Note that the bound depends on size of the network via parameter a. 3. Then 2-layer relu networks are studied. It shown that max margin is monotonically increasing in size of the network. Note however, it is hard to relate this results to inexact solutions since the bound in that case as was pointed out also depends on the size of the network. 4. Paper also provides comparison with kernel methods, simulations and shows that perturbed wasserstein flows find global optimiziers in poly time. The paper argues that over-parameterization is good for generalization since margin grows with the number of parameters. However, it should be also noted the radius of data may also grow (and in case of the bounds it seems to be the radius of data in lifted space which increases with the size of the network). I hope authors can clarify this and points 2 and 3 above in their response. In the current form the paper is below the acceptance threshold for me.