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. 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; BID17 Li et al., 2018; BID16 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 BID5 Neyshabur et al., 2017a; BID14 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 ( FIG3 ) 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; BID10 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. 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; BID8 BID9 ) 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 BID15 Soudry et al., 2018; Nacson et al., 2018; BID17 Li et al., 2018; BID16 ) 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. 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. 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. DISPLAYFORM0 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 Θ λ .
We show that training feedforward relu networks with a weak regularizer results in a maximum margin and analyze the implications of this result. Studies margin theory for neural sets  and shows that max margin is monotonically increasing in size of the network This paper studies the implicit bias of minimizers of a regularized cross entropy loss of a two-layer network with ReLU activations, obtaining a generalization upper bound which does not increase with the network size.