A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods

We present a simple scheme for restarting first-order methods for convex optimization problems. Restarts are made based only on achieving specified decreases in objective values, the specified amounts being the same for all optimization problems. Unlike existing restart schemes, the scheme makes no...

Full description

Saved in:
Bibliographic Details
Published in:Foundations of computational mathematics 2022-02, Vol.22 (1), p.211-256
Main Authors: Renegar, James, Grimmer, Benjamin
Format: Article
Language:English
Subjects:
Algorithms
Applications of Mathematics
Computer Science
Convex functions
Convexity
Economics
Linear and Multilinear Algebras
Math Applications in Computer Science
Mathematical optimization
Mathematical research
Mathematics
Mathematics and Statistics
Matrix Theory
Numerical Analysis
Optimization
Restarting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a simple scheme for restarting first-order methods for convex optimization problems. Restarts are made based only on achieving specified decreases in objective values, the specified amounts being the same for all optimization problems. Unlike existing restart schemes, the scheme makes no attempt to learn parameter values characterizing the structure of an optimization problem, nor does it require any special information that would not be available in practice (unless the first-order method chosen to be employed in the scheme itself requires special information). As immediate corollaries to the main theorems, we show that when some well-known first-order methods are employed in the scheme, the resulting complexity bounds are nearly optimal for particular—yet quite general—classes of problems.
ISSN:1615-3375
1615-3383
DOI:10.1007/s10208-021-09502-2