163. On the convergence rate of the difference-of-convex algorithm (DCA)
Invited abstract in session WF-2: Recent advances in computer-aided analyses of optimization algorithms II, stream Conic optimization: theory, algorithms and applications.
Wednesday, 16:20 - 18:00Room: M:O
Authors (first author is the speaker)
| 1. | Hadi Abbaszadehpeivasti
|
| Tilburg University |
Abstract
In this talk, I present the non-asymptotic convergence rate of the DCA (difference-of-convex algorithm), also known as the convex–concave procedure, with two different termination criteria that are suitable for smooth and non-smooth decompositions, respectively. The DCA is a popular algorithm for difference-of-convex (DC) problems and known to converge to a stationary point of the objective under some assumptions. I derive a worst-case convergence rate of O(1/sqrt(N)) after N iterations of the objective gradient norm for certain classes of DC problems, without assuming strong convexity in the DC decomposition and give an example which shows the convergence rate is exact. I also provide a new convergence rate of O(1/N) for the DCA with the second termination criterion. Moreover, I present a new linear convergence rate result for the DCA under the assumption of the Polyak–Łojasiewicz inequality. The novel aspect of this analysis is that it employs semidefinite programming performance estimation.
Keywords
- Complexity and efficiency of optimization algorithms
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers