# Local Convergence Properties of SAGA/Prox-SVRG and Acceleration

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

## Built on by (most cited first, 10 of 10)

- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (2022)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [Hybrid ISTA: Unfolding ISTA With Convergence Guarantees Using Free-Form Deep Neural Networks](https://mlsanity.com/paper/2204.11640/) (2022)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Screening for Sparse Online Learning](https://mlsanity.com/paper/2101.06982/) (2021)
- [Accelerating Frank-Wolfe via Averaging Step Directions](https://mlsanity.com/paper/2205.11794/) (2022)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Regularized Adaptive Momentum Dual Averaging with an Efficient Inexact Subproblem Solver for Training Structured Neural Network](https://mlsanity.com/paper/2403.14398/) (2024)

## Abstract (arXiv)

Over the past ten years, driven by large scale optimisation problems arising from machine learning, the development of stochastic optimisation methods have witnessed a tremendous growth. However, despite their popularity, the theoretical understandings of these methods are quite limited in contrast to the deterministic optimisation methods. In this paper, we present a local convergence analysis for a typical type of stochastic optimisation methods: proximal variance reduced stochastic gradient methods, and mainly focus on the SAGA [12] and Prox-SVRG [43] algorithms. Under the assumption that the non-smooth component of the optimisation problem is partly smooth relative to a smooth manifold, we present a unified framework for the local convergence analysis of the SAGA/Prox-SVRG algorithms: (i) the sequences generated by the SAGA/Prox-SVRG are able to identify the smooth manifold in a finite number of iterations; (ii) then the sequence enters a local linear convergence regime. Beyond local convergence analysis, we also discuss various possibilities for accelerating these algorithms, including adapting to better local parameters, and applying higher-order deterministic/stochastic optimisation methods which can achieve super-linear convergence. Concrete examples arising from machine learning are considered to verify the obtained results.