Improving the Bit Complexity of Communication for Distributed Convex Optimization

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 optimal, as proven by our lower bounds.

For example, for solving least squares regression in the coordinator model with s servers, n examples, d dimensions, and coefficients specified using at most L bits, we improve the prior communication bound of Vempala, Wang, and Woodruff (SODA, 2020) from Õ(sd 2 L) to Õ(sdL+ d 2 ε -1 L), which is optimal up to logarithmic factors. We also study the problem of solving least squares regression in the coordinator model to high accuracy, for which we provide an algorithm with a communication complexity of O(sd(L + log κ) log(ε -1 ) + d 2 L), matching our improved lower bound for well-conditioned matrices up to a log(ε -1 ) factor. 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.

We also give an improved algorithm for high-accuracy linear programming in the coordinator model that computes an approximate solution on well-conditioned inputs using Õ(sd 1.5 L + d 2 L) communication. This improves over the previous bound of sd 2 L. Finally, we give an improved algorithm, in the blackboard model of communication, for the problem min θ∈R d s i=1 f i (θ) where each f i is convex, Lipschitz, and supported on d i ≤ d (potentially overlapping) coordinates of θ using Õ(

Our techniques yield improved rates for decomposable submodular function minimization in the non-distributed setting as well.