# A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2018.

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

- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples](https://mlsanity.com/paper/2203.13908/) (2022)
- [Efficient Self-Supervised Learning for Earth Observation via Dynamic Dataset Curation](https://mlsanity.com/paper/2504.06962/) (2025)
- [NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems](https://mlsanity.com/paper/2203.00804/) (2022)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization](https://mlsanity.com/paper/2210.17550/) (2022)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)
- [Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions](https://mlsanity.com/paper/2507.19465/) (2025)

## Abstract (arXiv)

We present a simple scheme for restarting first-order methods for convex optimization problems. Restarts are made based only on achieving specified decreases in objective values, the specified amounts being the same for all optimization problems. Unlike existing restart schemes, the scheme makes no attempt to learn parameter values characterizing the structure of an optimization problem, nor does it require any special information that would not be available in practice (unless the first-order method chosen to be employed in the scheme itself requires special information). As immediate corollaries to the main theorems, we show that when some well-known first-order methods are employed in the scheme, the resulting complexity bounds are nearly optimal for particular -- yet quite general -- classes of problems.