Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
On the Hardness of Robust Classification
Authors: Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
JMLR 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study the feasibility of adversarially robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the distribution-free setting against an adversary who can perturb just a single input bit. We show, moreover, that the class of monotone conjunctions cannot be robustly learned under the uniform distribution against an adversary who can perturb ω(log n) input bits. However, we also show that if the adversary is restricted to perturbing O(log n) bits, then one can robustly learn the class of 1-decision lists (which subsumes monotone conjunctions) with respect to the class of log Lipschitz distributions. We then extend this result to show learnability of 2-decision lists and monotone k-decision lists in the same distributional and adversarial setting. Finally, we provide a simple proof of the computational hardness of robust learning on the boolean hypercube. |
| Researcher Affiliation | Academia | Pascale Gourdeau EMAIL Varun Kanade EMAIL Marta Kwiatkowska EMAIL James Worrell EMAIL Department of Computer Science, University of Oxford Parks Road Oxford, OX1 3QD UK |
| Pseudocode | No | The paper primarily focuses on theoretical analysis, presenting definitions, theorems, lemmas, and proofs. It references existing PAC-learning algorithms (e.g., Rivest (1987), Goldberg (2006)) but does not include any explicit pseudocode blocks or algorithms within its own methodology description. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to repositories or supplementary materials for code related to the described methodology. While it mentions a CC-BY 4.0 license, this pertains to the paper's content, not its implementation code. |
| Open Datasets | No | The paper is theoretical and explores concepts like 'input space is the boolean hypercube X = {0, 1}n' and 'α-log-Lipschitz distributions'. It does not use or refer to any specific, named empirical datasets for experimentation, and therefore provides no access information for any open datasets. |
| Dataset Splits | No | As a theoretical paper that does not perform experiments on specific datasets, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not describe any computational experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments that would necessitate specific software dependencies with version numbers. It references theoretical 'PAC-learning algorithms' but not concrete software implementations. |
| Experiment Setup | No | As a theoretical paper, it does not detail any experimental setup, hyperparameters, model initialization, or training configurations. The content is focused on mathematical proofs and theoretical concepts of learnability and hardness. |