Introduction
Many problems in machine learning and statistics involve Difference of Convex (DC) programming—optimizing an objective of the form $f(x) - g(x)$, where both $f$ and $g$ are convex. Because the difference of two convex functions is generally non-convex, these problems are notoriously difficult to solve. The Convex-Concave Procedure (CCCP) is an elegant and widely used algorithm for tackling these problems, serving as the engine behind famous methods like the Expectation-Maximization (EM) algorithm.
However, while CCCP is known to converge asymptotically, its non-asymptotic convergence rate—exactly how many iterations are needed to reach a specific level of accuracy—has remained a significant theoretical gap, especially for its most general forms. This paper reveals a surprising theoretical "missing link": CCCP is actually a special case of the Frank-Wolfe (FW) algorithm in disguise. By establishing this connection, the authors successfully port advanced convergence theory from the Frank-Wolfe literature to provide the first non-asymptotic convergence guarantees for general versions of CCCP.
The Methodological Bridge: Epigraph Reformulation
The authors bridge this theoretical gap using a technique called epigraph reformulation. Instead of directly minimizing $f(x) - g(x)$, the problem is rewritten as minimizing a concave objective over a convex constraint set: $\min t - g(x)$ subject to $f(x) \le t$.
The paper formally proves that applying the standard Frank-Wolfe algorithm—which relies on linear approximations of the objective—to this reformulated problem yields steps that are mathematically identical to the CCCP algorithm.
Furthermore, to handle the most complex cases where the constraints themselves are also differences of convex functions (a variant known as CCCP+), the authors introduce a new variant of Frank-Wolfe called FW+. This novel variant linearizes both the objective and the constraints simultaneously, extending the equivalence to constrained DC programming.
Key Theoretical Results and Insights
The realization that CCCP is a specific instance of Frank-Wolfe allows decades of research on FW to be immediately applied to DC programming. The most significant outcome of this equivalence is the establishment of non-asymptotic rates: the authors prove an $O(1/k)$ convergence rate to a stationary point for unconstrained, convex-constrained, and advanced CCCP+ problems.
A fascinating insight from this analysis is the concept of curvature independence. Standard Frank-Wolfe convergence typically depends on a curvature constant (how much the function curves). However, because the reformulated CCCP objective is concave, this constant effectively vanishes. This mathematical quirk explains why CCCP is often much faster and more robust in practice than other first-order methods, as it does not require the usual Lipschitz smoothness assumptions to guarantee its $1/k$ convergence rate.
Broader Implications and Future Work
This work suggests a unifying theory for optimization algorithms. Seemingly disparate algorithms—such as the proximal point method, mirror descent, and Sinkhorn’s algorithm—might all belong to the same "Frank-Wolfe family" when viewed through the correct mathematical lens. Since CCCP is a type of Majorize-Minorize (MM) algorithm, the authors speculate that other MM algorithms might also be disguised versions of known optimization procedures.
While this paper is purely theoretical and does not include empirical benchmarks, it lays a robust foundation for future research. Current limitations and future directions include:
- Smoothness Assumptions: The current analysis primarily assumes that the functions $f$ and $g$ are differentiable. Extending this framework to non-smooth DC programming using subgradients remains an open challenge.
- Stochastic Variants: The paper focuses on deterministic settings. The authors propose developing "Stochastic CCCP" by leveraging recent breakthroughs in stochastic Frank-Wolfe methods.
- Broader Unification: Further exploration into how other MM algorithms map to existing optimization procedures could yield new theoretical breakthroughs across the field.
Summary updated