提出新方法，让约束在概率上严格满足，同时保证收敛速度不降。
Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees
- 用截断动量法降低随机梯度方差，提升优化稳定性。
- 在θ=1时，样本复杂度达O(ε⁻³)，首次匹配无约束最优水平。
- 适合对约束必须严格成立的场景，如金融、医疗决策建模。
本文研究一类确定性约束的随机非凸优化问题。现有方法通常寻找ε-随机驻点，即期望约束违反和一阶平稳性均不超过ε，但在许多实际应用中，约束需以高概率近乎精确满足，此时ε-随机驻点可能因存在显著约束违反而不可接受。为此，本文提出单循环方差缩减的随机一阶方法：随机部分使用截断递归动量或截断Polyak动量进行方差缩减，确定性部分梯度精确计算。在误差界条件（参数θ≥1）及其他合理假设下，证明该方法分别实现样本复杂度O(ε⁻ᵐᵃˣ{θ+2,2θ})和一阶操作复杂度O(ε⁻ᵐᵃˣ{4,2θ})，以找到更强的ε-随机驻点——约束违反以确定性方式小于ε，且一阶平稳性期望违反小于ε。当θ=1时，复杂度分别为O(ε⁻³)与O(ε⁻⁴)，与当前无约束光滑随机优化问题最优复杂度仅差对数因子。
原文摘要 · Abstract (English)
In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an $ε$-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy $ε$. However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, making such an $ε$-stochastic stationary point potentially undesirable due to the risk of significant constraint violations. To address this issue, we propose single-loop variance-reduced stochastic first-order methods, where the stochastic gradient of the stochastic component is computed using either a truncated recursive momentum scheme or a truncated Polyak momentum scheme for variance reduction, while the gradient of the deterministic component is computed exactly. Under the error bound condition with a parameter $θ\geq 1$ and other suitable assumptions, we establish that these methods respectively achieve a sample and first-order operation complexity of $\widetilde O(ε^{-\max\{θ+2, 2θ\}})$ and $\widetilde O(ε^{-\max\{4, 2θ\}})$ for finding a stronger $ε$-stochastic stationary point, where the constraint violation is within $ε$ with certainty, and the expected violation of first-order stationarity is within $ε$. For $θ=1$, these complexities reduce to $\widetilde O(ε^{-3})$ and $\widetilde O(ε^{-4})$ respectively, which match, up to a logarithmic factor, the best-known complexities achieved by existing methods for finding an $ε$-stochastic stationary point of unconstrained smooth stochastic optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。