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

• URL: http://arxiv.org/abs/2604.00505v1
• Date: Wed, 01 Apr 2026 05:42:40 GMT
• Title: Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks
• Abstract summary: We develop the first emphfully initialization-dependent bounds for shallow neural networks with general Lipschitz activation functions.<n>Our bounds depend on the path-norm of the distance from initialization, which are derived by introducing a new peeling technique.<n>We also develop a lower bound tight up to a constant factor.
• Score: 21.223229143122897
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis [80.64607823130437]
  We extend PAC-Bayesian framework from deep neural networks to message passing GNNs.<n>We derive a tighter robust generalization bound in the adversarial setting.
  arXiv  Detail & Related papers  (2026-06-04T15:31:21Z)
• PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory [10.93258787701145]
  We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors.<n>Unlike classical worst-case complexity bounds based on uniform laws of large numbers, our analysis yields posterior-averaged risk bounds.
  arXiv  Detail & Related papers  (2026-04-19T03:00:18Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• Generalization of Scaled Deep ResNets in the Mean-Field Regime [55.77054255101667]
  We investigate emphscaled ResNet in the limit of infinitely deep and wide neural networks. Our results offer new insights into the generalization ability of deep ResNet beyond the lazy training regime.
  arXiv  Detail & Related papers  (2024-03-14T21:48:00Z)
• Principles for Initialization and Architecture Selection in Graph Neural Networks with ReLU Activations [17.51364577113718]
  We show three principles for architecture selection in finite width graph neural networks (GNNs) with ReLU activations. First, we theoretically derive what is essentially the unique generalization to ReLU GNNs of the well-known He-initialization. Second, we prove in finite width vanilla ReLU GNNs that oversmoothing is unavoidable at large depth when using fixed aggregation operator.
  arXiv  Detail & Related papers  (2023-06-20T16:40:41Z)
• Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK [86.45209429863858]
  We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime. We show that the neural networks possess a different limiting kernel which we call textitbias-generalized NTK We also study various properties of the neural networks with this new kernel.
  arXiv  Detail & Related papers  (2023-01-01T02:11:39Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks [1.0323063834827415]
  We present a novel analysis of single-hidden-layer linear networks trained under gradient flow. We show that the squared loss converges exponentially to its optimum. We derive a novel non-asymptotic upper-bound on the distance between the trained network and the min-norm solution.
  arXiv  Detail & Related papers  (2021-05-13T15:13:51Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks [39.856439772974454]
  We show that the width needed for efficient convergence to a global minimum is independent of the depth. Our results suggest an explanation for the recent empirical successes found by initializing very deep non-linear networks according to the principle of dynamical isometry.
  arXiv  Detail & Related papers  (2020-01-16T18:48:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.