Stochastic gradient descent with initial regularization
2026-08-24 • Machine Learning
Machine Learning
AI summaryⓘ
The authors studied a variation of the stochastic gradient descent algorithm called SGDIR, focusing on how well it performs in predicting outcomes with squared error. They found new mathematical limits showing that SGDIR can learn efficiently when there is no noise, depending on certain assumptions about the data. They also showed that in some cases, SGDIR performs similarly or better than ridge regression when noise is present. Their theoretical results were supported by experiments using both synthetic and real datasets.
Stochastic Gradient DescentInitial RegularizationSquared LossExcess RiskNoiseless CaseSource ConditionCapacity AssumptionRidge RegressionExpected RiskRegularization
Authors
Nabil Kahalé
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.