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)- 梯度差异性，展示了这一模型覆盖了比现有理论更广泛的学习问题，并且证明了分布式学习算法的学习误差存在下界。我们推导了一个强鲁棒的分布式梯度下降算法的上界，并且通过实证分析表明了我们提出的分析方法能够减小理论和实践之间的差距。

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

Robust Distributed Learning: Tight Error Bounds and Breakdown Point  under Data Heterogeneity

We develop and analyze a general technique for learning with an unknown
distribution drift. Given a sequence of independent observations from the last
$T$ steps of a drifting distribution, our algorithm agnostically learns a
family of functions with respect to the current distribution at time $T$.
Unlike previous work, our technique does not require prior knowledge about the
magnitude of the drift. Instead, the algorithm adapts to the sample data.
Without explicitly estimating the drift, the algorithm learns a family of
functions with almost the same error as a learning algorithm that knows the
magnitude of the drift in advance. Furthermore, since our algorithm adapts to
the data, it can guarantee a better learning error than an algorithm that
relies on loose bounds on the drift.

我们开发和分析了一种普适技术，可以在未知分布漂移的情况下进行学习。给定一个来自漂移分布的最后 $T$ 步的独立观测序列，我们的算法在时刻 $T$ 对当前分布进行从容学习。与先前的工作不同，我们的技术不需要关于漂移幅度的先验知识，而是根据样本数据进行算法调整。我们的算法学习了一类函数，其误差几乎与预先了解漂移幅度的学习算法相同。此外，由于我们的算法适应数据，它可以保证比依赖漂移松限制的算法具有更好的学习误差。