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

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.