Stochastic Difference-of-Convex Optimization with Momentum

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 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}( ε^{-4})$ stochastic gradients of $H$ to reach $ε$-stationarity, and momentum-based variance reduction (MVR) uses $\mathcal{O}(ε^{-3})$ under averaged smoothness, with a single $\mathcal 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 $\mathcal{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 $r_2$ and vanishes exactly at DC-critical points; both give the same $ε$-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.