On the sample complexity of adversarial multi-source PAC learning
N.H. Konstantinov, E. Frantar, D.-A. Alistarh, C. Lampert, ArXiv (n.d.).
Download
No fulltext has been uploaded. References only!
Preprint
| Submitted
| English
Author
Department
Abstract
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.
Publishing Year
Date Published
2020-02-24
Journal Title
arXiv
Acknowledged SSUs
Article Number
2002.10384
Page
2002.10384
IST-REx-ID
Cite this
Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity of adversarial multi-source PAC learning. arXiv.
Konstantinov, N. H., Frantar, E., Alistarh, D.-A., & Lampert, C. (n.d.). On the sample complexity of adversarial multi-source PAC learning. arXiv.
Konstantinov, Nikola H, Elias Frantar, Dan-Adrian Alistarh, and Christoph Lampert. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” ArXiv, n.d.
N. H. Konstantinov, E. Frantar, D.-A. Alistarh, and C. Lampert, “On the sample complexity of adversarial multi-source PAC learning,” arXiv. .
Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity of adversarial multi-source PAC learning. arXiv, 2002.10384.
Konstantinov, Nikola H., et al. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” ArXiv, 2002.10384.
Export
Marked PublicationsOpen Data IST Research Explorer
Sources
arXiv 2002.10384