Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks

Wenquan Ma; Yang Sui; Jiaye Teng; Bohan Wang; Jing Xu; Jingqin Yang

cs.LGFeb 26, 2026

Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks

Authors: Wenquan Ma, Yang Sui, Jiaye Teng, Bohan Wang, Jing Xu, Jingqin Yang

Abstract

Algorithmic stability is among the most potent techniques in generalization analysis. However, its derivation usually requires a stepsize $η_t = \mathcal{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/\sqrt{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

Panel of Figure 1 — Figure 1: The training and test accuracy curves for SGD with various stepsize schedulers on CIFAR-10 using ResNet 18. Models trained with stepsize $\Theta(1/\sqrt{t})$ (dotted line) converge faster and perform better than those trained with stepsize $\Theta(1/t)$ (solid line).

	Stepsize Order	PL Condition	Multi- pass	Overpara- meterization	Generalization Metric
Hardt et al. (2016)	$\mathcal{O}(1/t)$	No	Yes	Yes	Loss
Kuzborskij and Lampert (2018)	$\mathcal{O}(1/t)$	No	Yes	Yes	Loss
Zhang et al. (2022)	$\mathcal{O}(1/t)$	No	Yes	Yes	Loss
Charles and Papailiopoulos (2018)	$\mathcal{O}(1)$	Yes	Yes	Yes	Loss
Nikolakakis et al. (2022)	$\mathcal{O}(1)$	Yes	Yes	Yes	Loss
Zhu et al. (2024)	$\mathcal{O}(1)$	Yes	Yes	Yes	Loss

Table 1: Comparison of our method with related works on non-convex training regimes with SGD.

Panel of Figure 2 — 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},\cdots,10^{1}\}$ . SGD with stepsize $\Theta(1/t\|{\bm{w}}_{t}\|)$ achieves similar training accuracy as SGD with stepsize $\Theta(1/\sqrt{t})$ , both outperforming SGD with stepsize $\Theta(1/t)$ ; (right) When $T_{a}=o(n/\tilde{\gamma}^{1/m_{1}})$ , the training and test loss curve does not decrease at $t\in(T_{a},o(n/\tilde{\gamma}^{1/m_{1}}))$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — 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
$\Phi({\bm{w}};{X})$	Neural network function $\Phi(\cdot;\cdot)$ with weights ${\bm{w}}$ and input ${X}$
$f_{\bm{w}}(\cdot)$	Equivalent notation to $\Phi({\bm{w}};\cdot)$
$H$	Degree of positive homogeneity of the neural network $\Phi$
${\bm{w}}_{t}$	Weight vector at iteration $t$
${\bm{v}}_{t}$	Direction of weight (normalized weight), defined as ${\bm{v}}_{t}={\bm{w}}_{t}/\\|{\bm{w}}_{t}\\|$

Appendix

Table 2: Summary of Notations

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 154 papers

Learning Non-Vacuous Generalization Bounds from Optimization
Jun 9, 2022Chengli Tan, Jiangshe Zhang, Junmin Liu +1Neural Network Generalization Statistical Learning Theory
Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China
A Theoretical Analysis of Generalization Dynamics in Neural Networks under Gradient Descent with Weight Decay
Sep 7, 2026Yuqing Wang, Ioannis G. Kevrekidis, Mikhail BelkinNeural Network Generalization Neural Network Training Dynamics
Johns Hopkins University · University of California San Diego
Flatland: The Adventures of Gradient Descent with Large Step Sizes
Jun 4, 2026Leonardo Galli, Curtis Fox, Wiebke Bartolomaeus +2Edge of Stability Gradient Descent
LMU Munich · Munich Center for Machine Learning · University of British Columbia +1

Jun 9, 2022J/K move · Enter open · S save

Learning Non-Vacuous Generalization Bounds from Optimization

Chengli Tan, Jiangshe Zhang, Junmin Liu, Yihong Gong

Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China

Neural Network Generalization Statistical Learning Theory Generalization Bounds

Open paper AskPDF arXiv

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).

Abstract

Generalization Bounds

Explore similar work

Learning Non-Vacuous Generalization Bounds from Optimization

A Theoretical Analysis of Generalization Dynamics in Neural Networks under Gradient Descent with Weight Decay

Flatland: The Adventures of Gradient Descent with Large Step Sizes