# Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 27 Feb 2025.

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

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017)
- [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020)
- [First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points](https://mlsanity.com/paper/2212.00927/) (2022)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018)
- [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraints](https://mlsanity.com/paper/2101.08519/) (2021)
- [First-order methods for constrained convex programming based on linearized augmented Lagrangian function](https://mlsanity.com/paper/1711.08020/) (2017)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming](https://mlsanity.com/paper/1603.05738/) (2016)
- [Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications](https://mlsanity.com/paper/1604.00543/) (2016)
- [Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems](https://mlsanity.com/paper/2006.08048/) (2020)
- [Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints](https://mlsanity.com/paper/2008.07080/) (2020)
- [On the Iteration Complexity of Smoothed Proximal ALM for Nonconvex Optimization Problem with Convex Constraints](https://mlsanity.com/paper/2207.06304/) (2022)
- [Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function](https://mlsanity.com/paper/2008.00562/) (2020)
- [Smoothed Proximal Lagrangian Method for Nonlinear Constrained Programs](https://mlsanity.com/paper/2408.15047/) (2024)
- [An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems](https://mlsanity.com/paper/1812.06352/) (2018)
- [An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition](https://mlsanity.com/paper/2010.15267/) (2020)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Adaptive Augmented Lagrangian Methods: Algorithms and Practical Numerical Experience](https://mlsanity.com/paper/1408.4500/) (2014)

## Built on by (most cited first, 1 of 1)

- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)

## Abstract (arXiv)

In this paper, we investigate how structural properties of the constraint system impact the oracle complexity of smooth non-convex optimization problems with convex inequality constraints over a simple polytope. In particular, we show that, under a local error bound condition with exponent d∈[1,2] on constraint functions, an inexact Moreau envelope Lagrangian method can attain an ε-Karush--Kuhn--Tucker point with tilde O(ε-2d) gradient oracle complexity. When d=1, this result matches the best-known complexity in literature up to logarithmic factors. Importantly, the assumed error bound condition with any d∈[1,2] is strictly weaker than the local linear independence constraint qualification that is required to achieve the best-known complexity. Our results clarify the interplay between error bound conditions of constraints and algorithmic complexity, and extend complexity guarantees to a broader class of constrained non-convex problems.