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].
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
Authors: Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
NeurIPS 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on Lp perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the L1 perturbations case is provably computationally harder than the case 2 p < 1. |
| Researcher Affiliation | Collaboration | Ilias Diakonikolas University of Wisconsin, Madison EMAIL Daniel M. Kane University of California, San Diego EMAIL Pasin Manurangsi Google Research, Mountain View EMAIL |
| Pseudocode | Yes | Figure 1: Hardness Reduction from Label Cover to L1-margin Halfspace Learning. Here we use ei to denote the i-th vector in the standard basis (i.e. the vector with value one in the i-th coordinate and zero in the remaining coordinates). Furthermore, we extend this notation and use e S, for a set S of coordinates, to denote the indicator vector for S, i.e. e S = P i2S ei. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity and algorithms. It does not conduct empirical experiments with real-world datasets, nor does it specify any publicly available datasets for training purposes. It refers to theoretical 'distributions' and 'multisets of samples'. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments that would involve training, validation, or test dataset splits. Therefore, no specific dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and computational complexity analysis. It does not conduct empirical experiments, and therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and discusses algorithms and complexity bounds. It does not mention any specific software or library dependencies with version numbers, as there are no empirical experiments described that would require them. |
| Experiment Setup | No | The paper is theoretical and presents algorithms and complexity analysis rather than empirical experiments. No details regarding experimental setup, such as hyperparameters or training configurations, are provided. |