analiza aiqbench
This paper develops momentum-based variants of difference-of-convex (DC) optimization for stochastic learning problems such as sparse regression with nonconvex penalties, robust regression, and positive-unlabeled learning. It gives sample-complexity bounds for reaching approximate stationarity, with a single-loop variant whose guarantee applies to a smoothed surrogate rather than the original objective. For ML practitioners, the main takeaway is the theoretical efficiency gain from momentum and variance reduction with constant batch sizes, though the results are validated only on two LIBSVM datasets.
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 \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.
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.
Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)
arXiv:2510.17503 [cs.LG]
(or arXiv:2510.17503v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2510.17503 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 322 cuvinte
Subiecte conexe
Convergence Analysis of STORM Under Different Geometries
arXiv · 2 oct. 2026
Adaptive Variance Reduction without Knowing Oracle Smoothness
arXiv · 12 oct. 2026
Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
arXiv · 29 iul. 2026
Exact information accounting for SGD methods
arXiv · 2 oct. 2026