Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Authors: Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | 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 ilias@cs.wisc.edu Daniel M. Kane University of California, San Diego dakane@ucsd.edu Vasilis Kontonis University of Texas, Austin mailto:vasilis@cs.utexas.edu Sihan Liu University of California, San Diego il046@ucsd.edu Nikos Zarifis University of Wisconsin, Madison zarifis@wisc.edu |
| 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. |