TY - JOUR

T1 - On the convergence analysis of asynchronous SGD for solving consistent linear systems

AU - Sahu, Atal Narayan

AU - Dutta, Aritra

AU - Tiwari, Aashutosh

AU - Richtárik, Peter

N1 - Funding Information:
Aritra Dutta acknowledges being an affiliated researcher at the Pioneer Centre for AI, Denmark.
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2023/4/15

Y1 - 2023/4/15

N2 - Parallel and distributed stochastic algorithms have drawn significant attention in the realm of big data and machine learning. While the synchronous versions of these algorithms are well understood in terms of their convergence, the convergence analyses of their asynchronous counterparts are not widely studied. In this paper, we propose and analyze a distributed, asynchronous parallel algorithm to solve an arbitrary, consistent linear system by reformulating the system into a stochastic optimization problem as Richtárik and Takác̃ in [1]. We compare the convergence rates of our asynchronous algorithm with the synchronous parallel algorithm proposed by Richtárik and Takáč in [1] under different choices of the hyperparameters—the stepsize, the damping factor, the number of processors, and the delay factor. We show that our asynchronous parallel algorithm enjoys a global linear convergence rate, similar to the synchronous parallel algorithm in [1] under the same setup. We also show that our asynchronous algorithm improves upon the synchronous algorithm in [1] with a better convergence rate when the number of processors is larger than four. Furthermore, our asynchronous parallel algorithm performs asymptotically better than its synchronous counterpart for certain linear systems. Finally, we compute the minimum number of processors required for those systems for which our asynchronous algorithm is better and find that this number can be as low as two for some ill-conditioned problems.

AB - Parallel and distributed stochastic algorithms have drawn significant attention in the realm of big data and machine learning. While the synchronous versions of these algorithms are well understood in terms of their convergence, the convergence analyses of their asynchronous counterparts are not widely studied. In this paper, we propose and analyze a distributed, asynchronous parallel algorithm to solve an arbitrary, consistent linear system by reformulating the system into a stochastic optimization problem as Richtárik and Takác̃ in [1]. We compare the convergence rates of our asynchronous algorithm with the synchronous parallel algorithm proposed by Richtárik and Takáč in [1] under different choices of the hyperparameters—the stepsize, the damping factor, the number of processors, and the delay factor. We show that our asynchronous parallel algorithm enjoys a global linear convergence rate, similar to the synchronous parallel algorithm in [1] under the same setup. We also show that our asynchronous algorithm improves upon the synchronous algorithm in [1] with a better convergence rate when the number of processors is larger than four. Furthermore, our asynchronous parallel algorithm performs asymptotically better than its synchronous counterpart for certain linear systems. Finally, we compute the minimum number of processors required for those systems for which our asynchronous algorithm is better and find that this number can be as low as two for some ill-conditioned problems.

KW - Asynchronous communication

KW - Distributed optimization

KW - Iterative methods

KW - Linear systems

KW - Parallel algorithms

KW - Stochastic optimization

U2 - 10.1016/j.laa.2022.12.017

DO - 10.1016/j.laa.2022.12.017

M3 - Journal article

AN - SCOPUS:85146421627

SN - 0024-3795

VL - 663

SP - 1

EP - 31

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -