On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
复制标题
DOI：
10.1007/s10915-017-0628-z
复制
发表时间：
2016-09
影响因子：
2.5
通讯作者：
Robert Hannah;W. Yin
中科院分区：
文献类型：
--
作者：
Robert Hannah;W. Yin
大规模优化问题对可扩展求解器的需求推动了异步并行算法的发展，其中一组节点并行运行，几乎没有同步，从而使用延迟信息进行计算。本文发展了强大的Lyapunov函数技巧，并利用它们研究了潜在无界时滞下的异步并行算法的收敛问题。AROCK是一种非常通用的异步算法，它将许多流行的算法作为特例：例如，异步块梯度下降、前向向后、ADMM等。因此，我们的结果具有广泛的含义和广泛的应用。Arock通过让一组节点随机选择要以异步并行方式更新的解决方案坐标来并行化定点迭代。现有的AROCK分析假设延迟是有界的，并使用这个界来设置一个对收敛和效率都很重要的步长。其他工作虽然允许无限延迟，但对底层的定点运算符施加了严格的条件，导致应用有限。本文建立了无界时滞下的收敛问题，无界时滞可以是随机的，也可以是确定性的。所提出的步长比已有工作中的步长更实用、更大。步长适应延迟分布或系统中正在经历的当前延迟，而不是受最坏情况下的延迟的限制。生成了新的Lyapunov函数，这是分析异步算法的关键，以获得我们的结果。给出了一种生成Lyapunov函数的一般策略，该策略可应用于其他算法的收敛分析。给出了一套适合大规模应用的优化算法，包括机器学习算法和科学计算算法。
The need for scalable solvers for massive optimization problems has motivated the development of asynchronous-parallel algorithms, where a set of nodes runs in parallel with little or no synchronization, thus computing with delayed information. This paper develops powerful Lyapunov-functions techniques, and uses them to study the convergence of the asynchronous-parallel algorithm ARock underpotentially unbounded delays. ARock is a very general asynchronous algorithm, that takes many popular algorithms as special cases: for instance, asynchronous block gradient descent, forward backward, ADMM, etc. Therefore our results have broad implications, and a range of applications. ARock parallelizes a fixed-point iterations by letting a set of nodes randomly choose solution coordinates to update in an asynchronous parallel fashion. The existing analysis of ARock assumes the delays to be bounded, and uses this bound to set a step size that is important to both convergence and efficiency. Other works, though allowing unbounded delays, impose strict conditions on the underlying fixed-point operator, resulting in limited applications. In this paper, convergence is established under unbounded delays, which can be either stochastic or deterministic. The proposed step sizes are more practical and larger than those in the existing work. The step size adapts to the delay distribution or the current delay being experienced in the system, instead of being limited by worst-case scenario delays. New Lyapunov functions, which are the key to analyzing asynchronous algorithms, are generated to obtain our results. A general strategy for generating Lyapunov functions is presented, which may find application in convergence analyses of other algorithms. A set of applicable optimization algorithms with large-scale applications are given, including machine learning and scientific computing algorithms.