An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization

Understand

We propose an inexact proximal augmented Lagrangian framework with explicit inner problem termination rule for composite convex optimization problems.

• We consider arbitrary linearly convergent inner solver including in particular stochastic algorithms, making the resulting framework more scalable facing the ever-increasing problem dimension.
• Each subproblem is solved inexactly with an explicit and self-adaptive stopping criterion, without requiring to set an a priori target accuracy.
• When the primal and dual domain are bounded, our method achieves $O(1/\sqrt{\epsilon})$ and $O(1/{\epsilon})$ complexity bound in terms of number of inner solver iterations, respectively for the strongly convex and non-strongly convex case.