# Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 26 May 2026.

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

- [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)
- [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)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)
- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Agnostic learning in (almost) optimal time via Gaussian surface area](https://mlsanity.com/paper/2603.06027/) (2026)
- [Learning Functions of Halfspaces](https://mlsanity.com/paper/2603.08700/) (2026)

## Abstract (arXiv)

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over ℝd × ± 1 whose marginal on ℝd is Gaussian, the goal is to output a hypothesis from a target class F whose 0-1 loss is within ε of that of the best classifier in F. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces under Gaussian marginals. Our algorithm runs in time dO(K2 log(1/ε)/ε2) + (K/ε)^O(K3/ε2.5). Prior to our work, the only known algorithm for K ≥ 2 was brute-force search, with run-time exponential in d. Moreover, the dependence of our run-time on the dimension d matches that of the best known improper learning algorithm, namely d^widetildeO(K2/ε2). For the special case of a single halfspace (K=1), the best previous run-time was dO(1/ε4) + (1/ε)O(1/ε6). Our algorithm improves this to dO(1/ε2) + (1/ε)^O(1/ε2.5). Once again, the dependence on d matches that of the best known improper algorithm, namely dO(1/ε2). Furthermore, the dependence of our run-time on the dimension d is essentially optimal in the statistical query model.