Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods
Foundations of Computational Mathematics · 2026-04 · 26 (2) · 1137-1192
DOI: 10.1007/s10208-024-09673-8 ↗Kurz gefasst
Fachartikel in der Zeitschrift Foundations of Computational Mathematics, online erschienen am 18.02.2025. Verfasst von Ben Adcock und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 73 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Adcock, B., Colbrook, M. J., & Neyra-Nesterenko, M. (2026). Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods. Foundations of Computational Mathematics, 26(2), 1137-1192. https://doi.org/10.1007/s10208-024-09673-8
Vancouver
Adcock B, Colbrook MJ, Neyra-Nesterenko M. Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods. Foundations of Computational Mathematics. 2026;26(2):1137-1192. doi:10.1007/s10208-024-09673-8
BibTeX
@article{Adcock2026,
author = {Adcock, Ben and Colbrook, Matthew J. and Neyra-Nesterenko, Maksym},
title = {Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods},
journal = {Foundations of Computational Mathematics},
year = {2026},
volume = {26},
number = {2},
pages = {1137--1192},
doi = {10.1007/s10208-024-09673-8}
}
EUVIMED