SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data

By Alon Brutzkus, Amir Globerson, Eran Malach, Shai Shalev-Shwartz. 2017

287 citations recorded by the source corpus.

Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.

Subfields: Artificial Intelligence, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, positive): “The accumulation of dense mixture is consistent with the finding [23] (for linearly-separable data).”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “For linearly separable datasets, [55, 27, 14, 32, 33] show that first-order methods find solutions that generalize well without an explicit regularization for logistic regression.”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Since the ReLU activation is positive homogeneous, the effect of overparameterization can still be studied, and a similar approach has been adopted in previous work [7].”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “ve to the landscape approach is a direct analysis of the trajectories taken by the optimizer. Various papers (e.g. Brutzkus and Globerson (2017); Li and Yuan (2017); Zhong et al. (2017); Tian (2017); Brutzkus et al. (2018); Li et al. (2018); Du et al. (2018c;b); Liao et al. (2018)) have recently ado”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “]. Also, studying non-linear activations is critical because otherwise one can only learn linear functions, which can also be easily learned via linear models without neural networks. Brutzkus et al. [18] prove that two-layer networks with ReLU activations can learn linearlyseparable data (and thus ”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Our result can be applied to a broad family of loss functions, as opposed to cross entropy loss studied in Li and Liang (2018) and quadratic loss considered in Du et al. (2018b). • We also prove a similar convergence result for SGD.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Another relevant work is Brutzkus et al. [8] where the authors studied over-paramterization in the case of two-layer neural network under a linear-separable assumption.”
Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization (2019, background): “, 2018), and to the implicit regularization properties of SGD (Brutzkus et al., 2017; Zhang et al., 2018a; Poggio et al., 2017), though a thorough theoretical understanding is not yet complete.”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, methodology): “If a non-linear network is obtained by composing transformations, each of which is chosen from a Hilbert space of functions (as in Daniely et al. (2016)), then a step in “function space” corresponds to a step in an (infinite-dimensional) linear space of functions. Related work. The motivation for th”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “A line of research focused on analyzing gradient descent dynamics for (convolutional) neural networks with one or two unknown layers [Tian, 2017, Brutzkus and Globerson, 2017, Du et al., 2017a,b, Zhong et al., 2017, Li and Yuan, 2017, Ma et al., 2017, Brutzkus et al., 2017].”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Brutzkus et al. (2017) showed that SGD learns overparameterized networks that provably generalize on linearly separable data.”
Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex (2018, background): “When τ = 1 , it reduces to the classic hinge loss [43, 17, 38].”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects (2018, background): “…are ﬁxed during training; (2) the output of neural network is bounded during the training, f Then, we have the following relationship between Fisher F and Hessian H almost everywhere: Note that as shown in [2], the neural network appears in Proposition (4) is non-convex, and has multiple minima.”
Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks (2019, background): “[7] showed that stochastic gradient descent (SGD) can learn an over-parameterized two-layer neural network with good generalization for linearly separable data.”
Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience (2019, background): “This observation has spurred an active line of research (Neyshabur et al., 2015; Soudry et al., 2018; Brutzkus et al., 2018) that has tried to understand what properties are possessed by stochastic gradient descent (SGD) training of deep networks that allows these networks to generalize well.”
On the Margin Theory of Feedforward Neural Networks (2018, background): “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.”
SupportNet: solving catastrophic forgetting in class incremental learning with support data (2018, background): “Secondly, because the deep learning model has very high expressibility (Brutzkus et al. , 2017) while the support data are often of limited size, the model is very likely to become overﬁtting.”