The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This is because the heterogeneity model considered is too restrictive and does not cover basic learning tasks such as least-squares regression. We consider in this paper a more realistic heterogeneity model, namely (G,B)-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction 1/2. We also prove a new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for a robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.

在实际场景中，数据的异质性通常是规范，传统的学习误差下界对于异质性数据是不准确的。本文通过引入更现实的异质性模型(G,B)-梯度差异性，展示了这一模型覆盖了比现有理论更广泛的学习问题，并且证明了分布式学习算法的学习误差存在下界。我们推导了一个强鲁棒的分布式梯度下降算法的上界，并且通过实证分析表明了我们提出的分析方法能够减小理论和实践之间的差距。

鲁棒分布式学习：数据异构下的紧密误差界和破坏点