Lune

SODA2020Top-tier venue

The Communication Complexity of Optimization

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

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 P1, …, Ps, the i-th of which holds a subset A(i) x = b(i) of ni constraints of a linear system in d variables, and the coordinator would like to output an x ϵ ℝd for which A(i) x = b(i) for i = 1, …, 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 (d2 L + sd) and (sd2L), respectively. We obtain similar results for the blackboard communication model. As a result of independent interest, we show the probability a random matrix with integer entries in –2L, …, 2L is invertible is 1–2−Θ(dL), whereas previously only 1 – 2−Θ(d) was known. When there is no solution to the linear system, a natural alternative is to find the solution minimizing the ℓp loss, which is the ℓp regression problem. While this problem has been studied, we give improved upper or lower bounds for every value of p ≥ 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, such as linear, semi-definite, and convex programming. For linear programming, we first resolve the communication complexity when d is constant, showing it is (sL) in the point-to-point model. For general d and in the point-to-point model, we show an Õ(sd3L) upper bound and an (d2 L + sd) lower bound. In fact, we show if one perturbs the coefficients randomly by numbers as small as 2−Θ(L), then the upper bound is Õ(sd2L) + poly(dL), and so this bound holds for almost all linear programs. Our study motivates understanding the bit complexity of linear programming, which is related to the running time in the unit cost RAM model with words of O(log(nd)) bits, and we give the fastest known algorithms for linear programming in this model.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

12 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Towards Tight Communication Lower Bounds for Distributed Optimisation cites Communication-Efficient Distributed Optimization with Quantized Preconditioners
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers12

  1. Coresets for Vertical Federated Learning: Regularized Linear Regression and KK-Means ClusteringLingxiao Huang, Zhize Li, Jialin Sun, Haoyu ZhaoNeurIPS 2022 · 31 citations
  2. Communication-Efficient Distributed Optimization with Quantized PreconditionersFoivos Alimisis, Peter Davies, Dan AlistarhICML 2021 · 17 citations
  3. The Structural Complexity of Matrix-Vector MultiplicationEmile Anand, Jan van den Brand, Rose McCartyNeurIPS 2025 · 12 citations
  4. Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract)Nikolai Karpov, Qin Zhang, Yuan ZhouFOCS 2020 · 10 citations
  5. Towards Tight Communication Lower Bounds for Distributed OptimisationJanne H. Korhonen, Dan AlistarhNeurIPS 2021 · 10 citations

Related papers

  1. Improving the Bit Complexity of Communication for Distributed Convex OptimizationMehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth et al.STOC 2024 · 1 citation
  2. Distributed Least Squares in Small Space via Sketching and Bias ReductionSachin Garg, Kevin Tan, Michal DerezinskiNeurIPS 2024 · 5 citations
  3. Tight Bounds for Maximum Weight Matroid Independent Set and Matching in the Zero Communication ModelIlan Doron-AradNeurIPS 2025
  4. Tight Bounds for the Subspace Sketch Problem with ApplicationsYi Li, Ruosong Wang, David P. WoodruffSODA 2020 · 5 citations
  5. Rounds vs Communication Tradeoffs for Maximal Independent SetsSepehr Assadi, Gillat Kol, Zhijun ZhangFOCS 2022 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines