A Comparative Analysis of Distributed Linear Solvers under Data Heterogeneity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916803225059328 |
|---|---|
| author | Velasevic, Boris Parasnis, Rohit Brinton, Christopher G. Azizan, Navid |
| author_facet | Velasevic, Boris Parasnis, Rohit Brinton, Christopher G. Azizan, Navid |
| contents | We consider the problem of solving a large-scale system of linear equations in a distributed or federated manner by a taskmaster and a set of machines, each possessing a subset of the equations. We provide a comprehensive comparison of two well-known classes of algorithms used to solve this problem: projection-based methods and optimization-based methods. First, we introduce a novel geometric notion of data heterogeneity called angular heterogeneity and discuss its generality. Using this notion, we characterize the optimal convergence rates of the most prominent algorithms from each class, capturing the effects of the number of machines, the number of equations, and that of both cross-machine and local data heterogeneity on these rates. Our analysis establishes the superiority of Accelerated Projected Consensus in realistic scenarios with significant data heterogeneity and offers several insights into how angular heterogeneity affects the efficiency of the methods studied. Additionally, we develop distributed algorithms for the efficient computation of the proposed angular heterogeneity metrics. Our extensive numerical analyses validate and complement our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_10640 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Comparative Analysis of Distributed Linear Solvers under Data Heterogeneity Velasevic, Boris Parasnis, Rohit Brinton, Christopher G. Azizan, Navid Distributed, Parallel, and Cluster Computing Machine Learning Numerical Analysis G.1.3; I.2.11; I.2.6 We consider the problem of solving a large-scale system of linear equations in a distributed or federated manner by a taskmaster and a set of machines, each possessing a subset of the equations. We provide a comprehensive comparison of two well-known classes of algorithms used to solve this problem: projection-based methods and optimization-based methods. First, we introduce a novel geometric notion of data heterogeneity called angular heterogeneity and discuss its generality. Using this notion, we characterize the optimal convergence rates of the most prominent algorithms from each class, capturing the effects of the number of machines, the number of equations, and that of both cross-machine and local data heterogeneity on these rates. Our analysis establishes the superiority of Accelerated Projected Consensus in realistic scenarios with significant data heterogeneity and offers several insights into how angular heterogeneity affects the efficiency of the methods studied. Additionally, we develop distributed algorithms for the efficient computation of the proposed angular heterogeneity metrics. Our extensive numerical analyses validate and complement our theoretical results. |
| title | A Comparative Analysis of Distributed Linear Solvers under Data Heterogeneity |
| topic | Distributed, Parallel, and Cluster Computing Machine Learning Numerical Analysis G.1.3; I.2.11; I.2.6 |
| url | https://arxiv.org/abs/2304.10640 |