Optimized methods for composite optimization: a reduction perspective

• 成果类型: Article; Early Access
• 署名作者: Bok, Jinho; Altschuler, Jason M.
• 署名单位: University of Pennsylvania
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02377-7
• 发表日期: 2026-06-13
• 关键词: First-order methods; Composite optimization; reduction; acceleration; Optimized methods; Proximal gradient descent; worst-case performance; thresholding algorithm; 1st-order methods; convex; interpolation

摘要

Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimized method is specially tailored for a particular problem setting, and it is a well-documented challenge to extend optimized methods to other settings due to their highly bespoke design and analysis. We provide a framework that derives optimized methods for composite optimization directly from those for unconstrained smooth optimization. The derived methods naturally extend the original methods, analogous to how proximal gradient descent extends gradient descent. The key to our result is certain algebraic identities that-by leveraging a common structure of optimized methods- provide a unified way of extending convergence analyses from unconstrained to composite settings. As concrete examples, we apply our framework to establish (1) the phenomenon of stepsize acceleration for proximal gradients descent; (2) a convergence rate for the proximal optimized gradient method [2] which is faster than FISTA [3]; (3) a new method that improves the state-of-the-art rate for minimizing gradient norm in the composite setting.