# On the Iteration Complexity of Smoothed Proximal ALM for Nonconvex Optimization Problem with Convex Constraints

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2022.

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

- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods](https://mlsanity.com/paper/2307.07605/) (2023)
- [Stochastic Penalty-Barrier Method for Constrained Machine Learning](https://mlsanity.com/paper/2605.18618/) (2026)

## Abstract (arXiv)

It is well-known that the lower bound of iteration complexity for solving nonconvex unconstrained optimization problems is Omega(1/ε2), which can be achieved by standard gradient descent algorithm when the objective function is smooth. This lower bound still holds for nonconvex constrained problems, while it is still unknown whether a first-order method can achieve this lower bound. In this paper, we show that a simple single-loop first-order algorithm called smoothed proximal augmented Lagrangian method (ALM) can achieve such iteration complexity lower bound. The key technical contribution is a strong local error bound for a general convex constrained problem, which is of independent interest.