# Improving the Bit Complexity of Communication for Distributed Convex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2024.

## Built on by (most cited first, 2 of 2)

- [Improved Sample Complexity of Imitation Learning for Barrier Model Predictive Control](https://mlsanity.com/paper/2410.00859/) (2024)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)

## Abstract (arXiv)

We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen known bounds for approximately solving linear regression, p-norm regression (for 1≤ p≤ 2), linear programming, minimizing the sum of finitely many convex nonsmooth functions with varying supports, and low rank approximation; for a number of these fundamental problems our bounds are nearly optimal, as proven by our lower bounds. Among our techniques, we use the notion of block leverage scores, which have been relatively unexplored in this context, as well as dropping all but the ``middle" bits in Richardson-style algorithms. We also introduce a new communication problem for accurately approximating inner products and establish a lower bound using the spherical Radon transform. Our lower bound can be used to show the first separation of linear programming and linear systems in the distributed model when the number of constraints is polynomial, addressing an open question in prior work.