Stochastic Difference-of-Convex Optimization with Momentum

We study the online stochastic difference-of-convex (DC) program 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 grad 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 r 2 and vanishes exactly at DC-critical points; both give the same ε-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.