Asynchronous Distributed Optimization with Delay-free Parameters
Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or use fixed step-sizes that depend on and decrease with an upper bound of the delays. Not only are such delay bounds hard to obtain in advance, but they also tend to be large and rarely attained, resulting in unnecessarily slow convergence. This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays. We establish convergence guarantees for convex and strongly convex problems under both partial and total asynchrony. We also show that the convergence speed of the two asynchronous methods adjusts to the actual level of asynchrony rather than being constrained by the worst-case. Numerical experiments demonstrate a strong practical performance of our asynchronous algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Asynchronous Heavy-Tailed Optimization
Heavy-tailed stochastic gradient noise, commonly observed in transformer models, can destabilize the optimization process. Recent works mainly focus on developing and understanding approaches to address heavy-tailed nois…
On Parallel or Distributed Asynchronous Iterations with Unbounded Delays and Possible Out of Order Messages or Flexible Communication for Convex Optimization Problems and Machine Learning
We describe several features of parallel or distributed asynchronous iterative algorithms such as unbounded delays, possible out of order messages or flexible communication. We concentrate on the concept of macroiteratio…
SurveyThe Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical…
BIG-bench Machine LearningAsynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
Aiming at solving large-scale learning problems, this paper studies distributed optimization methods based on the alternating direction method of multipliers (ADMM). By formulating the learning problem as a consensus pro…
Distributed OptimizationDistributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?
One of the most widely used optimization methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue that arises here is that of delayed gr…