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.

本文提出一种结合 Alternating minimization（AM）和 Nesterov's acceleration 的自适应加速交替最小化算法，可用于解决具有凸性和非凸性的优化问题，同时不需要任何有关问题的凸性或函数参数等知识。通过证明该算法的收敛速度，得出该方法是自适应且优化的。此外还为具有线性约束的强凸问题开发了其原始 - 对偶修改。

交替最小化和 Nesterov 动量方法的组合

On a Combination of Alternating Minimization and Nesterov's Momentum

The growing amount of high dimensional data in different machine learning
applications requires more efficient and scalable optimization algorithms. In
this work, we consider combining two techniques, parallelism and Nesterov's
acceleration, to design faster algorithms for L1-regularized loss. We first
simplify BOOM, a variant of gradient descent, and study it in a unified
framework, which allows us to not only propose a refined measurement of
sparsity to improve BOOM, but also show that BOOM is provably slower than
FISTA. Moving on to parallel coordinate descent methods, we then propose an
efficient accelerated version of Shotgun, improving the convergence rate from
$O(1/t)$ to $O(1/t^2)$. Our algorithm enjoys a concise form and analysis
compared to previous work, and also allows one to study several connected work
in a unified way.

结合并行化和 Nesterov 加速技术，设计了更高效的算法，用于高维数据的 L1 正则化损失函数，包括优化 BOOM 和提高 Shotgun 的收敛速度。