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

Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis

This paper, titled "Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals," represents a significant step in computational learning theory. It essentially "closes the book" on a long-standing complexity gap regarding one of the most fundamental geometric concept classes in machine learning.

TL;DR

The authors prove that learning intersections of $k$ halfspaces is fundamentally hard in the Statistical Query (SQ) model, establishing a lower bound of $n^{\Omega(\log k)}$. This result is nearly optimal, as it matches the best-known upper bounds, proving that existing algorithms are essentially as efficient as theoretically possible under Gaussian distributions.

What Problem Does This Paper Address?

The paper focuses on intersections of halfspaces, a concept class where a data point is classified as "positive" only if it falls on the correct side of $k$ different linear boundaries. This is a natural generalization of a single linear classifier (a halfspace) and is a building block for more complex models like neural networks.

The authors study this in the agnostic learning model. Unlike "realizable" learning, where we assume a perfect classifier exists in our class, agnostic learning is more realistic: the data might be noisy, and we just want to find a classifier that performs nearly as well as the best possible one in the class.

Specifically, they work within the Statistical Query (SQ) model. In this framework, an algorithm doesn't see individual data points. Instead, it asks "queries" about the statistical properties of the dataset (e.g., "What is the average value of this function over the data?"). Most standard machine learning algorithms (like gradient descent or PCA) can be implemented as SQ algorithms. Proving a lower bound in the SQ model is a strong way to show that a problem is computationally difficult.

Methods

The authors bridge a gap between two previous approaches to proving hardness:

  1. Resilience and $L^1$ Approximation: They leverage a known equivalence: a function is hard to learn if it is "resilient" (uncorrelated with all low-degree polynomials) or, equivalently, if it cannot be well-approximated by low-degree polynomials in the $L^1$ norm.
  2. Hybrid Techniques: They combine the "blueprint" for Boolean functions (Dachman-Soled et al., 2014) with newer techniques for Gaussian distributions (Diakonikolas et al., 2021b).

Key Technical Innovations: * The Cube Function: For small $k$, they directly analyze the Hermite coefficients of a $k$-dimensional cube. They use an iterative "thresholding transform" to construct a bounded function that is orthogonal to low-degree polynomials, proving the cube is "approximately resilient." * Weak Learning Contradiction: For larger $k$, they use a clever contradiction. They show that if a better algorithm existed, it would violate known lower bounds for "weak learning" (doing just slightly better than random guessing). * Handling Error ($\epsilon$): To account for the desired error level, they augment the intersection of $k$ halfspaces with an additional halfspace in a new dimension, allowing them to incorporate lower bounds for single halfspaces that depend on $1/\epsilon^2$.

Datasets

As a theoretical work in computational complexity, this paper does not use empirical datasets like ImageNet or CIFAR. Instead, it uses a rigorous mathematical framework:

  • Gaussian Marginals: The data points are assumed to be drawn from a standard $n$-dimensional Gaussian distribution ($N(0, I_n)$). This is a standard "nice" distribution used to study the inherent complexity of learning problems.

Key Insights and Ideas

  • Closing the Gap: Previously, there was a square-root gap in the exponent between the best algorithm ($n^{\log k}$) and the best lower bound ($n^{\sqrt{\log k}}$). This paper removes that square root, showing the $\log k$ complexity is intrinsic.
  • The Hardness of "Cubes": A surprising insight is that the hardness of learning any intersection of $k$ halfspaces is already present in the very simple case of a $k$-dimensional cube.
  • Universality of the Approach: The techniques aren't just for halfspaces. The authors show their method also provides near-optimal lower bounds for:
  • Convex Subspace Juntas: Functions that depend on a low-dimensional convex set.
  • Bounded Gaussian Surface Area: A broad class of geometric sets.

Key Results

  • The Main Bound: Any SQ algorithm learning an intersection of $k$ halfspaces to a constant excess error requires either an exponential number of queries ($2^{n^{\Omega(1)}}$) or queries with extremely high precision (tolerance $n^{-\Omega(\log k)}$).
  • Optimality: This matches the $n^{O(\log k)}$ upper bound from Klivans et al. (2008), meaning we now know the "true" complexity of this problem in the SQ model.
  • Subconstant Error: When the error $\epsilon$ is small, the complexity increases to $n^{-\Omega(\log k + 1/\epsilon^2)}$, showing exactly how the problem gets harder as you demand more precision.

Limitations and Future Work

  • The SQ Model Constraint: While the SQ model covers most practical algorithms, it does not cover all possible computation. There are "non-SQ" algorithms (like those using Gaussian elimination for parity learning) that could theoretically bypass these bounds, though none are currently known for this specific problem.
  • Distribution Specificity: The results are specific to Gaussian distributions. While Gaussians are a standard benchmark, the complexity might change under different "nice" distributions (like the uniform distribution on a cube).
  • Computational vs. Sample Complexity: This paper focuses on computational hardness (how much work the algorithm does). A natural next step is exploring if these bounds hold for general (non-SQ) algorithms using only a limited number of samples.

Summary updated

Abstract

We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging \emph{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 $\mathbb{R}^n$ to constant excess error either must make queries of tolerance at most $n^{-\tilde{\Omega}(\sqrt{\log k})}$ or must make $2^{n^{\Omega(1)}}$ queries. We strengthen this result by improving the tolerance requirement to $n^{-\tilde{\Omega}(\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 $n^{O(\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).
BibTeX
@inproceedings{hsu2022near,
  author = {Daniel Hsu and Clayton Sanford and Rocco A. Servedio and Emmanouil-Vasileios Vlatakis-Gkaragkounis},
  title = {{Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals}},
  booktitle = {Conference on Learning Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=EPmILWEQkr},
}
Figure