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

Computer Science > Machine Learning arXiv:2604.00505 (cs) [Submitted on 1 Apr 2026] Title:Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks Authors:Yunwen Lei, Yufeng Xie View a PDF of the paper titled Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks, by Yunwen Lei and Yufeng Xie View PDF HTML (experimental) 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 cannot fully exploit the power of initialization since the associated bounds depend on the spectral norm of the initialization matrix, which can scale as a square-root function of the width and are therefore not effective for overparameterized models. In this paper, we develop the first \emph{fully} initialization-dependent complexity bounds for shallow neural networks with general Lipschitz activation functions, which enjoys a logarithmic dependency on the width. Our bounds depend on the path-norm of the distance from ini...