Algorithmic stability is among the most potent techniques in generalization analysis. However, its derivation usually requires a stepsize ηt=O(1/t) under non-convex training regimes, where t denotes iterations. This rigid decay of the stepsize potentially impedes optimization and may not align with practical scenarios. In this paper, we derive the generalization bounds under the homogeneous neural network regimes, proving that this regime enables slower stepsize decay of order Ω(1/t) under mild assumptions. We further extend the theoretical results from several aspects, e.g., non-Lipschitz regimes. This finding is broadly applicable, as homogeneous neural networks encompass fully-connected and convolutional neural networks with ReLU and LeakyReLU activations.
Figures & tables
Figure 1: The training and test accuracy curves for SGD with various stepsize schedulers on CIFAR-10 using ResNet 18. Models trained with stepsize Θ(1/t) (dotted line) converge faster and perform better than those trained with stepsize Θ(1/t) (solid line).
Stepsize Order
PL Condition
Multi- pass
Overpara- meterization
Generalization Metric
Hardt et al. (2016)
O(1/t)
No
Yes
Yes
Loss
Kuzborskij and Lampert (2018)
O(1/t)
No
Yes
Yes
Loss
Zhang et al. (2022)
O(1/t)
No
Yes
Yes
Loss
Charles and Papailiopoulos (2018)
O(1)
Yes
Yes
Yes
Loss
Nikolakakis et al. (2022)
O(1)
Yes
Yes
Yes
Loss
Zhu et al. (2024)
O(1)
Yes
Yes
Yes
Loss
Table 1: Comparison of our method with related works on non-convex training regimes with SGD.
Figure 2: (left) Training accuracy of SGD with different schedulers over a three-layer ReLU network. The initial learning rate is selected via grid search over {10−5,10−4,⋯,101} . SGD with stepsize Θ(1/t∥wt∥) achieves similar training accuracy as SGD with stepsize Θ(1/t) , both outperforming SGD with stepsize Θ(1/t) ; (right) When Ta=o(n/γ~1/m1) , the training and test loss curve does not decrease at t∈(Ta,o(n/γ~1/m1)) .
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: An instance of construction for H=3 . Following the rules in Proposition 1 , normalized layers (left) accomodate arbitrary activations and connections with 0 -homogeneity, while the subsequent unnormalized layers (right) compose a 3 -layer MLP to achieve the desired three-homogeneity.
Symbol
Description
Model
Φ(w;X)
Neural network function Φ(⋅;⋅) with weights w and input X
fw(⋅)
Equivalent notation to Φ(w;⋅)
H
Degree of positive homogeneity of the neural network Φ
wt
Weight vector at iteration t
vt
Direction of weight (normalized weight), defined as vt=wt/∥wt∥
One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or only valid to the compressed nets. In this study, we present a simple yet non-vacuous generalization bound from the optimization perspective. We achieve this goal by leveraging that the hypothesis set accessed by stochastic gradient algorithms is essentially fractal-like and thus can derive a tighter bound over the algorithm-dependent Rademacher complexity. The main argument rests on modeling the discrete-time recursion process via a continuous-time stochastic differential equation driven by fractional Brownian motion. Numerical studies demonstrate that our approach is able to yield plausible generalization guarantees for modern neural networks such as ResNet and Vision Transformer, even when they are trained on a large-scale dataset (e.g. ImageNet-1K).
Chengli Tan, Jiangshe Zhang, Junmin Liu +1
Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China
Understanding generalization remains a central challenge in machine learning because it requires jointly considering data, architecture, and training dynamics. In this paper, we develop a theoretical framework that characterizes how these factors jointly shape generalization performance throughout training. More precisely, we study a broad class of neural networks trained under the ℓ2 loss by gradient descent (GD) with weight decay, and prove the convergence of GD to a neighbourhood of the global minimizers of the empirical loss. By partitioning the space based on the input data, we then decompose the population error into data error, optimization error, and prediction variation error, and bound them separately. In particular, for the prediction variation error, which measures the oscillations of the learned function, we propose (local) approximate homogeneity and derive explicit cellwise and layerwise bounds for its evolution along the training trajectory. These bounds yield two important implications: a necessary condition of improved generalization explains differences in layerwise generalization behavior; a sufficient condition describes delayed generalization and provides a theoretical characterization of grokking.
Yuqing Wang, Ioannis G. Kevrekidis, Mikhail Belkin
Johns Hopkins University · University of California San Diego
The training of neural networks often entails objective functions that are not globally L-smooth. For these functions, it is both theoretically and practically difficult to reply to the question: what is the largest possible step size that ensures the convergence of gradient descent (GD)? We address this longstanding open question in deep learning by providing a unifying definition of "large" step sizes that requires only local Lipschitz (or even Hölder) continuity of the gradient. We design first-order adaptive methods that provably yield large step sizes and show that they operate at the edge of stability (EoS) right from the start of the training. In particular, the loss decreases nonmonotonically and the product between the step size and sharpness, i.e., the largest eigenvalue of the Hessian, stays above the EoS threshold of 2 throughout training. Using our method, we are also able to minimize the sharpness all the way down to its global minimum. Contrary to expectation, we find that encountering globally-flat regions too early in the training may both slow down convergence and jeopardize the generalization ability of the network. Exploiting a self-stabilization argument, we allow GD to enter slightly sharper valleys and turn unsuccessful training runs into very successful ones.