# Order Optimal One-Shot Distributed Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2019.

## Built on by (most cited first, 4 of 4)

- [FedDM: Iterative Distribution Matching for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2207.09653/) (2022)
- [Order Optimal Bounds for One-Shot Federated Learning over non-Convex Loss Functions](https://mlsanity.com/paper/2108.08677/) (2021)
- [On Collaboration in Distributed Parameter Estimation with Resource Constraints](https://mlsanity.com/paper/2307.06442/) (2023)
- [Distributed Continual Learning with CoCoA in High-dimensional Linear Regression](https://mlsanity.com/paper/2312.01795/) (2023)

## Abstract (arXiv)

We consider distributed statistical optimization in one-shot setting, where there are m machines each observing n i.i.d. samples. Based on its observed samples, each machine then sends an O(log(mn))-length message to a server, at which a parameter minimizing an expected loss is to be estimated. We propose an algorithm called Multi-Resolution Estimator (MRE) whose expected error is no larger than tildeObig(m^-1/max(d,2) n-1/2big), where d is the dimension of the parameter space. This error bound meets existing lower bounds up to poly-logarithmic factors, and is thereby order optimal. The expected error of MRE, unlike existing algorithms, tends to zero as the number of machines (m) goes to infinity, even when the number of samples per machine (n) remains upper bounded by a constant. This property of the MRE algorithm makes it applicable in new machine learning paradigms where m is much larger than n.