Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks

Abstract

We consider the problem of finding a two-layer neural network with sigmoid, rectified linear unit (ReLU), or binary step activation functions that "fits" a training data set as accurately as possible as quantified by the training error; and study the following question: \emph{does a low training error guarantee that the norm of the output layer (outer norm) itself is small?} We answer affirmatively this question for the case of non-negative output weights. Using a simple covering number argument, we establish that under quite mild distributional assumptions on the input/label pairs; any such network achieving a small training error on polynomially many data necessarily has a well-controlled outer norm. Notably, our results (a) have a polynomial (in $d$) sample complexity, (b) are independent of the number of hidden units (which can potentially be very high), (c) are oblivious to the training algorithm; and (d) require quite mild assumptions on the data (in particular the input vector $X\in {\mathbb{R}}^d$ need not have independent coordinates). We then leverage our bounds to establish generalization guarantees for such networks through \emph{fat-shattering dimension}, a scale-sensitive measure of the complexity class that the network architectures we investigate belong to. Notably, our generalization bounds also have good sample complexity (polynomials in $d$ with a low degree), and are in fact near-linear for some important cases of interest.

arXiv comment34 pages. Some of the results in the present paper are significantly strengthened versions of certain results appearing in arXiv:2003.10523

References in corpus (29)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Understanding deep learning requires rethinking generalization
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Exploring Generalization in Deep Learning
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Spectrally-normalized margin bounds for neural networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Stronger generalization bounds for deep nets via a compression approach
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Norm-Based Capacity Control in Neural Networks
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Learning One Convolutional Layer with Overlapping Patches
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena