We study the online stochastic difference-of-convex (DC) program minx∈RnF(x)=G(x)−H(x)+r1(x)−r2(x), which covers sparse learning with nonconvex penalties, robust regression with smooth robust losses, and non-negative positive--unlabeled learning. We propose momentum-based DCA (MDCA), which combines a damped DCA step with a momentum estimator for ∇H and uses a constant per-iteration batch size. With exact solutions of the convex subproblems, MDCA with Polyak momentum uses O(ε−4) stochastic gradients of H to reach ε-stationarity, and momentum-based variance reduction (MVR) uses O(ε−3) under averaged smoothness, with a single O(ε−1) warm-up batch in place of the periodic large batches of DCA-PAGE, whose ε-dependence it matches. We also introduce a single-loop variant (S-MDCA) that replaces the subproblem solve by one stochastic prox-gradient step; for every fixed smoothing parameter γ for which the separately smoothed surrogate Fγ is bounded below, it reaches ε-stationarity of Fγ in O(ε−4) iterations, which does not by itself imply stationarity of F. A variance--drift trade-off lemma describes how the momentum parameter trades estimator variance against iterate-drift bias in steady-state upper bounds. Guarantees are given for two criteria: the critical-distance measure, and a DCA fixed-point residual that requires no smoothness of r2 and vanishes exactly at DC-critical points; both give the same ε-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.
Figure 1: Results on a9a . Median over 3 seeds; IQR shaded (with three seeds this band is only indicative). Left: training objective. Center: stationarity (squared prox-gradient mapping norm). Right: sparsity. Horizontal axis: stochastic gradient evaluations on G and H combined.
Figure 2: Results on w8a . Same conventions as Figure 1 .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Robust sparse regression on synthetic data ( n=5000 , d=700 , s=10 , 10% corrupted targets, Toeplitz correlation 0.7 ). Median over five seeds; IQR shaded. Out-of-assumption stress test (see text). Left: training objective, with F(θ⋆) marked. Center: stationarity at the F -best iterate. Right: sparsity at the F -best iterate, with the sparsity of θ⋆ marked; see the discussion in the text. Horizontal axis: stochastic gradient evaluations on G and H combined. Undamped SDCA diverged on all five seeds and is omitted.
Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.
In this paper, we study a structured class of nonconvex constrained stochastic problems with difference-of-convex (DC) regularization, where the feasible set is possibly nonconvex and the concave part of the DC regularizer is allowed to be nonsmooth. The fundamental challenge lies in maintaining feasibility for nonconvex constraints while achieving favorable oracle complexity. Although single-loop algorithms efficiently solve unconstrained DC optimization problems, their potential for constrained optimization with DC structure remains largely unexplored. To address this gap, we develop MoSSP, a Momentum-based Single-loop Stochastic Penalty method for such problems with provable complexity guarantees. The key idea is to apply a single stochastic proximal-gradient step to the Moreau envelope of the penalty plus the convex DC part, with the concave part's proximal mapping computed in parallel. We derive two algorithm variants: a Polyak-momentum version with O(ε−4) oracle complexity for finding stochastic ε-KKT points, and an improved O(ε−3) version incorporating recursive momentum. Experimental results demonstrate the effectiveness of the proposed algorithms.
Luxuan Li, Chunfeng Cui, Xiao Wang
School of Mathematical Sciences, Beihang University, Beijing 100191, China · School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China.
Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least O(ε−4) sample complexity to find an ε-stationary point. Some works indicate that this complexity can be improved to O(ε−3) when the stochastic loss gradient is Lipschitz continuous. The question of achieving enhanced convergence rates under distinct conditions, remains open. In this work, we address this question for optimization problems that are nonconvex in the minimization variable and strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We introduce novel bias-corrected momentum algorithms utilizing efficient Hessian-vector products. We establish convergence conditions and demonstrate a lower iteration complexity of O(ε−3) for the proposed algorithms. The effectiveness of the proposed method is validated through applications to robust logistic regression and robust adaptive cruise control.
Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. Sayed
Ecole Polytechnique Fédérale de Lausanne, Switzerland · Kuwait University, Kuwait
We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when active sets are large or combinatorial. We propose RA-DCA, a vertex-first randomized active-set DCA that projects active gradients onto sampled directions, checks a sampled vertex residual, and uses a small linear program only as a low-residual convex-combination fallback. The method preserves the descent structure of DCA and reduces the randomized screening layer to matrix multiplications. Under the stated regularity, numerical active-set consistency, and random-embedding assumptions, every accumulation point generated by the safeguarded method is directionally stationary with probability one. MATLAB experiments first test the theorem on degenerate max-affine, max-quadratic, and sparse support-function models, where the safeguard avoids nonstationary critical points and closely tracks a full active-vertex scan. Block top-k tests then show that the same screening idea remains useful when exact aggregate enumeration is combinatorial. Trimmed-regression, complementarity, and QUBO diagnostics separate cases where active-set selection helps from cases dominated by multistart search, the DC split, or other problem-specific features.
Yi-Shuai Niu
Beijing Institute of Mathematical Sciences and Applications (BIMSA), Beijing, China