On the Sample Complexity of Adversarial Multi-Source PAC Learning
Authors: Nikola Konstantinov, Elias Frantar, Dan Alistarh, Christoph Lampert
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. In this work, we study the question of robust learning in the multi-source case... Specifically, our main result is an upper bound on the sample complexity of adversarial multi-source learning, that holds as long as less than half of sources are manipulated (Theorem 1). Besides our main result we prove two additional theorems that shed light on the difficulty of adversarial multi-source learning. |
| Researcher Affiliation | Academia | 1Institute of Science and Technology Austria, Klosterneuburg, Austria 2Vienna University of Technology, Vienna, Austria. |
| Pseudocode | Yes | Algorithm 1 input Datasets S1, . . . , SN Initialize T = {} // trusted sources for i = 1, . . . , N do if d H Si, Sj s m, δ 2N , Si + s m, δ 2N , Sj , for at least N 2 values of j = i, then T = T {i} end if end for output S i T Si // all data of trusted sources |
| Open Source Code | No | The paper does not provide any links to open-source code or explicitly state that code for the described methodology is available. |
| Open Datasets | No | This is a theoretical paper that defines concepts like 'datasets' and 'samples' abstractly for theoretical analysis. It does not describe practical experiments using specific, publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper and does not describe experimental setup with dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper focusing on mathematical proofs and algorithms. It does not describe any computational experiments or specify hardware used. |
| Software Dependencies | No | This is a theoretical paper focusing on mathematical proofs and algorithms. It does not describe any computational experiments or specify software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that does not include practical experimental setup details, hyperparameters, or training configurations. |