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.