The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

Abstract

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 communication to optimize the objective, and during each round of communication, each machine may sequentially compute $K$ stochastic gradient estimates. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.

arXiv comment48 pages

References in corpus (20)

• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Local SGD Converges Fast and Communicates Little
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Communication Complexity of Distributed Convex Learning and Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Federated Accelerated Stochastic Gradient Descent
• Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Acceleration with a Ball Optimization Oracle
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions

Cited by in corpus (5)

• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Parallel and Distributed algorithms for ML problems
• On Second-order Optimization Methods for Federated Learning