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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Authors: Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give the first polynomial-time algorithm for the testable learning of halfspaces in the presence of adversarial label noise under the Gaussian distribution. |
| Researcher Affiliation | Academia | Ilias Diakonikolas University of Wisconsin, Madison EMAIL Daniel M. Kane University of California, San Diego EMAIL Vasilis Kontonis University of Texas, Austin mailto:EMAIL Sihan Liu University of California, San Diego EMAIL Nikos Zarifis University of Wisconsin, Madison EMAIL |
| Pseudocode | Yes | Input: Sample access to a distribution Dx over Rd; tolerance parameter η > 0; unit vector v Rd; failure probability τ (0, 1). Output: Certifies that for all unit vectors w such that w v 2 η it holds that Prx Dx[sign(v x) = sign(w x)] Cη, for some absolute constant C > 1, or reports that Dx is not N(0, I). 1. Set B = p log(1/η)/η . 2. Let e D be the empirical distribution obtained by drawing poly(d, 1/η) log(1/τ) samples from Dx. 3. For integers B 1 i B, define Ei to be the event that {v x [iη, (i + 1)η]} and EB+1 to be the event that {|v x| p 4. Verify that PB+1 i= B 1 Pr N(0,I) [Ei] Pr e D [Ei] η. 5. Let Si the distribution of e D conditioned on Ei and S i be Si projected on the subspace orthogonal to v. 6. For each i, verify that S i has bounded covariance, i.e., check that Ex S i [xx ] 2I . Algorithm 1: Wedge-Bound |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the methodology described in this paper is openly available. |
| Open Datasets | No | The paper is theoretical and does not use datasets for empirical evaluation. It assumes a Gaussian distribution as a theoretical model, but no concrete dataset is specified or made available. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation or data splitting for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |