# Norm-based Generalization Bounds for Compositionally Sparse Neural Networks

arXiv: https://arxiv.org/abs/2301.12033 · HTML: https://mlsanity.com/paper/2301.12033/

## 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 (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Scaling Vision Transformers](https://mlsanity.com/paper/2106.04560/) (2021)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks](https://mlsanity.com/paper/1602.07868/) (2016)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization](https://mlsanity.com/paper/1908.09375/) (2019)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience](https://mlsanity.com/paper/1905.13344/) (2019)
- [AlphaStar: An Evolutionary Computation Perspective](https://mlsanity.com/paper/1902.01724/) (2019)

## Built on by (most cited first, 7 of 7)

- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [Parameter Symmetry Potentially Unifies Deep Learning Theory](https://mlsanity.com/paper/2502.05300/) (2025)
- [A path-norm toolkit for modern networks: consequences, promises and challenges](https://mlsanity.com/paper/2310.01225/) (2023)
- [Sparsity-aware generalization theory for deep neural networks](https://mlsanity.com/paper/2307.00426/) (2023)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [Generalization Bounds for Magnitude-Based Pruning via Sparse Matrix Sketching](https://mlsanity.com/paper/2305.18789/) (2023)

## 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.