Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
Authors: Shiwei Zeng, Jie Shen
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is a new algorithm that runs in time (nd/ϵ)O(d) and under the Gaussian marginal distribution, PAC learns the class up to error rate ϵ with O( K4d ϵ2d log5d n) samples even when an η O(ϵd) fraction of them are corrupted by the nasty noise of Bshouty et al. (2002), possibly the strongest corruption model. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stevens Institute of Technology, Hoboken, New Jersey, USA. |
| Pseudocode | Yes | Algorithm 1 Main Algorithm: Attribute-Efficient Robust Chow Vector Estimator Algorithm 2 SPARSEFILTER |
| Open Source Code | No | The paper does not mention providing open-source code for its methodology. It refers to 'open-source code' in related works section regarding prior research, but not its own contribution. |
| Open Datasets | No | The paper is theoretical and does not describe actual experimental training or refer to specific datasets for this purpose. |
| Dataset Splits | No | The paper is theoretical and does not describe actual experimental validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments or specific software implementations with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |