# Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 30 of 57)

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [Learning Linear Utility Functions From Pairwise Comparison Queries](https://mlsanity.com/paper/2405.02612/) (2024)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Learning ReLU networks to high uniform accuracy is intractable](https://mlsanity.com/paper/2205.13531/) (2022)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)

## Abstract (arXiv)

We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. In the former problem, given labeled examples (x, y) from an unknown distribution on ℝd ×  ± 1, whose marginal distribution on x is the standard Gaussian and the labels y can be arbitrary, the goal is to output a hypothesis with 0-1 loss OPT+ε, where OPT is the 0-1 loss of the best-fitting halfspace. In the latter problem, given labeled examples (x, y) from an unknown distribution on ℝd × ℝ, whose marginal distribution on x is the standard Gaussian and the labels y can be arbitrary, the goal is to output a hypothesis with square loss OPT+ε, where OPT is the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower bounds of dpoly(1/ε) for both of these problems. Our SQ lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.