Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA

The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal, and we present a new method OptISTA that improves upon it by a factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-o...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-09
Main Authors: Jang, Uijeong, Shuvomoy Das Gupta, Ryu, Ernest K
Format: Article
Language:English
Subjects:
Algorithms
CAD
Computer aided design
Design optimization
Lower bounds
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal, and we present a new method OptISTA that improves upon it by a factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-order methods, but the methodology was largely limited to unconstrained optimization with a single function. In this work, we present a novel double-function stepsize-optimization PEP methodology that poses the optimization over fixed-step first-order methods for composite optimization as a finite-dimensional nonconvex QCQP, which can be practically solved through spatial branch-and-bound algorithms, and use it to design the exact optimal method OptISTA for the composite optimization setup. We then establish the exact optimality of OptISTA with a novel lower-bound construction that extends the semi-interpolated zero-chain construction (Drori, Taylor 2022) to the double-function setup of composite optimization. By establishing exact optimality, our work concludes the search for the fastest first-order methods for the proximal, projected-gradient, and proximal-gradient setups.
ISSN:2331-8422