Learning Theory of the SVRG: Generalization and Convergence Analysis

• URL: http://arxiv.org/abs/2605.28513v1
• Date: Wed, 27 May 2026 14:17:00 GMT
• Title: Learning Theory of the SVRG: Generalization and Convergence Analysis
• Abstract summary: Variance reduction (VR) methods employ gradients with decreasing variance, and they have been widely applied to solve large-scale optimization problems in machine learning because of their efficiency.<n>We develop the first non-vacuous analysis of the representative VR method: the behavior Variance Reduced Gradient (SVRG) through the lens of algorithmic stability.
• Score: 20.643275323974425
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Stochastic Non-Smooth Convex Optimization with Unbounded Gradients [10.350093268971836]
  We show that clipped AdamW is theoretically better than other popular optimization methods, such as SGDW and AdaGrad.<n>We also establish the critical role of AdamW's exponentially weighted accumulation, as opposed to simple averaging.
  arXiv  Detail & Related papers  (2026-05-15T01:43:22Z)
• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  Bilevel optimization (SBO) has been integrated into many machine learning paradigms recently.<n>In this paper, we provide a systematic analysis of bilevel optimization methods.<n>Results do not require re-reading and are applicable to more general objective functions.
  arXiv  Detail & Related papers  (2026-04-05T12:12:58Z)
• Truncated Kernel Stochastic Gradient Descent with General Losses and Spherical Radial Basis Functions [3.308257914042897]
  We propose a novel kernel gradient unifies descent (SGD) algorithm for large-scale supervised learning with general losses.<n>Compared to traditional kernel SGD, our algorithm improves efficiency and scalability through an innovative regularization strategy.<n>Our framework accommodates a broad class of classical loss functions, including least-squares, Huber, and logistic losses.
  arXiv  Detail & Related papers  (2025-10-05T15:04:03Z)
• A Simplified Analysis of SGD for Linear Regression with Weight Averaging [64.2393952273612]
  Recent work bycitetzou 2021benign provides sharp rates for SGD optimization in linear regression using constant learning rate.<n>We provide a simplified analysis recovering the same bias and variance bounds provided incitepzou 2021benign based on simple linear algebra tools.<n>We believe our work makes the analysis of gradient descent on linear regression very accessible and will be helpful in further analyzing mini-batching and learning rate scheduling.
  arXiv  Detail & Related papers  (2025-06-18T15:10:38Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing [74.2952487120137]
  It is believed that Gradient Descent (GD) induces an implicit bias towards good generalization in machine learning models. This paper provides a fine-grained analysis of the dynamics of GD for the matrix sensing problem.
  arXiv  Detail & Related papers  (2023-01-27T02:30:51Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  We propose a novel, robust and accelerated iteration that relies on two key elements. The convergence and stability of the obtained method, referred to as NAG-GS, are first studied extensively. We show that NAG-arity is competitive with state-the-art methods such as momentum SGD with weight decay and AdamW for the training of machine learning models.
  arXiv  Detail & Related papers  (2022-09-29T16:54:53Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex Optimization [15.731908248435348]
  We develop gradient descent averaging and primal-dual averaging algorithms for strongly convex cases. We prove that primal-dual averaging yields the optimal convergence rate in terms of output averaging, while SC-PDA derives the optimal individual convergence. Several experiments on SVMs and deep learning models validate the correctness of theoretical analysis and effectiveness of algorithms.
  arXiv  Detail & Related papers  (2020-12-29T01:40:30Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.