Optimized methods for composite optimization: a reduction perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911029898772480 |
|---|---|
| author | Bok, Jinho Altschuler, Jason M. |
| author_facet | Bok, Jinho Altschuler, Jason M. |
| contents | 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 general framework that derives optimized methods for composite optimization directly from those for unconstrained smooth optimization. The derived methods naturally extend the original methods, generalizing how proximal gradient descent extends gradient descent. The key to our result is certain algebraic identities that provide a unified and straightforward 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 gradient descent; (2) a convergence rate for the proximal optimized gradient method which is faster than FISTA; (3) a new method that improves the state-of-the-art rate for minimizing gradient norm in the composite setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23756 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimized methods for composite optimization: a reduction perspective Bok, Jinho Altschuler, Jason M. Optimization and Control Data Structures and Algorithms 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 general framework that derives optimized methods for composite optimization directly from those for unconstrained smooth optimization. The derived methods naturally extend the original methods, generalizing how proximal gradient descent extends gradient descent. The key to our result is certain algebraic identities that provide a unified and straightforward 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 gradient descent; (2) a convergence rate for the proximal optimized gradient method which is faster than FISTA; (3) a new method that improves the state-of-the-art rate for minimizing gradient norm in the composite setting. |
| title | Optimized methods for composite optimization: a reduction perspective |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.23756 |