Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 23 of its 77 references that are in the map. First posted on arXiv 5 Jan 2023.
Builds on
23 of 77 references.
References · 23
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
- 2021Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problemcited by 53
- 2021Acceleration Methodscited by 48
- 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
- 2017Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applicationscited by 29
- 2014Splitting methods with variable metric for KL functionscited by 26
- 2014Optimized first-order methods for smooth convex minimizationcited by 18
- 2018A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methodscited by 14
- 2021Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpnesscited by 13
- 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
- 2021The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learningcited by 11
11 more
- 2022On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samplescited by 8
- 2016"Efficient" Subgradient Methods for General Convex Optimizationcited by 6
- 2017Adaptive restart of accelerated gradient methods under local quadratic growth conditioncited by 6
- 2018Restarting Frank-Wolfe: Faster Rates Under H"olderian Error Boundscited by 6
- 2022Generalised hardness of approximation and the SCI hierarchy -- On determining the boundaries of training algorithms in AIcited by 6
- 2015New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measurecited by 5
- 2022NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problemscited by 5
- 2015Accelerated First-Order Methods for Hyperbolic Programmingcited by 3
- 2016Restarting accelerated gradient methods with a rough strong convexity estimatecited by 3
- 2022Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradientcited by 2
- 2016Randomized Primal-Dual Proximal Block Coordinate Updatescited by 1
Built on by
Citing papers per year: 2023: 1; 2024: 1.
2 papers.