mlsanityData to 7 Oct 2026

Order Optimal Bounds for One-Shot Federated Learning over non-Convex Loss Functions

arXiv 2108.08677 ↗First posted 19 Aug 2021cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider the problem of federated learning in a one-shot setting in which there are m machines, each observing n sample functions from an unknown distribution on non-convex loss functions. Let F:[-1,1]d→ℝ be the expected loss function with respect to this unknown distribution. The goal is to find an estimate of the minimizer of F. Based on its observations, each machine generates a signal of bounded length B and sends it to a server. The server collects signals of all machines and outputs an estimate of the minimizer of F. We show that the expected loss of any algorithm is lower bounded by maxbig(1/(√n(mB)1/d), 1/√mnbig), up to a logarithmic factor. We then prove that this lower bound is order optimal in m and n by presenting a distributed learning algorithm, called Multi-Resolution Estimator for Non-Convex loss function (MRE-NC), whose expected loss matches the lower bound for large mn up to polylogarithmic factors.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 63 references that are in the map. First posted on arXiv 19 Aug 2021.

Builds on

29 of 63 references.

References · 29

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  5. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  6. 2021Model-Contrastive Federated Learningcited by 762
  7. 2021Federated Learning on Non-IID Data Silos: An Experimental Studycited by 566
  8. 2020An Efficient Framework for Clustered Federated Learningcited by 505
  9. 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 451
  10. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
  11. 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 408
  12. 2021Data-Free Knowledge Distillation for Heterogeneous Federated Learningcited by 380
17 more
  1. 2018Scalable Private Learning with PATEcited by 266
  2. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 188
  3. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  4. 2020Privacy and Robustness in Federated Learning: Attacks and Defensescited by 163
  5. 2018Expanding the Reach of Federated Learning by Reducing Client Resource Requirementscited by 162
  6. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 115
  7. 2020Distilled One-Shot Federated Learningcited by 108
  8. 2021PPFL: Privacy-preserving Federated Learning with Trusted Execution Environmentscited by 93
  9. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 91
  10. 20211-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speedcited by 74
  11. 2018Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applicationscited by 67
  12. 2017DeepSecure: Scalable Provably-Secure Deep Learningcited by 48
  13. 20211-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speedcited by 24
  14. 2019One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Themcited by 23
  15. 2014High-Performance Distributed ML at Scale through Parameter Server Consistency Modelscited by 10
  16. 2019Secure Computation for Machine Learning With SPDZcited by 5
  17. 2019Order Optimal One-Shot Distributed Learningcited by 4

Built on by

Not cited yet.