Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence
Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence
复制标题
DOI：
10.1109/tsp.2020.3031071
复制
发表时间：
2019-12
影响因子：
5.4
通讯作者：
Ran Xin;U. Khan;S. Kar
中科院分区：
文献类型：
--
作者：
Ran Xin;U. Khan;S. Kar
本文描述了一种新的算法框架，以最小化网络节点上可用的函数的有限和。我们称之为GT-VR的拟议框架是随机和分散的，因此特别适合于无法在集中式服务器上收集或处理大规模潜在隐私数据的问题。GT-VR框架产生了一系列具有两个关键成分的算法：（i）局部方差减少，这使得能够从任意抽取的局部数据样本中估计局部批量梯度;以及（ii）全局梯度跟踪，它融合了跨节点的梯度信息。自然地，将不同的方差减小和梯度跟踪技术相结合会产生不同的感兴趣的算法，这些算法具有有价值的实际权衡和设计考虑。我们在本文中的重点是两个实例的${\bf \mathtt {GT-VR}}$框架，即GT-SAGA和GT-SVRG，类似于他们的集中式对应（佐贺和SVRG），表现出空间和时间之间的妥协。我们表明，GT-SAGA和GT-SVRG实现加速线性收敛光滑和强凸问题，并进一步描述了他们实现非渐近，网络独立的线性收敛速度更快，相对于现有的分散一阶计划的制度。此外，我们表明，这两种算法实现了线性加速比，在这样的制度相比，他们的集中式的同行，在一个单一的节点上处理所有的数据。大量的仿真结果表明了相应算法的收敛性。
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 GT-VR, 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 GT-VR framework leads to a family of algorithms with two key ingredients: (i) local variance reduction, that enables estimating the local batch gradients from arbitrarily drawn samples of local data; and, (ii) 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 ${\bf \mathtt {GT-VR}}$ framework, namely GT-SAGA and GT-SVRG, that, similar to their centralized counterparts (SAGA and SVRG), exhibit a compromise between space and time. We show that both GT-SAGA and 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 compared to their centralized counterparts that process all data at a single node. Extensive simulations illustrate the convergence behavior of the corresponding algorithms.