On a Combination of Alternating Minimization and Nesterov's Momentum
  Alternating minimization (AM) procedures are practically efficient in many
applications for solving convex and non-convex optimization problems. On the
other hand, Nesterov's accelerated gradient is theoretically optimal
first-order method for convex optimization. In this paper we combine AM and
Nesterov's acceleration to propose an accelerated alternating minimization
algorithm. We prove $1/k^2$ convergence rate in terms of the objective for
convex problems and $1/k$ in terms of the squared gradient norm for non-convex
problems, where $k$ is the iteration counter. Our method does not require any
knowledge of neither convexity of the problem nor function parameters such as
Lipschitz constant of the gradient, i.e. it is adaptive to convexity and
smoothness and is uniformly optimal for smooth convex and non-convex problems.
Further, we develop its primal-dual modification for strongly convex problems
with linear constraints and prove the same $1/k^2$ for the primal objective
residual and constraints feasibility.
