# On the Sample Complexity of Adversarial Multi-Source PAC Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2020.

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

- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithms](https://mlsanity.com/paper/2310.15330/) (2023)
- [Incentivizing Honesty among Competitors in Collaborative Learning and Optimization](https://mlsanity.com/paper/2305.16272/) (2023)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation](https://mlsanity.com/paper/2405.02745/) (2024)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)
- [FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data](https://mlsanity.com/paper/2106.11732/) (2021)
- [GeoERM: Geometry-Aware Multi-Task Representation Learning on Riemannian Manifolds](https://mlsanity.com/paper/2505.02972/) (2025)
- [Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations](https://mlsanity.com/paper/2506.06613/) (2025)

## Abstract (arXiv)

We study the problem of learning from multiple untrusted data sources, a scenario of increasing practical relevance given the recent emergence of crowdsourcing and collaborative learning paradigms. Specifically, we analyze the situation in which a learning system obtains datasets from multiple sources, some of which might be biased or even adversarially perturbed. It is known that in the single-source case, an adversary with the power to corrupt a fixed fraction of the training data can prevent PAC-learnability, that is, even in the limit of infinitely much training data, no learning system can approach the optimal test error. In this work we show that, surprisingly, the same is not true in the multi-source setting, where the adversary can arbitrarily corrupt a fixed fraction of the data sources. Our main results are a generalization bound that provides finite-sample guarantees for this learning setting, as well as corresponding lower bounds. Besides establishing PAC-learnability our results also show that in a cooperative learning setting sharing data with other parties has provable benefits, even if some participants are malicious.