Stochastic gradient descent with initial regularization

Nabil Kahalé

cs.LGAug 24, 2026

Stochastic gradient descent with initial regularization

Authors: Nabil Kahalé

Organizations: ESCP Business School, Paris, France

Abstract

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$ , where the number of training samples is of order $m$ . For another value of the source parameter, we obtain, for any $ε>0$ , bounds of order $m^{-3+ε}$ , provided that the capacity parameter exceeds $ε^{-1}$ . We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.

Figures & tables

Panel of Figure 1 — Figure 1: Test error versus $n$ for in a noiseless setting.

$n$	house_8L ( $d^{\prime}=8$ )			elevators ( $d^{\prime}=18$ )			MSD ( $d^{\prime}=90$ )
	SGD	KRR	$\lambda n$	SGD	KRR	$\lambda n$	SGD	KRR	$\lambda n$
150	0.0016	0.00086	0.09	0.0014	0.00079	$3.5\times 10^{-5}$	0.0019	0.00081	2.1
300	0.0039	0.0042	0.12	0.0034	0.0034	$1\times 10^{-6}$	0.0044	0.0034	0.12
600	0.015	0.019	0.16	0.014	0.018	$1\times 10^{-6}$	0.016	0.019	0.11
1200	0.048	0.084	0.19	0.046	0.092	$1\times 10^{-6}$	0.053	0.083	0.17
2400	0.19	0.42	0.23	0.20	0.42	$1\times 10^{-6}$	0.17	0.41	0.23

Table 1: Running time (in seconds) of a single run of tail-averaged SGD (representative of both SGD-like methods) and KRR, together with the corresponding values of

\lambda n

. The reported running times exclude cross-validation and test error evaluation.

Panel of Figure 2 — Figure 2: Average test error versus $n$ for the house_8L, elevators and MSD datasets, from left to right.

Panel of Figure 3 — Figure 3: Upper bound on ${E[\mathcal{R}(\bar{\theta}_{n/2:n+1})]}/{E[\mathcal{R}(\hat{\theta}_{\lambda,n})]}$ , with $\tilde{n}=14000$ .

Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) uses noisy, data-sampled gradients to train models and solve large-scale optimization problems.

See all 225 papers

Learning Theory of the SVRG: Generalization and Convergence Analysis
May 27, 2026Yunwen Lei, Zimeng Wang, Xiaoming YuanStochastic Optimization Convergence Variance Reduction
Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden
Optimal ridge regularization revisited
May 27, 2026Jack Timmermans, Sergio A. AlvarezLinear Regression Statistical Learning Theory
Department of Computer Science, Boston College, Chestnut Hill, MA 02467 USA
On Regularization via Early Stopping for Least Squares Regression
Jun 6, 2024Rishi Sonthalia, Jackie Lok, Elizaveta RebrovaEarly Stopping Linear Regression
Department of Mathematics, Boston College · ORFE Department, Princeton University

May 27, 2026J/K move · Enter open · S save

Learning Theory of the SVRG: Generalization and Convergence Analysis

Yunwen Lei, Zimeng Wang, Xiaoming Yuan

Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden

Stochastic Optimization Convergence Variance Reduction Stochastic Gradient Descent Generalization Bounds

Open paper AskPDF arXiv

Variance reduction (VR) methods employ stochastic gradients with decreasing variance, and they have been widely applied to solve large-scale optimization problems in machine learning because of their efficiency. Existing theoretical studies of VR methods are mainly focused on the convergence analysis, leaving the generalization behavior largely unexplored. In this paper, we bridge this gap by developing the first non-vacuous generalization analysis of the representative VR method: Stochastic Variance Reduced Gradient (SVRG), through the lens of algorithmic stability. In particular, we establish sharp stability bounds of the SVRG in both convex and strongly convex settings by exploiting its algorithmic structure. The obtained bounds are data-dependent, because the training errors are incorporated along the trajectory. Our analysis clarifies the interplay between optimization and generalization, leading to optimal excess population risk bounds in both settings. Our approach differs substantially from existing analyses of stochastic algorithms in the sense that we decompose the SVRG update as an SGD-like step plus a zero-mean correction term and then introduce novel Lyapunov functions to absorb the additional gradient terms induced by the reference points. Our analytical framework can be generalized to other VR methods, and we demonstrate the generalization by the well-known Stochastic Average Gradient Accelerated (SAGA) method.

Abstract

Stochastic Gradient Descent

Explore similar work

Learning Theory of the SVRG: Generalization and Convergence Analysis

Optimal ridge regularization revisited

On Regularization via Early Stopping for Least Squares Regression