# Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

arXiv: https://arxiv.org/abs/1506.01972 · HTML: https://mlsanity.com/paper/1506.01972/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2015.

## Built on by (most cited first, 30 of 38)

- [Rethinking Model Ensemble in Transfer-based Adversarial Attacks](https://mlsanity.com/paper/2303.09105/) (2023)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning](https://mlsanity.com/paper/2411.19285/) (2024)
- [MARS-M: When Variance Reduction Meets Matrices](https://mlsanity.com/paper/2510.21800/) (2025)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Trade-off Between Efficiency and Consistency for Removal-based Explanations](https://mlsanity.com/paper/2210.17426/) (2022)
- [Memory Augmented Optimizers for Deep Learning](https://mlsanity.com/paper/2106.10708/) (2021)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [PPI-SVRG: Unifying Prediction-Powered Inference and Variance Reduction for Semi-Supervised Optimization](https://mlsanity.com/paper/2601.21470/) (2026)
- [Variance reduction techniques for stochastic proximal point algorithms](https://mlsanity.com/paper/2308.09310/) (2023)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications](https://mlsanity.com/paper/2101.01505/) (2021)
- [EMO: Episodic Memory Optimization for Few-Shot Meta-Learning](https://mlsanity.com/paper/2306.05189/) (2023)
- [SADAM: Stochastic Adam, A Stochastic Operator for First-Order Gradient-based Optimizer](https://mlsanity.com/paper/2205.10247/) (2022)
- [Theoretical Analysis of Primal-Dual Algorithm for Non-Convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2205.11979/) (2022)
- [VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence](https://mlsanity.com/paper/2505.13954/) (2025)

## Abstract (arXiv)

Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly convex or sum-of-non-convex settings. More precisely, we provide new analysis to improve the state-of-the-art running times in both settings by either applying SVRG or its novel variant. Since non-strongly convex objectives include important examples such as Lasso or logistic regression, and sum-of-non-convex objectives include famous examples such as stochastic PCA and is even believed to be related to training deep neural nets, our results also imply better performances in these applications.