An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914590254694400 |
|---|---|
| author | Upadhyaya, Manu Thomsen, Daniel Berg Dieuleveut, Aymeric Taylor, Adrien B. |
| author_facet | Upadhyaya, Manu Thomsen, Daniel Berg Dieuleveut, Aymeric Taylor, Adrien B. |
| contents | We introduce Prox-ITEM, an optimal proximal gradient method for minimizing $f+g$, where $f$ is smooth and strongly convex, and $g$ is convex, proper, and lower semicontinuous. In the smooth case $g=0$, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for $f$ and an arbitrary number of proximal-oracle calls for $g$. We also identify the stationary limit of Prox-ITEM, denoted Prox-TMM, which gives a proximal extension of the triple momentum method (TMM) to the composite setting and achieves the corresponding TMM distance-convergence rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_22929 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit Upadhyaya, Manu Thomsen, Daniel Berg Dieuleveut, Aymeric Taylor, Adrien B. Optimization and Control We introduce Prox-ITEM, an optimal proximal gradient method for minimizing $f+g$, where $f$ is smooth and strongly convex, and $g$ is convex, proper, and lower semicontinuous. In the smooth case $g=0$, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for $f$ and an arbitrary number of proximal-oracle calls for $g$. We also identify the stationary limit of Prox-ITEM, denoted Prox-TMM, which gives a proximal extension of the triple momentum method (TMM) to the composite setting and achieves the corresponding TMM distance-convergence rate. |
| title | An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.22929 |