# Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 68 references that are in the map.
- First posted on arXiv 19 Dec 2022.

## Builds on (most cited first, 24 of 24)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problems](https://mlsanity.com/paper/2203.04869/) (2022)
- [On the Convergence of SARAH and Beyond](https://mlsanity.com/paper/1906.02351/) (2019)
- [Accelerating Variance-Reduced Stochastic Gradient Methods](https://mlsanity.com/paper/1910.09494/) (2019)
- [Composite Self-Concordant Minimization](https://mlsanity.com/paper/1308.2867/) (2013)
- [Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2006.15266/) (2020)
- [Restarting accelerated gradient methods with a rough strong convexity estimate](https://mlsanity.com/paper/1609.07358/) (2016)
- [Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD](https://mlsanity.com/paper/1810.04100/) (2018)

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

- [Learning dynamical systems from data: Gradient-based dictionary optimization](https://mlsanity.com/paper/2411.04775/) (2024)

## Abstract (arXiv)

In this book chapter, we briefly describe the main components that constitute the gradient descent method and its accelerated and stochastic variants. We aim at explaining these components from a mathematical point of view, including theoretical and practical aspects, but at an elementary level. We will focus on basic variants of the gradient descent method and then extend our view to recent variants, especially variance-reduced stochastic gradient schemes (SGD). Our approach relies on revealing the structures presented inside the problem and the assumptions imposed on the objective function. Our convergence analysis unifies several known results and relies on a general, but elementary recursive expression. We have illustrated this analysis on several common schemes.