This paper describes a novel algorithmic framework to minimize a finite-sum
of functions available over a network of nodes. The proposed framework, that we
call~\GTVR, is stochastic and decentralized, and thus is particularly suitable
for problems where large-scale, potentially private data, cannot be collected
or processed at a centralized server. The \GTVR~framework leads to a family of
algorithms with two key ingredients: (i) \textit{local variance reduction},
that enables estimating the local batch gradients from arbitrarily drawn
samples of local data; and, (ii) \textit{global gradient tracking}, which fuses
the gradient information across the nodes. Naturally, combining different
variance reduction and gradient tracking techniques leads to different
algorithms of interest with valuable practical tradeoffs and design
considerations.
Our focus in this paper is on two instantiations of the~$\GTVR$ framework,
namely~\textbf{\texttt{GT-SAGA}} and~\textbf{\texttt{GT-SVRG}}, that, similar
to their centralized counterparts (\SAGA~and~\SVRG), exhibit a compromise
between space and time. We show that both~\textbf{\texttt{GT-SAGA}}
and~\textbf{\texttt{GT-SVRG}} achieve accelerated linear convergence for smooth
and strongly convex problems and further describe the regimes in which they
achieve non-asymptotic, network-independent linear convergence rates that are
faster with respect to the existing decentralized first-order schemes.
Moreover, we show that both algorithms achieve a linear speedup in such
regimes, in that, the total number of gradient computations required at each
node is reduced by a factor of $1/n$, where $n$ is the number of nodes,
compared to their centralized counterparts that process all data at a single
node. Extensive simulations illustrate the convergence behavior of the
corresponding algorithms.

本文提出一种名为 GTVR 的随机分散算法框架，其基于本地方差缩减和全局梯度跟踪的技术，用于解决大规模，有可能无法集中处理私有数据的优化问题。我们在本文中重点研究了 GTVR 并介绍了两种算法 GT-SAGA 和 GT-SVRG，证明它们在解决光滑问题上呈现出线性收敛，并实现了在网络独立下的线性速度提升。

具有加速收敛的方差缩减分散随机优化

Variance-Reduced Decentralized Stochastic Optimization with Accelerated  Convergence

Stochastic gradient descent (SGD) is a simple and popular method to solve
stochastic optimization problems which arise in machine learning. For strongly
convex problems, its convergence rate was known to be O(\log(T)/T), by running
SGD for T iterations and returning the average point. However, recent results
showed that using a different algorithm, one can get an optimal O(1/T) rate.
This might lead one to believe that standard SGD is suboptimal, and maybe
should even be replaced as a method of choice. In this paper, we investigate
the optimality of SGD in a stochastic setting. We show that for smooth
problems, the algorithm attains the optimal O(1/T) rate. However, for
non-smooth problems, the convergence rate with averaging might really be
\Omega(\log(T)/T), and this is not just an artifact of the analysis. On the
flip side, we show that a simple modification of the averaging step suffices to
recover the O(1/T) rate, and no other change of the algorithm is necessary. We
also present experimental results which support our findings, and point out
open problems.

本文研究了随机梯度下降在随机情形下的最优性。结果表明，对于光滑问题，算法可以达到最优的 O (1/T) 收敛速率，但对于非光滑问题，平均收敛速率可能真的是 Ω(log (T)/T)，而这不仅仅是分析的产物。反过来，我们展示了一种简单的平均步骤修改方法，足以恢复到 O (1/T) 收敛速率，而无需对算法做出任何其他改变。此外，我们还给出了支持我们发现的实验结果，并指出了开放性问题。