Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods
Three inexact AL schemes are developed that preserve the standard AL subproblem structure and attain the optimal primal-dual complexity in the convex setting, improving prior AL bounds of $\mathcal O(\epsilon^{-4/3})$, $\mathcal O(\epsilon^{-7/4})$, and $\mathcal O(\epsilon^{-2})$, and removing the logarithmic factor from PAL guarantees.