stat.MLNov 14, 2026

Generalization Bounds for Neural Networks with Sparse Connectivity

Authors: Nong Minh Hieu, Antoine Ledent

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 ℓp\ell_p quasi-norm (0<p≤10<p\leq 1) 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 pp 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

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Apr 1, 2026

Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks

Overparameterized neural networks often show a benign overfitting property in the sense of achieving excellent generalization behavior despite the number of parameters exceeding the number of training examples. A promising direction to explain benign overfitting is to relate generalization to the norm of distance from initialization, motivated by the empirical observations that this distance is often significantly smaller than the norm itself. However, the existing initialization-dependent complexity analyses measure the distance from initialization by the Frobenius norm, and often imply vacuous bounds in practice for overparamterized models. In this paper, we develop initialization-dependent complexity bounds for shallow neural networks with general Lipschitz activation functions. Our bounds depend on the path-norm of the distance from initialization, which are derived by introducing a new peeling technique to handle the challenge along with the initialization-dependent constraint. We also develop a lower bound tight up to a constant factor. Finally, we conduct empirical comparisons and show that our generalization analysis implies non-vacuous bounds for overparameterized networks.
May 18, 2026

Pointwise Generalization in Deep Neural Networks

We address the fundamental question of why deep neural networks generalize by establishing a pointwise generalization theory for fully connected networks. This framework resolves long-standing barriers to characterizing the rich nonlinear feature-learning regime and builds a new statistical foundation for representation learning. For each trained model, we characterize the hypothesis via a pointwise Riemannian Dimension, derived from the eigenvalues of the learned feature representations across layers. This establishes a principled framework for deriving hypothesis-dependent, representation-aware generalization bounds. These bounds offer a systematic upgrade over approaches based on model size, products of norms, and infinite-width linearizations, yielding guarantees that are orders of magnitude tighter in both theory and experiment. Analytically, we identify the structural properties and mathematical principles that explain the tractability of deep networks. Empirically, the pointwise Riemannian Dimension exhibits substantial feature compression, decreases with increased over-parameterization, and captures the implicit bias of optimizers. Taken together, our results indicate that deep networks are mathematically tractable in practical regimes and that their generalization is sharply explained by pointwise, feature-spectrum-aware complexity.
Sep 8, 2026

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the one-hidden-layer ReLU model of Awasthi et al. (COLT 2024). For width ss, at most kk active units per input, and effective weight and bias bounds W,BW,B, every size-mm sample in the class's fixed radius-RR input domain satisfies R(S)≤CWRmin⁡{k,sk/mlog⁡3/2(2m)}+kB/m\mathcal{R}(S)\le CWR\min\{k,\sqrt{sk/m}\log^{3/2}(2m)\}+kB/\sqrt m. A support-preserving cover and a single normalized chaining argument remove the previous explicit dimension factor, up to logarithms. Lower bounds on appropriate i.i.d. marginals match up to those logarithms, showing how changing active units across inputs retains a width dependence. The input domain matters: zero-bias networks sparse on the entire ball have at most 2k2k nonzero units and complexity O(kWR/m)O(kWR/\sqrt m), whereas bias bounds comparable to WRWR restore the worst-case rate on that same domain in only logarithmic dimension. A spherical-cap construction proves the latter claim without assuming sparsity merely on the sampling support. For a specified normalized bounded loss and biases comparable to WRWR, we also obtain agnostic minimax excess-risk bounds of order min⁡{1,s/(km)}\min\{1,\sqrt{s/(km)}\} up to logarithms.