A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization
Yawen Cui, Qiankun Shi, Xiao Wang, Xiantao Xiao · 2026
Read A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization by Yawen Cui, Qiankun Shi, Xiao Wang, Xiantao Xiao (2026) 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-2606-28230.txt.
Introduction
Yawen Cui, Qiankun Shi, Xiao Wang, and Xiantao Xiao design an algorithm for hard optimization problems where both the goal and the equality constraints are nonconvex and can only be estimated noisily. Most existing methods pay heavily in evaluations of the noisy constraint function, which can dominate the total cost.
Cui's team builds a search direction from decomposed pieces and uses Fletcher's augmented Lagrangian, a smooth scoring function, to choose step sizes. A technical hurdle is that the noisy constraint Jacobian can nearly degenerate. They split the analysis by its smallest singular value to control the resulting errors. Under smoothness assumptions, the method provably reaches an approximate KKT point, the standard certificate of a good solution, with a total expected cost they characterize, and experiments support the theory.
Catalog record
| CREATOR | Yawen Cui, Qiankun Shi, Xiao Wang, Xiantao Xiao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28230
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization Yawen Cui, Qiankun Shi, Xiao Wang, Xiantao Xiao Abstract In this paper, we study nonconvex equality-constrained optimization problems in which only stochastic first-order approximations of the objective and constraint functions are available. Owing to the stochasticity in both objective and constraints, most existing stochastic first-order methods incur relatively high oracle complexity, particularly in terms of stochastic constraint function evaluations. To address this issue, we develop a stochastic first-order method based on a decomposed stochastic search direction, and employ Fletcher’s augmented Lagrangian as a smooth merit function for step-size selection. To cope with the possible loss of uniform nondegeneracy of the stochastic Jacobian, we introduce an event decomposition based on the smallest singular value, which enables us to control perturbations in the stochastic search direction. Under an additional Lipschitz continuity assumption on the second-order derivatives of the objective and constraint functions, we show that the proposed algorithm attains a stochastic ϵ \epsilon -KKT point with an expected total oracle complexity of 𝒪 ( ϵ − 3 ) \mathcal{O}(\epsilon^{-3}) in terms of stochastic gradient and stochastic constraint function evaluations. Finally, we present numerical experiments to demonstrate the performance of the proposed method. Keywords nonconvex constrained optimization, Fletcher’s augmented Lagrangian, stochastic approximation, oracle complexity 1 Introduction In this paper, we consider the nonconvex constrained optimization problem \displaystyle{}\min_{x\in\mathbb{R}^{n}}\quad \displaystyle f(x):=\mathbb{E}_{\xi}[F(x;\xi)] s.t. \displaystyle c(x):=\mathbb{E}_{\xi}[C(x;\xi)]=\mathbf{0}, (1.1) where \xi is a random variable in the probability space \Xi and independent of x , and \mathbb{E}_{\xi} refers to the expectation taken in \xi . Here F:\mathbb{R}^{n}\times\Xi\to\mathbb{R} and C:\mathbb{R}^{n}\times\Xi\to\mathbb{R}^{m} are continuously differentiable with respect to x but possibly nonconvex. Throughout the paper, we assume that the feasible set of ( 1 ) is nonempty. Problems of the form ( 1 ), commonly referred to as fully-stochastic constrained optimization, capture a broad class of real-world applications ranging from stochastic optimal control [ 3 ] , and chance-constrained programming [ 22 , 26 ] to fair machine learning [ 24 , 32 ] and physics–informed neural networks [ 17 ] . When solving these models in practice, exact evaluations of the objective and constraint functions are typically unavailable, while only stochastic approximations can be accessed. The challenges posed by possibly nonconvex constraints and the stochastic nature of the problem significantly complicate both algorithm design and complexity analysis. A related setting that has been extensively studied is the semi-stochastic case, where the exact information of constraints can always be available. Existing approaches include penalty and augmented Lagrangian methods [ 7 , 16 , 20 , 29 , 28 , 30 , 34 ] , proximal-point methods [ 4 , 5 , 21 ] , and stochastic sequential quadratic programming (SQP) methods [ 2 , 9 , 10 , 12 , 23 , 25 ] . The best-known oracle complexity in the semi-stochastic setting is of order \mathcal{O}(\epsilon^{-3}) for finding a stochastic \epsilon -KKT point, typically under a mean-squared smoothness assumption and suitable constraint qualification conditions [ 7 , 15 , 20 , 29 , 28 ] . Compared with the semi-stochastic setting, the study on fully-stochastic problems has been developed more recently, but with generally higher complexity bounds. Among existing approaches, the inexact proximal point method proposed in [ 4 ] solves the nonconvex constrained problem through a sequence of stochastic convex subproblems, resulting in a double-loop framework. Given the strong feasibility assumption, this method requires an overall oracle complexity of order \mathcal{O}(\epsilon^{-6}) for obtaining an approximate KKT point. A stochastic SQP method [ 27 ] has also been developed for ( 1 ), yielding a complexity bound of the same order \mathcal{O}(\epsilon^{-6}) provided that a strong linear independence constraint qualification (LICQ) holds. Penalty and ALMs form another line of work, with several recent results achieving improved complexity bounds of order \mathcal{O}(\epsilon^{-5}) . Specifically, Li et al. [ 18 ] propose stochastic inexact augmented Lagrangian methods, in which the inner subproblems are solved by a momentum-based variance-reduced proximal stochastic gradient method followed by a postprocessing step. Different from this, Alacaoglu and Wright [ 1 ] and Cui et al. [ 8 ] develop momentum-based methods with a single-loop structure. Under the nonsingularity condition, the former attains an \tilde{\mathcal{O}}(\epsilon^{-5}) sample complexity for finding a stochastic \epsilon -KKT point with a varying penalty parameter setting, while the latter adopts a two-phase strategy and achieves an \mathcal{O}(\epsilon^{-5}) oracle complexity for a stochastic \epsilon -KKT point with constant parameter settings. Cui et al. [ 7 ] introduce an adaptive penalty method that updates the penalty parameter according to the progress of the algorithm and approximately solves each penalty subproblem by a truncated stochastic prox-linear method. Under the strong LICQ condition and sample-wise smoothness assumptions, they derive oracle complexity bounds of order \mathcal{O}(\epsilon^{-3}) for stochastic gradient evaluations of both the objective and constraints, and \mathcal{O}(\epsilon^{-5}) for stochastic constraint function value evaluations. In a broader constrained setting, Shi and Wang [ 29 ] consider problems with both equality and inequality constraints and propose an adaptive directional decomposition method. They establish high-probability oracle complexity for finding an \epsilon -KKT point, requiring \tilde{\mathcal{O}}(\epsilon^{-3}) stochastic gradient evaluations and \tilde{\mathcal{O}}(\epsilon^{-5}) stochastic constraint function value evaluations under a strong MFCQ condition and the sample-wise smoothness assumption. Stochastic constrained optimization problems with nonsmooth or weakly convex structures form a special class of fully-stochastic nonconvex problems [ 19 , 31 , 33 ] . A notable recent work by Liu and Xu [ 19 ] develops an exact penalty model solved by a single-loop SPIDER-type stochastic subgradient method. Their method guarantees an (\epsilon,\epsilon) -KKT point with sample complexities of order \mathcal{O}(\epsilon^{-4}) for stochastic subgradient evaluations and \mathcal{O}(\epsilon^{-6}) for stochastic constraint function value evaluations, assuming a uniform Slater-type constraint qualification. Overall, existing results suggest that the oracle complexity of fully-stochastic constrained optimization remains relatively high, especially for stochastic constraint function value evaluations. Motivation. Reducing the oracle complexity regarding constraint value evaluations within a tractable stochastic first-order framework is a central challenge. Existing methods that employ smooth merit/penalty functions, such as quadratic penalty function or augmented Lagrangian function, typically require \epsilon^{-1} -dependent penalty parameters, thus own higher oracle complexity bounds [ 1 , 8 , 18 ] . Alternatively, methods based on nonsmooth merit/penalty functions, such as f(x)+\rho\|c(x)\| , admit exactness once \rho exceeds a finite threshold under certain CQ conditions. However, the nonsmooth term makes stochastic constraint approximation more demanding, leading to relatively high sample complexity for constraint evaluations [ 7 , 19 , 27 , 29 ] . Therefore, to better control the total oracle complexity bounds, we are motivated to search for a merit function that unifies smoothness and exactness. Fletcher’s augmented Lagrangian [ 13 ] serves this purpose by replacing the seperately updated dual variable with a continuous function of the primal variable, thereby providing a suitable choice to help design a stochastic approximation method for solving ( 1 ). 1.1 Contributions This paper develops a single-loop stochastic first-order method based on Fletcher’s augmented Lagrangian for fully-stochastic nonconvex equality-constrained optimization. At each iteration, the algorithm employs truncated SPIDER-type recursive estimators to generate stochastic approximations, from which a decomposed direction is computed to balance objective decrease and feasibility improvement, with the Fletcher’s augmented Lagrangian serving as a smooth merit function and to