mlsanityData to 14 Oct 2026

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

arXiv 1805.10222 ↗First posted 25 May 2018math.OC cs.LG stat.MLcited by 34

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2020: 1; 2021: 11; 2022: 6; 2023: 7; 2024: 6; 2025: 3.

34 papers.

Sort:

By area:

  1. 2022FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correctioncited by 181
  2. 2021Learning with User-Level Privacycited by 72
  3. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  4. 2021Personalized Federated Learning: A Unified Framework and Universal Optimization Techniquescited by 34
  5. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  6. 2021A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularizationcited by 27
  7. 2023Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reductioncited by 24
  8. 2021Federated Learning with Taskonomy for Non-IID Datacited by 21
  9. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 21
  10. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 18
  11. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  12. 2021Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradientscited by 13
22 more
  1. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  2. 2023Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimizationcited by 11
  3. 2023Mixed-Precision Quantization for Federated Learning on Resource-Constrained Heterogeneous Devicescited by 11
  4. 2021Communication-Efficient Agnostic Federated Averagingcited by 10
  5. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  6. 2021The Minimax Complexity of Distributed Optimizationcited by 7
  7. 2023Federated Online and Bandit Convex Optimizationcited by 7
  8. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
  9. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  10. 2022Federated Optimization of Smooth Loss Functionscited by 6
  11. 2023Distributed Personalized Empirical Risk Minimizationcited by 6
  12. 2022On the Convergence of Heterogeneous Federated Learning with Arbitrary Adaptive Online Model Pruningcited by 4
  13. 2020Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descentcited by 3
  14. 2022STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronizationcited by 2
  15. 2021Byzantine-Robust Federated Learning via Credibility Assessment on Non-IID Datacited by 1
  16. 2023Cross-Silo Federated Learning Across Divergent Domains with Iterative Parameter Alignmentcited by 1
  17. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  18. 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
  19. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  20. 2025Non-Convex Federated Optimization under Cost-Aware Client Selectioncited by 1
  21. 2023DRAG: Divergence-based Adaptive Aggregation in Federated learning on Non-IID Datacited by 0
  22. 2024Approximate Gradient Coding for Privacy-Flexible Federated Learning with Non-IID Datacited by 0