🔢 mathematics

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

This paper introduces MoSSP, a momentum-based single-loop stochastic penalty method that achieves provable $O(\varepsilon^{-4})$ and $O(\varepsilon^{-3})$ oracle complexities for finding stochastic $\varepsilon$ -KKT points in nonconvex constrained optimization problems with nonsmooth difference-of-convex regularization.

Original authors: Luxuan Li, Chunfeng Cui, Xiao Wang

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Luxuan Li, Chunfeng Cui, Xiao Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley (the objective function). However, there are two major complications:

The Terrain is Bumpy and Weird: The ground isn't just a smooth bowl; it's a mix of smooth hills and jagged, sharp rocks. In math terms, this is a "Difference-of-Convex" (DC) problem. It's like trying to walk down a hill that is actually a smooth hill minus a jagged mountain. The "minus mountain" part makes the path unpredictable and hard to navigate.
You Have Invisible Fences: You can't just wander anywhere. You must stay within a specific, possibly twisted, boundary (the constraints). In the real world, this is like a robot that must stay within a certain energy budget or a financial model that must obey strict safety rules. These boundaries aren't simple straight lines; they are curved and complex.
The Fog is Thick: You can't see the whole map. You only get to peek at small, random patches of the ground (the stochastic part) to guess where the bottom is.

The Problem with Old Methods

Previous algorithms tried to solve this by taking two steps at a time:

Step 1: Guess a path.
Step 2: Stop and solve a tiny, difficult puzzle to make sure you didn't hit a fence.
Repeat: Then guess again, solve another tiny puzzle, and so on.

This "double-loop" approach is like trying to drive a car while stopping every 10 feet to check a detailed map and re-calculate your route. It's accurate, but incredibly slow and computationally expensive, especially when the data is huge.

The New Solution: MoSSP

The paper introduces MoSSP (Momentum-based Single-loop Stochastic Penalty). Think of it as a smart, energetic hiker who uses a new strategy to navigate this foggy, fenced-in, jagged terrain.

Here is how MoSSP works, using simple metaphors:

1. The "Single-Loop" Shortcut

Instead of stopping to solve a tiny puzzle every time, MoSSP keeps moving in one continuous flow. It takes a step, checks the immediate surroundings, and immediately takes the next step. It's like a runner who adjusts their stride on the fly rather than stopping to tie their shoe every few seconds. This makes it much faster.

2. The "Penalty" Trick (The Rubber Band)

How does it handle the invisible fences without stopping? It uses a penalty method. Imagine the fences are actually made of giant, invisible rubber bands.

If you stay inside the fence, the rubber band is loose.
If you try to step outside, the rubber band pulls you back hard.
MoSSP treats this "pull" as part of the terrain itself. It doesn't need to check if you are inside the fence; it just feels the pull of the rubber band and adjusts its path accordingly.

3. The "Momentum" (The Heavy Ball)

The paper uses two versions of this hiker, both using momentum.

MoSSP-P (Polyak Momentum): Imagine a heavy ball rolling down the hill. If the ball is rolling fast, it doesn't stop immediately when it hits a small bump; it carries its speed forward. This helps the algorithm ignore small, noisy errors in the fog and keeps it moving toward the true bottom.
MoSSP-R (Recursive Momentum): This is a smarter version. It's like a hiker who remembers exactly how the fog shifted in the last step and uses that memory to correct their current guess. This "correction" makes the hiker even more efficient, cutting down the time needed to find the solution.

4. The "Smooth Surrogate" (The Map Overlay)

Because the terrain has jagged rocks (nonsmooth parts), the hiker can't just walk straight. MoSSP creates a "smooth overlay" (called a Moreau envelope) over the jagged rocks. It's like putting a sheet of clear plastic over a bumpy surface; you can't feel the individual bumps anymore, just the general slope. This allows the hiker to use standard walking techniques even on the roughest ground.

What Did They Prove?

The authors didn't just build this hiker; they proved mathematically how fast it works:

MoSSP-P is guaranteed to find a good solution (a point where you are close to the bottom and close to the fence) very quickly.
MoSSP-R is even faster, reaching the best possible speed for this type of problem.

They tested this on real-world data (like classifying emails as spam or not, and compressing neural networks) and showed that MoSSP reaches the finish line much faster than the old "double-loop" methods, while still obeying all the rules.

Summary

In short, MoSSP is a new, faster way to solve complex optimization problems where:

The goal is tricky (jagged terrain).
There are strict rules (invisible fences).
You only have partial information (fog).

It achieves this by combining a "rubber band" penalty system with "momentum" (carrying forward speed) and a "smoothing" technique, all in a single, continuous loop of movement, rather than stopping to solve tiny puzzles along the way.

Technical Summary: MoSSP for Nonconvex Constrained DC-Regularized Optimization

Problem Formulation
This paper addresses a structured class of nonconvex constrained stochastic optimization problems featuring Difference-of-Convex (DC) regularization. The problem is formulated as:
$\min_{x \in \mathbb{R}^n} F(x) = \mathbb{E}_{\xi}[f(x, \xi)] + h(x) - g(x) \quad \text{s.t.} \quad c(x) = 0,$
where $f$ is a stochastic smooth loss function, $h$ and $g$ are proper, closed, convex functions (with $g$ potentially nonsmooth), and $c(x)=0$ represents nonconvex equality constraints. The feasible set is assumed to be nonconvex. A key challenge in this setting is that the composite regularizer $h-g$ is generally non-prox-friendly (i.e., the proximal operator of the difference is not available in closed form), and the constraints are nonconvex, making feasibility maintenance difficult. Furthermore, exact gradients of $f$ are often inaccessible, necessitating the use of stochastic gradients.

Methodology: MoSSP
To address these challenges, the authors propose MoSSP (Momentum-based Single-loop Stochastic Penalty), a single-loop framework that avoids the computational burden of double-loop algorithms (which require solving inner subproblems approximately). The methodology relies on three core components:

Penalty and Smoothing: The nonconvex constraints are handled via a quadratic penalty method, transforming the problem into a sequence of unconstrained DC problems with increasing penalty parameters $\rho_k$ . To handle the nonsmoothness of the DC structure, the authors employ the Difference-of-Moreau-Envelopes (DME) technique. Instead of smoothing the entire objective, they construct a smooth surrogate $F_{\rho, \mu}(z) = M_{\mu}\psi_{\rho}(z) - M_{\mu}g(z)$ , where $\psi_{\rho} = f + \frac{\rho}{2}\|c(x)\|^2 + h$ . This allows the use of gradient-based updates while preserving the DC structure's criticality properties.
Single-Loop Updates: The algorithm maintains two variables, $x_k$ $x_{k}$ and $z_k$ $z_{k}$ .
- $x_k$ is updated via a stochastic proximal-gradient step on the convex part of the smoothed surrogate, effectively estimating the proximal mapping of $\psi_{\rho}$ .
- $z_k$ is updated via a gradient-type step using the difference of the proximal mappings of $g$ and the estimated $\psi_{\rho}$ .
Momentum Variants: The framework integrates two momentum strategies to control stochastic variance and improve convergence rates:
- MoSSP-P: Utilizes Polyak momentum (heavy-ball) for the stochastic gradient estimator.
- MoSSP-R: Utilizes recursive momentum (STORM) for variance reduction, which incorporates a correction term based on single samples.

Key Contributions
The paper claims the following contributions:

First Single-Loop Complexity for Constrained DC: To the best of the authors' knowledge, this is the first systematic complexity study of single-loop stochastic methods for nonconvex, functionally constrained optimization involving DC structure.
Provable Complexity Guarantees:
- MoSSP-P achieves an oracle complexity of $O(\epsilon^{-4})$ for finding a stochastic $\epsilon$ -KKT point (under mild conditions) or a stochastic $\epsilon$ -stationary point.
- MoSSP-R, incorporating recursive momentum and a mean-squared smoothness assumption, improves this to $O(\epsilon^{-3})$ . This matches the known lower bound for unconstrained stochastic optimization with variance reduction and the best-known rates for nonconvex constrained stochastic optimization without DC structure.
Novel Theoretical Analysis: The authors develop a DC-aware complexity analysis that explicitly characterizes stochastic errors within the criticality measure. They construct a specific potential function to coordinate the control of smoothing, momentum, and penalty parameters, ensuring that the DC structure does not degrade the complexity order compared to unconstrained settings.
Handling Nonsmooth DC: Unlike prior work that often assumes smooth concave components or requires double-loop schemes, MoSSP handles cases where the concave part $g$ is nonsmooth and the constraints are nonconvex.

Experimental Results
The authors evaluate MoSSP-P and MoSSP-R on an equality-constrained binary classification problem with DC regularization (using $\ell_1 - \ell_2$ sparsity) across three LIBSVM datasets (a9a, phishing, australian). They compare against double-loop baselines: SPDC (stochastic DC algorithm) and SALM (stochastic augmented Lagrangian method), both equipped with Polyak or recursive momentum.

Convergence Speed: On large-scale datasets (a9a, phishing), MoSSP variants converge significantly faster in terms of objective value reduction and constraint violation reduction compared to the double-loop baselines.
Feasibility: MoSSP rapidly reduces constraint violations from initial levels (e.g., 100) to $10^{-3}$ with fewer gradient evaluations. In contrast, baselines often remain at higher violation levels ( $10^{-2}$ or higher) for longer durations.
Robustness: The proposed framework demonstrates robustness to the choice of momentum technique, achieving competitive final objective values and constraint violations across different datasets.

Significance and Claims
The paper positions MoSSP as a significant step forward in stochastic optimization for structured nonconvex problems. The authors emphasize that their single-loop design eliminates the need for extensive hyperparameter tuning and precise inner-loop termination criteria required by double-loop methods. Crucially, they claim that their analysis proves that the presence of the DC structure and nonconvex constraints does not inherently worsen the oracle complexity order compared to simpler unconstrained or convex-constrained stochastic problems. The $O(\epsilon^{-3})$ rate achieved by MoSSP-R is highlighted as matching state-of-the-art bounds for nonconvex constrained optimization, demonstrating that the single-loop penalty framework can effectively handle complex DC regularizations without sacrificing theoretical efficiency.