Computer-assisted design of accelerated composite optimization methods: OptISTA

• 成果类型: Article; Early Access
• 署名作者: Jang, Uijeong; Gupta, Shuvomoy Das; Ryu, Ernest K.
• 署名单位: University of California System; University of California Los Angeles; Rice University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02258-5
• 发表日期: 2025
• 关键词: worst-case performance; monotone-operators; thresholding algorithm; convergence analysis; 1st-order methods; convex; gradient; shrinkage; SUM

摘要

The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal by a constant factor, and we present a new method OptISTA that improves FISTA by a constant factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-order methods. In this work, we present a 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 under the large-scale assumption with a 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, with respect to the performance measure of worst-case function value suboptimality, for the proximal, projected-gradient, and proximal-gradient setups involving a smooth convex function and a closed proper convex function.