mlsanityData to 14 Oct 2026

Norm-based Generalization Bounds for Compositionally Sparse Neural Networks

arXiv 2301.12033 ↗First posted 28 Jan 2023cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate the Rademacher complexity of deep sparse neural networks, where each neuron receives a small number of inputs. We prove generalization bounds for multilayered sparse ReLU neural networks, including convolutional neural networks. These bounds differ from previous ones, as they consider the norms of the convolutional filters instead of the norms of the associated Toeplitz matrices, independently of weight sharing between neurons. As we show theoretically, these bounds may be orders of magnitude better than standard norm-based generalization bounds and empirically, they are almost non-vacuous in estimating generalization in various simple classification problems. Taken together, these results suggest that compositional sparsity of the underlying target function is critical to the success of deep neural networks.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 35 of its 61 references that are in the map. First posted on arXiv 28 Jan 2023.

Builds on

35 of 61 references.

References · 35

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  6. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  7. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  8. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  9. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  10. 2021Scaling Vision Transformerscited by 999
  11. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  12. 2017Exploring Generalization in Deep Learningcited by 600
23 more
  1. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  2. 2016Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networkscited by 543
  3. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  4. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  5. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  6. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  7. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  8. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  9. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  10. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  11. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 126
  12. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 122
  13. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 76
  14. 2019Theoretical Issues in Deep Networks: Approximation, Optimization and Generalizationcited by 72
  15. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  16. 2019Generalization bounds for deep convolutional neural networkscited by 59
  17. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  18. 2019AlphaStar: An Evolutionary Computation Perspectivecited by 50
  19. 2019Why ResNet Works? Residuals Generalizecited by 39
  20. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 26
  21. 2018On Tighter Generalization Bound for Deep Neural Networks: CNNs, ResNets, and Beyondcited by 24
  22. 2018How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?cited by 19
  23. 2019Generalization Bounds for Neural Networks via Approximate Description Lengthcited by 15

Built on by

Cited by year (2026 to 14 Oct)

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

7 papers.

  1. 2023Deep networks for system identification: a Surveycited by 37
  2. 2025Parameter Symmetry Potentially Unifies Deep Learning Theorycited by 12
  3. 2023A path-norm toolkit for modern networks: consequences, promises and challengescited by 10
  4. 2023Sparsity-aware generalization theory for deep neural networkscited by 8
  5. 2024How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learningcited by 6
  6. 2026Learning Sparse Compositional Functions with Norm-Constrained Neural Networkscited by 3
  7. 2023Generalization Bounds for Magnitude-Based Pruning via Sparse Matrix Sketchingcited by 0