The Communication Complexity of Optimization

Santosh S. Vempala, Ruosong Wang, David P. Woodruff

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.

Summary of communication complexity bounds for various error measures, highlighting the gap between randomized and deterministic protocols.

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.

Upper and lower bounds for $\ell_1$ and $\ell_2$ regression as a function of the error parameter $\epsilon$.

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

Abstract

We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator together with $s$ servers $P_1, \ldots, P_s$, the $i$-th of which holds a subset $A^{(i)} x = b^{(i)}$ of $n_i$ constraints of a linear system in $d$ variables, and the coordinator would like to output $x \in \mathbb{R}^d$ for which $A^{(i)} x = b^{(i)}$ for $i = 1, \ldots, s$. We assume each coefficient of each constraint is specified using $L$ bits. We first resolve the randomized and deterministic communication complexity in the point-to-point model of communication, showing it is $\tildeΘ(d^2L + sd)$ and $\tildeΘ(sd^2L)$, respectively. We obtain similar results for the blackboard model. When there is no solution to the linear system, a natural alternative is to find the solution minimizing the $\ell_p$ loss. While this problem has been studied, we give improved upper or lower bounds for every value of $p \ge 1$. One takeaway message is that sampling and sketching techniques, which are commonly used in earlier work on distributed optimization, are neither optimal in the dependence on $d$ nor on the dependence on the approximation $ε$, thus motivating new techniques from optimization to solve these problems. Towards this end, we consider the communication complexity of optimization tasks which generalize linear systems. For linear programming, we first resolve the communication complexity when $d$ is constant, showing it is $\tildeΘ(sL)$ in the point-to-point model. For general $d$ and in the point-to-point model, we show an $\tilde{O}(sd^3 L)$ upper bound and an $\tildeΩ(d^2 L + sd)$ lower bound. We also show if one perturbs the coefficients randomly by numbers as small as $2^{-Θ(L)}$, then the upper bound is $\tilde{O}(sd^2 L) + \textrm{poly}(dL)$.
BibTeX
@inproceedings{vempala2020communication,
  author = {Santosh S. Vempala and Ruosong Wang and David P. Woodruff},
  title = {{The Communication Complexity of Optimization}},
  booktitle = {SODA},
  year = {2020},
  doi = {10.1137/1.9781611975994.106},
}
Figure