论文标题
朝着紧密的沟通下限以进行分布式优化
Towards Tight Communication Lower Bounds for Distributed Optimisation
论文作者
论文摘要
我们考虑一个标准分布式优化设置，其中$ n $机器，每个机器持有$ d $ d $二维函数$ f_i $，旨在共同最大程度地减少功能的总和$ \ sum_ {i = 1}^n f_i（x）$。这个问题自然出现在大规模分布式优化中，其中标准解决方案是应用（随机）梯度下降的变体。我们专注于此问题的通信复杂性：我们的主要结果为$ n $机器需要发送和接收的位数为第一个完全无条件的界限，以在给定的错误耐受性范围内解决该问题。具体来说，我们表明需要在机器之间传达$ω（nd \ log d / n \ varepsilon）$总位，以找到添加剂$ε$ - approximation至$ \ sum_ {i = 1}^n f_i（x）$的最低限度。结果既适用于确定性和随机算法，而且重要的是，不需要对算法结构的假设。在对参数值的一定限制下，下限是紧密的，并且通过新的量化梯度下降的新变体在二次目标的恒定因子中匹配，我们将描述和分析。我们的结果带来了从通信复杂性到分布式优化的工具，这有可能进行进一步的应用。
We consider a standard distributed optimisation setting where $N$ machines, each holding a $d$-dimensional function $f_i$, aim to jointly minimise the sum of the functions $\sum_{i = 1}^N f_i (x)$. This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that $Ω( Nd \log d / N\varepsilon)$ total bits need to be communicated between the machines to find an additive $ε$-approximation to the minimum of $\sum_{i = 1}^N f_i (x)$. The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.
