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

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 ≥ 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 O(p d2/pε-3) for p ∈ [2,2ln d] and O(ln d,ε-3) for p > 2ln 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 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 O(1+loglog(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.