# Adaptive restart of accelerated gradient methods under local quadratic growth condition

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2017.

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

- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper Representations](https://mlsanity.com/paper/2101.06848/) (2021)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Outer-Momentum Restarting in High-Dimensional Two-Phase Optimization](https://mlsanity.com/paper/2605.28585/) (2026)
- [Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/2608.09022/) (2026)

## Abstract (arXiv)

By analyzing accelerated proximal gradient methods under a local quadratic growth condition, we show that restarting these algorithms at any frequency gives a globally linearly convergent algorithm. This result was previously known only for long enough frequencies. Then, as the rate of convergence depends on the match between the frequency and the quadratic error bound, we design a scheme to automatically adapt the frequency of restart from the observed decrease of the norm of the gradient mapping. Our algorithm has a better theoretical bound than previously proposed methods for the adaptation to the quadratic error bound of the objective. We illustrate the efficiency of the algorithm on a Lasso problem and on a regularized logistic regression problem.