summaries: This paper studies the implicit bias of minimizers of a regularized cross entropy loss of a two-layer network with ReLU activations. By combining several results, the authors obtain a generalization upper bound which does not increase with the network size. Furthermore, they show that the maximum normalized margin is, up to a scaling factor, the l1 svm margin over the lifted feature space of an infinite-size network. Finally, in a setting of infinite-sized networks, it is proved that perturbed Wasserstein gradient flow finds a global minimum in polynomial time. The authors claim to prove three things: (1) Under logistic loss (with a vanishing regularization), the normalized margin (of the solution) converges to the max normalized margin, for positive homogenous functions. This is an asymptotic result: the amount of regularization vanishes. (2) For one hidden layer NN, the max margin under l_2 norm constraint on weights in the limit, is equivalent to the l_1 constraint (total variation) on the sign measure (specified by infinite neurons) for the one hidden layer NN. (3) Show some convergence rate for the mean-field view of one hidden layer NN, i.e., the Wasserstein gradient flow on the measure (of the neurons). The author show some positive result for a perturbed version.
abstractText: 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.
references.authors: Sanjeev Arora Nadav Cohen Elad Hazan
references.title: On the optimization of deep networks: Implicit acceleration by overparameterization
references.venue: arXiv preprint arXiv:1802.06509,
references.authors: Sanjeev Arora Rong Ge Behnam Neyshabur Yi Zhang
references.title: Stronger generalization bounds for deep nets via a compression approach
references.venue: arXiv preprint arXiv:1802.05296,
references.authors: Francis Bach
references.title: Breaking the curse of dimensionality with convex neural networks
references.venue: Journal of Machine Learning Research,
references.authors: Keith Ball
references.title: An elementary introduction to modern convex geometry
references.venue: Flavors of geometry,
references.authors: Peter L Bartlett Shahar Mendelson
references.title: Rademacher and gaussian complexities: Risk bounds and structural results
references.venue: Journal of Machine Learning Research,
references.authors: Peter L Bartlett Dylan J Foster Matus J Telgarsky
references.title: Spectrally-normalized margin bounds for neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Mikhail Belkin Siyuan Ma Soumik Mandal
references.title: To understand deep learning we need to understand kernel learning
references.venue: arXiv preprint arXiv:1802.01396,
references.authors: Yoshua Bengio Nicolas L Roux Pascal Vincent Olivier Delalleau Patrice Marcotte
references.title: Convex neural networks. In Advances in neural information processing
references.authors: Alon Brutzkus Amir Globerson Eran Malach Shai Shalev-Shwartz
references.title: Sgd learns overparameterized networks that provably generalize on linearly separable data
references.venue: arXiv preprint arXiv:1710.10174,
references.authors: Pratik Chaudhari Anna Choromanska Stefano Soatto Yann LeCun Carlo Baldassi Christian Borgs Jennifer Chayes Levent Sagun Riccardo Zecchina
references.title: Entropy-sgd: Biasing gradient descent into wide valleys
references.venue: arXiv preprint arXiv:1611.01838,
references.authors: Lenaic Chizat Francis Bach
references.title: On the global convergence of gradient descent for over-parameterized models using optimal transport
references.venue: arXiv preprint arXiv:1805.09545,
references.authors: Simon S Du Jason D Lee
references.title: On the power of over-parametrization in neural networks with quadratic activation
references.venue: arXiv preprint arXiv:1803.01206,
references.authors: Simon S Du Jason D Lee Yuandong Tian Barnabas Poczos Aarti Singh
references.title: Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima
references.venue: arXiv preprint arXiv:1712.00779,
references.authors: Gintare Karolina Dziugaite Daniel M Roy
references.title: Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
references.venue: arXiv preprint arXiv:1703.11008,
references.authors: Noah Golowich Alexander Rakhlin Ohad Shamir
references.title: Size-independent sample complexity of neural networks
references.venue: arXiv preprint arXiv:1712.06541,
references.authors: Suriya Gunasekar Blake E Woodworth Srinadh Bhojanapalli Behnam Neyshabur Nati Srebro
references.title: Implicit regularization in matrix factorization
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Suriya Gunasekar Jason Lee Daniel Soudry Nathan Srebro
references.title: Characterizing implicit bias in terms of optimization geometry
references.venue: arXiv preprint arXiv:1802.08246,
references.authors: Suriya Gunasekar Jason Lee Daniel Soudry Nathan Srebro
references.title: Implicit bias of gradient descent on linear convolutional networks
references.venue: arXiv preprint arXiv:1806.00468,
references.authors: Benjamin D Haeffele René Vidal
references.title: Global optimality in tensor factorization, deep learning, and beyond
references.venue: arXiv preprint arXiv:1506.07540,
references.authors: Moritz Hardt Benjamin Recht Yoram Singer
references.title: Train faster, generalize better: Stability of stochastic gradient descent
references.venue: arXiv preprint arXiv:1509.01240,
references.authors: Ziwei Ji Matus Telgarsky
references.title: Risk and parameter convergence of logistic regression
references.venue: arXiv preprint arXiv:1803.07300,
references.authors: Sham M Kakade Karthik Sridharan Ambuj Tewari
references.title: On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
references.venue: In Advances in neural information processing systems,
references.authors: Vladimir Koltchinskii Dmitry Panchenko
references.title: Empirical margin distributions and bounding the generalization error of combined classifiers
references.venue: The Annals of Statistics,
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E Hinton
references.title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing
references.authors: Yuanzhi Li Tengyu Ma Hongyang Zhang
references.title: Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
references.venue: In Conference On Learning Theory,
references.authors: T. Liang A. Rakhlin
references.title: Just Interpolate: Kernel “Ridgeless
references.venue: Regression Can Generalize. ArXiv e-prints,
references.authors: Roi Livni Shai Shalev-Shwartz Ohad Shamir
references.title: On the computational efficiency of training neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Cong Ma Kaizheng Wang Yuejie Chi Yuxin Chen
references.title: Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution
references.venue: arXiv preprint arXiv:1711.10467,
references.authors: Song Mei Andrea Montanari Phan-Minh Nguyen
references.title: A mean field view of the landscape of two-layers neural networks
references.venue: arXiv preprint arXiv:1804.06561,
references.authors: Ari S Morcos David GT Barrett Neil C Rabinowitz Matthew Botvinick
references.title: On the importance of single directions for generalization
references.venue: arXiv preprint arXiv:1803.06959,
references.authors: Mor Shpigel Nacson Jason Lee Suriya Gunasekar Nathan Srebro Daniel Soudry
references.title: Convergence of gradient descent on separable data
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: In search of the real inductive bias: On the role of implicit regularization in deep learning
references.venue: arXiv preprint arXiv:1412.6614,
references.authors: Behnam Neyshabur Ruslan R Salakhutdinov Nati Srebro
references.title: Path-sgd: Path-normalized optimization in deep neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: Norm-based capacity control in neural networks
references.venue: In Conference on Learning Theory, pp
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nathan Srebro
references.title: A pacbayesian approach to spectrally-normalized margin bounds for neural networks
references.venue: arXiv preprint arXiv:1707.09564,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nati Srebro
references.title: Exploring generalization in deep learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Behnam Neyshabur Zhiyuan Li Srinadh Bhojanapalli Yann LeCun Nathan Srebro
references.title: Towards understanding the role of over-parametrization in generalization of neural networks
references.authors: Andrew Y Ng
references.title: Feature selection, l 1 vs. l 2 regularization, and rotational invariance
references.venue: In Proceedings of the twenty-first international conference on Machine learning,
references.authors: Quynh Nguyen Matthias Hein
references.title: The loss surface of deep and wide neural networks
references.venue: arXiv preprint arXiv:1704.08045,
references.authors: Saharon Rosset Ji Zhu Trevor Hastie
references.title: Boosting as a regularized path to a maximum margin classifier
references.venue: Journal of Machine Learning Research,
references.authors: Saharon Rosset Ji Zhu Trevor J Hastie
references.title: Margin maximizing loss functions
references.venue: In Advances in neural information processing systems,
references.authors: Saharon Rosset Grzegorz Swirszcz Nathan Srebro Ji Zhu
references.title: l1 regularization in infinite dimensional feature spaces
references.venue: In International Conference on Computational Learning Theory,
references.authors: Grant M Rotskoff Eric Vanden-Eijnden
references.title: Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error
references.venue: arXiv preprint arXiv:1805.00915,
references.authors: Itay Safran Ohad Shamir
references.title: On the quality of the initial basin in overspecified neural networks
references.venue: In International Conference on Machine Learning,
references.authors: Levent Sagun Utku Evci V Ugur Guney Yann Dauphin Leon Bottou
references.title: Empirical analysis of the hessian of over-parametrized neural networks
references.venue: arXiv preprint arXiv:1706.04454,
references.authors: Justin Sirignano Konstantinos Spiliopoulos
references.title: Mean field analysis of neural networks
references.venue: arXiv preprint arXiv:1805.01053,
references.authors: Daniel Soudry Yair Carmon
references.title: No bad local minima: Data independent training error guarantees for multilayer neural networks
references.venue: arXiv preprint arXiv:1605.08361,
references.authors: Daniel Soudry Elad Hoffer Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: In International Conference on Learning Representations,
references.authors: Ryan J Tibshirani
references.title: The lasso problem and uniqueness
references.venue: Electronic Journal of Statistics,
references.authors: Twan van Laarhoven
references.title: L2 regularization versus batch and weight normalization
references.venue: arXiv preprint arXiv:1706.05350,
references.authors: Luca Venturi Afonso Bandeira Joan Bruna
references.title: Neural networks with finite intrinsic dimension have no spurious valleys
references.venue: arXiv preprint arXiv:1802.06384,
references.authors: Sergey Zagoruyko Nikos Komodakis
references.title: Wide residual networks
references.venue: arXiv preprint arXiv:1605.07146,
references.authors: Chiyuan Zhang Samy Bengio Moritz Hardt Benjamin Recht Oriol Vinyals
references.title: Understanding deep learning requires rethinking generalization
references.venue: arXiv preprint arXiv:1611.03530,
references.authors: Ji Zhu Saharon Rosset Robert Tibshirani Trevor J Hastie
references.title: 1-norm support vector machines. In Advances in neural information processing
references.authors: Du
references.title: Now we plug this into Lemma C.3 to get the desired bound
references.venue: We will now prove Lemma 4.2. Proof of Lemma 4.2. From equation C.2,
sections.heading: 1 INTRODUCTION
sections.text: 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.
sections.heading: 1.1 ADDITIONAL RELATED WORK
sections.text: 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.
sections.heading: 1.2 NOTATION
sections.text: 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/‖u‖, where the norm ‖ · ‖ will be clear from context. Let Sd−1 , {ū ∈ Rd : ‖ū‖2 = 1} be the unit sphere in d dimensions. Let Lp(Sd−1) be the space of functions on Sd−1 for which the p-th power of the absolute value is Lebesgue integrable. For α ∈ Lp(Sd−1), we overload notation and write ‖α‖p , (∫ Sd−1 |α(ū)| pdū )1/p
  . Additionally, for α1 ∈ L1(Sd−1) and α2 ∈ L∞(Sd−1) or α1, α2 ∈ L2(Sd−1), we can define 〈α1, α2〉 , ∫ Sd−1 α1(ū)α2(ū)dū < ∞.
  Furthermore, we will use Vol(Sd−1) , ∫ Sd−1 1dū. Throughout this paper, we reserve the symbol X = [x1, . . . , xn] to denote the collection of datapoints (as a matrix), and Y = [y1, . . . , yn] 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.
sections.heading: 2 WEAK REGULARIZER GUARANTEES MAX MARGIN SOLUTIONS
sections.text: 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 yi ∈ [l]. We work with a family F of prediction functions f(Θ; ·) : Rd → Rl that are a-positive-homogeneous in their parameters for some a > 0: f(cΘ;x) = caf(Θ;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(fyi(Θ;xi))∑l j=1 exp(fj(Θ;xi)) + λ‖Θ‖r (2.1)
  for fixed r > 0. Let Θλ ∈ arg minLλ(Θ).1 We define the normalized margin of Θλ as:
  γλ , min i
  ( fyi(Θ̄λ;xi)−max
  j 6=yi fj(Θ̄λ;xi)
  ) (2.2)
  Define the ‖ · ‖-max normalized margin as
  γ? , max ‖Θ‖≤1 [ min i ( fyi(Θ;xi)−max j 6=yi fj(Θ;xi) )] 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 1We formally show that Lλ has a minimizer in Claim A.1 of Section A.
  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.
sections.heading: 2.1 OPTIMIZATION ACCURACY
sections.text: 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(−(2r/a − 1)−a/r) (γ ?)r/a
  nc(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 .
sections.heading: 3 GENERALIZATION PROPERTIES OF A MAXIMUM MARGIN NEURAL NETWORK
sections.text: 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 W1, . . . ,WK . The K-layer network will compute a real-valued score
  f(Θ;x) ,WKφ(WK−1φ(· · ·φ(W1x) · · · )) (3.1)
  where we overload notation to let φ(·) denote the element-wise application of the activation φ. Let mi denote the size of the i-th hidden layer, so W1 ∈ Rm1×d,W2 ∈ Rm2×m1 , · · · ,WK ∈ R1×mK−1 . We will letM , (m1, . . . ,mK−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 sizesM is therefore
  Lλ,M(Θ) , 1
  n n∑ i=1 log(1 + exp(−yif(Θ;xi))) + λ‖Θ‖2F (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 yif(Θ̄λ,M;xi)
  γ?,M , max ‖Θ‖2≤1 min i yif(Θ;xi)
  When the data is not separable by a neural network with architectureM, we define γ?,M to be zero. Recall that X = [x1, . . . , xn] denotes the matrix with all the data points as columns, and Y = [y1, . . . , yn] denotes the labels. We sample X and Y i.i.d. from the data generating distribution pdata, 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)∼pdata
  [yf(Θ;x) ≤ 0]
  Let C , supx∈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 γ , mini yif(Θ̄;xi) > 0, with probability at least 1− δ over the draw of X,Y ,
  L(Θ) . C
  γK(K−1)/2 √ n + (γ) (3.3)
  where (γ) , √ log log2 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
  γ?,MK(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.
  2Although 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.
  3Although 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 architecturesM = (m1, . . . ,mK−1) andM′ = (m′1, . . . ,m′K−1), we sayM ≤ M′ if mi ≤ m′i ∀i = 1, . . .K − 1. Theorem 3.3 states that ifM ≤ M′, then the max-margin over networks with architecture M′ is at least the max-margin over networks with architectureM. Theorem 3.3. Recall that γ?,M denotes the maximum normalized margin of a network with architectureM. IfM≤M′, we have γ?,M ≤ γ?,M′ . As a important consequence,
  the generalization error bound of Corollary 3.2 forM′ is at least as good as that forM.
  This theorem is simple to prove and follows because we can directly implement any network of architectureM using one of architectureM′, ifM ≤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.
sections.heading: 4 NEURAL NET MAX-MARGIN VS. KERNEL METHODS
sections.text: 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 usem 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 ϕ : Rd → L∞(Sd−1) mapping data to an infinite feature vector:
  x ∈ Rd → ϕ(x) ∈ L∞(Sd−1) satisfying ϕ(x)[ū] = φ(ū>x) (4.1)
  where φ is the activation of Section 3. We look at the margin of linear functionals corresponding to α ∈ L1(Sd−1) . The 1-norm SVM (Zhu et al., 2004) over the lifted feature ϕ(x) solves for the maximum margin:
  γ`1 ,max α min i∈[n] yi〈α,ϕ(xi)〉
  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) 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 equivalence4 also holds when the size of the hidden layer is n. Proposition 4.1. Let γ`1 be defined in equation 4.2. Then γ`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(Sd−1):
  γ`2 ,max α min i∈[n] yi〈α,ϕ(xi)〉
  subject to √ κ‖α‖2 ≤ 1
  (4.3)
  where κ , Vol(Sd−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 { log2
  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 pdata 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 pdata, 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 {√ logn n , 1/d } and therefore the generalization upper bound from
  4The factor of 1 2 is due the the relation that every unit-norm parameter Θ corresponds to an α in the lifted space with ‖α‖ = 2.
  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 pdata here. The full proof is in Section D.1.
  Proof sketch for Theorem 4.3. We base pdata on the distribution D of examples (x, y) described below. Here ei is the i-th standard basis vector and we use x>ei to represent the i-coordinate of x (since the subscript is reserved to index training examples).e > 3 x ...
  e>d x
   ∼ N (0, Id−2), and  y = +1, x>e1 = +1, x >e2 = +1 w/ prob. 1/4
  y = +1, x>e1 = −1, x>e2 = −1 w/ prob. 1/4 y = −1, x>e1 = +1, x>e2 = −1 w/ prob. 1/4 y = −1, x>e1 = −1, x>e2 = +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 pdata where the 1-norm solution will have a generalization error bound of O( √ d/n), whereas the 2- norm 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.
sections.heading: 5 PERTURBED WASSERSTEIN GRADIENT FLOW FINDS GLOBAL OPTIMIZERS IN POLYNOMIAL TIME
sections.text: 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 Rd+1:
  L[ρ] , R (∫ Φdρ ) + ∫ V dρ
  where Φ : Rd+1 → Rk, R : Rk → R, and V : Rd+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>xi) 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 (θ) , λ‖θ‖22 and R(a1, . . . , an) , ∑n i=1 log(1 + exp(−yiai)).
  We will define L′[ρ] : Rd+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 + σUd −∇ · (v[ρt]ρt) (5.2)
  where Ud is the uniform distribution on Sd. In our perturbed dynamics, we add very small uniform noise over Ud, 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 2- homogeneous 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 + σUd −∇ · (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.
  5The 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.
sections.heading: 6 SIMULATIONS
sections.text: 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.
sections.heading: 7 CONCLUSION
sections.text: 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.
  6We 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.
sections.heading: A MISSING PROOFS IN SECTION 2
sections.text: 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 Θλ.
sections.heading: A.1 MISSING PROOFS FOR MULTI-CLASS SETTING
sections.text: 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 γΘ , mini ( f(Θ̄;xi)−maxj 6=yi f(Θ̄;xi) ) ,
  Lλ(MΘ) = 1
  n n∑ i=1 − log exp(M afyi(Θ;xi))∑l j=1 exp(M afj(Θ;xi)) + λMr‖Θ‖r (by the homogeneity of f )
  = 1
  n n∑ i=1 − log 1 1 + ∑ j 6=yi exp(M a(fj(Θ;xi)− fyi(Θ;xi))) + λMr‖Θ‖r (A.1) ≤ log(1 + (l − 1) exp(−MaγΘ)) + λMr‖Θ‖r (A.2)
  We can also apply ∑ j 6=yi exp(M
  a(fj(Θ;xi) − fyi(Θ;xi))) ≥ max exp(Ma(fj(Θ;xi) − fyi(Θ;xi))) = exp γΘ in order to lower bound equation A.1 and obtain
  Lλ(MΘ) ≥ 1
  n log(1 + exp(−MaγΘ)) + λMr‖Θ‖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 fj(Θ, xi) before softmax) are bounded in absolute value by some constant (that depends on C), and therefore the loss function − log exp(fyi (Θ;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(−Maγ?) + λMr (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.
sections.heading: A.2 FULL BINARY CLASSIFICATION SETTING
sections.text: For completeness, we state and prove our max-margin results for the setting where we fit binary labels yi ∈ {−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(−yif(Θ;xi))) + λ‖Θ‖r
  As before, let Θλ ∈ arg minLλ(Θ), and define the normalized margin γλ by γλ , mini yif(Θ̄λ;xi). Define the maximum possible normalized margin
  γ? , max ‖Θ‖≤1 min i yif(Θ;xi) (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̃ : Rd → R2 with f̃1(Θ;xi) = − 12f(Θ;xi) and f̃2(Θ;xi) = 1 2f(Θ;xi). Define new labels ỹi = 1 if yi = −1 and ỹi = 2 if yi = 1. Now note that f̃ỹi(Θ;xi)−f̃j 6=ỹi(Θ;xi) = yif(Θ;xi), 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̃ỹi(Θ;xi))∑2 j=1 exp(f̃j(Θ;xi)) + λ‖Θ‖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.
sections.heading: A.3 MISSING PROOF FOR OPTIMIZATION ACCURACY
sections.text: 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(−Baγ?)) + βλBr (by equation A.2) ≤ β(l − 1) exp(−Baγ?) + βλBr (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(UB)
  Furthermore, it holds that ‖Θ′‖r ≤ L (UB)
  λ . Now we note that
  Lλ(Θ ′) ≤ L(UB) ≤ 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) ≥ x1+x ∀x ≥ −1, we additionally have the lower bound Lλ(Θ′) ≥ 1n log(1 + exp(−γ ′‖Θ′‖a)) ≥ 1n exp(−γ′‖Θ′‖a) 1+exp(−γ′‖Θ′‖a) . Since L(UB) ≤ 1, we can rearrange to get
  γ′ ≥ − log nLλ(Θ ′) 1−nLλ(Θ′)
  ‖Θ′‖a ≥ − log nL
  (UB)
  1−nL(UB) ‖Θ′‖a ≥ − log(2nL (UB)) ‖Θ′‖a
  The middle inequality followed because x1−x is increasing in x for 0 ≤ x < 1, and the last because L(UB) ≤ 12n . Since − log 2nL (UB) > 0 we can also apply the bound ‖Θ′‖r ≤ L (UB) λ to get
  γ′ ≥ −λ a/r log 2nL(UB)
  (L(UB))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(UB))
  ≥ γ ?
  β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 (2r/a−1)a/r , we note that( 1 + ( log (l − 1)(γ?)r/a
  λ
  )−r/a)a/r ≤ ( 1 + ( 1
  (2r/a − 1)a/r
  )−r/a)a/r ≤ 2 (A.8)
  Combining equation A.7 and equation A.8, we can conclude that
  ♣ = log( (γ
  ?)r/a
  2βnλ )
  log (l−1)(γ ?)r/a
  λ
  ( 1 + ( log (l − 1)(γ?)r/a
  λ
  )−r/a)−a/r ≥ c− 3
  2c
  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 ♥ ≤ 110 . Thus, if c ≥ 5, we can combine our bounds on ♣ and ♥ to get that
  γ′ ≥ γ ?
  10βa/r
sections.heading: B MISSING PROOF OF PROPOSITION 4.1
sections.text: 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).
  Lemma B.1. Let supp(α) , {ū : |α(ū)| > 0}. There exists an optimal solution α? to equation 4.2 with |supp(α?)| ≤ n.
  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:
  min α ‖α‖1
  subject to yi〈α,ϕ(xi)〉 ≥ 1 ∀i (B.1)
  Claim B.2. Let S ⊂ L1(Sd−1) be the set of optimizers for equation 4.2, and let S′ ⊂ L1(Sd−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.
  Proof. Let opt′ denote the optimal objective for equation B.1. We note that α ′
  ‖α′‖1 is feasible for equation 4.2 with objective 1opt′ , and therefore γ`1 ≥ 1 opt′ . Furthermore,
  1 2γ`1 yi ∫ ū∈Sd−1 α(ū)φ(ū
  >xi)dū ≥ 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.2, and αγ`1 is optimal for 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
  max λ∈Rn
  λ>~1
  subject to ∣∣∣∣∣ n∑ i=1 λiyiφ(ū >xi) ∣∣∣∣∣ ≤ 1 ∀ū ∈ Sd−1 λi ≥ 0
  For any primal optimal solution α? and dual optimal solution λ?, it must hold that n∑ i=1 λ?i yiφ(ū >xi) = sign(α ?(ū)) ⇐⇒ α?(ū) 6= 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 : Sd−1 → Rn with vi(ū) , yiφ(ū>xi). We will show a general result about linearly dependent v(ū) for ū ∈ 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(ū) : ū ∈ S} forms a linearly dependent set, i.e.∑
  ū∈S cūv(ū) = ~0 (B.3)
  for coefficients c. Then ∑ ū∈S cū sign(α ?(ū)) = 0.
  Proof. Let λ? be any dual optimal solution, then λ?>v(ū) = sign(α?(ū)) ∀ū ∈ 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(ū) : ū ∈ 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(ū) : ū ∈ 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 w1, . . . , wm ∈ R and bottom layer weights u1, . . . , um ∈ Rd. As before, we use Θ to refer to the collection of parameters, so the network computes the real-valued function
  f(Θ;x) = m∑ j=1 wjφ(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∑ ū∈supp(α?) |α?(ū)| ≤ 1. We construct Θ corresponding to a two-layer network with m ≥ n hidden units and normalized margin at least γ`12 . For clarity, we let W correspond to the top layer weights and U correspond to the bottom layer weights. For every ū ∈ supp(α), we let Θ have a corresponding
  hidden unit j with (wj , uj) = ( sign(α?(ū)) √ |α?(ū)| 2 , √ |α?(ū)| 2 ū ) , and set the remaining hidden
  units to ~0. This is possible because m ≥ n. Now
  f(Θ;x) = m∑ j=1 wjφ(u > j x) = 1 2 ∑ ū∈supp(α?) α?(ū)φ(ū>x)
  Furthermore,
  ‖Θ‖22 = m∑ j=1 w2j + ‖uj‖22 = ∑ ū∈supp(α) |α?(ū)| 2 + |α?(ū)| 2 ‖ū‖22 = ∑ ū∈supp(α) |α?(ū)| ≤ 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?,mj , u ?,m j ) for j ∈ [m]. We can construct α to put a scaled delta mass of 2w?,mj ‖u ?,m j ‖2 on ū ?,m j for j ∈ [m]. It follows that
  ‖α‖1 = m∑ j=1 2|w?,mj |‖u ?,m j ‖2 ≤ m∑ j=1 w?,mj 2 + ‖u?,mj ‖ 2 2 = ‖Θ?,m‖22 ≤ 1
  Furthermore, ∫ Sd−1 α(ū)φ(ū>x) = 2 m∑ j=1 w?,mj ‖u ?,m j ‖2φ((ū ?,m j ) >x)
  = 2 m∑ j=1 w?,mj φ(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.
sections.heading: C RADEMACHER COMPLEXITY AND GENERALIZATION ERROR
sections.text: 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 pdata supported on X × Y . For some hypothesis classF 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 if(xi) ] 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)∼pdata(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 (xi, yi)ni=1 be drawn iid from pdata. We work in the binary classification setting, so Y = {−1, 1}. Assume that for all f ∈ F , we have supx∈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(yif(xi) < γ) + 4R̂(F) γ +
  √ log log2 4C γ
  n +
  √ log(1/δ)
  2n
sections.heading: C.1 PROOF OF PROPOSITION 3.1
sections.text: 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 FK over depth-K neural networks by
  FK = { f(Θ; ·) : ‖Wj‖F ≤ 1√ K ∀j }
  Let C , supx∈X ‖x‖2. Recall that L(Θ) denotes the 0-1 population loss L(f(Θ; ·)). Then for any f(Θ; ·) ∈ FK classifying the training data correctly with unnormalized margin γΘ , mini yif(Θ;xi) > 0, with probability at least 1− δ,
  L(Θ) . C
  γΘK(K−1)/2 √ n +
  √ log log2 4C γΘ
  n +
  √ log(1/δ)
  n (C.1)
  Note the dependence on the unnormalized margin rather than the normalized margin.
  Proof. We first claim that supf(Θ;·)∈FK supx∈X f(Θ;x) ≤ C. To see this, for any f(Θ; ·) ∈ FK ,
  f(Θ;x) = WKφ(· · ·φ(W1x) · · · ) ≤ ‖WK‖F ‖φ(WK−1φ(· · ·φ(W1x) · · · )‖2 ≤ ‖WK‖F ‖WK−1φ(· · ·φ(W1x) · · · )‖2
  (since φ is 1-Lipschitz and φ(0) = 0, so φ performs a contraction) < ‖x‖2 ≤ C (repeatedly applying this argument and using ‖Wj‖F < 1)
  Furthermore, by Theorem 1 of Golowich et al. (2017), R̂(FK) has upper bound
  R̂(FK) . C
  K(K−1)/2 √ n
  Thus, we can apply Theorem C.1 to conclude that for all f(Θ; ·) ∈ FK and all γ > 0, with probability 1− δ,
  L(Θ) . 1
  n n∑ i=1 1(yif(Θ;xi) < γ) + C γK(K−1)/2 √ n +
  √ log log2 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 Θ = (W1, . . . ,WK), we first construct parameters Θ̃ = (W̃1, . . . , W̃K) such that f(Θ̄; ·) and f(Θ̃; ·) compute the same function, and ‖W̃1‖2F = ‖W̃2‖2F = · · · = ‖W̃K‖2F ≤ 1K . To do this, we set
  W̃j = ( ∏K k=1 ‖Wk‖F )1/k
  ‖Wj‖F ‖Θ‖F Wj
  By construction
  ‖W̃j‖2F = ( ∏K k=1 ‖Wk‖2F )1/k
  ‖Θ‖2F = ( ∏K k=1 ‖Wk‖2F )1/k∑K k=1 ‖Wk‖2F ≤ 1 k
  (by the AM-GM inequality)
  Furthermore, we also have
  f(Θ̃;x) = W̃Kφ(· · ·φ(W̃1x) · · · )
  = K∏ j=1 ( ∏K k=1 ‖Wk‖F )1/k ‖Wj‖F ‖Θ‖F WKφ(· · ·φ(W1x) · · · ) (by the homogeneity of φ)
  = 1
  ‖Θ‖KF 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(Θ̃; ·) ∈ FK . 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.
sections.heading: C.2 PROOF OF KERNEL GENERALIZATION BOUNDS
sections.text: Let F2,φB denote the class of `2-bounded linear functionals in lifted feature space: F 2,φ B , {x 7→ 〈α,ϕ(x)〉 : α ∈ L2(Sd−1), ‖α‖2 ≤ B}. We abuse notation and write α ∈ F2,φB to indicate a linear functional from F2,φB . As before, we will use L(α) to indicate the 0-1 population loss of the classifier x 7→ 〈α,ϕ(x)〉 and let C , supx∈X ‖x‖2 be an upper bound on the norm of the data. We focus on analyzing the Rademacher complexity R̂(F2,φB ), mirroring derivations done in the past (Bartlett & Mendelson, 2002). We include our derivations here for completeness.
  Lemma C.3. R̂(F2,φB ) ≤ 1 nB √∑n i=1 ‖ϕ(xi)‖22.
  Proof. We write
  R̂(F2,φB ) = 1
  n E i
  [ sup
  α∈F2,φB 〈α, n∑ i=1 iϕ(xi)〉
  ]
  ≤ 1 n E i
  [ sup
  α∈F2,φB
  ‖α‖2 ∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ 2 ]
  ≤ 1 n B · E i [∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ 2 ]
  ≤ 1 n B √√√√√E i ∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ 2
  2  (via Jensen’s inequality) ≤ 1 n B √√√√√E i  n∑ i=1 n∑ j=1 i j〈ϕ(xi), ϕ(xi)〉
   ≤ 1 n B √√√√ n∑ i=1 ‖ϕ(xi)‖22 (terms where i 6= 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(Sd−1). Then R̂(F2,φB ) . B‖X‖F √ κ
  n √ d ≤ BC
  √ κ√
  dn .
  Proof. We first show that ‖ϕ(xi)‖22 = Θ ( κ d‖xi‖ 2 2 ) . We can compute
  ‖ϕ(xi)‖22 = Vol(Sd−1)Eū∼Sd−1 [relu(ū>xi)2]
  = κ
  d Eū∼Sd−1 [relu(
  √ dū>xi) 2]
  = κ
  d
  1
  M2 Eu∼N (0,Id×d)[relu(u Txi) 2] (M2 is the second moment of N (0, 1)) = Θ (κ d ‖xi‖22 ) (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. Proof of Lemma 4.2. From equation C.2, we first obtain supx∈X ‖ϕ(x)‖2 . C √ κ d . Denote the optimizer for equation 4.3 by α`2 . Note that √ κα`2 ∈ F 2,φ 1 , and furthermore L(α`2) = L( √ κα`2).
  Since √ κα`2 has unnormalized margin √ κγ`2 , we apply Theorem C.1 on margin √ κγ`2 and hypothesis class F2,φ1 to get with probability 1− δ,
  L`2-svm = L( √ κα`2) ≤ 4R̂(F2,φ1 )√ κγ`2 +
  √ log log2
  4 supx∈X ‖ϕ(x)‖2√ κγ`2
  n +
  √ log(1/δ)
  2n
  . C
  γ`2 √ dn +
  √√√√ log max{log2 C√dγ`2 , 2} n + √ log(1/δ) n
  (applying Corollary C.4)
sections.heading: D MISSING PROOFS FOR COMPARISON TO KERNEL METHODS
sections.heading: D.1 CLASSIFICATION
sections.text: In this section we will complete a proof of Theorem 4.3. Recall the construction of the distribution D provided in Section 4. We first provide a classifier of this data with small `1 norm.
  Lemma D.1. In the setting of Theorem 4.3, we have that
  γ`1 ≥ √ 2
  4 .
  Proof. Consider the network f(x) = 14 ( (x>(e1 +e2)/ √ 2)+ +(x >(−e1−e2)/ √ 2)+− (x>(−e1 + e2)/ √ 2)+ − (x>(e1 − e2)/ √ 2)+ ) . The attained margin γ = √ 2 4 , so γ`1 ≥ √ 2 4 .
  Now we will upper bound the margin attainable by the `2 SVM.
  Lemma D.2 (Margin upper bound tool). In the setting of Theorem 4.3, we have
  γ`2 ≤ 1√ κ · ∥∥∥∥∥ 1n n∑ i=1 ϕ(xi)yi ∥∥∥∥∥ 2
  Proof. By the definition of γ`2 , we have that for any α with √ κ‖α‖2 ≤ 1, we have
  γ`2 ≤ max√ κ‖α‖2≤1
  1
  n n∑ i=1 〈α, yiϕ(xi)〉
  Setting α = 1√ κ 1 n ∑n i=1 ϕ(xi)yi/‖ 1 n ∑n i=1 ϕ(xi)yi‖2 completes the proof. (Attentive readers may realize that this is equivalent to setting the dual variable of the convex program 4.3 to all 1’s function.)
  Lemma D.3. In the setting of Theorem 4.3, let (xi, yi)ni=1 be n i.i.d samples and corresponding labels from D. Let ϕ be defined in equation 4.1 with φ = relu. With high probability (at least 1− dn−10), we have ∥∥∥∥∥ 1n n∑ i=1 ϕ(xi)yi ∥∥∥∥∥ 2 . √ κ/n log n+ √ κ/d
  Proof. Let Wi = ϕ(xi)yi. We will bound several quantities regarding Wi’s. In the rest of the proof, we will condition on the event E that ∀i, ‖xi‖22 . d log n. Note that E is a high probability event and conditioned on E, xi’s are still independent. We omit the condition on E in the rest of the proof for simplicity.
  We first show that assuming the following three inequalities that the conclusion of the Lemma follows.
  1. ∀i, ‖Wi‖22 . κ log n . 2. σ2 , Var[ ∑ iWi] , ∑n i=1 E[‖Wi − EWi‖22] . nκ log n
  3. ‖E [ ∑ Wi] ‖2 . √ κn/d.
  By bullets 1, 2, and Bernstein inequality, we have that with probability at least 1− dn−10 over the randomness of the data (X,Y ),∥∥∥∥∥ n∑ i=1 Wi − E [ n∑ i=1 Wi ]∥∥∥∥∥ 2 . √ κ log1.5 n+ √ nκ log2 n . √ nκ log2 n
  By bullet 3 and equation above, we complete the proof with triangle inequality:∥∥∥∥∥ n∑ i=1 Wi ∥∥∥∥∥ 2 ≤ ∥∥∥∥∥E [ n∑ i=1 Wi ]∥∥∥∥∥ 2 + √ nκ log2 n . √ nκ log2 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 L2(Sd−1) and the independence of (xi, yi)’s, we can rewrite∥∥∥∥∥E [ n∑ i=1 Wi ]∥∥∥∥∥ 2
  2
  = κ · n2 E ū∼Sd−1
  [ E
  (x,y)∼D ϕ(x)[ū] · y
  ]2 (D.1)
  Let ū = (ū1, . . . , ūd) and ū−2 = (ū3, . . . , ūd) ∈ Rd−2, and define τ , ‖ū−2‖2. Let x−2 = (x>e3, . . . , x
  >ed). Note that ϕ(x)[ū]y = y[ū1 · x>e1 + ū2 · x>e2 + ū>−2x−2] and ū>−2x−2 has distribution ‖ū−2‖2 · N (0, 1) = τ · N (0, 1). Let z = ū>−2x−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)[ū] · y = 1 4 E z∼N(0,1) [(ū1 + ū2 + τz)+] + 1 4 E z∼N(0,1) [(−ū1 − ū2 + τz)+]
  − 1 4 E z∼N(0,1) [(ū1 − ū2 + τz)+]− 1 4 E z∼N(0,1) [(+ū1 − ū2 + τz)+]
  By claim D.4, and the 1-homogeneity of relu, we can simplify the above equation to
  E (x,y)∼D ϕ(x)[ū] · y = 1 4 τ · ( 2c1 +O(min{|ū1 + ū2|/τ, |ū1 + ū2|2/τ2})
  −τ 4
  ( 2c1 −O(min{|ū1 − ū2|/τ, |ū1 − ū2|2/τ2}) )) . min{|ū1|+ |ū2|, (|ū1|+ |ū2|)2/τ}
  It follows that
  E ū∼Sd−1
  [ E
  (x,y)∼D ϕ(x)[ū] · y
  ]2 . Eū [ min{(|ū1|+ |ū2|)2, (|ū1|+ |ū2|)4/‖ū−2‖22} ] . Eū [ (|ū1|+ |ū2|)2 · 1[‖ū−2‖2 ≤ 1/2] ] + Eū [ (|ū1|+ |ū2|)4/‖ū−2‖22 · 1[‖ū−2‖2 ≥ 1/2]
  ] . exp(− √ d) + Eū [ (|ū1|+ |ū2|)4 ] . 1/d2 (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)[ū]y is bounded by |ū1| + |ū2| + ‖ū>−2x−2‖2. Therefore, conditioned on ‖xi‖2 . d log n
  ‖Wi‖22 ≤ E ū∼Sd−1
  [ (|ū1|+ |ū2|+ ‖ū>−2x−2‖2)2 ] . E ū∼Sd−1 [ |ū1|2 ] + E ū∼Sd−1 [ |ū2|2 ] + E ū∼Sd−1 [ ‖ū>−2x−2‖22
  ] . 1/d+ ‖x−2‖22/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 c1 and c2 such that |E [(a+ Z)+ + (−a+ Z)+]− 2c1| ≤ c2 min{|a|, a2}.
  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]] + 2E [Z · 1[Z ≥ a]] (by E [Z · 1[−a ≤ Z ≤ a]] = 0) = E [a1[−a ≤ Z ≤ a]] + 2E [Z · 1[Z ≥ 0]]− 2E [Z · 1[a ≥ Z ≥ 0]] = 2c1 +O(min{a, a2})
  where the last equality uses the fact that c1 , E [Z · 1[Z ≥ 0]] and E [a1[−a ≤ Z ≤ a]] ≤ aE [1[−a ≤ Z ≤ a]] . amin{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 pdata to be a slightly modified version of D: perform rejection sampling of (x, y) ∼ D until we obtain a sample with ‖x‖22 . d log n. Since this occurs with very high probability, the high probability result of Lemma D.3 still translates to pdata. Now apply Lemma D.2 to conclude that γ`2 . logn√ n + 1d . 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
sections.heading: D.2 REGRESSION
sections.text: We will first define the 1-norm and 2-norm regression problems. The regression equivalent of equation 4.2 for α ∈ L1(Sd−1) is as follows:
  α`1 ∈ arg min α ‖α‖1
  subject to 〈α,ϕ(xi)〉 = yi (D.3)
  Next we define the regression version of equation 4.3:
  α`2 ∈ arg min α ‖α‖2
  subject to 〈α,ϕ(xi)〉 = yi (D.4)
  where α ∈ L2(Sd−1). 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
  Lλ,m(Θ) , 1
  n n∑ i=1 (f(Θ;xi)− yi)2 + λ‖Θ‖22
  with Θλ,m ∈ arg minΘ Lλ,m(Θ). Suppose that equation D.3 is feasible with optimal solution α`1 . Then as λ→ 0, Lλ,m(Θλ,m)→ 0 and ‖Θλ,m‖22 → 2‖α`1‖1.
  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 7→ 〈α?, ϕ(x)〉 is implementable by a neural network Θ?,m with ‖Θ?,m‖22 = 2‖α?‖1 = 2‖α`1‖1. Following the same reasoning as before, we can also conclude that Θ?,m is an optimal solution for:
  min Θ ‖Θ‖22 subject to f(Θ;xi) = yi (D.5)
  Now we note that λ‖Θλ,m‖22 ≤ Lλ,m(Θλ,m) ≤ Lλ,m(Θ?,m) = λ‖Θ?,m‖22, 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(Θ;xi)− yi)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‖22 = ‖Θ?,m‖22.
  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 7→ 〈α,ϕ(x)〉 (for ϕ(x) defined in equation 4.1). Following the convention in Section C.2, define hypothesis class F1,φB , {fφ(α; ·) : α ∈ L1(Sd−1), ‖α‖1 ≤ B} of linear functionals bounded by B in 1-norm. As before, define F2,φB and let R̂(F) denote the empirical Rademacher complexity of hypothesis class F . We will first derive a Rademacher complexity bound for F1,φB .
  Claim D.6. R̂(F1,φB ) ≤ 1 nBE i [ ‖ ∑n i=1 iϕ(xi)‖∞ ] .
  Proof. We write
  R̂(F1,φB ) = 1
  n E i
  [ sup
  α∈F1,φB 〈α, n∑ i=1 iϕ(xi)〉
  ]
  ≤ 1 n E i
  [ sup
  α∈F1,φB
  ‖α‖1 ∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ ∞ ]
  ≤ 1 n B · E i [∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ ∞ ]
  We will now complete the bound on R̂(F1,φB ) for Lipschitz activations φ with φ(0) = 0. Claim D.7. Suppose that our activation φ is M -Lipschitz and φ(0) = 0.Then
  R̂(F1,φB ) ≤ 3BM √∑n i=1 ‖xi‖22 n
  Proof. We will show that
  E i [∥∥∥∥∥ n∑ i=1 iϕ(xi) ∥∥∥∥∥ ∞ ] ≤ 3M √√√√ n∑ i=1 ‖xi‖22
  from which the statement of the lemma follows via Claim D.6. Fix any ū′ ∈ Sd−1. Then we get the decomposition
  E i
  [ sup
  ū∈Sd−1 ∣∣∣∣∣ n∑ i=1 iφ(ū >xi) ∣∣∣∣∣ ] ≤ E i [∣∣∣∣∣ n∑ i=1 iφ(ū ′>xi) ∣∣∣∣∣ ] +
  E i
  [ sup
  ū∈Sd−1 ∣∣∣∣∣ n∑ i=1 iφ(ū >xi) ∣∣∣∣∣− infū∈Sd−1 ∣∣∣∣∣ n∑ i=1 iφ(ū >xi) ∣∣∣∣∣ ] (D.6)
  We can bound the first term as
  E i [∣∣∣∣∣ n∑ i=1 iφ(ū ′>xi) ∣∣∣∣∣ ] ≤ √√√√√E i ( n∑ i=1 iφ(ū′>xi) )2 ≤
  √√√√ n∑ i=1 φ(ū′>xi)2
  ≤M √√√√ n∑ i=1 (ū′>xi)2 (since φ is Lipschitz and φ(0) = 0)
  ≤M √√√√ n∑ i=1 ‖xi‖22 (D.7)
  We note that the second term of equation D.6 can be bounded by
  E i
  [ sup
  ū∈Sd−1 ∣∣∣∣∣ n∑ i=1 iφ(ū >xi) ∣∣∣∣∣− infū∈Sd−1 ∣∣∣∣∣ n∑ i=1 iφ(ū >xi) ∣∣∣∣∣ ]
  ≤ E i
  [ sup
  ū∈Sd−1 n∑ i=1 iφ(ū >xi)− inf ū∈Sd−1 n∑ i=1 iφ(ū >xi) ] 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 between the supremum and the infimum. Furthermore, by symmetry of the Rademacher random variables,
  E i
  [ sup
  ū∈Sd−1 n∑ i=1 iφ(ū >xi)− inf ū∈Sd−1 n∑ i=1 iφ(ū >xi) ] ≤ 2E i [ sup ū∈Sd−1 n∑ i=1 iφ(ū >xi) ] (D.8)
  This simply gives an empirical Rademacher complexity of the hypothesis class F , {x 7→ φ(ū>x) : ū ∈ Sd−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
  ū∈Sd−1 n∑ i=1 iφ(ū >xi)
  ] ≤ 2M √√√√ n∑ i=1 ‖xi‖22 (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 (xi, yi)ni=1 be drawn i.i.d from pdata. Then with probability at least 1− δ over the dataset, every α ∈ L1(Sd−1) satisfies
  E(x,y)∼pdata [l(f φ(α;x); y)] ≤
  1
  n n∑ i=1 l(fφ(α;xi); yi) + 12M max{1, ‖α‖1‖X‖F } n + c
  √ log(1/δ) + log(max{1, 2‖α‖1‖X‖F })
  2n
  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)∼pdata [l(f(x); y)] ≤ 1
  n n∑ i=1 l(f(xi); yi) + 2MR̂(F) + c √ log(1/δ) n (D.10)
  We define Bj , 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 F1,φBj using δj , δ 2j+1 . Then using a union bound, with probability 1− ∑∞ j=0 δj = 1− δ, for all j ≥ 0 and fφ(α; ·) ∈ F1,φBj
  E(x,y)∼pdata [l(f φ(α;x); y)] ≤ 1
  n n∑ i=1 l(fφ(α;xi); yi) + 2MR̂(F1,φBj ) + c √ log(1/δj) n
  ≤ 1 n n∑ i=1 l(fφ(α;xi); yi) + 6M 2j n + c
  √ log(1/δ) + log(2j+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 F1,φBj+1 , where 2 j ≤ ‖α‖1‖X‖F ≤ 2j+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 α ∈ L2(Sd−1) satisfies
  E(x,y)∼pdata [l(f φ(α;x); y)] .
  1
  n n∑ i=1 l(fφ(α;xi); yi) +M √ κmax{1, ‖α‖2‖X‖F } n √ d + c
  √ log(1/δ) + log(max{1, ‖α‖2‖X‖F })
  2n
  Proof. We proceed the same way as in the proof of Lemma D.8. We define Bj as before, and this time have R̂(F2,φBj ) . √ κ2j 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φ(α; ·) ∈ F2,φBj
  E(x,y)∼pdata [l(f φ(α;x); y)] .
  1
  n n∑ i=1 l(fφ(α;xi); yi) +M √ κ2j n √ d + c
  √ log(1/δ) + log(2j+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 , Ex,y∼pdata [l(fφ(α`1 ;x); y)] L`2-reg , Ex,y∼pdata [l(fφ(α`2 ;x); y)]
  Next, we will define the kernel matrix K with Kij = 〈ϕ(xi), ϕ(xj)〉. 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 pdata such that with probability 1,
  ‖α`1‖1 ≤ 1 On the other hand,
  E(xi,yi)ni=1∼iidpdata [‖α`2‖ 2 2] =
  n
  κ
  For i.i.d samples from this choice of pdata, 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‖22 ≥ 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 L1(Sd−1) such that for any dataset X with yi , 〈ϕ(xi), β〉 for β ∼ A,
  Eβ [‖α`2‖22] ≥ 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‖22. Claim D.12. If K is full rank, then ‖α`2‖22 = y>K−1y.
  Proof. This follows by taking the dual of equation D.4.
  Proof of Lemma D.11. We sample β ∼ A as follows: first sample ū ∼ Sd−1 uniformly. Then set β to have a delta mass of 1 at ū and be 0 everywhere else. Define the vector vū , [φ(ū>x1) · · ·φ(ū>xn)]; then it follows that we set our labels y to vū. It is immediately clear that ‖α`1‖1 ≤ ‖β‖1 ≤ 1. To lower bound Eβ [‖α`2‖22], from Claim D.12 we get
  Eβ∼A[‖α`2‖22] = Eū∼Sd−1 [v>ūK−1vū] = Eū∼Sd−1 [traceK −1(vūv > ū )]
  = trace(K−1Eū∼Sd−1 [vūv > ū ]
  = 1
  κ trace(K−1K) (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
  E(xi)ni=1∼iidN (0,Id×d) [ Eβ∼A[‖α`2‖22] ] = n
  κ Eβ∼A [ E(xi)ni=1∼iidN (0,Id×d)[‖α`2‖ 2 2] ] = n
  κ
  Thus, there exists β? such that if we sample X i.i.d. from the standard normal and set yi = 〈ϕ(xi), β?〉, the expectation of ‖α`2‖22 is at least nκ . We choose pdata corresponding to this β
  ?, with x sampled from the standard normal. Now it is clear that pdata 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)
sections.heading: E MISSING PROOFS IN SECTION 5
sections.heading: E.1 DETAILED SETUP
sections.text: We first write our regularity assumptions on Φ, R, and V in more detail:
  Assumption E.1 (Regularity conditions on Φ, R, V ). R is convex, nonnegative, Lipschitz, and smooth: ∃MR, CR such that ‖∇2R‖op ≤ CR, and ‖∇R‖2 ≤MR. Assumption E.2. Φ is differentiable, bounded and Lipschitz on the sphere: ∃BΦ,MΦ such that ‖Φ(θ̄)‖ ≤ BΦ ∀θ̄ ∈ Sd, and |Φi(θ̄)− Φi(θ̄′)| ≤MΦ‖θ̄ − θ̄′‖2 ∀θ̄, θ̄′ ∈ Sd. Assumption E.3. V is Lipschitz and upper and lower bounded on the sphere: ∃bV , BV ,MV such that 0 < bV ≤ V (θ̄) ≤ BV ∀θ̄ ∈ Sd, and ‖∇V (θ̄)‖2 ≤MV ∀θ̄ ∈ Sd.
  We state the version of Theorem 5.3 that collects these parameters:
  Theorem E.4 (Theorem 5.3 with problem parameters). Suppose that Φ and V are 2-homogeneous and Assumptions E.1, E.2, and E.3 hold. Fix a desired error threshold > 0. Suppose that from a starting distribution ρ0, a solution to the dynamics in equation 5.2 exists. Choose
  σ , exp(−d log(1/ )poly(k,MV ,MR,MΦ, bV , BV , CR, BΦ, L[ρ0]− L?))
  t , d2
  4 poly(log(1/ ), k,MV ,MR,MΦ, bV , BV , CR, BΦ, L[ρ0]− L?)
  Then it must hold that min0≤t≤t L[ρt]− infρ L[ρ] ≤ 2 .
sections.heading: E.2 PROOF OF THEOREM E.4
sections.text: Throughout the proof, it will be useful to keep track of Wt , √
  Eθ∼ρt [‖θ‖22], the second moment of ρt. We first introduce a general lemma on integrals over vector field divergences.
  Lemma E.5. For any h1 : Rd+1 → R, h2 : Rd+1 → Rd+1 and distribution ρ with ρ(θ) → 0 as ‖θ‖ → ∞, ∫
  h1(θ)∇ · (h2(θ)ρ(θ))dθ = −Eθ∼ρ[〈∇h1(θ), h2(θ)〉]
  Proof. The proof follows from integration by parts.
  We note that ρt will satisfy the boundedness condition of Lemma E.5 during the course of our algorithm - ρ0 starts with this property, and Lemma E.9 proves that ρt will continue to have this property. We therefore freely apply Lemma E.5 in the remaining proofs. We first bound the absolute value of L′[ρt] over the sphere by BL ,MRBΦ +BV .
  Lemma E.6. For any θ̄ ∈ Sd−1, t ≥ 0, |L′[ρt](θ̄)| ≤, BL.
  Proof. We compute |L′[ρt](θ̄)| = ∣∣∣∣〈∇R(∫ Φdρ) ,Φ(θ̄)〉+ V (θ̄)∣∣∣∣
  ≤ ∥∥∥∥∇R(∫ Φdρ)∥∥∥∥
  2
  ‖Φ(θ̄)‖2 + V (θ̄) ≤MRBΦ +BV
  Now we analyze the decrease in L[ρt].
  Lemma E.7. Under the perturbed Wasserstein gradient flow
  d dt L[ρt] = −σEθ∼ρt [L′[ρt](θ)] + σEθ̄∼Ud [L′[ρt](θ̄)]− Eθ∼ρt [‖v[ρt](θ)‖22]
  Proof. Applying the chain rule, we can compute
  d dt L[ρt] =
  〈 ∇R (∫ Φdρt ) , d
  dt
  ∫ Φdρt 〉 + d
  dt
  ∫ V dρt
  = d
  dt Eθ∼ρt [L′[ρt](θ)]
  = ∫ L′[ρt](θ)ρ ′ t(θ)dθ
  = −σ ∫ L′[ρt]dρt + σ ∫ L′[ρt]dU d − ∫ L′[ρt](θ)∇ · (v[ρt](θ)ρt(θ))dθ
  = −σEθ∼ρt [L′[ρt](θ)] + σEθ̄∼Ud [L′[ρt](θ̄)]− Eθ∼ρt [‖v[ρt](θ)‖22],
  where we use Lemma E.5 with h1 = L′[ρt] and h2 = v[ρt].
  Now we show that the decrease in objective value is approximately the average velocity of all parameters under ρt plus some additional noise on the scale of σ. At the end, we choose σ small enough so that the noise terms essentially do not matter.
  Corollary E.8. We can bound ddtL[ρt] by
  d dt L[ρt] ≤ σBL(W 2t + 1)− Eθ∼ρt [‖v[ρt](θ)‖22] (E.1)
  Proof. By homogeneity, and Lemma E.6, Eθ∼ρt [L′[ρt](θ)] = Eθ∼ρt [L′[ρt](θ̄)‖θ‖22] ≤ BLW 2t . We also get Eθ̄∼Ud [L′[ρt](θ̄)] ≤ BL since Ud is only supported on Sd. Combining these with Lemma E.7 gives the desired statement.
  Now we show that if we run the dynamics for a short time, the second moment of ρt will grow slowly, again at a rate that is roughly the scale of the noise σ.
  Lemma E.9. For all 0 ≤ t′ ≤ t, W 2t′ ≤ L[ρ0]+σtBL bV −tσBL .
  Proof. Let t∗ , arg maxt′∈[0,t]W 2 t′ . Integrating both sides of equation E.1, and rearranging, we get
  0 ≤ ∫ t∗
  0
  Eθ∼ρs [‖v[ρs](θ)‖22]ds ≤ L[ρ0]− L[ρt] + σBL ∫ t∗
  0
  (W 2s + 1)ds
  ≤ L[ρ0]− L[ρt∗ ] + t∗σBL(W 2t∗ + 1)
  Now since R is nonnegative, we apply L[ρt∗ ] ≥ Eθ∼ρt∗ [V (θ)] ≥ Eθ∼ρt∗ [V (θ̄)‖θ‖22] ≥ bVW 2t∗ . We now plug this in and rearrange to get W 2t′ ≤W 2t∗ ≤ L[ρ0]+t ∗σBL bV −t∗σBL ≤ L[ρ0]+tσBL bV −tσBL ∀0 ≤ t ′ ≤ t.
  Now let W 2 , L[ρ0]+σt BL bv−t σBL . By Lemma E.9, ∀0 ≤ t ≤ t , W 2 t ≤W 2 .
  The next statement allows us to argue that our dynamics will never increase the objective by too much.
  Lemma E.10. For any t1, t2 with 0 ≤ t1 ≤ t2 ≤ t , L[ρt2 ]− L[ρt1 ] ≤ σ(t2 − t1)BL(W 2 + 1).
  Proof. From Corollary E.8, ∀t ∈ [t1, t2] we have
  d dt L[ρt] ≤ σBL(W 2 + 1)
  Integrating from t1 to t2 gives the desired result.
  The following lemma bounds the change in expectation of a 2-homogeneous function over ρt. At a high level, we lower bound the decrease in our loss as a function of the change in this expectation.
  Lemma E.11. Let h : Rd+1 → R that is 2-homogeneous, with ‖∇h(θ̄)‖ ≤ M ∀θ̄ ∈ Sd and |h(θ̄)| ≤ B ∀θ̄ ∈ Sd. Then ∀0 ≤ t ≤ t , we have∣∣∣∣ ddt ∫ hdρ ∣∣∣∣ ≤ σB(W 2 + 1) +MW (− ddtL[ρt] + σBL(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θ + σ ∫ hdUd
  = −σ ∫ h(θ̄)‖θ‖22ρt(θ)dθ + σ ∫ hdUd − ∫ 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(θ)‖22]Eθ∼ρt [‖v[ρt](θ)‖22] (by Cauchy-Schwarz)
  ≤ √ Eθ∼ρt [‖∇h(θ̄)‖22‖θ‖22]Eθ∼ρt [‖v[ρt](θ)‖22] (by homogeneity of∇h)
  ≤MW √ Eθ∼ρt [‖v[ρt](θ)‖22] (since h is Lipschitz on the sphere)
  ≤MW ( − d dt L[ρt] + σBL(W 2 + 1) )1/2 (by Corollary E.8)
  Plugging this into equation E.3, we get that
  |Q′(t)| ≤ σB(W 2 + 1) +MW ( − d dt L[ρt] + σBL(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 c1 that is some polynomial in the problem constants.
  Lemma E.12. Define Q(t) , ∫
  Φdρt. For every θ̄ ∈ Sd and 0 ≤ t ≤ t + l ≤ t , ∃c1 , poly(k,CR, BΦ,MΦ, BL) such that
  |L′[ρt](θ̄)− L′[ρt+l](θ̄)| ≤ CRBΦ ∫ t+l t ‖Q′(t)‖1 (E.4)
  ≤ σlc1(W 2 + 1) + c1W √ l(L[ρt]− L[ρt+l] + σlc1(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 ) ,Φ(θ̄) 〉 = Φ(θ̄)>∇2R(Q(t))Q′(t) ≤ CRBΦ‖Q′(t)‖2 ≤ CRBΦ‖Q′(t)‖1 (E.6)
  Integrating and applying the same reasoning to −L′[ρt] gives us equation E.4. Now we apply Lemma E.11 to get
  ‖Q′(t)‖1 = k∑ i=1 ∣∣∣∣ ddt ∫ Φidρt ∣∣∣∣ ≤
  k∑ i=1
  [ σBΦ(W 2 + 1) +MΦW ( − d dt L[ρt] + σBL(W 2 + 1) )1/2]
  ≤ kσBΦ(W 2 + 1) + kMΦW ( − d dt L[ρt] + σBL(W 2 + 1) )1/2 We plug this into equation E.6 and then integrate both sides to obtain
  CRBΦ ∫ t+l t ‖Q′(t)‖1
  ≤ kσlCRB2Φ(W 2 + 1) + kCRBΦMΦW ∫ t+l t ( − d dt L[ρt] + σBL(W 2 + 1) )1/2 ≤ kσlCRB2Φ(W 2 + 1) + kCRBΦMΦW √ l(L[ρt]− L[ρt+l] + σlBL(W 2 + 1))1/2
  Using c1 , max{kCRB2Φ, kCRBΦMΦ, BL} gives the statement in the lemma.
  Now we also show that L′ is Lipschitz on the unit ball. For clarity, we let c2 , √ kMRMΦ +MV . Lemma E.13. For all θ̄, θ̄′ ∈ Sd,
  |L′[ρ](θ̄)− L′[ρ](θ̄′)| ≤ c2‖θ̄ − θ̄′‖2 (E.7)
  Proof. Using the definition of L′ and triangle inequality, |L′[ρ](θ̄)− L′[ρ](θ̄′)| ≤ ∥∥∥∥∇R(∫ Φdρ)∥∥∥∥
  2
  ‖Φ(θ̄)− Φ(θ̄′)‖2 + |V (θ̄)− V (θ̄′)|
  ≤ ( √ kMRMΦ +MV )‖θ̄ − θ̄′‖2 (by definition of MΦ,MR,MV )
  Now the remainder of the proof will proceed as follows: we show that if ρt is far from optimality, either the expected velocity of θ under ρt will be large in which case the loss decreases from Corollary E.8, or there will exist θ̄ such that L′[ρt](θ̄) 0. We will first show that in the latter case, the σUd noise term will grow mass exponentially fast in a descent direction until we make progress. Define K−τt , {θ̄ ∈ Sd : L′[ρt](θ̄) ≤ −τ}, the −τ -sublevel set of L′[ρt], and let m(S) , Eθ∼Ud [1(θ ∈ S)] be the normalized spherical area of the set S. Lemma E.14. If K−τt is nonempty, for 0 ≤ δ ≤ τ , logm(K−τ+δt ) ≥ −2d log c2δ .
  Proof. Let θ̄ ∈ K−τt . From Lemma E.13, L′[ρ](θ̄′) ≤ −τ + δ for all θ̄′ with ‖θ̄′ − θ̄‖2 ≤ δc2 . Thus, we have
  m(K−τ+δt ) ≥ Eθ̄′∼Ud [ 1[‖θ̄′ − θ̄‖2 ≤ δ
  c2 ] ] Now the statement follows by Lemma 2.3 of (Ball, 1997).
  Now we show that if a descent direction exists, the added noise will find it and our function value will decrease. We start with a general lemma about the magnitude of the gradient of a 2-homogeneous function in the radial direction. Lemma E.15. Let h : Rd+1 → R be a 2-homogeneous function. Then for any θ ∈ Rd+1, θ̄>∇h(θ) = 2‖θ‖2h(θ̄).
  Proof. We have h(θ + αθ̄) = (‖θ‖2 + α)2h(θ̄). Differentiating both sides with respect to α and evaluating the derivative at 0, we get θ̄>∇h(θ) = 2‖θ‖2h(θ̄), as desired.
  We state the lemma claiming that our objective will decrease if L′[ρt](θ̄) 0 for some θ̄ ∈ Sd. Lemma E.16. Choose
  l ≥ log(W 2 /σ) + 2d log 2c2 τ
  τ − σ + 1
sections.heading: If K−τt∗ is nonempty for some t
sections.text: ∗ satisfying t∗ + l ≤ t , then after l steps, we will have
  L[ρt∗+l] ≤ L[ρt∗ ]− (τ/4− σlc1(W 2 + 1))2
  lc21W 2
  + σlc1(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) , CRBΦ ∫ t∗+s t∗
  ‖Q′(t)‖1dt. Note that from Lemma E.12, for all θ̄ ∈ Sd 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 Ts , K −τ/2+z(s) t∗+s for 0 ≤ s ≤ l. We now argue that this set Ts does not shrink as t increases. Claim E.18. For all s′ > s, Ts′ ⊇ Ts.
  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 θ̄ ∈ Ts
  L′[ρt+s′ ](θ̄) ≤ L′[ρt+s](θ̄) + z(s′)− z(s) ≤ −τ/2 + z(s)− z(s) + z(s′) (by definition of Ts) ≤ −τ/2 + z(s′)
  which means that θ̄ ∈ Ts′ .
  Now we show that the weight of the particles in Ts grows very fast if z(k) is small. Claim E.19. Suppose that z(l) ≤ τ/4. Let T̃s = {θ ∈ Rd+1 : θ̄ ∈ Ts}. Define N(s) ,∫ T̃s ‖θ‖2dρt∗+s and β , exp(−2d log 2c2τ ). Then N ′(s) ≥ (τ − σ)N(s) + σβ.
  Proof. From the assumption z(l) ≤ τ4 , it holds that Ts ⊆ K −τ/4 t∗+s ∀s ≤ k. Since Ts is defined as a sublevel set, v[ρt∗+s](θ̄) points inwards on the boundary of Ts for all θ̄ ∈ Ts, and by 1-homogeneity of the gradient, the same must hold for all u ∈ T̃s.
  Now consider any particle θ ∈ T̃s. 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 ∈ T̃s. Now we compute∫
  T̃s ‖θ‖22dρt∗+s+ds = (1− σds) ∫ T̃s ‖θ + v[ρt∗+s](θ)ds‖22dρt∗+s + σds ∫ T̃s 1dUd
  ≥ (1− σds) ∫ T̃s (‖θ‖22 + 2θ>v[ρt∗+s](θ)ds)dρt∗+s + σm(K −τ/2+z(s) t∗+s )ds
  (E.9)
  Now we apply Lemma E.15, using the 2-homogeneity of F ′ and the fact that L′[ρt∗+s](θ̄) ≤ −τ/4 ∀θ ∈ T̃s
  ‖θ‖22 + 2θ>v[ρt∗+s](θ)ds = ‖θ‖22 − 4‖θ‖22L′[ρt∗+s](θ̄)ds ≥ ‖θ‖22(1 + τds) (E.10)
  Furthermore, since K−τ+z(s)t∗+s is nonempty by Claim E.17, we can apply Lemma E.14 and obtain
  m(K −τ/2+z(s) t∗+s ) ≥ β (E.11)
  Plugging equation E.10 and equation E.11 back into equation E.9, we get∫ T̃s ‖u‖22dρt∗+s+ds ≥ (1− σds)(1 + 2τds)N(s) + σβds
  Since we also have that T̃s+ds ⊇ T̃s, it follows that
  N(s+ ds) = ∫ T̃s+ds ‖u‖22dρt∗+s+ds ≥ (1− σds)(1 + τds)N(s) + σβds
  and so N ′(s) ≥ (τ − σ)N(s) + σβ.
  Now we are ready to prove Lemma E.16. Proof of Lemma E.16. If z(l) = CRBΦ ∫ t+l t ‖Q′(t)‖1 ≥ τ4 , then by rearranging the conclusion of Lemma E.12 we immediately get equation E.8.
  Suppose for the sake of contradiction that z(l) ≤ τ/4. From Claim E.19, it follows that N(1) ≥ σβ, andN(l) ≥ exp((τ−σ)(l−1))N(1). Thus, in log(W 2 /σ)+2d log 2c2 τ
  τ−σ +1 time,Wt∗+l ≥ N(l) ≥W 2 ,
  a contradiction. Therefore, it must be true that z(l) ≥ τ/4.
  The following lemma will be useful in showing that the objective will decrease fast when ρt is very suboptimal. Lemma E.20. For any time t with 0 ≤ t ≤ t , we have
  d dt L[ρt] ≤ σBL(W 2 + 1)−
  Eθ∼ρt [L′[ρt](θ)]2
  W 2 (E.12)
  Proof. We can first compute
  Eθ∼ρt [L′[ρt](θ)] = Eθ∼ρt [L′[ρt](θ̄)‖θ‖22]
  = 1
  2 Eθ∼ρt [‖θ‖2θ̄>v[ρt](θ)] (via Lemma E.15)
  ≤ 1 2
  √ Eθ∼ρt [‖θ‖22]Eθ∼ρt [‖v[ρt](θ)‖22] (by Cauchy-Schwarz)
  ≤ 1 2 W
  √ Eθ∼ρt [‖v[ρt](θ)‖22]
  Rearranging gives Eθ∼ρt [‖v[ρt](θ)‖22] ≥ Eθ∼ρt [L
  ′[ρt](θ)] 2
  W 2 , and plugging this into equation E.1 gives
  the desired result.
  Proof of Theorem E.4. Let L? denote the infimum infρ L[ρ], and let ρ? be an -approximate global minimizer of L: L[ρ?] ≤ L? + . (We define ρ? because a true minimizer of L might not exist.) Let W ? , Eθ∼ρ? [‖θ‖22]. We first note that since bVW ?
  2 ≤ L[ρ?] ≤ L[ρ0], W ?2 ≤ L[ρ0]/bV ≤W 2 . Now we bound the suboptimality of ρt: since L is convex in ρ,
  L[ρ?] ≥ L[ρt] + Eθ∼ρ? [L′[ρt](θ)]− Eθ∼ρt [L′[ρt](θ)]
  Rearranging gives L[ρt]− L[ρ?] ≤ Eθ∼ρt [L′[ρt](θ)]− Eθ∼ρ? [L′[ρt](θ)]
  ≤ Eθ∼ρt [L′[ρt](θ)]−W ? 2 min { min θ̄∈Sd−1 L′[ρt](θ̄), 0 } (E.13)
  Now let l , W 2 −2W 2 σ ( 2 log W 2 σ + 2d log 4W 2 c2 ) , which satisfies Lemma E.16 with the value of τ later specified. Suppose that there is a t with 0 ≤ t ≤ t − 2l and ∀t′ ∈ [t, t+ 2l], L[ρt′ ]− L? ≥ 2 . Then L[ρt′ ]− L[ρ?] ≥ . We will argue that the objective decreases when we are suboptimal:
  L[ρt]− L[ρt+2l] ≥ (E.14)
  min
  { ( /8W 2 − lσc1(W 2 + 1))2
  c21W 2 l
  − 3σlc1(W 2 + 1), l 2
  4W 2 − 2σlBL(W 2 + 1)
  } (E.15)
  Using equation E.13 and W ≥W ?, we first note that
  ≤ Eθ∼ρt′ [L ′[ρt′ ](θ)]−W 2 min { min θ̄∈Sd−1 L′[ρt′ ](θ̄), 0 } ∀t′ ∈ [t, t+ l]
  Thus, either minθ̄∈Sd L ′[ρt′ ](θ̄) ≤ − 2W?2 ≤ − 2W 2 , or Eθ∼ρt′ [L ′[ρt′ ](θ)] ≥ 2 . If ∃t ′ ∈ [t, t + l] such that the former holds, then the τ , 2W 2 sub-level set K −τ t′ is non-empty. Applying Lemma E.16 gives
  L[ρt′ ]− L[ρt′+l] ≥ ( /8W 2 − lσc1(W 2 + 1))2
  c21W 2 l
  − σlc1(W 2 + 1)
  Furthermore, from Lemma E.10, L[ρt+2l] − L[ρt′+l] ≤ σlc1(W 2 + 1) and L[ρt′ ] − L[ρt] ≤ σlBL(W 2 + 1), and so combining gives
  L[ρt]− L[ρt+2k] ≥ ( /8W 2 − lσc1(W 2 + 1))2
  c21W 2 l
  − 3σlc1(W 2 + 1) (E.16)
  In the second case Eθ∼ρt′ [L ′[ρt′ ](θ)] ≥ 2 , ∀t ′ ∈ [t, t+ l]. Therefore, we can integrate equation E.12 from t to t+ l in order to get
  L[ρt]− L[ρt+l] ≥ l 2
  4W 2 − σlBL(W 2 + 1)
  Therefore, applying Lemma E.10 again gives
  L[ρt]− L[ρt+2l] ≥ l 2
  4W 2 − 2σlBL(W 2 + 1) (E.17)
  Thus equation E.15 follows.
  Now recall that we choose σ , exp(−d log(1/ )poly(k,MV ,MR,MΦ, bV , BV , CR, BΦ, L[ρ0]− L[ρ?]))
  For the simplicity, in the remaining computation, we will use O(·) notation to hide polynomials in the problem parameters besides d, . We simply write σ = exp(−c3d log(1/ )). Recall our choice t , O(d 2 4 log 2(1/ )). It suffices to show that our objective would have sufficiently decreased in t steps. We first note that with c3 sufficiently large, W 2 = O(L[ρ0]/bv) = O(1). Simplifying our expression for l, we get that l = O(d log 1 ), so long as σW 2 = o( ), which holds for sufficiently large c3. Now let
  δ1 , ( /8W 2 − lσc1(W 2 + 1))2
  c21W 2 l
  − 3σlc1(W 2 + 1)
  δ2 , l 2
  4W 2 − 2σlBL(W 2 + 1)
  Again, for sufficiently large c3, the terms with σ become negligible, and δ1 = O( 2 l ) = O( 3
  d log(1/ ) ). Likewise, δ2 = O(d log(1/ )).
  Thus, if by time t we have not encountered 2 -optimal ρt, then we will decrease the objective by O( 3
  d log(1/ ) ) in O( d log 1 ) time. Therefore, a total of O(
  d2
  4 log 2(1/ )) time is sufficient to obtain
  accuracy.
sections.heading: E.3 DISCRETE-TIME OPTIMIZATION
sections.text: 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 CV -Lipschitz, respectively. Let ρt evolve according to the following discrete-time update:
  ρt+1 , ρt + η(−σρt + σUd −∇ · (v[ρt]ρt))
sections.heading: There exists a choice of
sections.text: σ , exp(−d log(1/ )poly(k,MV ,MR, bV , BV , CR, BΦ, CΦ, CV , L[ρ0]− L[ρ?])) η , poly(k,MV ,MR, bV , BV , CR, BΦ, CΦ, CV , L[ρ0]− L[ρ?])
  t , d2
  4 poly(k,MV ,MR, bV , BV , CR, BΦ, CΦ, CV , L[ρ0]− L[ρ?])
  such that min0≤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.
sections.heading: F ADDITIONAL MATERIAL ON EXPERIMENTS
sections.heading: F.1 DETAILED SETUP FOR FIGURE 2 EXPERIMENT
sections.text: 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.
sections.heading: F.2 DETAILED SETUP FOR FIGURE 3 EXPERIMENT
sections.text: 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 2i 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 27 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 2i 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 7→ ajrelu(wjx+ bj). We add ‖ · ‖22-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(wxi + b) for w2 + b2 = 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.
sections.heading: F.4 EXPERIMENTS ON CIFAR10 AND CIFAR100
sections.text: 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.