# SAGA with Arbitrary Sampling

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

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

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [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)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)

## Abstract (arXiv)

We study the problem of minimizing the average of a very large number of smooth functions, which is of key importance in training supervised learning models. One of the most celebrated methods in this context is the SAGA algorithm. Despite years of research on the topic, a general-purpose version of SAGA---one that would include arbitrary importance sampling and minibatching schemes---does not exist. We remedy this situation and propose a general and flexible variant of SAGA following the em arbitrary sampling paradigm. We perform an iteration complexity analysis of the method, largely possible due to the construction of new stochastic Lyapunov functions. We establish linear convergence rates in the smooth and strongly convex regime, and under a quadratic functional growth condition (i.e., in a regime not assuming strong convexity). Our rates match those of the primal-dual method Quartz for which an arbitrary sampling analysis is available, which makes a significant step towards closing the gap in our understanding of complexity of primal and dual methods for finite sum problems.