Improved convergence rates for the Difference-of-Convex algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909149505257472 |
|---|---|
| author | Rotaru, Teodor Patrinos, Panagiotis Glineur, François |
| author_facet | Rotaru, Teodor Patrinos, Panagiotis Glineur, François |
| contents | We consider a difference-of-convex formulation where one of the terms is allowed to be hypoconvex (or weakly convex). We first examine the precise behavior of a single iteration of the Difference-of-Convex algorithm (DCA), giving a tight characterization of the objective function decrease. This requires distinguishing between eight distinct parameter regimes.
Our proofs are inspired by the performance estimation framework, but are much simplified compared to similar previous work.
We then derive sublinear DCA convergence rates towards critical points, distinguishing between cases where at least one of the functions is smooth and where both functions are nonsmooth. We conjecture the tightness of these rates for four parameter regimes, based on strong numerical evidence obtained via performance estimation, as well as the leading constant in the asymptotic sublinear rate for two more regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16864 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved convergence rates for the Difference-of-Convex algorithm Rotaru, Teodor Patrinos, Panagiotis Glineur, François Optimization and Control We consider a difference-of-convex formulation where one of the terms is allowed to be hypoconvex (or weakly convex). We first examine the precise behavior of a single iteration of the Difference-of-Convex algorithm (DCA), giving a tight characterization of the objective function decrease. This requires distinguishing between eight distinct parameter regimes. Our proofs are inspired by the performance estimation framework, but are much simplified compared to similar previous work. We then derive sublinear DCA convergence rates towards critical points, distinguishing between cases where at least one of the functions is smooth and where both functions are nonsmooth. We conjecture the tightness of these rates for four parameter regimes, based on strong numerical evidence obtained via performance estimation, as well as the leading constant in the asymptotic sublinear rate for two more regimes. |
| title | Improved convergence rates for the Difference-of-Convex algorithm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.16864 |