# Generalization Bounds for Neural Networks via Approximate Description Length

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2019.

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

- [Provably End-to-end Label-Noise Learning without Anchor Points](https://mlsanity.com/paper/2102.02400/) (2021)
- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation](https://mlsanity.com/paper/2211.09634/) (2022)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Dirichlet-based Per-Sample Weighting by Transition Matrix for Noisy Label Learning](https://mlsanity.com/paper/2403.02690/) (2024)
- [Depth Separation in Norm-Bounded Infinite-Width Neural Networks](https://mlsanity.com/paper/2402.08808/) (2024)
- [Learning Causal Transition Matrix for Instance-dependent Label Noise](https://mlsanity.com/paper/2412.13516/) (2024)
- [Approximate Description Length, Covering Numbers, and VC Dimension](https://mlsanity.com/paper/2209.12882/) (2022)
- [Generalization Bounds for Magnitude-Based Pruning via Sparse Matrix Sketching](https://mlsanity.com/paper/2305.18789/) (2023)
- [Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data](https://mlsanity.com/paper/2502.18167/) (2025)
- [Overfitting has a limitation: a model-independent generalization gap bound based on R'enyi entropy](https://mlsanity.com/paper/2506.00182/) (2025)
- [Data-Driven Deep MIMO Detection:Network Architectures and Generalization Analysis](https://mlsanity.com/paper/2602.20178/) (2026)
- [Width-Robust Learnability in Mean-Field Bayesian Neural Networks](https://mlsanity.com/paper/2607.05735/) (2026)

## Abstract (arXiv)

We investigate the sample complexity of networks with bounds on the magnitude of its weights. In particular, we consider the class [ H=leftWtcircρcirc ldotscircρcirc W1 :W1,ldots,Wt-1∈ Md, d, Wt∈ M1,dright ] where the spectral norm of each Wi is bounded by O(1), the Frobenius norm is bounded by R, and ρ is the sigmoid function fracex1+ex or the smoothened ReLU function  ln (1+ex). We show that for any depth t, if the inputs are in [-1,1]d, the sample complexity of H is tilde Oleft(fracdR2ε2right). This bound is optimal up to log-factors, and substantially improves over the previous state of the art of tilde Oleft(fracd2R2ε2right). We furthermore show that this bound remains valid if instead of considering the magnitude of the Wi's, we consider the magnitude of Wi - Wi0, where Wi0 are some reference matrices, with spectral norm of O(1). By taking the Wi0 to be the matrices at the onset of the training process, we get sample complexity bounds that are sub-linear in the number of parameters, in many typical regimes of parameters. To establish our results we develop a new technique to analyze the sample complexity of families H of predictors. We start by defining a new notion of a randomized approximate description of functions f:X→ℝd. We then show that if there is a way to approximately describe functions in a class H using d bits, then d/ε2 examples suffices to guarantee uniform convergence. Namely, that the empirical loss of all the functions in the class is ε-close to the true loss. Finally, we develop a set of tools for calculating the approximate description length of classes of functions that can be presented as a composition of linear function classes and non-linear functions.