%We consider a canonical nonlinear-constrained nonconvex problem template with broad applications in machine learning, theoretical computer science, and signal processing.
%This template involves the Burer-Monteiro splitting for semidefinite programming as a special case.
We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints.
%involving nonlinear operators.
We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to the Polyak-Lojasiewicz and Mangasarian-Fromowitz conditions.
\vspace{1mm}
In particular, when a first-order solver is used for the inner iterates, we prove that iALM finds a first-order stationary point with {\color{blue}$\tilde{\mathcal{O}}(1/\epsilon^4)$} calls to the first-order oracle. {If, in addition, the problem is smooth and} a second-order solver is used for the inner iterates, iALM finds a second-order stationary point with $\tilde{\mathcal{O}}(1/\epsilon^5)$ calls to the second-order oracle.
These complexity results match the known theoretical results in the literature. % with a simple, implementable and versatile algorithm.
\vspace{1mm}
We also provide strong numerical evidence on large-scale machine learning problems, including the Burer-Monteiro factorization of semidefinite programs, and a novel nonconvex relaxation of the standard basis pursuit template. For these examples, we also show how to verify our geometric condition.
%For these problems and under suitable assumptions, our algorithm in fact achieves global optimality for the underlying convex SDP.
{\color{blue} This paper was updated on 22 December 2020 due to an error in the proof of Corollary \eqref{cor:first}. The gradient complexity for obtaining a first order stationary point is now $\tilde{\mathcal{O}}(1/{\epsilon^4})$}.
%\textbf{AE: we should add something about gans if we do that in time.}