# Distributed Linear Solvers and Data Heterogeneity

arXiv: https://arxiv.org/abs/2304.10640 · HTML: https://mlsanity.com/paper/2304.10640/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 20 Apr 2023.

## Builds on (most cited first, 11 of 11)

- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [A Survey of Distributed Consensus Protocols for Blockchain Networks](https://mlsanity.com/paper/1904.04098/) (2019)
- [ORFit: One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares](https://mlsanity.com/paper/2207.13853/) (2022)
- [A Distributed Algorithm for Solving a Linear Algebraic Equation](https://mlsanity.com/paper/1503.00808/) (2015)
- [Distributed Solution of Large-Scale Linear Systems via Accelerated Projection-Based Consensus](https://mlsanity.com/paper/1708.01413/) (2017)
- [A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks](https://mlsanity.com/paper/1809.07955/) (2018)
- [Robustness of Iteratively Pre-Conditioned Gradient-Descent Method: The Case of Distributed Linear Regression Problem](https://mlsanity.com/paper/2101.10967/) (2021)

## Abstract (arXiv)

We consider the problem of solving a large-scale system of linear equations in a distributed/federated setting. The taskmaster solves the system with the help of a set of machines, each of which possesses a subset of the equations. While various solutions for this problem exist, a fundamental understanding and rigorous comparison between the convergence rates of the main algorithmic classes - the projection-based methods and the optimization-based ones - is missing. We provide the first comprehensive analysis and comparison of these two classes of algorithms, with a particular focus on the fastest representative method from each class, i.e., the Accelerated Projection-Based Consensus (APC) and the Distributed Heavy-Ball Method. We introduce a novel notion of data heterogeneity called angular heterogeneity, discussing its significance. Using this notion, we characterize and compare the optimal convergence rates of the algorithms of interest and capture the effects of the number of machines, the number of equations, and cross-machine and local data heterogeneity on these rates. Our analysis sheds light on the previously observed superior performance of APC in realistic scenarios, where there is often large data heterogeneity, and provides several insights into the effect of angular heterogeneity on the efficiencies of different algorithms. Additionally, we provide distributed algorithms for efficiently computing the angular heterogeneity metrics. Lastly, as a by-product of this investigation, we obtain a tight bound on the condition number of an arbitrary matrix with full column rank in terms of the Euclidean norms of its columns and the angles between them. Numerical analyses validate our theoretical results, supporting the predicted advantage of APC in the high-heterogeneity regime and providing a deeper understanding of the effects of angular heterogeneity on convergence rates.