CCCP is Frank-Wolfe in disguise

Alp Yurtsever, Suvrit Sra

Abstract

This paper uncovers a simple but surprising connection: the well-known convex-concave procedure (CCCP) and its generalization to constrained problems are both special cases of the Frank-Wolfe (FW) method. This connection provides significant pedagogical value and immediately transfers the recently discovered convergence theory of nonconvex Frank-Wolfe methods to CCCP, closing a long-standing gap in its non-asymptotic convergence theory. The authors establish that CCCP reaches stationary points at a rate of $O(1/k)$, a result that is remarkably independent of the curvature constants typically required in first-order optimization proofs.

Introduction: The Challenge of Difference-of-Convex Programming

In non-convex optimization, Difference-of-Convex (DC) programming is a fundamental framework. It addresses problems where the objective function can be decomposed into the difference of two convex functions: $f(x) - g(x)$. While both $f$ and $g$ are convex, their difference is generally non-convex, making global optimization difficult.

The standard algorithm for solving such problems is the Convex-Concave Procedure (CCCP). CCCP is prized for its simplicity and effectiveness, serving as the engine for many popular algorithms, including Expectation-Maximization (EM). Historically, while the asymptotic convergence of CCCP (i.e., that it eventually reaches a stationary point) was well-established, its non-asymptotic convergence rate—how many iterations are required to reach a specific precision $\epsilon$—remained a mystery.

The Hidden Identity: Mapping CCCP to Frank-Wolfe

The central contribution of this work is the revelation that CCCP is not a distinct algorithmic species but rather a specific application of the Frank-Wolfe (FW) algorithm, also known as the conditional gradient method.

The authors achieve this by reformulating the unconstrained DC problem into an equivalent "epigraph" form: $$\min_{x,t} \quad t - g(x) \quad \text{s.t.} \quad f(x) \le t$$ In this formulation, the objective $t - g(x)$ is concave (since $-g(x)$ is concave), and the constraint $f(x) \le t$ defines a convex feasible set. When the standard Frank-Wolfe algorithm is applied to this specific concave minimization problem over a convex set, the resulting update steps are mathematically identical to those of CCCP.

Theoretical Breakthroughs: Speed and Smoothness

By establishing this link, the authors can leverage the mature convergence theory of Frank-Wolfe to solve the theoretical gaps in CCCP.

1. Non-Asymptotic Convergence Rates

While Frank-Wolfe on general non-convex problems typically converges at a rate of $O(1/\sqrt{k})$, the specific structure of the DC reformulation—minimizing a concave function—allows for a faster rate. The paper proves that CCCP finds an $\epsilon$-stationary point in $O(1/\epsilon)$ iterations, or a rate of $O(1/k)$. This provides the first rigorous "speed limit" for an algorithm that has been used empirically for decades.

2. Independence from Smoothness Constants

Most first-order optimization proofs rely on "L-smoothness," where the gradient's rate of change is bounded by a Lipschitz constant $L$. A striking insight from this paper is that the convergence rates for CCCP are independent of these curvature constants. This theoretical result explains why CCCP remains robust and efficient in practice even when applied to functions that are not perfectly smooth or have high curvature.

Generalizing to Constraints: CCCP+ and FW+

The paper goes further by addressing DC programs with DC constraints, often referred to as CCCP+. Standard Frank-Wolfe requires a convex feasible set, which poses a problem for non-convex constraints. To bridge this, the authors introduce FW+, a variant that linearizes both the objective and the non-convex constraints at each iteration. They demonstrate that CCCP+ is a specialized version of FW+, thereby providing the first non-asymptotic convergence guarantees for this more general class of problems.

Conclusion and Future Directions

By unmasking CCCP as Frank-Wolfe in disguise, this work unifies two major branches of optimization. Beyond the immediate theoretical gains, this perspective opens several new avenues for research:

  • Stochastic Extensions: Existing stochastic variants of Frank-Wolfe can now be directly adapted to create "Stochastic CCCP" for large-scale machine learning.
  • Non-Smooth Optimization: While the current theory handles some subgradient cases, a full treatment of non-smooth DC components remains an open challenge.
  • Broader MM Methods: CCCP is a member of the Majorize-Minorize (MM) family. This research suggests that other MM algorithms might also be reformulations of Frank-Wolfe, potentially leading to a broader unification of optimization techniques.

This work effectively closes a long-standing gap in the literature, providing the rigorous mathematical foundation that matches the long-observed empirical success of the Convex-Concave Procedure.

Summary updated

Abstract

This paper uncovers a simple but rather surprising connection: it shows that the well-known convex-concave procedure (CCCP) and its generalization to constrained problems are both special cases of the Frank-Wolfe (FW) method. This connection not only provides insight of deep (in our opinion) pedagogical value, but also transfers the recently discovered convergence theory of nonconvex Frank-Wolfe methods immediately to CCCP, closing a long-standing gap in its non-asymptotic convergence theory. We hope the viewpoint uncovered by this paper spurs the transfer of other advances made for FW to both CCCP and its generalizations.
BibTeX
@inproceedings{yurtsever2022cccp,
  author = {Alp Yurtsever and Suvrit Sra},
  title = {{CCCP is Frank-Wolfe in disguise}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=OGGQs4xFHrr},
}
Figure