Do Outliers Ruin Collaboration?
This addresses robust collaborative learning for scenarios with adversarial data sources, though it is incremental as it builds on existing overhead analysis.
The paper tackles the problem of learning a binary classifier from multiple data sources with adversarial outliers, achieving an overhead of O(ηn + ln n) that is proven worst-case optimal.
We consider the problem of learning a binary classifier from $n$ different data sources, among which at most an $η$ fraction are adversarial. The overhead is defined as the ratio between the sample complexity of learning in this setting and that of learning the same hypothesis class on a single data distribution. We present an algorithm that achieves an $O(ηn + \ln n)$ overhead, which is proved to be worst-case optimal. We also discuss the potential challenges to the design of a computationally efficient learning algorithm with a small overhead.