mlsanityData to 7 Oct 2026

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

arXiv 2103.01887 ↗First posted 2 Mar 2021stat.ML cs.LG math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

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: 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∈ℝd need not have independent coordinates). We then leverage our bounds to establish generalization guarantees for such networks through 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 33 of its 58 references that are in the map. First posted on arXiv 2 Mar 2021.

Builds on

33 of 58 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  5. 2017Exploring Generalization in Deep Learningcited by 595
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  7. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  8. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  9. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  10. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  11. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  12. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
21 more
  1. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  3. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  4. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  5. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  6. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  7. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  8. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  9. 2017Fisher-Rao Metric, Geometry, and Complexity of Neural Networkscited by 99
  10. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  11. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  12. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  13. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  14. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  15. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  16. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  17. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  18. 2019Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networkscited by 16
  19. 2019Mildly Overparametrized Neural Nets can Memorize Training Data Efficientlycited by 7
  20. 2016A Neural Network Alternative to Non-Negative Audio Modelscited by 5
  21. 2020Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomenacited by 5

Built on by

Not cited yet.