Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods.
Saved in:
| Title: | Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods. |
|---|---|
| Authors: | Adcock, Ben1 (AUTHOR), Colbrook, Matthew J.2 (AUTHOR) m.colbrook@damtp.cam.ac.uk, Neyra-Nesterenko, Maksym1 (AUTHOR) |
| Source: | Foundations of Computational Mathematics. Apr2026, Vol. 26 Issue 2, p1137-1192. 56p. |
| Subjects: | Mathematical optimization, Subgradient methods |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 193283907 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Adcock%2C+Ben%22">Adcock, Ben</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Colbrook%2C+Matthew+J%2E%22">Colbrook, Matthew J.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> m.colbrook@damtp.cam.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Neyra-Nesterenko%2C+Maksym%22">Neyra-Nesterenko, Maksym</searchLink><relatesTo>1</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Foundations+of+Computational+Mathematics%22">Foundations of Computational Mathematics</searchLink>. Apr2026, Vol. 26 Issue 2, p1137-1192. 56p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Subgradient+methods%22">Subgradient methods</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=193283907 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10208-024-09673-8 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 56 StartPage: 1137 Subjects: – SubjectFull: Mathematical optimization Type: general – SubjectFull: Subgradient methods Type: general Titles: – TitleFull: Restarts Subject to Approximate Sharpness: A Parameter-Free and Optimal Scheme For First-Order Methods. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Adcock, Ben – PersonEntity: Name: NameFull: Colbrook, Matthew J. – PersonEntity: Name: NameFull: Neyra-Nesterenko, Maksym IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: Apr2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 16153375 Numbering: – Type: volume Value: 26 – Type: issue Value: 2 Titles: – TitleFull: Foundations of Computational Mathematics Type: main |
| ResultId | 1 |
