Na minha lista:
| Main Authors: | , , |
|---|---|
| Formato: | Preprint |
| Publicado em: |
2025
|
| Assuntos: | |
| Acesso em linha: | https://arxiv.org/abs/2502.19764 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
Sumário:
- 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\in[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\in[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.