mlsanityData to 7 Oct 2026

On Size-Independent Sample Complexity of ReLU Networks

arXiv 2306.01992 ↗First posted 3 Jun 2023cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of learning ReLU neural networks from the point of view of generalization. Given norm constraints on the weight matrices, a common approach is to estimate the Rademacher complexity of the associated function class. Previously Golowich-Rakhlin-Shamir (2020) obtained a bound independent of the network size (scaling with a product of Frobenius norms) except for a factor of the square-root depth. We give a refinement which often has no explicit depth-dependence at all.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 9 of its 16 references that are in the map. First posted on arXiv 3 Jun 2023.

Builds on

9 of 16 references.

References · 9

  1. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  2. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  3. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  4. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  5. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  7. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  8. 2019Generalization bounds for deep convolutional neural networkscited by 58
  9. 2019On Generalization Bounds of a Family of Recurrent Neural Networkscited by 42

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 1; 2026: 1.

6 papers.

  1. 2023Improved Sample Complexity Bounds for Diffusion Model Trainingcited by 13
  2. 2023Size Lowerbounds for Deep Operator Networkscited by 6
  3. 2024How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learningcited by 6
  4. 2024Public-data Assisted Private Stochastic Optimization: Power and Limitationscited by 5
  5. 2025DFNN: A Deep Fr'echet Neural Network Framework for Learning Metric-Space-Valued Responsescited by 2
  6. 2026Dimension-invariant uniform consistency of the empirical spatial distribution function and its associated spatial depth estimatorcited by 0