# Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 59 references that are in the map.
- First posted on arXiv 10 Feb 2022.

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

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning](https://mlsanity.com/paper/2010.11925/) (2020)

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

- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging agnostic learning model. Recent work of Diakonikolas et al. (2021) shows that any Statistical Query (SQ) algorithm for agnostically learning the class of intersections of k halfspaces over ℝn to constant excess error either must make queries of tolerance at most n^-tildeOmega(√log k) or must make 2^nOmega(1) queries. We strengthen this result by improving the tolerance requirement to n^-tildeOmega(log k). This lower bound is essentially best possible since an SQ algorithm of Klivans et al. (2008) agnostically learns this class to any constant excess error using nO(log k) queries of tolerance n-O(log k). We prove two variants of our lower bound, each of which combines ingredients from Diakonikolas et al. (2021) with (an extension of) a different earlier approach for agnostic SQ lower bounds for the Boolean setting due to Dachman-Soled et al. (2014). Our approach also yields lower bounds for agnostically SQ learning the class of "convex subspace juntas" (studied by Vempala, 2010) and the class of sets with bounded Gaussian surface area; all of these lower bounds are nearly optimal since they essentially match known upper bounds from Klivans et al. (2008).