# Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 29 Apr 2026.

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

- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [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)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins](https://mlsanity.com/paper/2010.00539/) (2020)
- [Distribution-Independent Reliable Learning](https://mlsanity.com/paper/1402.5164/) (2014)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [Distribution-Specific Agnostic Conditional Classification With Halfspaces](https://mlsanity.com/paper/2502.00172/) (2025)
- [Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution](https://mlsanity.com/paper/2509.15592/) (2025)

## Abstract (arXiv)

We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples (x, y) drawn from an unknown distribution on ℝd×-1, +1, whose marginal distribution on x is standard Gaussian and on y is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.