提出新型随机光滑对偶算法，高效求解带线性约束的非凸优化问题。
Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
- 基于Moreau包络的近似梯度下降，每轮仅需单样本梯度。
- 在随机约束下达到最优 $O(\varepsilon^{-4})$ 样本复杂度，可提升至 $O(\varepsilon^{-3})$。
- 无需子问题、大批次或递增惩罚参数，保持解的可行性。
针对带有线性不等式约束的随机平滑非凸优化问题，本文提出一种单循环的平滑对偶算法。该算法每轮迭代仅需基于一个样本的随机梯度。其核心思想是基于Moreau包络的非精确梯度下降框架，利用一步随机原对偶增广拉格朗日法估计Moreau包络的梯度。为处理约束与随机性，结合了约束优化中最新的全局误差界与基于Moreau包络的随机近端算法分析方法。对于获得 $\varepsilon$-平稳点，建立了 $O(\varepsilon^{-4})$ 的最优样本复杂度保证，并扩展至随机线性约束情形。通过引入方差缩减与期望光滑性假设，可进一步将复杂度优化至 $O(\varepsilon^{-3})$。与现有方法不同，该算法的迭代过程无需求解子问题、避免大批次数据或递增惩罚参数，且通过对偶变量更新确保解的可行性。
原文摘要 · Abstract (English)
We propose smoothed primal-dual algorithms for solving stochastic and smooth nonconvex optimization problems with linear inequality constraints. Our algorithms are single-loop and only require a single stochastic gradient based on one sample at each iteration. A distinguishing feature of our algorithm is that it is based on an inexact gradient descent framework for the Moreau envelope, where the gradient of the Moreau envelope is estimated using one step of a stochastic primal-dual augmented Lagrangian method. To handle inequality constraints and stochasticity, we combine the recently established global error bounds in constrained optimization with a Moreau envelope-based analysis of stochastic proximal algorithms. For obtaining $\varepsilon$-stationary points, we establish the optimal $O(\varepsilon^{-4})$ sample complexity guarantee for our algorithms and provide extensions to stochastic linear constraints. We also show how to improve this complexity to $O(\varepsilon^{-3})$ by using variance reduction and the expected smoothness assumption. Unlike existing methods, the iterations of our algorithms are free of subproblems, large batch sizes or increasing penalty parameters and use dual variable updates to ensure feasibility.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。