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)$.

我们考虑了一些分布式优化问题的通信复杂性。我们从求解线性系统的问题开始。假设有一个协调器和$s$服务器$P_1, \ldots, P_s$，其中$i$ -th持有$d$变量中$n_i$约束的一个子集$A^{(i)} x = b^{(i)}$，并且协调器想要输出$x \in \mathbb{R}^d$为$A^{(i)} x = b^{(i)}$为$i = 1, \ldots, s$。我们假设每个约束的每个系数都使用$L$位来指定。我们首先解决了通信点对点模型中的随机化和确定性通信复杂度，分别为$\tilde{\Theta}(d^2L + sd)$和$\tilde{\Theta}(sd^2L)$。对于黑板模型，我们得到了类似的结果。当线性系统没有解时，一个自然的替代方法是找到最小化$\ell_p$损失的解。在研究这个问题的同时，我们给出了改进的$p \ge 1$值的上界或下界。一个重要的信息是，在早期的分布式优化工作中通常使用的采样和素描技术，在依赖$d$和依赖近似$\epsilon$时都不是最优的，因此激发了从优化到解决这些问题的新技术。为此，我们考虑了广义线性系统的优化任务的通信复杂性。对于线性规划，我们首先求解$d$为常数时的通信复杂度，表明它在点对点模型中为$\tilde{\Theta}(sL)$。对于一般的$d$和点到点模型，我们给出了一个$\tilde{O}(sd^3 L)$上界和一个$\tilde{\Omega}(d^2 L + sd)$下界。我们还表明，如果用小到$2^{-\Theta(L)}$的数字随机扰动系数，则上界为$\tilde{O}(sd^2 L) + \textrm{poly}(dL)$。