# Reliable Learning of Halfspaces under Gaussian Marginals

arXiv: https://arxiv.org/abs/2411.11238 · HTML: https://mlsanity.com/paper/2411.11238/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Efficient Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2102.07802/) (2021)
- [A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2010.01705/) (2020)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Distribution-Independent Reliable Learning](https://mlsanity.com/paper/1402.5164/) (2014)

## Built on by (most cited first, 1 of 1)

- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)

## 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.