skip to main content

Rigorous Systems Research Group (RSRG) Seminar

Thursday, January 24, 2019
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Decentralized Statistical Learning in Adversarial Environments: Byzantine Gradient Descent
Lili Su, Postdoctoral Scholar, Electrical Engineering and Computer Science, Massachusetts Institute of Technology,

We assume in each communication round, up to $q$ ($q \not=0$) out of the $m$ workers suffer Byzantine faults. Each worker keeps a local sample of size $n$ (which can possibly be small) and the total sample size is $N=nm$. We propose two secured variants of the gradient descent method with different robust gradient aggregation rules.

The first variant is based on the simple geometric median of means.  We show that the estimation error converges to $O(\sqrt{qd/N})$, where $d$ is the model dimension.

The second variant is based on an iterative filtering procedure. We show that the estimation error converges to $O(\sqrt{q/N} + \sqrt{d/N})$. As long as $q=O(d)$, our proposed algorithm achieves the optimal error rate $O(\sqrt{d/N})$ in the fault-free environments. 

Both of these variants converge exponentially fast in rounds. A key challenge arises in the analysis is that Byzantine faults create arbitrary and unstructured dependency among the iterations and the aggregated gradients. To handle this dependency issue, we prove that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function.

For more information, please visit Seminar & Events.