Optimal Acceleration for Proximal Minimization of the Sum of Convex and Strongly Convex Functions
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_ | 1866916029886627840 |
|---|---|
| author | Chari, Govind M. Jang, Uijeong Ryu, Ernest K. Açıkmeşe, Behçet |
| author_facet | Chari, Govind M. Jang, Uijeong Ryu, Ernest K. Açıkmeşe, Behçet |
| contents | When minimizing the sum of a convex and a strongly convex function, or when finding the zero of the sum of a monotone operator and a strongly monotone operator, Chambolle and Pock (2010) and Davis and Yin (2015) proposed accelerated mechanisms that achieve an $\mathcal{O}(1/N^2)$ convergence rate for the squared distance to the solution, but the optimality of this rate was not established. In this work, we present Fast Douglas--Rachford Splitting (FDR), an accelerated method that improves the constants established in the prior works, and provide a complexity lower bound establishing that both the $\mathcal{O}(1/N^2)$ convergence rate and the leading-order constant of FDR's rate are optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08593 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Acceleration for Proximal Minimization of the Sum of Convex and Strongly Convex Functions Chari, Govind M. Jang, Uijeong Ryu, Ernest K. Açıkmeşe, Behçet Optimization and Control When minimizing the sum of a convex and a strongly convex function, or when finding the zero of the sum of a monotone operator and a strongly monotone operator, Chambolle and Pock (2010) and Davis and Yin (2015) proposed accelerated mechanisms that achieve an $\mathcal{O}(1/N^2)$ convergence rate for the squared distance to the solution, but the optimality of this rate was not established. In this work, we present Fast Douglas--Rachford Splitting (FDR), an accelerated method that improves the constants established in the prior works, and provide a complexity lower bound establishing that both the $\mathcal{O}(1/N^2)$ convergence rate and the leading-order constant of FDR's rate are optimal. |
| title | Optimal Acceleration for Proximal Minimization of the Sum of Convex and Strongly Convex Functions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.08593 |