The Minimax Complexity of Distributed Optimization
arXiv:2109.00534
Abstract
In this thesis, I study the minimax oracle complexity of distributed stochastic optimization. First, I present the "graph oracle model", an extension of the classic oracle complexity framework that can be applied to study distributed optimization algorithms. Next, I describe a general approach to proving optimization lower bounds for arbitrary randomized algorithms (as opposed to more restricted classes of algorithms, e.g., deterministic or "zero-respecting" algorithms), which is used extensively throughout the thesis. For the remainder of the thesis, I focus on the specific case of the "intermittent communication setting", where multiple computing devices work in parallel with limited communication amongst themselves. In this setting, I analyze the theoretical properties of the popular Local Stochastic Gradient Descent (SGD) algorithm in convex setting, both for homogeneous and heterogeneous objectives. I provide the first guarantees for Local SGD that improve over simple baseline methods, but show that Local SGD is not optimal in general. In pursuit of optimal methods in the intermittent communication setting, I then show matching upper and lower bounds for the intermittent communication setting with homogeneous convex, heterogeneous convex, and homogeneous non-convex objectives. These upper bounds are attained by simple variants of SGD which are therefore optimal. Finally, I discuss several additional assumptions about the objective or more powerful oracles that might be exploitable in order to develop better intermittent communication algorithms with better guarantees than our lower bounds allow.
References in corpus (29)
- Adam: A Method for Stochastic Optimization
- Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
- Constrained Consensus
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
- Optimal Distributed Online Prediction using Mini-Batches
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- Don't Use Large Mini-Batches, Use Local SGD
- Local SGD Converges Fast and Communicates Little
- 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
- Adaptive Bound Optimization for Online Convex Optimization
- Communication Complexity of Distributed Convex Learning and Optimization
- Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
- Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
- Parallel SGD: When does averaging help?
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Unified Optimal Analysis of the (Stochastic) Gradient Method
- On Communication Cost of Distributed Statistical Estimation and Dimensionality
- Optimal Black-Box Reductions Between Optimization Objectives
- Accelerating SGD with momentum for over-parameterized learning
- Minibatch vs Local SGD for Heterogeneous Distributed Learning
- "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
- A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
- Lower Bound for Randomized First Order Convex Optimization
- On the Randomized Complexity of Minimizing a Convex Quadratic Function
- Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
- On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions