Rigorous Systems Research Group (RSRG) Seminar

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.