Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
arXiv:1805.10222
Abstract
We suggest a general oracle-based framework that captures different parallel stochastic optimization settings described by a dependency graph, and derive generic lower bounds in terms of this graph. We then use the framework and derive lower bounds for several specific parallel optimization settings, including delayed updates and parallel processing with intermittent communication. We highlight gaps between lower and upper bounds on the oracle complexity, and cases where the "natural" algorithms are not known to be optimal.
Cited by in corpus (24)
- On the Convergence of FedAvg on Non-IID Data
- SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
- Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
- Applied Federated Learning: Improving Google Keyboard Query Suggestions
- Federated Optimization in Heterogeneous Networks
- Fair Resource Allocation in Federated Learning
- Three Approaches for Personalization with Applications to Federated Learning
- Local SGD Converges Fast and Communicates Little
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Lower Bounds and Optimal Algorithms for Personalized Federated Learning
- Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
- The Complexity of Making the Gradient Small in Stochastic Convex Optimization
- Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
- Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
- Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
- Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
- A Stochastic Newton Algorithm for Distributed Convex Optimization
- Communication-Efficient Agnostic Federated Averaging
- Optimal Complexity in Decentralized Training
- Accelerated and nonaccelerated stochastic gradient descent with model conception
- Never Go Full Batch (in Stochastic Convex Optimization)
- DEED: A General Quantization Scheme for Communication Efficiency in Bits
- Towards Tight Communication Lower Bounds for Distributed Optimisation