On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays
复制标题
DOI：
10.1007/s40305-017-0183-1
复制
发表时间：
2016-12
影响因子：
1.4
通讯作者：
Zhimin Peng;Yangyang Xu;Ming Yan;W. Yin
中科院分区：
文献类型：
--
作者：
Zhimin Peng;Yangyang Xu;Ming Yan;W. Yin
近年来，由于涉及大规模数据和大量决策变量的问题，异步并行(异步-并行)迭代算法激增。由于异步性，迭代是用过时的信息计算的，而过时信息的年龄，我们称之为延迟，是它自创建以来被更新的次数。几乎所有最近的工作都在有限最大时滞的假设下证明了收敛，并相应地设置了步长参数。然而，最大延迟实际上是未知的。本文从概率的角度分析了一种考虑大延迟的异步并行算法的收敛性能。根据时延的统计特性，给出了保证收敛的步长的显式公式。在相同的处理器下，我们经验地测量了延迟与参数p符合泊松分布，与我们的理论模型相匹配，因此，步长可以相应地设置。对凸优化问题和非凸优化问题的仿真验证了分析的有效性，同时也表明现有的最大延迟诱导步长过于保守，往往会降低算法的收敛速度。
Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we calldelay, is the number of times it has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown. This paper presents convergence analysis of an async-parallel method from a probabilistic viewpoint, and it allows for large unbounded delays. An explicit formula of stepsize that guarantees convergence is given depending on delays’ statistics. Withidentical processors, we empirically measured that delays closely follow the Poisson distribution with parameterp, matching our theoretical model, and thus, the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay-induced stepsize is too conservative, often slows down the convergence of the algorithm.