Stochastic gradient descent with initial regularization

This paper investigates a variant of stochastic gradient descent known as stochastic gradient descent with initial regularization (SGDIR) for least-squares regression problems in separable Hilbert spaces and reproducing kernel Hilbert spaces (RKHSs). The core research question is whether an appropriately regularized initial phase in SGD can accelerate convergence and overcome the limitations of standard unregularized SGD or ridge regression in high-dimensional or infinite-dimensional settings.

The author analyzes SGDIR under standard moment, capacity, and source assumptions. By splitting the training process into an initial regularized phase of length $m$ followed by an unregularized phase, the algorithm leverages the strong convexity induced by initial regularization to rapidly forget initial conditions. The analysis evaluates both averaged and non-averaged variants of SGDIR in noiseless and noisy environments, utilizing bias-variance decompositions and operator-theoretic bounds on the expected excess risk.

In the noiseless setting, the paper establishes dimension-free upper bounds for the expected excess risk of SGDIR under capacity and source parameters. For a particular value of the source parameter, the upper bounds reach an order of $m^{-2}\log^2 m$, where $m$ is proportional to the training sample size. For another value of the source parameter, the method yields bounds of order $m^{-3+\epsilon}$ for any $\epsilon > 0$, provided the capacity parameter satisfies specific threshold conditions.

In the noisy setting, the paper provides an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, SGDIR's expected excess risk is shown to be no larger than that of ridge regression up to a polylogarithmic factor. Furthermore, the work derives a new minimax lower bound for any estimator in the noiseless case, proving that the upper bounds are tight in certain regimes up to polylogarithmic factors.

Over-parameterized learning models and high-dimensional kernel methods frequently demand efficient optimization algorithms that balance computational complexity with optimal statistical convergence rates. While kernel ridge regression enjoys strong statistical guarantees, it suffers from prohibitive computational scaling in terms of time and memory with respect to sample size. SGDIR bridges this gap by offering the computational efficiency of stochastic gradient descent alongside the rigorous statistical convergence properties typically reserved for ridge regression.