DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Saeed Soori;Konstantin Mischenko;Aryan Mokhtari;M. Dehnavi;Mert Gurbuzbalaban
中科院分区：
文献类型：
--
作者：
Saeed Soori;Konstantin Mischenko;Aryan Mokhtari;M. Dehnavi;Mert Gurbuzbalaban
在本文中，我们考虑分布式算法解决的经验风险最小化问题下的主/工人通信模型。我们开发了一个分布式异步拟牛顿算法，可以实现超线性收敛。据我们所知，这是第一个具有超线性收敛保证的分布式异步算法。我们的算法是通信效率的意义上说，在每次迭代的主节点和工人沟通向量的大小为O（p），其中$p$是决策变量的维度。所提出的方法是基于一个分布式异步平均方案的决策向量和梯度的方式，以有效地捕捉局部Hessian信息的目标函数。我们的收敛理论支持异步计算受到有界延迟和无界延迟有界的时间平均。与大多数异步优化文献不同，当延迟很大时，我们不需要选择较小的步长。我们提供的数值实验，我们的理论结果相匹配，并展示了显着的改进相比，最先进的分布式算法。
In this paper, we consider distributed algorithms for solving the empirical risk minimization problem under the master/worker communication model. We develop a distributed asynchronous quasi-Newton algorithm that can achieve superlinear convergence. To our knowledge, this is the first distributed asynchronous algorithm with superlinear convergence guarantees. Our algorithm is communication-efficient in the sense that at every iteration the master node and workers communicate vectors of size $O(p)$, where $p$ is the dimension of the decision variable. The proposed method is based on a distributed asynchronous averaging scheme of decision vectors and gradients in a way to effectively capture the local Hessian information of the objective function. Our convergence theory supports asynchronous computations subject to both bounded delays and unbounded delays with a bounded time-average. Unlike in the majority of asynchronous optimization literature, we do not require choosing smaller stepsize when delays are huge. We provide numerical experiments that match our theoretical results and showcase significant improvement comparing to state-of-the-art distributed algorithms.