%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 constrains.
%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-Lojsiewicz and Mangasarian-Fromovitz 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 $\tilde{\mathcal{O}}(1/\epsilon^3)$ 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 provide 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. We verify our geometric condition in all these examples.
%For these problems and under suitable assumptions, our algorithm in fact achieves global optimality for the underlying convex SDP.
%\textbf{AE: we should add something about gans if we do that in time.}