  The goal of this paper is to reduce the total complexity of gradient-based
methods for two classes of problems: affine-constrained composite convex
optimization and bilinear saddle-point structured non-smooth convex
optimization. Our technique is based on a double-loop inexact accelerated
proximal gradient (APG) method for minimizing the summation of a non-smooth but
proximable convex function and two smooth convex functions with different
smoothness constants and computational costs. Compared to the standard APG
method, the inexact APG method can reduce the total computation cost if one
smooth component has higher computational cost but a smaller smoothness
constant than the other. With this property, the inexact APG method can be
applied to approximately solve the subproblems of a proximal augmented
Lagrangian method for affine-constrained composite convex optimization and the
smooth approximation for bilinear saddle-point structured non-smooth convex
optimization, where the smooth function with a smaller smoothness constant has
significantly higher computational cost. Thus it can reduce total complexity
for finding an approximately optimal/stationary solution. This technique is
similar to the gradient sliding technique in the literature. The difference is
that our inexact APG method can efficiently stop the inner loop by using a
computable condition based on a measure of stationarity violation, while the
gradient sliding methods need to pre-specify the number of iterations for the
inner loop. Numerical experiments demonstrate significantly higher efficiency
of our methods over an optimal primal-dual first-order method and the gradient
sliding methods.
