On the Convergence Analysis of DCA
For researchers and practitioners using DCA in machine learning and optimization, this work clarifies convergence conditions and rates, though it is an incremental theoretical contribution.
The paper provides a global convergence analysis of the Difference-of-Convex Algorithm (DCA) under the Kurdyka-Lojasiewicz property, establishing finite-time, linear, and sublinear convergence rates for both objective values and iterates.
Difference-of-Convex (DC) programming, which seeks to minimize a function expressed as the difference of two convex functions, arises in a wide range of applications in machine learning, signal processing, and operations research. A classical and widely used algorithm for solving DC programs is the Difference-of-Convex Algorithm (DCA). In this paper, we revisit DCA from a distinctly DC-specific perspective. We first separate well-definedness from asymptotic convergence and introduce an additional assumption ensuring the solvability of the DCA subproblems, which clarifies why the choice of DC decomposition matters. We then develop a Lyapunov-descent-regularity framework in which the descent estimate is read directly from the convex subproblems and the regularity estimate is verified from DCA optimality conditions. This yields global convergence of the iterates $\{x^k\}$ for both standard and convex-constrained DC programs under either the classical Lojasiewicz subgradient inequality or the broader Kurdyka-Lojasiewicz (KL) property. We further explain how stronger regularity regimes, such as the Polyak-Lojasiewicz (PL) condition, fit into the same framework and sharpen the resulting convergence rates. Consequently, we obtain finite-time, linear, and sublinear rates for objective values and iterates in a way that cleanly separates well-definedness, DCA-specific structure, and KL/PL regularity, and that is readily transferable to DCA-type variants.