MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-regularized Optimization

In this paper, we study a structured class of nonconvex constrained stochastic problems with difference-of-convex (DC) regularization, where the feasible set is possibly nonconvex and the concave part of the DC regularizer is allowed to be nonsmooth. The fundamental challenge lies in maintaining feasibility for nonconvex constraints while achieving favorable oracle complexity. Although single-loop algorithms efficiently solve unconstrained DC optimization problems, their potential for constrained optimization with DC structure remains largely unexplored. To address this gap, we develop **MoSSP**, a **Mo**mentum-based **S**ingle-loop **S**tochastic **P**enalty method for such problems with provable complexity guarantees. The key idea is to apply a single stochastic proximal-gradient step to the Moreau envelope of the penalty plus the convex DC part, with the concave part's proximal mapping computed in parallel. We derive two algorithm variants: a Polyak-momentum version with $\mathcal{O}(\varepsilon^{-4})$ oracle complexity for finding stochastic $\varepsilon$-KKT points, and an improved $\mathcal{O}(\varepsilon^{-3})$ version incorporating recursive momentum. Experimental results demonstrate the effectiveness of the proposed algorithms.

Many machine learning systems are trained by solving optimization problems: the system adjusts many numbers until it performs well. In practice, these problems often include extra rules, such as keeping a model within an energy budget, enforcing safety requirements, or selecting only a small number of useful features. These rules can make the optimization problem hard, especially when the training data are sampled randomly and the feature-selection penalty is itself difficult to handle. This paper proposes MoSSP, a new method for this setting. MoSSP updates the solution in a single loop, instead of repeatedly solving costly inner problems, and uses momentum to make progress more efficiently from noisy training information. We prove that two versions of MoSSP reach meaningful approximate solutions with predictable computational cost, with the recursive-momentum version requiring fewer gradient queries in theory. Experiments on constrained classification problems show that MoSSP reduces the objective and constraint violations effectively compared with double-loop baselines.