In this paper we show how the stochastic heavy ball method (SHB) -- a popular
method for solving stochastic convex and non-convex optimization problems
--operates as a randomized gossip algorithm. In particular, we focus on two
special cases of SHB: the Randomized Kaczmarz method with momentum and its
block variant. Building upon a recent framework for the design and analysis of
randomized gossip algorithms, [Loizou Richtarik, 2016] we interpret the
distributed nature of the proposed methods. We present novel protocols for
solving the average consensus problem where in each step all nodes of the
network update their values but only a subset of them exchange their private
values. Numerical experiments on popular wireless sensor networks showing the
benefits of our protocols are also presented.

本文示范了随机重球（SHB）方法是如何作为随机化闲话算法解决随机凸和非凸优化问题的。为此，我们专注于 SHB 的两种特殊情况：带动量的随机 Kaczmarz 方法及其块变体。在最近提出的随机化闲话算法设计和分析框架 [L Richtarik，2016] 的基础上，我们解释了所提出方法的分布式性质，并提出了用于解决平均一致性问题的新协议，其中在每个步骤中，网络的所有节点都更新其值，但只有其中的子集交换其私有值。我们还展示了在流行的无线传感器网络上运行我们协议的数字实验结果。

随机重球法加速 Gossip 算法

Accelerated Gossip via Stochastic Heavy Ball Method

In this work we establish the first linear convergence result for the
stochastic heavy ball method. The method performs SGD steps with a fixed
stepsize, amended by a heavy ball momentum term. In the analysis, we focus on
minimizing the expected loss and not on finite-sum minimization, which is
typically a much harder problem. While in the analysis we constrain ourselves
to quadratic loss, the overall objective is not necessarily strongly convex.

本文针对随机重球方法进行分析与研究，证明了该方法的线性收敛性，并着重探讨了期望损失的最小化以及动量项所起的作用。