One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them
By Saber Salehkaleybar, Arsalan Sharifnassab, S. J. Golestani. 2019
40 citations recorded by the source corpus.
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 sends a $B$-bit-long message to a server. The server then collects messages from all machines, and estimates a parameter that minimizes an expected convex loss function. We investigate the impact of communication constraint, $B$, on the expected error and derive a tight lower bound on the error achievable by any algorithm. We then propose an estimator, which we call Multi-Resolution Estimator (MRE), whose expected error (when $B\ge\log mn$) meets the aforementioned lower bound up to poly-logarithmic factors, and is thereby order optimal. We also address the problem of learning under tiny communication budget, and present lower and upper error bounds when $B$ is a constant. 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$.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Arsalan Sharifnassab
- S. J. Golestani
- Saber Salehkaleybar
- Dapeng Oliver Wu
- Xiyao Ma
- Xiaolin Li
- Yanlin Zhou
- George Pu
Citations in the corpus
- Distilled One-Shot Federated Learning (2020, background): “Upper and lower bounds have been proven for one-shot distributed optimization, along with an order optimal algorithm [25, 28].”
- Order Optimal One-Shot Distributed Learning (2019, methodology): “In contrary, it was shown in Proposition 1 of [Salehkaleybar et al., 2019] that no estimator yields error better than a constant if n = 1 and the number of bits per transmission is a constant independent of m.”