Communication Complexity of Distributed Convex Learning and Optimization

Abstract

We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.

References in corpus (3)

• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Communication-Efficient Distributed Dual Coordinate Ascent
• Improved Distributed Principal Component Analysis

Cited by in corpus (40)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Distributed Mean Estimation with Limited Communication
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Adaptive Federated Learning in Resource Constrained Edge Computing Systems
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Communication optimization strategies for distributed deep neural network training: A survey
• Challenges of AI in Wireless Networks for IoT
• Tight Complexity Bounds for Optimizing Composite Objectives
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Efficient Distributed Learning with Sparsity
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• D2P-Fed: Differentially Private Federated Learning With Efficient Communication
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Distributed Saddle-Point Problems Under Similarity
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• A Distributed One-Step Estimator
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
• Acceleration in Distributed Optimization under Similarity
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Collaborative Top Distribution Identifications with Limited Interaction
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Optimal Complexity in Decentralized Training
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• A Survey on Large-scale Machine Learning
• Model Aggregation via Good-Enough Model Spaces
• Accelerated Sparsified SGD with Error Feedback
• The Minimax Complexity of Distributed Optimization
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Parallel and Distributed algorithms for ML problems
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• Newton Method over Networks is Fast up to the Statistical Precision