Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

Abstract

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 $\epsilon$-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}\epsilon^{-3})$ for $p \in [2,2\ln d]$ and $\mathcal{O}(\ln d\,\epsilon^{-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\epsilon^{-3})$, improving the $\epsilon$-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an $\epsilon$-KKT point within $\mathcal{O}(1+\log\log(e/\epsilon))$ 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.