A Comparative Analysis of Distributed Linear Solvers under Data Heterogeneity
This work addresses efficiency challenges in distributed linear solvers for applications like federated learning, though it is incremental as it compares existing algorithm classes with a new analysis framework.
The paper tackles the problem of solving large-scale linear equations in distributed or federated settings under data heterogeneity, introducing a novel geometric notion called angular heterogeneity to characterize optimal convergence rates and establishing the superiority of Accelerated Projected Consensus in scenarios with significant heterogeneity.
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.