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

Qiankun Shi, Han Yuan, Xiao Wang, Hao Wang · 2025

Read Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization by Qiankun Shi, Han Yuan, Xiao Wang, Hao Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09409.txt.

Introduction

Shi and co-authors present a paper, published in 2025, on optimization when a function's slope cannot be measured directly. In their setting, only noisy values of the goal are available, and the answer must obey exact constraints. The shape of the goal may also curve in complex, nonconvex ways. Their method estimates slopes from pairs of sampled points. It folds the constraints into an augmented penalty form and steps downhill in a bent geometry that fits the problem.

The authors prove how many samples the method needs to reach a point that nearly satisfies the optimality conditions. Their analysis exposes a trade-off: noisier slope estimates can be offset by a smoother stepping geometry. In the high-accuracy range, the total cost takes a clean form. Such guarantees matter for tuning systems where each test is costly, like physical experiments or large simulations.

Catalog record

CREATORQiankun Shi, Han Yuan, Xiao Wang, Hao Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-09409

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization Qiankun Shi, Han Yuan, Xiao Wang, Hao Wang Abstract In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems in which exact constraint information is available, while the objective can be accessed only through stochastic function 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 stochastic oracle assumptions and a regularity assumption, we establish oracle complexity guarantees for finding an ϵ \epsilon -KKT point under mirror descent geometries parameterized by p ≥ 2 p\geq 2 . Under Rademacher smoothing, our analysis reveals a trade-off between the dimension-dependent variance of the zeroth-order gradient estimators and the smoothness of the non-Euclidean mirror map. In the high accuracy regime, the resulting effective oracle complexity is 𝒪 ⁡ ( p ​ d 2 / p ​ ϵ − 3 ) \mathcal{O}(pd^{2/p}\epsilon^{-3}) for p ∈ [ 2 , 2 ​ ln ⁡ d ] p\in[2,2\ln d] and 𝒪 ⁡ ( ln ⁡ d ​ ϵ − 3 ) \mathcal{O}(\ln d\,\epsilon^{-3}) for p > 2 ​ ln ⁡ d p>2\ln d . These bounds reduce the dependence on the problem dimension d d in the leading oracle complexity term at the expense of additional geometry dependent lower-order terms. In particular, when p = 2 p=2 , the method recovers the standard Euclidean setting and achieves an oracle complexity of 𝒪 ⁡ ( d ​ ϵ − 3 ) \mathcal{O}(d\epsilon^{-3}) , improving the dependence on ϵ \epsilon over existing constrained stochastic zeroth-order methods. Furthermore, to eliminate near-feasibility requirement on the initial point, we develop a multi-stage scheme that finds an ϵ \epsilon -KKT point within 𝒪 ⁡ ( 1 + log ⁡ log ⁡ ( e / ϵ ) ) \mathcal{O}(1+\log\log(e/\epsilon)) stages while preserving the leading-order high-accuracy oracle complexity, up to an additional ϵ \epsilon independent initialization cost. Numerical tests on quadratically constrained quadratic programs, black-box adversarial attacks, and fairness-constrained classification showcase the effectiveness of the proposed method. Keywords : Nonconvex constrained optimization, stochastic optimization, zeroth-order optimization, mirror descent, oracle complexity, high-accuracy regime MSC codes : 65K05, 68Q25, 90C30 1 Introduction In this paper, we focus on the following constrained optimization problem: \displaystyle\min_{x\in X} \displaystyle\Phi(x):=\{f(x):=\mathbb{E}_{\xi}[F(x;\xi)]\}+h(x)\quad\text{s.t.}\quad c(x)=0, (1.1) where X\subset\mathbb{R}^{d} is convex, f:\mathbb{R}^{d}\rightarrow\mathbb{R} and c:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m} are continuously differentiable and potentially nonconvex, \xi is a random variable from the probability space (\Omega,\mathcal{F},\mathbb{P}) and is independent of x , F(x;\xi) is continuously differentiable in x for almost any \xi , \mathbb{E}_{\xi}[\cdot] represents the expectation taken with respect to (w.r.t.) \xi , and h:\mathbb{R}^{d}\to\mathbb{R}\cup\{\infty\} is a simple convex but nonsmooth function. Problem ( 1.1 ) arises in many application fields. For instance, to enforce specific behaviors or properties in deep learning, constraints are imposed on the output of deep neural networks [ 40 ] , such as the physics-constrained deep learning model [ 58 ] , constraint-aware deep neural network compression [ 11 ] , manifold-regularized deep learning [ 47 ] . Other applications include portfolio allocation [ 6 ] , two-stage and multi-stage modeling [ 49 ] and constrained maximum likelihood estimation [ 10 ] . Throughout this paper, we assume that d\geq 3 and that for the objective function f only stochastic function values are available at a query point. Zeroth-order algorithms, also known as gradient-free algorithms, address optimization problems without relying on explicit gradient computations. These algorithms can be roughly categorized into two classes: direct search methods [ 23 , 41 , 45 ] and model-based methods [ 7 , 12 , 44 ] . The former class operates by sampling the objective function and selecting iterates through straightforward comparisons of function values, while the latter approximates the original optimization problem with simpler models and determines iterates based on these approximations. For broader surveys, the reader is referred to [ 13 , 29 ] . Among model-based methods, finite-difference methods have been studied comprehensively. For instance, Nesterov’s seminal work [ 42 ] establishes the complexity bound for gradient-free methods in convex optimization. Duchi et al. [ 18 ] introduce two-point gradient estimators for stochastic convex minimization, achieving a nearly optimal oracle complexity of \mathcal{O}(d\epsilon^{-2}) . In stochastic zeroth-order nonconvex optimization, general methods such as zeroth-order SGD [ 21 ] exhibit an oracle complexity order of \mathcal{O}(d\epsilon^{-4}) and an improved order of \mathcal{O}(d\epsilon^{-3}) when incorporating variance reduction techniques [ 19 , 24 , 25 ] . A key challenge in this field is the impact of the problem dimension d , especially in high-dimensional settings, as zeroth-order gradient estimators yield a dimension-dependent variance, resulting in a strong dependence of oracle complexity on d [ 34 , 37 ] . To address this, stronger assumptions such as sparsity are often introduced [ 3 , 46 , 56 ] . However, such sparsity assumptions may not always hold. Moreover, the aforementioned zeroth-order algorithms are designed for unconstrained settings, making them inapplicable to general constrained optimization problems. For constrained stochastic optimization, stochastic first- and second-order methods have been well developed. Among stochastic first-order methods, proximal point methods including [ 8 , 9 , 36 ] focus on nonconvex inequality-constrained optimization and solve the original problem through a sequence of strongly convex subproblems. Stochastic sequential quadratic programming (SQP) methods have also recently been studied for equality constrained stochastic optimization [ 5 , 15 , 20 ] , with a complexity analysis provided in [ 15 ] . In subsequent work, Curtis et al. [ 16 ] study problems with both equality and inequality constraints and present a stochastic SQP method with global convergence analysis. Penalty methods for nonconvex constrained stochastic optimization discourage constraint violations by incorporating a penalty term, weighted by a parameter [ 1 , 14 , 30 , 26 , 35 , 50 , 55 , 57 ] . In terms of stochastic second-order algorithms, Na et al. [ 39 ] propose an adaptive SQP method with differentiable exact augmented Lagrangians, while Wang [ 54 ] employs a stochastic cubic-regularized primal-dual method to obtain an approximate second-order stationary point. More recently, Shi et al. [ 51 ] proposed a curvature-oriented variance-reduction method for finding approximate second-order stationary points of unconstrained nonconvex stochastic optimization. They further developed an augmented Lagrangian variant, for problems with deterministic nonlinear equality constraints. However, all these methods rely on unbiased stochastic gradients and are therefore inapplicable when only biased stochastic gradient estimates are available. Although in the literature Frank-Wolfe methods and projected gradient methods based on zeroth-order estimation have been studied for set-constrained optimization [ 2 , 3 ] , the nonconvexity of constraints in nonconvex constrained optimization limits the study of zeroth-order algorithms. In [ 55 ] , a double-loop penalty method, which calls a stochastic zeroth-order algorithm to solve each penalty subproblem, is proposed for equality constrained stochastic optimization, but with a relatively high oracle complexity. Recently, stochastic zeroth-order algorithms for solving functionally constrained optimization problems with stochastic inequality constraints have been studied in [ 43 ] , yielding an oracle complexity of order \mathcal{O}(d\epsilon^{-6}) . Notably, both algorithms exhibit a complexity in d of at least \mathcal{O}(d) . Reformulating the original problem into a min-max optimization problem, Shi

Read the complete text