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

arXiv: https://arxiv.org/abs/2504.09409 · HTML: https://mlsanity.com/paper/2504.09409/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 58 references that are in the map.
- First posted on arXiv 13 Apr 2025.

## Builds on (most cited first, 30 of 30)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Physics-Constrained Deep Learning for High-dimensional Surrogate Modeling and Uncertainty Quantification without Labeled Data](https://mlsanity.com/paper/1901.06314/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2007.10525/) (2020)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [Robust Sample Average Approximation](https://mlsanity.com/paper/1408.4445/) (2014)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020)
- [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022)
- [Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2112.14799/) (2021)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018)
- [Accelerated Stochastic Gradient-free and Projection-free Methods](https://mlsanity.com/paper/2007.12625/) (2020)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Sequential Quadratic Optimization for Stochastic Optimization with Deterministic Nonlinear Inequality and Equality Constraints](https://mlsanity.com/paper/2302.14790/) (2023)
- [Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming](https://mlsanity.com/paper/1312.2690/) (2013)
- [Level Constrained First Order Methods for Function Constrained Optimization](https://mlsanity.com/paper/2205.08011/) (2022)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Stochastic Zeroth-order Functional Constrained Optimization: Oracle Complexity and Applications](https://mlsanity.com/paper/2210.04273/) (2022)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)

## Abstract (arXiv)

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.