提出新方法解决随机零阶非凸约束优化，精度更高、维度依赖更小。
Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization
- 结合镜面下降与线性化拉格朗日法，用两点估计梯度并利用非欧几何。
- 在高精度下复杂度为O(p d^{2/p} ε^{-3})，维度依赖显著降低。
- 适合黑箱优化、对抗攻击等需零阶信息的场景，无需初始可行性要求。
本文研究具有精确约束和随机目标评估的非凸约束随机零阶优化问题。为此，我们提出一种镜面下降线性化增广拉格朗日框架，采用两点随机零阶梯度估计器，并利用非欧几里得镜面下降几何。在温和假设下，建立了寻找ε-KKT点的预言机复杂度界，参数化于p ≥ 2。在Rademacher平滑下，分析揭示了零阶梯度估计方差与镜面映射光滑性之间的权衡。在高精度区域，有效预言机复杂度为O(p d^{2/p} ε^{-3})（当p ∈ [2, 2 ln d]）和O(ln d ε^{-3})（当p > 2 ln d），显著降低了主导项中的维度依赖。当p=2时，方法退化为欧氏情形，复杂度为O(d ε^{-3})，相比现有方法提升了ε依赖性。此外，为消除初始近可行性要求，引入多阶段方案，在O(1 + log log(e/ε))阶段内找到ε-KKT点，同时保持主导阶复杂度不变。在QCQPs、黑箱对抗攻击和公平约束分类任务上的数值实验验证了方法的有效性。
原文摘要 · Abstract (English)
In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an $ε$-KKT point parameterized by $p \geq 2$. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is $\mathcal{O}(p d^{2/p}ε^{-3})$ for $p \in [2,2\ln d]$ and $\mathcal{O}(\ln d\,ε^{-3})$ for $p > 2\ln d$. These bounds reduce the dimension dependence in the leading term. When $p=2$, our method recovers the Euclidean setting with an oracle complexity of $\mathcal{O}(dε^{-3})$, improving the $ε$-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an $ε$-KKT point within $\mathcal{O}(1+\log\log(e/ε))$ stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。