Improved Rates for Stochastic Variance-Reduced Difference-of-Convex Algorithms

Anh Duc Nguyen Alp Yurtsever Suvrit Sra Kim-Chuan Toh · 2025

Read Improved Rates for Stochastic Variance-Reduced Difference-of-Convex Algorithms by Anh Duc Nguyen Alp Yurtsever Suvrit Sra Kim-Chuan Toh (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-2509-11657.txt.

Introduction

Anh Duc Nguyen and three co-authors speed up a class of optimization algorithms in this 2025 paper. Their target is difference-of-convex programs, problems whose objective splits into the difference of two convex functions, with a nonsmooth twist, a structure that appears across machine learning and signal processing.

Their algorithm, DCA-PAGE, marries the difference-of-convex algorithm with a probabilistic gradient estimator that reuses past stochastic gradients to cut variance. In the finite-sum setting it lowers the gradient computation cost compared with the previous best stochastic variance-reduced methods, improving the exponent in the problem-size term. Unlike those rivals, it also extends to online settings where data arrive as a stream, with a similar optimal cost. A refined analysis using a gap function recovers comparable guarantees under milder assumptions.

Catalog record

CREATORAnh Duc Nguyen Alp Yurtsever Suvrit Sra Kim-Chuan Toh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11657

Browse the full library · About the Tower of Babel

Full text

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

Improved Rates for Stochastic Variance-Reduced Difference-of-Convex Algorithms Anh Duc Nguyen Alp Yurtsever Suvrit Sra Kim-Chuan Toh Abstract In this work, we propose and analyze DCA-PAGE, a novel algorithm that integrates the difference-of-convex algorithm (DCA) with the ProbAbilistic Gradient Estimator (PAGE) to solve structured nonsmooth difference-of-convex programs. In the finite-sum setting, our method achieves a gradient computation complexity of 𝒪 ⁡ ( N + N 1 / 2 ​ ε − 2 ) \mathcal{O}(N+N^{1/2}\varepsilon^{-2}) with sample size N N , surpassing the previous best-known complexity of 𝒪 ⁡ ( N + N 2 / 3 ​ ε − 2 ) \mathcal{O}(N+N^{2/3}\varepsilon^{-2}) for stochastic variance-reduced (SVR) DCA methods. Furthermore, DCA-PAGE readily extends to online settings with a similar optimal gradient computation complexity 𝒪 ⁡ ( b + b 1 / 2 ​ ε − 2 ) \mathcal{O}(b+b^{1/2}\varepsilon^{-2}) with batch size b b , a significant advantage over existing SVR DCA approaches that only work for the finite-sum setting. We further refine our analysis with a gap function, which enables us to obtain comparable convergence guarantees under milder assumptions. I INTRODUCTION We study the following nonconvex nonsmooth problem: \displaystyle\min_{x\in\mathbb{R}^{n}}F(x)=G(x)-H(x)+r_{1}(x)-r_{2}(x), (M) where G,H:=\frac{1}{N}\sum_{i=1}^{N}h_{i},h_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R} and r_{1},r_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\{+\infty\} are convex, lower semicontinuous functions, and h_{i} are differentiable. Such problems arise in various applications, particularly in machine learning, where G-H represents the data-fitting term, i.e. the loss function, while r_{1}-r_{2} corresponds to the regularization term [ 1 ] . A convex regularizer admits the trivial DC decomposition r=r-0 . Moreover, popular nonconvex regularizers, like capped \ell_{1} [ 2 ] and SCAD [ 3 ] , also possess DC decompositions [ 4 , 5 ] . Broadly speaking, the structure presented in ( M ) falls within the well‐established class of difference‑of‑convex (DC) programs, a powerful framework for tackling challenging nonconvex nonsmooth optimization problems by decomposing them as the difference of two convex functions [ 6 , 7 ] . A prominent method for DC programs is the difference-of-convex algorithm (DCA) [ 6 ] , renowned for its simplicity and flexibility [ 8 ] . In its simplest form, DCA alternately linearizes the concave component and solves a convex subproblem, guaranteeing monotonic descent and convergence to a critical point under mild assumptions [ 6 ] . The subclass of DC problems represented by ( M ) encompasses a broad range of applications [ 1 ] . One prominent example is regularized empirical risk minimization (ERM), which underpins essential techniques such as LASSO [ 9 ] and principal component analysis (PCA) [ 10 ] . In particular, the regularized ERM has the form \displaystyle\min_{x\in\mathbb{R}^{n}}\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)+r(x), where f_{i} are L -smooth and not necessarily convex for all i\in[N] and r is a regularizer with DC structure, i.e. r(x)=r_{1}(x)-r_{2}(x) for convex functions r_{1} and r_{2} . ERM can be reformulated into ( M ) as follows \displaystyle\min_{x\in\mathbb{R}^{n}}\frac{L\|x\|^{2}}{2}-\frac{1}{N}\sum_{i=1}^{N}\left(\frac{L\|x\|^{2}}{2}-f_{i}(x)\right)+r_{1}(x)-r_{2}(x). (S) Note that in this case, L\|x\|^{2}/2-f_{i}(x) is convex since f_{i} are L -smooth for all i\in[N] . Beyond the finite-sum setting, many real-world applications involve large-scale or streaming data, where N can be extremely large or even effectively infinite [ 11 ] . In these scenarios, we also consider the online formulation of H(x) \displaystyle H(x)\vcentcolon=\mathbb{E}_{\zeta\sim\mathcal{D}}[\Phi(x,\zeta)], where \zeta is a random data instance and \Phi is the instantaneous sample loss. We use the same notation as in the finite-sum case, writing h_{i}(x)\vcentcolon=\Phi(x,\zeta_{i}) for i.i.d. samples \{\zeta_{i}\} drawn from the stream, and we treat N as large (or unbounded). In addition, recent applications of DC programming span various engineering disciplines, including signal recovery [ 12 ] , signal processing [ 13 ] , discrepancy estimation in domain adaptation [ 14 ] , neural networks optimization [ 15 ] , shortcut architecture [ 16 ] , unsupervised learning [ 17 ] , biomedical signal processing [ 18 ] , and reinforcement learning [ 19 ] . As these applications scale up, the demand for efficient DCA algorithms and their variants continues to grow. Incorporating stochastic methods is a natural extension given their success in convex and smooth nonconvex optimization [ 20 ] . However, significant challenges remain when adapting stochastic methods like stochastic variance reduction (SVR) to nonsmooth nonconvex settings. Since DCA is particularly well-suited for handling nonsmooth and nonconvex problems, it offers a promising framework for integrating these techniques. While [ 1 ] has introduced two SVR DCA methods, there still exists a gap between the optimal gradient computation complexity for smooth nonconvex optimization \mathcal{O}(N+N^{1/2}\varepsilon^{-2}) [ 21 ] and that for the nonsmooth case \mathcal{O}(N+N^{2/3}\varepsilon^{-2}) [ 1 ] . Our goal is to bridge this gap and further refine the analysis of SVR DCA methods in more general cases, like online settings. I-A Contributions In this work, we introduce DCA-PAGE, a novel SVR DC algorithm that leverages the ProbAbilistic Gradient Estimator (PAGE) [ 21 ] . Our key contributions are: • Improved Complexity: Compared to existing stochastic DC algorithms, DCA-PAGE achieves the complexity of \mathcal{O}(N+N^{1/2}\varepsilon^{-2}) , improving the SOTA complexity for SVR DCA methods \mathcal{O}(N+N^{2/3}\varepsilon^{-2}) [ 1 ] for problem ( M ) 1 1 1 MM-SARAH [ 22 ] achieves a similar optimal rate for the decomposition ( S ) which is a special case of ( M ). . We compare the complexity with other related DCA methods in Table I . • Online Settings: As DCA-PAGE only needs occasional large-minibatch updates, we readily extend the convergence analysis to the online case, overcoming a key limitation of previous SVR DCA methods [ 1 ] . • Refined Analysis with Gap Function: We propose an alternative measure of optimality for SVR DCA methods. This gap measure enables DCA-PAGE to maintain similar convergence guarantees while imposing fewer smoothness assumptions than earlier approaches. • Empirical Validation: We demonstrate the effectiveness of our method in practical applications, specifically in nonconvex binary and multi-class logistic classification. TABLE I: Overview of SVR DCA and Related Methods Algorithm Problem Complexity Online DCA-SAGA [ 1 ] ( M ) \mathcal{O}\left(N+N^{3/4}\varepsilon^{-2}\right) \times DCA-SVRG [ 1 ] ( M ) \mathcal{O}\left(N+N^{2/3}\varepsilon^{-2}\right) \times MM-SAGA [ 22 ] ( S ) \mathcal{O}\left(N+N^{2/3}\varepsilon^{-2}\right) \times MM-SVRG [ 22 ] ( S ) \mathcal{O}\left(N+N^{2/3}\varepsilon^{-2}\right) \times MM-SARAH [ 22 ] ( S ) \mathcal{O}\left(N+N^{1/2}\varepsilon^{-2}\right) \times DCA-PAGE (Alg 1 ) ( M ) \mathcal{O}\left(N+N^{1/2}\varepsilon^{-2}\right) \checkmark I-B Related Work Regarding SVR DCA variants, [ 1 ] constructs the convex subproblems by employing SVRG [ 23 ] and SAGA [ 24 ] gradient estimators, while [ 25 , 26 ] adopts the SAG estimator. Alternatively, [ 27 ] employs deterministic DCA and utilizes stochastic algorithms such as [ 23 ] to solve the convex subproblems. More recently, [ 22 ] focuses on the particular DC formulation ( S ) and introduces SVR Majorization-Minimization (MM) algorithms with variance reduction. The authors employ SVRG [ 23 ] , SAGA [ 24 ] , and SARAH [ 28 ] gradient estimators for the construction of the iterate update. Although [ 22 ] does not require the regularizer r to have a DC decomposition (as in ( M )), their study is confined to the specialized setting ( S ). For online DCA variants, [ 29 , 30 ] show only convergence of their online DCA variants without any computational complexity albeit in very general settings. Regarding the gap function measure, recent works [ 31 , 32

Read the complete text