Towards Tight Communication Lower Bounds for Distributed Optimisation

Abstract

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 $\Omega (Nd\log d/N\epsilon )$ total bits need to be communicated between the machines to find an additive $\epsilon$-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.

References in corpus (15)

• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Distributed Mean Estimation with Limited Communication
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Communication Complexity of Distributed Convex Learning and Optimization
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• Linearly Converging Error Compensated SGD
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• New Bounds For Distributed Mean Estimation and Variance Reduction

Cited by in corpus (1)

• Communication-Efficient Distributed Optimization with Quantized Preconditioners