# Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 77 references that are in the map.
- First posted on arXiv 5 Jan 2023.

## Builds on (most cited first, 23 of 23)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning](https://mlsanity.com/paper/2110.15734/) (2021)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [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)
- [Restarting Frank-Wolfe: Faster Rates Under H"olderian Error Bounds](https://mlsanity.com/paper/1810.02429/) (2018)
- ["Efficient" Subgradient Methods for General Convex Optimization](https://mlsanity.com/paper/1605.08712/) (2016)
- [Adaptive restart of accelerated gradient methods under local quadratic growth condition](https://mlsanity.com/paper/1709.02300/) (2017)
- [Generalised hardness of approximation and the SCI hierarchy -- On determining the boundaries of training algorithms in AI](https://mlsanity.com/paper/2209.06715/) (2022)
- [New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure](https://mlsanity.com/paper/1511.02974/) (2015)
- [NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems](https://mlsanity.com/paper/2203.00804/) (2022)
- [Accelerated First-Order Methods for Hyperbolic Programming](https://mlsanity.com/paper/1512.07569/) (2015)
- [Restarting accelerated gradient methods with a rough strong convexity estimate](https://mlsanity.com/paper/1609.07358/) (2016)
- [Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient](https://mlsanity.com/paper/2206.03041/) (2022)
- [Randomized Primal-Dual Proximal Block Coordinate Updates](https://mlsanity.com/paper/1605.05969/) (2016)

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

- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)

## Abstract (arXiv)

Sharpness is an almost generic assumption in continuous optimization that bounds the distance from minima by objective function suboptimality. It facilitates the acceleration of first-order methods through restarts. However, sharpness involves problem-specific constants that are typically unknown, and restart schemes typically reduce convergence rates. Moreover, these schemes are challenging to apply in the presence of noise or with approximate model classes (e.g., in compressive imaging or learning problems), and they generally assume that the first-order method used produces feasible iterates. We consider the assumption of approximate sharpness, a generalization of sharpness that incorporates an unknown constant perturbation to the objective function error. This constant offers greater robustness (e.g., with respect to noise or relaxation of model classes) for finding approximate minimizers. By employing a new type of search over the unknown constants, we design a restart scheme that applies to general first-order methods and does not require the first-order method to produce feasible iterates. Our scheme maintains the same convergence rate as when the constants are known. The convergence rates we achieve for various first-order methods match the optimal rates or improve on previously established rates for a wide range of problems. We showcase our restart scheme in several examples and highlight potential future applications and developments of our framework and theory.