# Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2020.

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

- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Distributed Deep Learning in Open Collaborations](https://mlsanity.com/paper/2106.10207/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Provable convergence guarantees for black-box variational inference](https://mlsanity.com/paper/2306.03638/) (2023)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning](https://mlsanity.com/paper/2111.11556/) (2021)
- [Sharpness-Aware Minimization: General Analysis and Improved Rates](https://mlsanity.com/paper/2503.02225/) (2025)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Distributed Methods with Absolute Compression and Error Compensation](https://mlsanity.com/paper/2203.02383/) (2022)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method](https://mlsanity.com/paper/2408.02936/) (2024)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Understanding Progressive Training Through the Framework of Randomized Coordinate Descent](https://mlsanity.com/paper/2306.03626/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)

## Abstract (arXiv)

We present a unified theorem for the convergence analysis of stochastic gradient algorithms for minimizing a smooth and convex loss plus a convex regularizer. We do this by extending the unified analysis of Gorbunov, Hanzely & Richt'arik (2020) and dropping the requirement that the loss function be strongly convex. Instead, we only rely on convexity of the loss function. Our unified analysis applies to a host of existing algorithms such as proximal SGD, variance reduced methods, quantization and some coordinate descent type methods. For the variance reduced methods, we recover the best known convergence rates as special cases. For proximal SGD, the quantization and coordinate type methods, we uncover new state-of-the-art convergence rates. Our analysis also includes any form of sampling and minibatching. As such, we are able to determine the minibatch size that optimizes the total complexity of variance reduced methods. We showcase this by obtaining a simple formula for the optimal minibatch size of two variance reduced methods (textitL-SVRG and textitSAGA). This optimal minibatch size not only improves the theoretical total complexity of the methods but also improves their convergence in practice, as we show in several experiments.