mlsanityData to 7 Oct 2026

Reliable Learning of Halfspaces under Gaussian Marginals

arXiv 2411.11238 ↗First posted 18 Nov 2024cs.LG cs.DS stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is costlier than the others. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on ℝd with sample and computational complexity d^O(log (min1/α, 1/ε))min (2^log(1/ε)O(log (1/α)),2poly(1/ε));, where ε is the excess error and α is the bias of the optimal halfspace. We complement our upper bound with a Statistical Query lower bound suggesting that the dOmega(log (1/α)) dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 20 of its 50 references that are in the map. First posted on arXiv 18 Nov 2024.

Builds on

20 of 50 references.

References · 20

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  4. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  5. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  6. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  7. 2020Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examplescited by 44
  8. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  9. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  10. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  11. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  12. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
8 more
  1. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  2. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  3. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  4. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  5. 2021Efficient Learning with Arbitrary Covariate Shiftcited by 15
  6. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  7. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  8. 2014Distribution-Independent Reliable Learningcited by 6

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Smoothed Analysis of Learning from Positive Samplescited by 2