On the Rate of Convergence of the Difference-of-Convex Algorithm (DCA)
研究了凸差算法（DCA）在光滑与非光滑分解下的非渐近收敛速率，推导出最坏情况下的收敛率O(1/√N)和O(1/N)，并在线性收敛条件下给出新结果，对优化算法研究者有参考价值。
Abstract In this paper, we study 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. We derive a worst-case convergence rate of $$O(1/\sqrt{N})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>N</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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. We also provide a new convergence rate of O (1/ N ) for the DCA with the second termination criterion. Moreover, we derive a new linear convergence rate result for the DCA under the assumption of the Polyak–Łojasiewicz inequality. The novel aspect of our analysis is that it employs semidefinite programming performance estimation.