On the convergence rate of the boosted Difference-of-Convex Algorithm (DCA)

Hadi Abbaszadehpeivasti, Etienne de Klerk, Adrien Taylor · 2025

Read On the convergence rate of the boosted Difference-of-Convex Algorithm (DCA) by Hadi Abbaszadehpeivasti, Etienne de Klerk, Adrien Taylor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16569.txt.

Introduction

Hadi Abbaszadehpeivasti, Etienne de Klerk, and Adrien Taylor rate a boosted solver in a 2025 paper. The Difference-of-Convex Algorithm, or DCA, solves tasks whose cost splits as a gap of two dome-shaped parts. Each step solves a dome-shaped sub-task, then moves on. Boosting adds one extra step along the same line. Past number tests praised the boost, but no proof said why.

The trio prove the boost is strictly better in the worst case, for set classes. Their proof leans on performance estimation with matrix tools. Those tools turn worst-case bounds into a solvable matrix task. The result backs wide reports that boosted runs beat plain runs. It also shows which cost splits gain most from a boost.

Catalog record

CREATORHadi Abbaszadehpeivasti, Etienne de Klerk, Adrien Taylor
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16569

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the convergence rate of the boosted Difference-of-Convex Algorithm (DCA) Hadi Abbaszadehpeivasti, Etienne de Klerk, Adrien Taylor Abstract The difference-of-convex algorithm (DCA) is a well-established nonlinear programming technique that solves successive convex optimization problems. These sub-problems are obtained from the difference-of-convex (DC) decompositions of the objective and constraint functions. We investigate the worst-case performance of the unconstrained DCA, with and without boosting, where boosting simply performs an additional step in the direction generated by the usual DCA method. We show that, for certain classes of DC decompositions, the boosted DCA is provably better in the worst-case than the usual DCA. While several numerical studies have reported that boosted DCA outperforms classical DCA, a theoretical explanation for this behavior has, to the best of our knowledge, not been given until now. Our proof technique relies on semidefinite programming (SDP) performance estimation. K eywords Boosted DCA, semidefinite programming, performance estimation, difference of convex functions 1 Introduction We consider the unconstrained difference-of-convex (DC) optimization problem \displaystyle\ \ f^{\star}:= \displaystyle\inf f(x) (1) \displaystyle\ \text{s.t.}\ x\in\mathbb{R}^{n} where f:\mathbb{R}^{n}\to\mathbb{R} is a difference-of-convex (DC) function, i.e. f=f_{1}-f_{2}, where f_{1} and f_{2} are closed convex proper functions. We also assume that the infimum f^{\star} is finite, but not necessarily attained. We will further restrict ourselves to the case where f_{1} and f_{2} are so-called functions of bounded curvature. To this end, recall that a function f has a maximum curvature 0\leq L<\infty if x\mapsto\tfrac{L}{2}\|x\|^{2}-f(x) is convex, and minimum curvature \mu>-\infty if x\mapsto f(x)-\tfrac{\mu}{2}\|x\|^{2} is convex. The class of functions with minimum curvature \mu and maximum curvature L will be denoted by \mathcal{F}_{\mu,L}(\mathbb{R}^{n}) . The celebrated difference-of-convex (DCA) algorithm for problem ( 1 ) may be stated as follows. Algorithm 1 DCA Pick x^{1}\in\mathbb{R}^{n} (starting point), N\in\mathbb{N} (number of iterations). For k=1,2,\ldots,N perform the following steps: 1. Pick g_{2}^{k}\in\partial f_{2}(x^{k}) . 2. Set \displaystyle x^{k+1}\in\text{argmin}_{x\in\mathbb{R}^{n}}f_{1}(x)-\left(f_{2}(x^{k})+\langle g_{2}^{k},x-x^{k}\rangle\right). In the statement of Algorithm 1 , \partial f_{i}(x^{k}) ( i=1,2 ) refers to the set of subgradients of f_{i} at x^{k} . The first convergence results for Algorithm 1 are attributed to [ 15 , Theorem 3(iv)] , namely if the sequence of iterates \{x^{k}\} is bounded, then each accumulation point x^{\star} of this sequence is a critical point of problem ( 1 ), i.e. \partial f_{1}(x^{\star})\cap\partial f_{2}(x^{\star})\neq\emptyset . For the history and properties of the DCA we refer to the surveys by Le Thi and Dinh [ 9 , 10 ] and Lipp and Boyd [ 11 ] . A more recent variant of the DCA, the so-called boosted DCA [ 8 , 3 , 4 ] , extends the DCA step as follows. Algorithm 2 Boosted DCA Pick x^{1}\in\mathbb{R}^{n} (starting point), N\in\mathbb{N} (number of iterations), and \alpha\in[0,1] (boosted step length). For k=1,2,\ldots,N perform the following steps: 1. Pick g_{2}^{k}\in\partial f_{2}(x^{k}) . 2. Set \displaystyle y^{k}\in\text{argmin}_{x\in\mathbb{R}^{n}}f_{1}(x)-\left(f_{2}(x^{k})+\langle g_{2}^{k},x-x^{k}\rangle\right). 3. Set d^{k}=y^{k}-x^{k} , and \displaystyle x^{k+1}=y^{k}+\alpha d^{k}. Note that the case \alpha=0 corresponds to the usual DCA. In both Algorithms 1 and 2 we assume that some subgradients of f_{1} and f_{2} are available at each iteration. The additional computational burden per iteration for boosted DCA is usually negligible compared to that of solving the intermediary subproblems and that of computing the subgradients. It is therefore natural to compare the worst-case performance of the two methods on the same number of iterations. The boosted DCA is motivated by the following lemma. Lemma 1 (Proposition 4 in [ 3 ] ) . Assume that f is continuously differentiable, and f_{1} and f_{2} have minimum curvature \mu>0 . Then, with reference to Algorithm 2 , one has \langle\nabla f(y^{k}),d^{k}\rangle\leq-\mu\|d^{k}\|^{2}. In other words, if f is smooth, and f_{1},f_{2} strongly convex, it is possible to reduce f further along the DCA direction d^{k} , i.e. d^{k} is a descent direction at y^{k} . This work investigates how different performance measures depend on the choice of “boosted” step length \alpha . Our goal is to give a theoretical explanation of the advantage that one may obtain using boosted DCA as opposed to DCA. This, in turn, is motivated by successful numerical experiments in [ 3 , 20 ] , which show that boosted DCA typically outperforms DCA in practice. Outline and contributions This work shows that boosted DCA enjoys the following worst-case convergence guarantee. Theorem 1 . Let f_{1}\in\mathcal{F}_{\mu,L}({\mathbb{R}^{n}}) and f_{2}\in\mathcal{F}_{\mu,L}({\mathbb{R}^{n}}) , 0\leq\mu<L<\infty . After N iterations of boosted DCA (Algorithm 2 ), one has, \min_{1\leqslant k\leqslant N+1}\frac{\left\|g_{1}^{k}-g_{2}^{k}\right\|^{2}}{L}\leqslant\frac{(f(x^{1})-f^{\star})}{(1+\kappa\alpha)N+\frac{1}{2(1-\kappa)}}, where \kappa:=\mu/L\in[0,1) , and where 0\leq\alpha\leq\min\{1,2\kappa\} . When \alpha=0 , this result reduces to a known (tight) convergence result for DCA, namely a special case of Theorem 3.1 in [ 1 ] . As soon as \kappa>0 , Theorem 1 shows that improved performance guarantees can be obtained with \alpha>0 . Theorem 1 is proved below in Section 3 using the semidefinite programming (SDP) performance estimation approach, as pioneered by Drori and Teboulle [ 7 ] . More precisely, we use the refined version from [ 17 , 18 ] to allow for tight analysis. Thus, we will first review the performance estimation method in some detail in Section 2 . One of the attractive features of the DCA is that it contains some well-known algorithms as special cases, like gradient descent, and proximal gradient descent; see e.g. [ 13 ] . In Section 4 , we investigate the implications of our analysis for the boosted DCA in the special case of gradient descent. In particular, if the objective satisfies a quadratic Łojasiewicz condition (also often referred to as Polyak-Łojasiewicz), we present results on the rate of linear convergence. Section 5 concludes with open questions and a further discussion of related literature. 2 Performance estimation A key step to the desired convergence results consists in formulating an abstract optimization problem that aims to find the worst-case input f_{1}\in\mathcal{F}_{\mu_{1},L_{1}}(\mathbb{R}^{n}) and f_{2}\in\mathcal{F}_{\mu_{2},L_{2}}(\mathbb{R}^{n}) for Algorithm 2 , where we view \mu_{1},\mu_{2},L_{1},L_{2} as given parameters: \displaystyle\max \displaystyle\left(\min_{1\leqslant k\leqslant N+1}\left\|g_{1}^{k}-g_{2}^{k}\right\|^{2}\right) (2) \displaystyle f_{1}\in\mathcal{F}_{\mu_{1},L_{1}}(\mathbb{R}^{n}),f_{2}\in\mathcal{F}_{\mu_{2},L_{2}}(\mathbb{R}^{n}) \displaystyle f_{1}(x)-f_{2}(x)\geqslant f^{\star}\ \ \ \forall x\in\mathbb{R}^{n} \displaystyle f_{1}(x^{1})-f_{2}(x^{1})-f^{\star}\leqslant\Delta \displaystyle g_{1}^{N+1},g_{2}^{N+1},x^{N+1},\ldots,x^{2}\ \textrm{are generated by Algorithm \ref{Alg:BCDA} w.r.t.}\ f_{1},f_{2},x^{1} \displaystyle x^{1}\in\mathbb{R}^{n}, where f_{1},f_{2} and x^{k},g_{1}^{k},g_{2}^{k} ( k\in\{1,...,N+1\} ) are decision variables, and \Delta,\mu_{1},L_{1},\mu_{2},L_{2},N are fixed parameters. At first glance, this problem seems intractable, since we need to optimize over the infinite-dimensional function spaces \mathcal{F}_{\mu_{1},L_{1}}(\mathbb{R}^{n}) and \mathcal{F}_{\mu_{2},L_{2}}(\mathbb{R}^{n}) . However, since we only reference f_{1} and f_{2} (and their subgradients) at the N iterates, we may reformulate these membership conditions as tractable interpolation conditions as in [ 17 ] . To this end, consider a finite index set I (that will correspond to iterates in our analysis), and given a set of triplets \left\{(x^{k},g^{k},f^{k})\right\}_{k\in I} where x^{k}\in\mathbb{R}^{n} , g^{k}\in\mathbb{R}^{n} and f^{k}\in\mathbb{R} . We are concerned with the following interpolation/extension result: for given \mu\geq 0 and L\geq\mu , does there exist a f\in\mathcal{F}_{\mu,L}(\mathbb{R}^{n}) such that f(x^{k})=f^{k} , and g^{k}\in\partial f(x^{k}) for all k\in I . If yes, we say that \left\{(x^{k},g^{k},f^{k})\right\}_{k\in I} is \mathcal{F}_{\mu,L}(\mathbb{R}^{n}) -interpolable. Theorem 2 . ( [ 17 ] , Theorem 4) The following statements are equivalent: 1. \left\{(x^{i},g^{i},f^{i})\right\}_{i\in I} is \mathcal{F}_{\mu,L}(\mathbb{R}^{n}) -interpolable; 2. \forall i,j\in I : \frac{1}{2(1-\frac{\mu}{L})}\left(\frac{1}{L}\left\|g^{i}-g^{j}\right\|^{2}+\mu\left\|x^{i}-x^{j}\right\|^{2}-\frac{2\mu}{L}\left\langle g^{j}-g^{i},x^{j}-x^{i}\right\rangle\right)\leqslant f^{i}-f^{j}-\left\langle g^{j},x^{i}-x^{j}\right\rangle. (3) Using this theorem, as well as the following lemma, we may reformulate ( 2 ) as an SDP. Lemma 2 ( [ 1 ] , Lemma 2.1 ( Descent

Read the complete text