REVIEW 5 cited by
Optimal first-order methods for convex functions with a quadratic upper bound
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We analyze worst-case convergence guarantees of first-order optimization methods over a function class extending that of smooth and convex functions. This class contains convex functions that admit a simple quadratic upper bound. Its study is motivated by its stability under minor perturbations. We provide a thorough analysis of first-order methods, including worst-case convergence guarantees for several algorithms, and demonstrate that some of them achieve the optimal worst-case guarantee over the class. We support our analysis by numerical validation of worst-case guarantees using performance estimation problems. A few observations can be drawn from this analysis, particularly regarding the optimality (resp. and adaptivity) of the heavy-ball method (resp. heavy-ball with line-search). Finally, we show how our analysis can be leveraged to obtain convergence guarantees over more complex classes of functions. Overall, this study brings insights on the choice of function classes over which standard first-order methods have working worst-case guarantees.
Forward citations
Cited by 5 Pith papers
-
Optimized methods for composite optimization: a reduction perspective
A reduction framework converts unconstrained optimized first-order methods into composite-setting methods with analogous rates, yielding new proximal OGM and proximal OGM-G guarantees.
-
Performance Estimation of second-order optimization methods on classes of univariate functions
The paper derives exact univariate interpolation conditions for second-order function classes and uses them to improve and certify worst-case guarantees for Newton-type methods.
-
Finding Simple Proofs for First-Order Optimization
Sparse optimization and SDP-based post-processing of PEP dual certificates recovers compact, interpretable proofs and Lyapunov functions for first-order optimization methods.
-
Continuized Nesterov Momentum Achieves the $O(\varepsilon^{-7/4})$ Complexity in Smooth Nonconvex Optimization
The paper proves a weighted, event-restricted O(ε^{-7/4}) complexity bound for a continuized Nesterov momentum algorithm without safeguard mechanisms; the restriction is not rigorously quantified.
-
Numerical Design of Optimized First-Order Algorithms
A sequential linearization method designs step sizes whose Performance Estimation bounds are competitive with BNB-PEP and give accelerated fitted rates for coordinate, inexact, and cyclic gradient descent.
Discussion (0). Continue with ORCID to comment.