# Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

arXiv: https://arxiv.org/abs/1805.10222 · HTML: https://mlsanity.com/paper/1805.10222/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2018.

## Built on by (most cited first, 30 of 34)

- [FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correction](https://mlsanity.com/paper/2203.11751/) (2022)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction](https://mlsanity.com/paper/2310.08670/) (2023)
- [Federated Learning with Taskonomy for Non-IID Data](https://mlsanity.com/paper/2103.15947/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients](https://mlsanity.com/paper/2102.06329/) (2021)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization](https://mlsanity.com/paper/2311.00465/) (2023)
- [Mixed-Precision Quantization for Federated Learning on Resource-Constrained Heterogeneous Devices](https://mlsanity.com/paper/2311.18129/) (2023)
- [Communication-Efficient Agnostic Federated Averaging](https://mlsanity.com/paper/2104.02748/) (2021)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Distributed Personalized Empirical Risk Minimization](https://mlsanity.com/paper/2310.17761/) (2023)
- [On the Convergence of Heterogeneous Federated Learning with Arbitrary Adaptive Online Model Pruning](https://mlsanity.com/paper/2201.11803/) (2022)
- [Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent](https://mlsanity.com/paper/2001.05918/) (2020)
- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)
- [Byzantine-Robust Federated Learning via Credibility Assessment on Non-IID Data](https://mlsanity.com/paper/2109.02396/) (2021)
- [Cross-Silo Federated Learning Across Divergent Domains with Iterative Parameter Alignment](https://mlsanity.com/paper/2311.04818/) (2023)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)

## Abstract (arXiv)

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.