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

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

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Model-Contrastive Federated Learning](https://mlsanity.com/paper/2103.16257/) (2021)
- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [An Efficient Framework for Clustered Federated Learning](https://mlsanity.com/paper/2006.04088/) (2020)
- [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Data-Free Knowledge Distillation for Heterogeneous Federated Learning](https://mlsanity.com/paper/2105.10056/) (2021)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Privacy and Robustness in Federated Learning: Attacks and Defenses](https://mlsanity.com/paper/2012.06337/) (2020)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Distilled One-Shot Federated Learning](https://mlsanity.com/paper/2009.07999/) (2020)
- [PPFL: Privacy-preserving Federated Learning with Trusted Execution Environments](https://mlsanity.com/paper/2104.14380/) (2021)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications](https://mlsanity.com/paper/1801.03239/) (2018)
- [DeepSecure: Scalable Provably-Secure Deep Learning](https://mlsanity.com/paper/1705.08963/) (2017)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them](https://mlsanity.com/paper/1905.04634/) (2019)
- [High-Performance Distributed ML at Scale through Parameter Server Consistency Models](https://mlsanity.com/paper/1410.8043/) (2014)
- [Secure Computation for Machine Learning With SPDZ](https://mlsanity.com/paper/1901.00329/) (2019)
- [Order Optimal One-Shot Distributed Learning](https://mlsanity.com/paper/1911.00731/) (2019)

## 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.