# Do Outliers Ruin Collaboration?

arXiv: https://arxiv.org/abs/1805.04720 · HTML: https://mlsanity.com/paper/1805.04720/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2018.

## Built on by (most cited first, 7 of 7)

- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithms](https://mlsanity.com/paper/2310.15330/) (2023)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)
- [GeoERM: Geometry-Aware Multi-Task Representation Learning on Riemannian Manifolds](https://mlsanity.com/paper/2505.02972/) (2025)

## Abstract (arXiv)

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.