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
O(dm)
−
(2)
[ 7 ]
Lipschitz
O(∥W∥∞,1∥V∥∞,1)
✓
(3)
[ 40 ]
ReLU
O(∑j=1m∣vj∣∥wj∥2)
−
(4)
[ 17 ]
ReLU
O(∥W∥F∥V∥F)
✓
(5)
[ 4 ]
Lipschitz
O(∥W∥σ∥V−V(0)∥1,2+∥W−W(0)∥1,2∥V∥σ)
✓
(6)
[ 37 ]
ReLU
O(∥W∥σ∥V−V(0)∥F+m∥W−W(0)∥F∥V∥σ)
−
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 ∥X∥F/n for data-dependent bounds, and a factor of supx∥x∥2/n for data-independent bounds (note ∥X∥F/n≤supx∥x∥2/n ). For simplicity, we assume c=1 here.
Figure 1: Behavior of n∥V∥F(∑j=1m∑i=1nγ2(xi⊤wj(0)))21 , ∥V∥F(Gγbx∥W(0)∥σ)/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.
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.
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 ).
We consider nonlinear networks as perturbations of linear ones. Based on this approach, we present novel generalization bounds that become non-vacuous for networks that are close to being linear. The main advantage over the previous works which propose non-vacuous generalization bounds is that our bounds are a-priori: performing the actual training is not required for evaluating the bounds. To the best of our knowledge, they are the first non-vacuous generalization bounds for neural nets possessing this property.
Eugene Golikov
Chair of Statistical Field Theory École Polytechnique Fédérale de Lausanne (EPFL)
Classical statistical learning theory predicts that overparameterized models should exhibit severe overfitting, yet modern deep neural networks with far more parameters than training samples consistently generalize well. This contradiction has become a central theoretical question in machine learning. This study investigates the role of optimization dynamics and implicit regularization in enabling generalization in overparameterized neural networks through controlled experiments. We examine stochastic gradient descent (SGD) across batch sizes, the geometry of flat versus sharp minima via Hessian eigenvalue estimation and weight perturbation analysis, the Neural Tangent Kernel (NTK) regime through wide-network experiments, double descent across model scales, and the Lottery Ticket Hypothesis through iterative magnitude pruning. All experiments use PyTorch on CIFAR-10 and MNIST with multiple random seeds. Our findings demonstrate that generalization is strongly influenced by the interaction between network architecture, optimization algorithms, and loss landscape geometry. Smaller batch sizes consistently produced lower test error and flatter minima, with an 11.8x difference in top Hessian eigenvalue between small-batch and large-batch solutions corresponding to 1.61 percentage points higher test accuracy. Sparse subnetworks retaining only 10% of parameters achieved within 1.15 percentage points of full model performance when retrained from their original initialization. These results highlight the need for revised learning-theoretic frameworks capable of explaining generalization in high-dimensional model regimes.
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.