# Restarting accelerated gradient methods with a rough strong convexity estimate

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2016.

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

- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions](https://mlsanity.com/paper/2110.12437/) (2021)
- [Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysis](https://mlsanity.com/paper/2212.09413/) (2022)

## Abstract (arXiv)

We propose new restarting strategies for accelerated gradient and accelerated coordinate descent methods. Our main contribution is to show that the restarted method has a geometric rate of convergence for any restarting frequency, and so it allows us to take profit of restarting even when we do not know the strong convexity coefficient. The scheme can be combined with adaptive restarting, leading to the first provable convergence for adaptive restarting schemes with accelerated gradient methods. Finally, we illustrate the properties of the algorithm on a regularized logistic regression problem and on a Lasso problem.