TL;DR
This paper provides the first set of tight, sublinear convergence rates for the Difference-of-Convex Algorithm (DCA) using the "composite gradient mapping" metric. By identifying six distinct curvature regimes and leveraging computer-aided performance estimation (PEP), the authors establish exact worst-case guarantees for short horizons and provide conjectured exact rates for any number of iterations.
What Problem Does This Paper Address?
The Difference-of-Convex Algorithm (DCA) is a workhorse for non-convex optimization, particularly when an objective can be split into two convex components: $F(x) = f_1(x) - f_2(x)$. While DCA is widely used, its theoretical convergence guarantees have historically been "loose" or restricted to specific settings.
Most existing analyses focus on the "gradient residual" (the norm of the subgradients). However, this paper shifts the focus to composite gradient mapping (also known as the prox-gradient mapping). This metric is more robust for non-smooth problems and provides a clearer picture of how close an iterate is to a critical point. The authors aim to fill the gap in theoretical guarantees for various curvature settings, including cases where the second function ($f_2$) is weakly convex rather than strictly convex.
Methods
The authors employ a mix of traditional mathematical proofs and modern computer-aided analysis:
- Performance Estimation Problems (PEP): This is a "meta-optimization" technique where researchers write a program to find the worst-case function and starting point for a specific algorithm. This allows them to discover the "tightest" possible bounds.
- Descent Lemmas: The authors derive new, adapted descent lemmas that account for the specific curvatures ($\mu$ and $L$ parameters) of $f_1$ and $f_2$.
- Regime Partitioning: They divide the parameter space into six distinct regimes based on the relationship between the strong convexity and smoothness constants of the two functions.
- Algorithmic Equivalence: They exploit the known equivalence between DCA and Proximal Gradient Descent (PGD) to translate results between the two, allowing for the derivation of exact PGD rates even for stepsizes that exceed the standard inverse Lipschitz constant.
Datasets
Not discussed in the paper. As a theoretical optimization paper, the results are validated through numerical performance estimation (PEP) rather than empirical testing on standard machine learning datasets.
Key Insights and Ideas
- The Six Regimes: Convergence isn't "one size fits all." Depending on whether the objective is non-convex-non-concave, strongly convex, or concave, the "bottleneck" for convergence changes. The authors provide a map (Figure 1 in the paper) that identifies which rate applies where.
- Tightness for $N=2$: The authors prove that their derived sublinear rates are exact (cannot be improved) for at least two iterations of the algorithm.
- DCA as PGD: By viewing DCA through the lens of PGD, the authors show that choosing the "splitting" of the function is analogous to choosing a stepsize. This opens the door for "curvature shifting"—adjusting the convexity of the components to speed up the algorithm.
- Conjectured Exactness: For regimes where a rigorous proof for $N$ iterations is mathematically grueling, the authors provide conjectures based on high-precision numerical results from PEP, which align perfectly with known rates for Gradient Descent.
Key Results
- New Sublinear Rates: The paper establishes rates of the form $\min \|x^k - x^{k+1}\|^2 \le \frac{\Delta}{C \cdot N}$, where $C$ is a constant depending on the curvature regime.
- Regimes $p_1, p_2, p_3$: These rates are proven to be tight for any number of iterations $N$.
- Exact PGD Rates: The authors provide exact convergence rates for PGD with any constant stepsize, filling a gap in the literature for stepsizes larger than $1/L$.
- Refined Analysis: They recover and refine existing rates for standard DC decompositions, showing that previous bounds were often conservative.
Limitations and Future Work
- Conjectures vs. Proofs: While three of the six regimes are rigorously proven for any $N$, the other three ($p_4, p_5, p_6$) rely on conjectures for $N > 2$. Though these are numerically validated, a formal analytical proof remains an open challenge.
- Practical Implementation: The paper proposes an "adaptive curvature shifting" procedure based on their theoretical findings. However, the practical utility of this procedure on large-scale, real-world problems (like deep learning or large-scale imaging) is left for future research.
- Smoothness Assumptions: The analysis assumes certain smoothness or curvature bounds are known; in practice, estimating these constants can be difficult.
Summary updated