Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization
Yurii Nesterov · 2025
Read Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization by Yurii Nesterov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20902.txt.
Description
Yurii Nesterov, a leading figure in optimization theory, presents universal gradient methods in a solo-authored 2025 paper. The methods solve composite optimization problems without knowing in advance which problem class they belong to. Only the desired accuracy must be supplied.
The paper gives a new complexity analysis with guarantees that do not depend on a parametric problem class. Plugging in an upper estimate for the objective's global curvature turns the universal bounds into concrete rates. Nesterov analyzes the plain gradient method for nonconvex problems, gradient methods for convex composite problems, and an accelerated variant. The accelerated scheme automatically achieves the best possible rate for the class it lands in. The work unifies several strands of first-order optimization.
Catalog record
| CREATOR | Yurii Nesterov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20902