Learning Theory of the SVRG: Generalization and Convergence Analysis
AuthorsYunwen Lei, Zimeng Wang, Xiaoming Yuan
Resources
This paper explains why the popular SVRG optimizer generalizes well, not just why it converges, and extends the same theory to related variance-reduced methods.
Key results
The paper states optimal excess population risk bounds of order O(1/√n) for SVRG in the convex setting, matching minimax lower bounds up to logarithmic factors.
For convex objectives, the paper improves the convergence step-size condition from η < 1/(4α) to η < 1/(2α) for SVRG.
What the paper found
This paper gives the first non-vacuous learning-theoretic analysis of SVRG by proving algorithmic-stability bounds that exploit its two-loop variance-reduced update instead of treating it as a black box. The key technical move is to rewrite each SVRG step as an SGD-like iterate plus a zero-mean correction term, then control the extra reference-point gradients with new Lyapunov functions; this removes the usual Lipschitz assumption by using the self-bounding property of smooth nonnegative losses. For convex α-smooth objectives, the paper proves on-average model stability with bounds scaling with the empirical risks along the trajectory, and combines that with a new convergence result under the looser step-size condition η < 1/(2α), improving on the earlier η < 1/(4α) requirement of Reddi et al. 2016. From this, it derives excess population risk bounds of order Õ(1/√n) in the convex case and Õ(1/(nµ)) in the µ-strongly convex case, matching minimax lower bounds up to logarithmic factors. The same framework extends to SAGA, yielding analogous stability and optimal-risk guarantees with weaker step-size restrictions than the original 2014 analysis. Experiments on binary logistic regression using MNIST, a9a, w6a, and mushrooms confirm that the empirical stability distance grows with step size and that the theoretical upper bounds track the observed distances closely, especially as training progresses.
Original abstract
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.
Read the original paperMore in Optimization
Browse all 36 papers →An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
This work proves that stochastic bilevel optimization fundamentally requires up to epsilon^{-6} oracle queries, showing existing methods are asymptotically optimal.
Hyper Algorithm Design Agent: Evolving Learnable Optimizer from Zero
Zipei Yu, Yue-Jiao Gong, Zeyuan Ma, Yuncheng Jiang, Zhiguang Cao
A pair of self-improving coding agents evolves new learnable optimization algorithms from a simple template, reducing the need for handcrafted optimizer design.
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Shinsaku Sakaue
A new multiscale matrix-weights algorithm learns hidden linear preferences online with provably optimal dimension-dependent regret.