A new framework of inexact proximal augmented Lagrangian method : towards arbitrary inner solver with both explicit stopping criteria and optimal complexity bound

Abstract

In this thesis, 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, thereby 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 \textit{a priori} target accuracy. We apply this framework in three different settings.

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

For the case that only the nonsmooth part on the dual variable is simple, we propose a new inner solver and our framework is extended to solve this case. Our method achieves $\tilde{O}(1/\epsilon)$ and $\tilde{O}(1/\epsilon^2)$ complexity bound respectively in terms of increment first order oracle (ifo) and linear minimization oracle (lmo). When the primal domain is a polytope, our method achieves $\tilde{O}(1/\epsilon)$ complexity bound in terms of ifo and lmo.

For the case that only the nonsmooth part on the primal variable is simple, we explore the possibility of extending our framework to the Bregman smoothing technique. Under some additional assumptions, we prove the same complexity bound in terms of the number of inner solver iterations—that is, $O(1/\sqrt{\epsilon})$ and $O(1/{\epsilon})$ complexity bound, for the strongly convex and non-strongly convex cases, respectively. Within the general framework that we propose, we also obtain $\tilde O(1/{\epsilon})$ and $\tilde O(1/{\epsilon^2})$ complexity bounds under the relative smoothness assumption on the differentiable component of the objective function, for the strongly convex and non-strongly convex cases, respectively.