# A generic adaptive restart scheme with applications to saddle point algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

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

- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

We provide a simple and generic adaptive restart scheme for convex optimization that is able to achieve worst-case bounds matching (up to constant multiplicative factors) optimal restart schemes that require knowledge of problem specific constants. The scheme triggers restarts whenever there is sufficient reduction of a distance-based potential function. This potential function is always computable. We apply the scheme to obtain the first adaptive restart algorithm for saddle-point algorithms including primal-dual hybrid gradient (PDHG) and extragradient. The method improves the worst-case bounds of PDHG on bilinear games, and numerical experiments on quadratic assignment problems and matrix games demonstrate dramatic improvements for obtaining high-accuracy solutions. Additionally, for accelerated gradient descent (AGD), this scheme obtains a worst-case bound within 60% of the bound achieved by the (unknown) optimal restart period when high accuracy is desired. In practice, the scheme is competitive with the heuristic of O'Donoghue and Candes (2015).