Stochastic Difference-of-Convex Optimization with Momentum

Abstract

We study the online stochastic difference-of-convex (DC) program ${\min }_{x\in R^n}F(x)=G(x)-H(x)+r_1(x)-r_2(x)$, which covers sparse learning with nonconvex penalties, robust regression with smooth robust losses, and non-negative positive--unlabeled learning. We propose \emph{momentum-based DCA} (MDCA), which combines a damped DCA step with a momentum estimator for $\nabla H$ and uses a constant per-iteration batch size. With exact solutions of the convex subproblems, MDCA with Polyak momentum uses $\mathcal{O}({\epsilon }^{-4})$ stochastic gradients of $H$ to reach $\epsilon$-stationarity, and momentum-based variance reduction (MVR) uses $\mathcal{O}({\epsilon }^{-3})$ under averaged smoothness, with a single $\mathcal{O}({\epsilon }^{-1})$ warm-up batch in place of the periodic large batches of DCA-PAGE, whose $\epsilon$-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 $\gamma$ for which the separately smoothed surrogate $F_{\gamma }$ is bounded below, it reaches $\epsilon$-stationarity of $F_{\gamma }$ in $\mathcal{O}({\epsilon }^{-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 $r_2$ and vanishes exactly at DC-critical points; both give the same $\epsilon$-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.

Published in Transactions on Machine Learning Research (10/2026)