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

Yunwen Lei; Yufeng Xie

cs.LGApr 1, 2026

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

Authors: Yunwen Lei, Yufeng Xie

Organizations: Department of Mathematics, The University of Hong Kong

Abstract

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.

Figures & tables

#	Reference	Activation	Bound	D
(1)	[ 5 ]	Piecewise linear	$\widetilde{O}(\sqrt{dm})$	$-$
(2)	[ 7 ]	Lipschitz	$\widetilde{O}\big(\\|\mathbf{W}\\|_{\infty,1}\\|\mathbf{V}\\|_{\infty,1}\big)$	✓
(3)	[ 40 ]	ReLU	$\widetilde{O}\big(\sum_{j=1}^{m}\|v_{j}\|\\|\mathbf{w}_{j}\\|_{2}\big)$	$-$
(4)	[ 17 ]	ReLU	$\widetilde{O}\big(\\|\mathbf{W}\\|_{F}\\|\mathbf{V}\\|_{F}\big)$	✓
(5)	[ 4 ]	Lipschitz	$\widetilde{O}\big(\\|\mathbf{W}\\|_{\sigma}\\|\mathbf{V}-\mathbf{V}^{(0)}\\|_{1,2}+\\|\mathbf{W}-\mathbf{W}^{(0)}\\|_{1,2}\\|\mathbf{V}\\|_{\sigma}\big)$	✓
(6)	[ 37 ]	ReLU	$\widetilde{O}\big(\\|\mathbf{W}\\|_{\sigma}\\|\mathbf{V}-\mathbf{V}^{(0)}\\|_{F}+\sqrt{m}\\|\mathbf{W}-\mathbf{W}^{(0)}\\|_{F}\\|\mathbf{V}\\|_{\sigma}\big)$	$-$

Table 1: Comparison with existing generalization bounds for two-layer networks with constant number of outputs. For the column ‘D’, ‘✓’ means data-dependent bounds, while ‘

-

’ means data-independent bounds. We ignore a factor of

{\|\mathbf{X}\|_{F}}/{n}

for data-dependent bounds, and a factor of

\sup_{\mathbf{x}}\|\mathbf{x}\|_{2}/\sqrt{n}

for data-independent bounds (note

{\|\mathbf{X}\|_{F}}/{n}\leq\sup_{\mathbf{x}}\|\mathbf{x}\|_{2}/\sqrt{n}

). For simplicity, we assume

c=1

here.

Panel of Figure 1 — Figure 1: Behavior of $\frac{\|V\|_{F}}{n}\big(\sum_{j=1}^{m}\sum_{i=1}^{n}\gamma^{2}(\mathbf{x}_{i}^{\top}\mathbf{w}_{j}^{(0)})\big)^{\frac{1}{2}}$ , $\|V\|_{F}(G_{\gamma}b_{x}\|\mathbf{W}^{(0)}\|_{\sigma})/\sqrt{n}$ , and path norm with respect to the number of hidden units $m$ on the MNIST dataset. The gray area represents the value range under different random trials.

Panel of Figure 2 — Figure 2: Dominant terms in the generalization bounds summarized in Table 1 on MNIST dataset. The gray area represents the value range under different random trials.

Panel of Figure 3 — Figure 3: The comparison of existing generalization bounds with all the terms and constants across the MNIST and Cifar10 datasets. The gray area represents the value range under different random trials. The label corresponds to the index number in Table 1 . SPN denotes generalization bounds based on standard path norm, i,e., Eq. ( 5.2 ), and PN means our generalization bounds based on path norm, i.e., Eq. ( 6.20 ).

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 154 papers

A Generalization Bound for Nearly-Linear Networks
Jul 9, 2024Eugene GolikovNeural Network Generalization Generalization Bounds
Chair of Statistical Field Theory École Polytechnique Fédérale de Lausanne (EPFL)
Implicit Regularization and Generalization in Overparameterized Neural Networks
Apr 8, 2026Zeran JohannsenOverparameterized Neural Network Neural Network Generalization
Pointwise Generalization in Deep Neural Networks
May 18, 2026Shaojie Li, Yunbei XuNeural Network Generalization Representation Learning
National University of Singapore

Abstract

Generalization Bounds

Explore similar work

A Generalization Bound for Nearly-Linear Networks

Implicit Regularization and Generalization in Overparameterized Neural Networks

Pointwise Generalization in Deep Neural Networks