mlsanityData to 7 Oct 2026

Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise

arXiv 2306.00673 ↗First posted 1 Jun 2023cs.DS cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

The concept class of low-degree polynomial threshold functions (PTFs) plays a fundamental role in machine learning. In this paper, we study PAC learning of K-sparse degree-d PTFs on ℝn, where any such concept depends only on K out of n attributes of the input. 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(fracK4dε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. Prior to this work, attribute-efficient robust algorithms are established only for the special case of sparse homogeneous halfspaces. Our key ingredients are: 1) a structural result that translates the attribute sparsity to a sparsity pattern of the Chow vector under the basis of Hermite polynomials, and 2) a novel attribute-efficient robust Chow vector estimation algorithm which uses exclusively a restricted Frobenius norm to either certify a good approximation or to validate a sparsity-induced degree-2d polynomial as a filter to detect corrupted samples.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 22 of its 76 references that are in the map. First posted on arXiv 1 Jun 2023.

Builds on

22 of 76 references.

References · 22

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  6. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  7. 2013Phase Retrieval using Alternating Minimizationcited by 58
  8. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  9. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  10. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  11. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  12. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
10 more
  1. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  2. 2016A Tight Bound of Hard Thresholdingcited by 16
  3. 2018Efficient active learning of sparse halfspacescited by 13
  4. 2020Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerancecited by 12
  5. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  6. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  7. 2022List-Decodable Sparse Mean Estimationcited by 11
  8. 2020Efficient PAC Learning from the Crowd with Pairwise Comparisonscited by 7
  9. 2021Semi-verified PAC Learning from the Crowdcited by 4
  10. 2020One-Bit Compressed Sensing via One-Shot Hard Thresholdingcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 2.

3 papers.

  1. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  2. 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifierscited by 1
  3. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0