# SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

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

## Key facts

- Cited by 402 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2014.

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

- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Leveraging Sparse Linear Layers for Debuggable Deep Networks](https://mlsanity.com/paper/2105.04857/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models](https://mlsanity.com/paper/2404.08080/) (2024)
- [FFCV: Accelerating Training by Removing Data Bottlenecks](https://mlsanity.com/paper/2306.12517/) (2023)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [CausalGym: Benchmarking causal interpretability methods on linguistic tasks](https://mlsanity.com/paper/2402.12560/) (2024)
- [Stable Target Field for Reduced Variance Score Estimation in Diffusion Models](https://mlsanity.com/paper/2302.00670/) (2023)
- [Closing the Generalization Gap of Cross-silo Federated Medical Image Segmentation](https://mlsanity.com/paper/2203.10144/) (2022)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating](https://mlsanity.com/paper/2103.00958/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [Pushing on Text Readability Assessment: A Transformer Meets Handcrafted Linguistic Features](https://mlsanity.com/paper/2109.12258/) (2021)
- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [From t-SNE to UMAP with contrastive learning](https://mlsanity.com/paper/2206.01816/) (2022)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)

## Abstract (arXiv)

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method.