Abstract
Distributed optimization is a cornerstone of modern large-scale data analysis, yet the fundamental limits of communication efficiency remain poorly understood. This work provides a comprehensive analysis of the communication complexity for solving linear systems, $\ell_p$ regression, and linear programming in distributed environments. We demonstrate that traditional sketching and sampling methods are often suboptimal and introduce new adaptive, optimization-driven protocols. Our results establish tight bounds on bit complexity, revealing that randomization can significantly reduce communication overhead.
Introduction
In distributed computing, the primary bottleneck is often the communication between servers rather than local computation. While previous research has focused on the number of communication rounds, this study addresses the more fundamental question of bit complexity: the minimum number of bits required to reach a solution. We consider scenarios where data and constraints are distributed across $s$ servers, focusing on three core problems: linear systems ($Ax = b$), $\ell_p$ regression, and linear/convex programming. A significant challenge in these settings is ensuring that intermediate calculations do not require infinite precision, which would lead to infinite communication costs.
Distributed Optimization Protocols
We move beyond "one-shot" sketching techniques toward adaptive protocols that leverage the structure of the optimization problem.
Linear Systems and Randomized Hashing
For solving linear systems where rows of $A$ are split across servers, we employ a randomized hashing trick. Instead of transmitting full equations, servers communicate random linear combinations of their constraints. This approach ensures that if a server possesses a linearly independent constraint, it is revealed with high probability, significantly reducing the total bits exchanged.
Linear and Convex Programming
We adapt classical algorithms, such as Clarkson’s and Seidel’s, for distributed linear programming (LP). These protocols involve sampling constraints, solving local sub-problems, and communicating to identify violated constraints. For convex programming, we implement a distributed Center-of-Gravity method using rounding techniques to maintain manageable bit complexity for communicated cutting planes.
Smoothed Analysis
To bridge the gap between theoretical worst-case bounds and practical performance, we apply smoothed complexity to LP. By introducing minor random noise to input coefficients, we demonstrate that the communication requirements for "almost all" linear programs are substantially lower than the worst-case scenarios.
Theoretical Insights
Our analysis yields several key findings in matrix theory and complexity:
- Randomization Benefits: Randomization reduces communication complexity for linear systems from $\Theta(sd^2L)$ to $\Theta(d^2L + sd)$, providing massive savings as the number of servers or precision requirements grow.
- Limits of Sketching: For $\ell_p$ regression with $p > 2$, standard sketching is shown to be suboptimal. Our LP-based approach achieves a superior dependence on the dimension $d$.
- Matrix Invertibility: We prove a long-standing conjecture that a random $d \times d$ matrix with $L$-bit integer entries is invertible with probability $1 - 2^{-\Theta(dL)}$, a result crucial for establishing our lower bounds.
- Feasibility vs. Solving: We find that in constant dimensions, determining if a linear system is feasible is exponentially easier ($O(s \log L)$ bits) than finding the actual solution.
Summary of Results
The paper establishes the first nearly tight bounds for several fundamental problems, as summarized in the tables below.
As shown in the table above, the transition from deterministic to randomized protocols often leads to significant reductions in lower bounds, particularly for $\ell_1$ and $\ell_2$ measures. Furthermore, we provide the first communication-efficient protocols for general distributed LP with an upper bound of $\tilde{O}(sd^3L)$, which improves to $\tilde{O}(sd^2L + d^4L)$ under smoothed analysis.
Limitations and Future Directions
Despite these advancements, several open questions remain. A gap persists between the $\tilde{O}(sd^3L)$ upper bound and the $\Omega(d^2L + sd)$ lower bound for general linear programming. Additionally, our optimal algorithms for the "Blackboard" model currently assume random assignment of constraints to servers. Future work will focus on removing these assumptions and exploring the Pareto frontier between communication rounds and total bit complexity.
Summary updated