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

Yunwen Lei, Yufeng Xie, [1.2pt] Department of Mathematics, The University of Hong Kong[1.2pt] [email protected], [email protected] · 2026

Read Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks by Yunwen Lei, Yufeng Xie, [1.2pt] Department of Mathematics, The University of Hong Kong[1.2pt] [email protected], [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00505.txt.

Introduction

Lei and Xie develop generalisation bounds for overparameterised shallow neural networks that depend on initialisation and stay non-vacuous. Overparameterised networks often generalise well despite having more parameters than training examples, a benign overfitting puzzle. One promising explanation ties generalisation to the distance from initialisation, often far smaller than the parameter norm itself. Existing analyses measure that distance with the Frobenius norm and often yield vacuous bounds in practice. The new bounds use the path-norm of the initialisation distance for shallow networks with general Lipschitz activations.

Catalog record

CREATORYunwen Lei, Yufeng Xie, [1.2pt] Department of Mathematics, The University of Hong Kong[1.2pt] [email protected], [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99885
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00505

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks Yunwen Lei, Yufeng Xie, [1.2pt] Department of Mathematics, The University of Hong Kong[1.2pt] [email protected], [email protected] 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. Keyword : Rademacher complexity, shallow neural networks, learning theory, generalization analysis, overparameterization. 1 Introduction Deep neural networks (DNNs) have found tremendous successful applications in various fields of science and engineering, leading to rapid progress of artificial intelligence [ 22 ] . A notable property of DNNs is that the models are often overparameterized [ 52 , 1 ] , meaning that the number of parameters far exceeds the number of training examples. By the conventional wisdom of statistical learning theory [ 48 ] , these overparameterized models are doomed to overfit the training examples, yielding vacuous generalization bounds. However, various studies show that overparameterized DNNs can be trained to overfit the training examples while still making accurate predictions on testing examples, showing an interesting benign overfitting phenomenon [ 6 , 38 ] . The benign overfitting phenomenon motivates a lot of generalization studies of DNNs [ 7 , 4 , 40 , 17 ] . A representative result in this direction is to build norm-based generalization bounds, meaning that the generalization bounds depend on the norm of weight matrices instead of the number of parameters. For example, the work [ 17 , 40 ] used covering numbers and Rademacher complexities to study generalization in terms of norm of weights. Their analyses critically depend on the homogeneity of ReLU activation function, and therefore the results apply only to ReLU networks. Furthermore, it is empirically observed that the neural networks trained by gradient methods often stay close to the initialization point, and the distance from the initialization can be significantly smaller than the norm of the weights [ 16 , 36 , 38 ] . Then, generalization bounds in terms of distance from initialization are significantly sharper than those in terms of weight norms. This observation has motivated the recent growing interests in developing initialization-dependent generalization bounds [ 4 , 33 , 38 , 12 , 38 ] . The work [ 4 ] used covering numbers to develop generalization bounds depending on \|\mathbf{W}-\mathbf{W}^{(0)}\|_{1,2} , where \mathbf{W} and \mathbf{W}^{(0)} are the weight matrices for the considered DNNs and the initialization point, respectively, and \|\cdot\|_{1,2} denotes the (1,2) -norm of matrices. However, due to the (1,2) -norm, the resulting bounds still enjoy a heavy dependency on the width. Several works try to improve this dependency by introducing other techniques. For example, the work [ 38 ] introduced a decomposition approach to study ReLU shallow neural networks (SNNs), the work [ 33 ] related the complexity of SNNs with smooth activation functions to that of Lipschitz function classes, and the work [ 12 ] studied the sample complexity of SNNs from the perspective of approximate description length. While these analyses imply bounds depending on the distance from initialization, they all use Frobenius norm to measure this distance. For neural networks, a more effective norm to measure the complexity of the function spaces is the path-norm [ 39 , 42 ] . However, to the best of our knowledge, there are no generalization analyses of SNNs in terms of the path-norm which take into account the effect of the initialization. Furthermore, the analysis in [ 33 ] imposes a smoothness assumption on the activation function, while the analysis in [ 38 ] considers only the ReLU activation. Moreover, the bounds in [ 33 , 12 ] are data-independent since they involve the largest norm of inputs. Due to these issues, the existing initialization-dependent analyses often imply vacuous generalization bounds for overparameterized models in practice. Therefore, there is still a gap between theoretical analysis and empirical observations. The above discussions motivate us to study the following natural questions. Can we develop initialization-dependent generalization bounds that remain valid for overparameterized networks? Can our generalization bounds be expressed in terms of the path-norm rather than the Frobenius norm? Can the resulting analysis apply to general Lipschitz activation functions and imply data-dependent bounds? Can these bounds be non-vacuous for overparamterized models in empirical analyses? In this paper, we aim to answer the above questions affirmatively by presenting sharper initialization-dependent generalization analysis of SNNs in terms of path-norm. We summarize our contributions as follows. 1. We present the first initialization-dependent Rademacher complexity bounds for SNNs with general Lipschitz activation functions. Our bounds are expressed by the path-norm and are data-dependent with a logarithmic dependency on the width, while the existing initialization-dependent bounds are expressed by the Frobenius norm [ 38 , 33 , 37 , 12 ] , data-independent [ 33 , 12 ] , enjoy a square-root dependency on the width [ 4 , 38 , 37 ] or require smoothness assumptions on the activation function [ 33 ] . Based on this, we present generalization bounds which are significantly sharper than existing results, especially if the width is large. 2. We also develop lower bounds for Rademacher complexity of SNNs, which match our upper bounds up to a constant factor. This shows the tightness of our complexity analysis. Unlike the existing lower bounds focusing on \mathbf{W}^{(0)}=0 [ 38 , 4 ] , our lower bounds are also established for initialization-dependent SNNs. 3. We introduce new techniques in the Rademacher complexity analysis to handle the initialization-dependent constraint. Our key idea is to introduce several auxiliary function spaces by fully exploiting the initialization-dependent constraint. We then relate the Rademacher complexity of SNNs to a finite union of these function spaces, which can be estimated by existing structural results on Rademacher complexities [ 34 ] . 4. We conduct an empirical analysis to illustrate the behavior of our generalization bounds 1 1 1 Code for empirical studies is available at https://github.com/xxyufeng/Generalization-SNNs. . The experimental comparison shows that our bound achieves a consistent and significant improvement over existing bounds. In particular, empirical analysis shows that our generalization bounds are non-vacuous in the sense of being smaller than 1 even the networks are highly overparameterized. We organize the paper as follows. We review the related work in Section 2 , and introduce the problem setup in Section 3 . We present our main results on Rademacher complexities and generalization bounds in Section 4 .

Read the complete text