Stochastic Difference-of-Convex Optimization with Momentum

arXiv:2510.17503v2 Announce Type: replace 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 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 O( epsilon^{-4}) stochastic gradients of H to reach epsilon-stationarity, and momentum-based variance reduction (MVR) uses 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 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.

Source: arXiv cs.LG | 2026-10-14