mlsanityData to 7 Oct 2026

Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks

arXiv 2404.18769 ↗First posted 29 Apr 2024stat.ML cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks as the curse of dimensionality (CoD) cannot be evaded when trying to approximate even a single ReLU neuron (Bach, 2017). In this paper, we study a suitable function space for over-parameterized two-layer neural networks with bounded norms (e.g., the path norm, the Barron norm) in the perspective of sample complexity and generalization properties. First, we show that the path norm (as well as the Barron norm) is able to obtain width-independence sample complexity bounds, which allows for uniform convergence guarantees. Based on this result, we derive the improved result of metric entropy for ε-covering up to O(ε^-frac2dd+2) (d is the input dimension and the depending constant is at most linear order of d) via the convex hull technique, which demonstrates the separation with kernel methods with Omega(ε-d) to learn the target function in a Barron space. Second, this metric entropy result allows for building a sharper generalization bound under a general moment hypothesis setting, achieving the rate at O(n^-fracd+22d+2). Our analysis is novel in that it offers a sharper and refined estimation for metric entropy with a linear dimension dependence and unbounded sampling in the estimation of the sample error and the output error.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 55 of its 98 references that are in the map. First posted on arXiv 29 Apr 2024.

Builds on

55 of 98 references.

References · 55

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  4. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 431
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  7. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  8. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  9. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 160
  10. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  11. 2019Linearized two-layers neural networks in high dimensioncited by 155
  12. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
38 more
  1. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  2. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  3. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  4. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 113
  5. 2019How do infinite width bounded norm networks look in function space?cited by 105
  6. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  7. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
  8. 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
  9. 2016Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ℓ1 and ℓ0 Controlscited by 84
  10. 2018A Priori Estimates of the Population Risk for Two-layer Neural Networkscited by 76
  11. 2020Representation formulas and pointwise properties for Barron functionscited by 62
  12. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  13. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  14. 2021Understanding neural networks with reproducing kernel Banach spacescited by 50
  15. 2019Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov spacecited by 46
  16. 2021Near-Minimax Optimal Estimation With Shallow ReLU Neural Networkscited by 40
  17. 2018A representer theorem for deep neural networkscited by 38
  18. 2015A Three-Operator Splitting Scheme and its Optimization Applicationscited by 34
  19. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  20. 2016Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networkscited by 26
  21. 2020Concentration Inequalities for Statistical Inferencecited by 24
  22. 2021Foolish Crowds Support Benign Overfittingcited by 24
  23. 2020Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspectivecited by 22
  24. 2020Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernelscited by 19
  25. 2021Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measurescited by 19
  26. 2014Convergence of Stochastic Proximal Gradient Algorithmcited by 17
  27. 2020A Functional Perspective on Learning Symmetric Functions with Neural Networkscited by 16
  28. 2021On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Settingcited by 16
  29. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
  30. 2022Duality for Neural Networks through Reproducing Kernel Banach Spacescited by 15
  31. 2023Optimal rates of approximation by shallow ReLUk neural networks and applications to nonparametric regressioncited by 15
  32. 2019Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variationcited by 14
  33. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 12
  34. 2022The Sample Complexity of One-Hidden-Layer Neural Networkscited by 10
  35. 2022Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methodscited by 10
  36. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  37. 2020Reproducing Kernel Hilbert Spaces Cannot Contain all Continuous Functions on a Compact Metric Spacecited by 6
  38. 2019A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functionscited by 4

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 4.

8 papers.

  1. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 14
  2. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
  3. 2026Shallow ReLUs Networks in Lp-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalizationcited by 2
  4. 2025Statistical Learning Guarantees for Group-Invariant Barron Functionscited by 1
  5. 2025On the Koopman-Based Generalization Bounds for Multi-Task Deep Learningcited by 1
  6. 2026Operator-Theoretic Generalization Bounds for Multitask Deep Learningcited by 1
  7. 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networkscited by 0
  8. 2026Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networkscited by 0