提出新算法解决非凸带DC正则的随机优化问题，兼顾可行性与效率。
MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization
- 用动量+单循环惩罚法处理非凸约束与非光滑凹部正则项
- 达到$O(\varepsilon^{-4})$和$O(\varepsilon^{-3})$的最优复杂度
- 适合求解带非凸约束的复杂随机优化问题的研究者
本文研究一类具有差分凸（DC）正则化的非凸随机约束优化问题，其可行集可能非凸，且DC正则器的凹部可为非光滑。核心挑战在于在保持非凸约束可行性的同时获得理想的预言机复杂度。尽管单循环算法能高效求解无约束的DC优化问题，但其在具有DC结构的约束优化中的潜力尚未被充分探索。为此，我们提出了MoSSP——一种基于动量的单循环随机惩罚方法，具备可证明的复杂度保证。关键思想是：对惩罚项与凸部的Moreau包络执行一次随机近端梯度步，并行计算凹部的近端映射。我们推导出两种算法变体：采用Polyak动量的版本实现$O(\varepsilon^{-4})$的预言机复杂度以找到随机$\varepsilon$-KKT点；另一改进版本引入递归动量，复杂度提升至$O(\varepsilon^{-3})$。实验结果验证了所提算法的有效性。
原文摘要 · Abstract (English)
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 Momentum-based Single-loop Stochastic Penalty 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 $O(\varepsilon^{-4})$ oracle complexity for finding stochastic $\varepsilon$-KKT points, and an improved $O(\varepsilon^{-3})$ version incorporating recursive momentum. Experimental results demonstrate the effectiveness of the proposed algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。