On the sample complexity of adversarial multi-source PAC learning

Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. 2020. On the sample complexity of adversarial multi-source PAC learning. Proceedings of the 37th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 119, 5416–5425.

Download
OA 2020_PMLR_Konstantinov.pdf 281.29 KB
Conference Paper | Published | English
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-07-12
Proceedings Title
Proceedings of the 37th International Conference on Machine Learning
Acknowledgement
Dan Alistarh is supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing (SciComp).
Acknowledged SSUs
Volume
119
Page
5416-5425
Conference
ICML: International Conference on Machine Learning
Conference Location
Online
Conference Date
2020-07-12 – 2020-07-18
IST-REx-ID

Cite this

Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity of adversarial multi-source PAC learning. In: Proceedings of the 37th International Conference on Machine Learning. Vol 119. ML Research Press; 2020:5416-5425.
Konstantinov, N. H., Frantar, E., Alistarh, D.-A., & Lampert, C. (2020). On the sample complexity of adversarial multi-source PAC learning. In Proceedings of the 37th International Conference on Machine Learning (Vol. 119, pp. 5416–5425). Online: ML Research Press.
Konstantinov, Nikola H, Elias Frantar, Dan-Adrian Alistarh, and Christoph Lampert. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” In Proceedings of the 37th International Conference on Machine Learning, 119:5416–25. ML Research Press, 2020.
N. H. Konstantinov, E. Frantar, D.-A. Alistarh, and C. Lampert, “On the sample complexity of adversarial multi-source PAC learning,” in Proceedings of the 37th International Conference on Machine Learning, Online, 2020, vol. 119, pp. 5416–5425.
Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. 2020. On the sample complexity of adversarial multi-source PAC learning. Proceedings of the 37th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 119, 5416–5425.
Konstantinov, Nikola H., et al. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” Proceedings of the 37th International Conference on Machine Learning, vol. 119, ML Research Press, 2020, pp. 5416–25.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2021-02-15
MD5 Checksum
cc755d0054bc4b2be778ea7aa7884d2f


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 2002.10384

Search this title in

Google Scholar