  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. Without the boundedness assumption, only logarithm
terms need to be added and the above two complexity bounds increase
respectively to $\tilde O(1/\sqrt{\epsilon})$ and $\tilde O(1/{\epsilon})$,
which hold both for obtaining $\epsilon$-optimal and $\epsilon$-KKT solution.
Within the general framework that we propose, we also obtain $\tilde
O(1/{\epsilon})$ and $\tilde O(1/{\epsilon^2})$ complexity bounds under
relative smoothness assumption on the differentiable component of the objective
function. We show through theoretical analysis as well as numerical experiments
the computational speedup possibly achieved by the use of randomized inner
solvers for large-scale problems.
