# An optimal first order method based on optimal quadratic averaging

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2016.

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

- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points](https://mlsanity.com/paper/2211.00866/) (2022)
- [Understanding Accelerated Gradient Methods: Lyapunov Analyses and Hamiltonian Assisted Interpretations](https://mlsanity.com/paper/2304.10063/) (2023)

## Abstract (arXiv)

In a recent paper, Bubeck, Lee, and Singh introduced a new first order method for minimizing smooth strongly convex functions. Their geometric descent algorithm, largely inspired by the ellipsoid method, enjoys the optimal linear rate of convergence. We show that the same iterate sequence is generated by a scheme that in each iteration computes an optimal average of quadratic lower-models of the function. Indeed, the minimum of the averaged quadratic approaches the true minimum at an optimal rate. This intuitive viewpoint reveals clear connections to the original fast-gradient methods and cutting plane ideas, and leads to limited-memory extensions with improved performance.