🔢 mathematics

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

本文介绍了 MoSSP，这是一种基于动量的单环随机惩罚方法，能够在具有非光滑凸差正则化的非凸约束优化问题中，以可证明的 $O(\varepsilon^{-4})$ 和 $O(\varepsilon^{-3})$ oracle 复杂度找到随机 $\varepsilon$ -KKT 点。

原作者： Luxuan Li, Chunfeng Cui, Xiao Wang

发布于 2026-05-29

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Luxuan Li, Chunfeng Cui, Xiao Wang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正试图在一个广阔、雾气弥漫的山谷中寻找最低点（即目标函数）。然而，存在两个主要难题：

地形崎岖怪异：地面并非一个平滑的碗状，而是平滑山丘与锯齿状尖锐岩石的混合体。用数学术语来说，这是一个“凸差”（DC）问题。这就像试图走下一座山，而这座山实际上是一个平滑山丘减去一座锯齿状山脉。“减去山脉”的部分使得路径不可预测且难以导航。
你面临隐形围栏：你不能随意漫游。你必须停留在一个特定的、可能是扭曲的边界内（即约束）。在现实世界中，这就像机器人必须保持在一定的能量预算内，或者金融模型必须遵守严格的安全规则。这些边界并非简单的直线，而是弯曲且复杂的。
雾气浓重：你无法看到整张地图。你只能窥视地面小块随机的区域（即随机部分），以此推测底部的位置。

旧方法的问题

以前的算法试图通过分两步走来解决这个问题：

第一步：猜测一条路径。
第二步：停下来，解决一个微小而困难的谜题，以确保你没有撞到围栏。
重复：然后再次猜测，再解决另一个微小谜题，依此类推。

这种“双循环”方法就像每走 10 英尺就停下来查看详细地图并重新计算路线。虽然准确，但极其缓慢且计算成本高昂，尤其是在数据量巨大的情况下。

新解决方案：MoSSP

本文介绍了MoSSP（基于动量的单循环随机惩罚法）。你可以将其想象为一位聪明、充满活力的徒步者，他利用一种新策略来穿越这片雾气弥漫、设有围栏且崎岖不平的地形。

以下是 MoSSP 的工作原理，使用简单的比喻：

1. “单循环”捷径

MoSSP 不再每次停下来解决微小谜题，而是保持连续流动。它迈出一大步，检查周围环境，随即迈出下一步。这就像一名跑步者随时调整步伐，而不是每隔几秒就停下来系鞋带。这使得速度大大提升。

2. “惩罚”技巧（橡皮筋）

它如何在不停止的情况下处理隐形围栏？它使用惩罚法。想象围栏实际上是由巨大的隐形橡皮筋制成的。

如果你待在围栏内，橡皮筋是松弛的。
如果你试图跨出围栏，橡皮筋会强力地将你拉回。
MoSSP 将这种“拉力”视为地形本身的一部分。它不需要检查你是否在围栏内；它只需感受橡皮筋的拉力，并据此调整路径。

3. “动量”（重球）

本文使用了该徒步者的两个版本，两者都利用了动量。

MoSSP-P（Polyak 动量）：想象一个重球滚下山坡。如果球滚得很快，当它撞上小凸起时不会立即停止；它会带着速度继续向前。这有助于算法忽略雾气中的微小噪声误差，并使其持续向真正的底部移动。
MoSSP-R（递归动量）：这是一个更聪明的版本。它就像一位徒步者，能确切记住上一步雾气是如何变化的，并利用这段记忆来修正当前的猜测。这种“修正”使徒步者更加高效，缩短了找到解决方案所需的时间。

4. “平滑代理”（地图叠加）

由于地形包含锯齿状岩石（非平滑部分），徒步者无法直线行走。MoSSP 在锯齿状岩石上创建一个“平滑叠加层”（称为Moreau 包络）。这就像在凹凸不平的表面上覆盖一层透明塑料；你再也感觉不到单个的凸起，只能感受到整体的坡度。这使得徒步者即使在最崎岖的地面上也能使用标准的行走技巧。

他们证明了什么？

作者不仅构建了这位徒步者，还从数学上证明了其工作速度：

MoSSP-P 保证能非常快速地找到一个良好的解决方案（即一个既接近底部又接近围栏的点）。
MoSSP-R 甚至更快，达到了此类问题所能达到的最佳速度。

他们在真实世界数据上（例如将电子邮件分类为垃圾邮件或非垃圾邮件，以及压缩神经网络）测试了该方法，结果表明，MoSSP 在遵守所有规则的同时，比旧的“双循环”方法更快地到达终点。

总结

简而言之，MoSSP 是一种解决复杂优化问题的新方法，其特点如下：

目标具有挑战性（崎岖地形）。
存在严格规则（隐形围栏）。
你只有部分信息（雾气）。

它通过将“橡皮筋”惩罚系统与“动量”（保持向前速度）以及“平滑”技术相结合，在一个连续的单循环运动中实现这一目标，而无需沿途停下来解决微小谜题。

技术摘要：MoSSP 用于非凸约束 DC 正则化优化

问题表述
本文研究了一类具有凸差（DC）正则化的结构化非凸约束随机优化问题。该问题表述为：
$\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,$
其中 $f$ 是随机平滑损失函数， $h$ 和 $g$ 是适当的、闭的凸函数（ $g$ 可能非光滑）， $c(x)=0$ 表示非凸等式约束。可行集被假定为非凸的。该设定下的一个关键挑战在于，复合正则化项 $h-g$ 通常不具有近端友好性（即差值的近端算子无法以闭式形式获得），且约束是非凸的，使得可行性维持变得困难。此外， $f$ 的精确梯度往往无法获取，因此需要使用随机梯度。

方法论：MoSSP
为应对这些挑战，作者提出了 MoSSP（基于动量的单循环随机惩罚法），这是一种单循环框架，避免了双循环算法（需要近似求解内层子问题）的计算负担。该方法依赖于三个核心组件：

惩罚与平滑：非凸约束通过二次惩罚法处理，将问题转化为一系列惩罚参数 $\rho_k$ 递增的无约束 DC 问题序列。为了处理 DC 结构的非光滑性，作者采用了 Moreau 包络差（DME） 技术。作者并非平滑整个目标函数，而是构造了一个平滑代理函数 $F_{\rho, \mu}(z) = M_{\mu}\psi_{\rho}(z) - M_{\mu}g(z)$ ，其中 $\psi_{\rho} = f + \frac{\rho}{2}\|c(x)\|^2 + h$ 。这使得在保留 DC 结构临界性性质的同时，能够使用基于梯度的更新。
单循环更新：算法维护两个变量 $x_k$ $x_{k}$ 和 $z_k$ $z_{k}$ 。
- $x_k$ 通过对平滑代理函数的凸部分进行随机近端梯度步更新，有效地估计 $\psi_{\rho}$ 的近端映射。
- $z_k$ 通过梯度型步长更新，利用 $g$ 的近端映射与估计的 $\psi_{\rho}$ 的近端映射之差。
动量变体：该框架整合了两种动量策略以控制随机方差并提高收敛速率：
- MoSSP-P：在随机梯度估计器中使用 Polyak 动量（重球法）。
- MoSSP-R：使用 递归动量（STORM）进行方差缩减，该方法包含基于单样本的校正项。

主要贡献
本文声称具有以下贡献：

首个单循环复杂度结果：据作者所知，这是针对涉及 DC 结构的非凸、函数约束优化的单循环随机方法的首次系统性复杂度研究。
可证明的复杂度保证：
- MoSSP-P 在温和条件下，找到随机 $\epsilon$ -KKT 点或随机 $\epsilon$ -平稳点的预言机复杂度为 $O(\epsilon^{-4})$ 。
- MoSSP-R 结合递归动量和均方平滑假设，将此复杂度提升至 $O(\epsilon^{-3})$ 。这匹配了具有方差缩减的无约束随机优化的已知下界，以及无 DC 结构的非凸约束随机优化的最佳已知速率。
新颖的理论分析：作者开发了 DC 感知的复杂度分析，明确刻画了临界性度量内的随机误差。他们构建了一个特定的势函数来协调平滑、动量和惩罚参数的控制，确保 DC 结构不会使复杂度阶数劣于无约束设定。
处理非光滑 DC：与通常假设平滑凹分量或需要双循环方案的前期工作不同，MoSSP 能够处理凹部分 $g$ 非光滑且约束为非凸的情况。

实验结果
作者在具有 DC 正则化（使用 $\ell_1 - \ell_2$ 稀疏性）的等式约束二分类问题上评估了 MoSSP-P 和 MoSSP-R，测试了三个 LIBSVM 数据集（a9a, phishing, australian）。他们与双循环基线进行了比较：SPDC（随机 DC 算法）和 SALM（随机增广拉格朗日法），两者均配备了 Polyak 或递归动量。

收敛速度：在大规模数据集（a9a, phishing）上，与双循环基线相比，MoSSP 变体在目标值减少和约束违反减少方面收敛显著更快。
可行性：MoSSP 迅速将约束违反从初始水平（例如 100）降低至 $10^{-3}$ ，且所需的梯度评估次数更少。相比之下，基线方法往往在较长时间内保持在较高的违反水平（ $10^{-2}$ 或更高）。
鲁棒性：所提出的框架对动量技术的选择表现出鲁棒性，在不同数据集上均实现了具有竞争力的最终目标值和约束违反水平。

意义与主张
本文将 MoSSP 定位为结构化非凸问题随机优化领域的重要进展。作者强调，其单循环设计消除了双循环方法所需的广泛超参数调整和精确的内层循环终止准则。至关重要的是，他们声称其分析证明，与更简单的无约束或凸约束随机问题相比，DC 结构和非凸约束的存在并不会本质上恶化预言机复杂度阶数。MoSSP-R 实现的 $O(\epsilon^{-3})$ 速率被强调为与非凸约束优化的最先进界限相匹配，证明了单循环惩罚框架可以在不牺牲理论效率的情况下有效处理复杂的 DC 正则化。