Improved convergence rates for the Difference-of-Convex algorithm

Teodor Rotaru, Panagiotis Patrinos, François GlineurarXiv 2024 · DOI · arXiv

TL;DR

This paper extends the theoretical analysis of the Difference-of-Convex Algorithm (DCA) to a broader class of problems where one of the functions is allowed to be "hypoconvex" (weakly nonconvex). By identifying eight distinct parameter regimes, the authors provide tight bounds on objective function decrease and prove new $O(1/N)$ sublinear convergence rates, significantly refining our understanding of how this classic algorithm behaves in non-standard settings.

What Problem Does This Paper Address?

Optimization problems often take the form of a "Difference-of-Convex" (DC) function: $F(x) = f_1(x) - f_2(x)$. The standard Difference-of-Convex Algorithm (DCA) is a go-to method for solving these, traditionally assuming both $f_1$ and $f_2$ are convex.

However, in many real-world applications, one of these terms might be slightly nonconvex (known as hypoconvex or weakly convex). While practitioners often use DCA anyway, the theoretical guarantees for these cases were either non-existent or not "tight"—meaning the predicted convergence speed was much slower than what was observed in practice. This paper fills that gap by providing a precise, rigorous characterization of DCA's performance when convexity is relaxed.

Methods

The authors employ the Performance Estimation Problem (PEP) framework. PEP is a powerful meta-optimization approach where one writes a computer program to find the "worst-case" function for a specific algorithm.

Key methodological contributions include:

  • Curvature Classes: They define functions using the class $\mathcal{F}_{\mu, L}$, where $L$ represents the maximum curvature (smoothness) and $\mu$ represents the minimum curvature. Crucially, they allow $\mu$ to be negative, which represents hypoconvexity.
  • Regime Partitioning: The authors divide the space of problem parameters into eight distinct "regimes" based on the relationship between the smoothness and convexity of $f_1$ and $f_2$.
  • Interpolation Inequalities: They use necessary and sufficient conditions for function interpolation to transform the search for convergence rates into a solvable semidefinite program (SDP).

Datasets

As a theoretical paper in mathematical optimization, no external real-world datasets were used. Instead, the "data" consists of numerical results from solving the Performance Estimation Problems (using tools like PESTO or PEPit). These numerical experiments were used to verify the tightness of the analytical bounds across thousands of parameter combinations.

Key Insights and Ideas

  • The $\mu_1 + \mu_2 \geq 0$ Condition: The authors show that DCA is guaranteed to decrease the objective function as long as the "total" convexity of the system is non-negative, even if one individual term is nonconvex.
  • Symmetry in Optimization: There is a striking symmetry between the eight identified regimes. Formulas for regimes with even indices can often be derived from odd indices simply by swapping the roles of $f_1$ and $f_2$.
  • Tightness via PEP: Unlike traditional proofs that use loose inequalities, the authors' use of PEP allowed them to find the exact worst-case behavior for a single step of the algorithm.
  • Threshold Conditions: They identified specific "threshold" lines (labeled $S_1$ and $S_2$ in the paper) that separate standard convex behavior from the more complex dynamics of hypoconvex optimization.

Key Results

  • One-Step Decrease: Theorem 3.1 provides an exact lower bound for the objective decrease after a single iteration for all eight regimes.
  • Global Convergence Rates: Theorem 3.2 proves that DCA converges to a critical point at a sublinear rate of $O(1/N)$.
  • Conjectured Tightness: Based on heavy numerical evidence, the authors conjecture that their derived rates are "tight" (the best possible) for four of the eight regimes.
  • Nonsmooth Extension: The paper also extends these results to the "nonsmooth" case (where functions aren't necessarily differentiable), providing a simpler and more general proof than previous state-of-the-art research.

Limitations and Future Work

  • Asymptotic vs. Finite-time: For two specific regimes ($p_5$ and $p_6$), the authors found that their single-step bounds are not tight over multiple iterations. They provide a conjecture for the asymptotic behavior but haven't yet proven a tight finite-time bound.
  • Linear Convergence: In regimes where the objective is strongly convex ($p_7$ and $p_8$), the algorithm actually achieves linear convergence (faster than $1/N$). The authors acknowledge this but leave the precise description of these linear rates for future research.
  • Optimal Splitting: A major open question is how to "split" a function $F(x)$ into $f_1 - f_2$ most effectively. Since different splits lead to different convergence regimes, finding the "optimal" split for a given problem remains a challenge.

Summary updated

Abstract

We consider a difference-of-convex formulation where one of the terms is allowed to be hypoconvex (or weakly convex). We first examine the precise behavior of a single iteration of the Difference-of-Convex algorithm (DCA), giving a tight characterization of the objective function decrease. This requires distinguishing between eight distinct parameter regimes. Our proofs are inspired by the performance estimation framework, but are much simplified compared to similar previous work. We then derive sublinear DCA convergence rates towards critical points, distinguishing between cases where at least one of the functions is smooth and where both functions are nonsmooth. We conjecture the tightness of these rates for four parameter regimes, based on strong numerical evidence obtained via performance estimation, as well as the leading constant in the asymptotic sublinear rate for two more regimes.
BibTeX
@misc{rotaru2024improved,
  author = {Teodor Rotaru and Panagiotis Patrinos and François Glineur},
  title = {{Improved convergence rates for the Difference-of-Convex algorithm}},
  year = {2024},
  eprint = {2403.16864},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.16864},
}
Figure