mlsanityData to 7 Oct 2026

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

arXiv 2604.26446 ↗First posted 29 Apr 2026cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

18 of 41 references.

References · 18

  1. 2017Counterfactual Fairnesscited by 802
  2. 2018A Reductions Approach to Fair Classificationcited by 585
  3. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 381
  4. 2018Fairness Through Computationally-Bounded Awarenesscited by 55
  5. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  6. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  7. 2020Metric-Free Individual Fairness in Online Learningcited by 30
  8. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  9. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  10. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  11. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  12. 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
6 more
  1. 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
  2. 2014Distribution-Independent Reliable Learningcited by 6
  3. 2022Individually Fair Learning with One-Sided Feedbackcited by 5
  4. 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
  5. 2025Distribution-Specific Agnostic Conditional Classification With Halfspacescited by 2
  6. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1

Built on by

Not cited yet.