Search papers, labs, and topics across Lattice.
This paper provides the first non-vacuous generalization analysis of the Stochastic Variance Reduced Gradient (SVRG) method, a popular variance reduction technique, using algorithmic stability. They derive sharp, data-dependent stability bounds for SVRG in both convex and strongly convex settings by exploiting its algorithmic structure and incorporating training errors along the trajectory. The analysis reveals the interplay between optimization and generalization, leading to optimal excess population risk bounds and a framework generalizable to other VR methods like SAGA.
SVRG, a popular variance reduction method, finally gets its generalization guarantees rigorously established, revealing optimal excess population risk bounds.
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.
