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)$.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationSimilar Papers 제목 키워드 기반
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization
For SGD based distributed stochastic optimization, computation complexity, measured by the convergence rate in terms of the number of stochastic gradient calls, and communication complexity, measured by the number of int…
Stochastic OptimizationThe Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
We resolve the min-max complexity of distributed stochastic convex optimization (up to a log factor) in the intermittent communication setting, where $M$ machines work in parallel over the course of $R$ rounds of communi…
CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity
With distributed machine learning being a prominent technique for large-scale machine learning tasks, communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. In thi…
Distributed OptimizationA Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization
Decentralized optimization methods with local updates have recently gained attention for their provable ability to communication acceleration. In these methods, nodes perform several iterations of local computations betw…
Distributed OptimizationCommunication-Efficient Federated Group Distributionally Robust Optimization
Federated learning faces challenges due to the heterogeneity in data volumes and distributions at different clients, which can compromise model generalization ability to various distributions. Existing approaches to addr…
Federated Learning