The Communication Complexity of Optimization
  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{\Theta}(d^2L +
sd)$ and $\tilde{\Theta}(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 $\epsilon$,
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{\Theta}(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{\Omega}(d^2 L + sd)$ lower bound. We also show if one perturbs the
coefficients randomly by numbers as small as $2^{-\Theta(L)}$, then the upper
bound is $\tilde{O}(sd^2 L) + \textrm{poly}(dL)$.
