Generalization Bounds for Neural Networks with Sparse Connectivity
Organizations: School of Computing and Information Systems, Singapore Management University
Abstract
Empirical evidence suggests that large neural networks rarely make effective use of all available parameters, with learned solutions exhibiting pronounced sparsity. Despite this ubiquity, existing generalization theory only partially explains how such sparsity influences statistical performance. In this paper, we derive non-asymptotic generalization gap bounds for deep neural networks whose layer-wise weight matrices are restricted by quasi-norm () constraints. Our analysis gives rise to a novel result that interpolates between classical norm-based generalization guarantees and parameter-counting bounds. Remarkably, in the extreme sparsity limit as the quasi-norm order approaches zero, our analysis reveals a transition to a square-root dependence on the number of active (non-zero) parameters, resulting in bounds that are strictly tighter than existing parameter-counting approaches. Experiments demonstrate that our bounds exhibit a milder dependence on initial architectural choice at the over-parametrization regime, effectively capturing the generalization benefit of the sparsity arising from training on natural data.
Figures & tables
| Arch. | Results | Dominant Term |
| DNNs | Thm. 3.1 | |
| DNNs | Thm. 3.3 | |
| CNNs | Thm. 3.4 | |
| CNNs | Thm. 3.5 | |
| CNNs & DNNs | Thm. 3.2 | (Limiting case as ) |
| Notation | DNNs | CNNs |
| Margin of the ramp loss , generalization gap of | ||
| Quasi-norm order of layer ( ) chosen after training; | ||
| Width of layer ( : input dim, : classes) | Patch size at layer , i.e., | |
| — | channels and spatial dimension of layer- feature map | |
| — | Convolutional patches | |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| Ntn. | Description |
| Frequently-used Notations | |
| Input data space | |
| Number of classes | |
| A joint distribution over | |
| , i.e., the dataset drawn i.i.d. from over | |
| , i.e., the maximum -norm of data points in | |
| Technique | Generalization Bound | Reference |
| Norm-based (Covering) | [ 3 ] | |
| Norm-based (PAC-Bayes) | [ 35 ] | |
| Norm-based (PAC-Bayes) | [ 34 ] | |
| Norm-based (Peeling) | [ 14 ] | |
| Norm-based (Peeling) | [ 14 ] | |
| Norm-based (Peeling) | [ 38 ] |
Neural Network Generalization
Neural network generalization studies why trained models perform well on unseen data and how architecture, data, and training shape that ability.
See all 324 papers