Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems

Stefan Tiegel

Abstract

We show hardness of improperly learning halfspaces in the agnostic model, both in the distribution-independent as well as the distribution-specific setting, based on the assumption that worst-case lattice problems, such as GapSVP or SIVP, are hard. In particular, we show that under this assumption there is no efficient algorithm that outputs any binary hypothesis, not necessarily a halfspace, achieving misclassification error better than $1/2 - \gamma$ even if the optimal misclassification error is as small as $\delta$. Here, $\gamma$ can be smaller than the inverse of any polynomial in the dimension and $\delta$ as small as $\exp(-\Omega(\log^{1-c}(d)))$, where $0 < c < 1$ is an arbitrary constant and $d$ is the dimension. For the distribution-specific setting, we show that if the marginal distribution is standard Gaussian, for any $\beta > 0$ learning halfspaces up to error $OPT_{LTF} + \epsilon$ takes time at least $d^{\tilde{\Omega}(1/\epsilon^{2-\beta})}$ under the same hardness assumptions. Similarly, we show that learning degree-$\ell$ polynomial threshold functions up to error $OPT_{PTF_\ell} + \epsilon$ takes time at least $d^{\tilde{\Omega}(\ell^{2-\beta}/\epsilon^{2-\beta})}$. Our work gives the first hardness results basing these fundamental learning problems on worst-case complexity assumptions, qualitatively matching algorithmic guarantees and nearly recovering known lower bounds based on non-worst-case assumptions.

Introduction

In machine learning theory, the problem of learning halfspaces (Linear Threshold Functions, or LTFs) is foundational. In the "agnostic" model, we acknowledge that data may be noisy or not perfectly separable by a linear boundary. The goal is to find a hypothesis that performs nearly as well as the best possible halfspace in the class. While the hardness of this task has long been suspected, previous proofs have largely relied on average-case complexity assumptions—such as variants of the random 3SAT problem—or were restricted to specific computational models like Statistical Query (SQ) learning.

This paper bridges a critical gap by basing the hardness of agnostically learning halfspaces on worst-case lattice problems, such as the Shortest Independent Vector Problem (SIVP). These problems are considered the "gold standard" of cryptographic assumptions and serve as the bedrock for post-quantum cryptography. By establishing this connection, the research implies that an efficient agnostic learner for halfspaces could potentially be used to break modern cryptographic systems.

The Agnostic Learning Framework

The study focuses on improper learning, a robust framework where the learner is allowed to output any binary hypothesis, not necessarily a halfspace. Ruling out improper learners provides a much stronger hardness result than restricting the learner to the same class as the target (proper learning).

We consider two primary settings:

  1. Distribution-Independent: The algorithm must perform well regardless of the underlying data distribution.
  2. Distribution-Specific: The algorithm is evaluated on data where the marginal distribution is a standard Gaussian $\mathcal{N}(0, I)$.

Methodology: Reductions from Lattice Problems

The core of the proof involves a reduction from the Continuous Learning with Errors (CLWE) problem. CLWE is a continuous analogue of the Learning with Errors (LWE) problem, where the objective is to distinguish a specific periodic distribution from a standard Gaussian.

The "Pancake" Distribution

The technical heart of the reduction is the use of Homogeneous CLWE (hCLWE). This variant constructs a distribution that resembles a mixture of many thin "pancakes"—narrow Gaussians—arranged periodically along a hidden direction. To an observer without knowledge of this secret direction, the distribution is statistically indistinguishable from a standard Gaussian. This structure is uniquely suited to frustrate learners, as any linear boundary (halfspace) will struggle to capture the periodic nature of the labels without exponential time or the secret key.

Key Technical Tools

  • Rejection Sampling: To prove hardness for standard Gaussian marginals, the author employs rejection sampling to transform CLWE samples into a hard learning instance where the input features follow a perfect Gaussian distribution.
  • Veronese Mapping: For the distribution-independent setting, the author uses a feature mapping to demonstrate that learning high-degree Polynomial Threshold Functions (PTFs) in low dimensions is equivalent to learning halfspaces in high dimensions.

Main Results

1. Distribution-Independent Hardness

Under the assumption that worst-case lattice problems are hard, no polynomial-time algorithm can achieve a misclassification error better than $1/2 - \gamma$ (essentially random guessing), even if the optimal error $\delta$ is extremely small (exponentially small in some regimes). This holds even for improper learners.

2. Gaussian Marginal Hardness

For the standard Gaussian distribution, the paper proves that learning a halfspace to within $\epsilon$ of the optimal error requires $d^{\tilde{\Omega}(1/\epsilon^{2-\beta})}$ time. This result is particularly significant because it qualitatively matches the performance of known algorithms, such as $L_1$-regression, suggesting that current algorithmic bounds are nearly optimal.

3. Polynomial Threshold Functions (PTFs)

The hardness results extend to degree-$\ell$ PTFs, showing that achieving an error of $OPT + \epsilon$ requires $d^{\tilde{\Omega}(\ell^{2-\beta}/\epsilon^{2-\beta})}$ time. This establishes a fundamental barrier for learning more complex decision boundaries.

Conclusion and Future Work

This work provides the first hardness results for agnostic learning based on worst-case complexity. It demonstrates that the difficulty of learning halfspaces is not merely a limitation of current algorithmic techniques but is tied to deep complexity-theoretic barriers.

Future research may look to close the remaining gaps, such as showing hardness when the optimal error (OPT) is a small constant (e.g., 1% or 10%) rather than approaching 1/2. Additionally, the CLWE framework introduced here may prove useful in establishing hardness for other fundamental classes, such as ReLUs or intersections of halfspaces.

Summary updated

Abstract

We show hardness of improperly learning halfspaces in the agnostic model, both in the distribution-independent as well as the distribution-specific setting, based on the assumption that worst-case lattice problems, such as GapSVP or SIVP, are hard. In particular, we show that under this assumption there is no efficient algorithm that outputs any binary hypothesis, not necessarily a halfspace, achieving misclassfication error better than $\frac 1 2 - \gamma$ even if the optimal misclassification error is as small is as small as $\delta$. Here, $\gamma$ can be smaller than the inverse of any polynomial in the dimension and $\delta$ as small as $exp(-\Omega(\log^{1-c}(d)))$, where $0 < c < 1$ is an arbitrary constant and $d$ is the dimension. For the distribution-specific setting, we show that if the marginal distribution is standard Gaussian, for any $\beta > 0$ learning halfspaces up to error $OPT_{LTF} + \epsilon$ takes time at least $d^{\tilde{\Omega}(1/\epsilon^{2-\beta})}$ under the same hardness assumptions. Similarly, we show that learning degree-$\ell$ polynomial threshold functions up to error $OPT_{{PTF}_\ell} + \epsilon$ takes time at least $d^{\tilde{\Omega}(\ell^{2-\beta}/\epsilon^{2-\beta})}$. $OPT_{LTF}$ and $OPT_{{PTF}_\ell}$ denote the best error achievable by any halfspace or polynomial threshold function, respectively. Our lower bounds qualitively match algorithmic guarantees and (nearly) recover known lower bounds based on non-worst-case assumptions. Previously, such hardness results [Daniely16, DKPZ21] were based on average-case complexity assumptions or restricted to the statistical query model. Our work gives the first hardness results basing these fundamental learning problems on worst-case complexity assumptions. It is inspired by a sequence of recent works showing hardness of learning well-separated Gaussian mixtures based on worst-case lattice problems.
BibTeX
@inproceedings{tiegel2023hardness,
  author = {Stefan Tiegel},
  title = {{Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems}},
  booktitle = {Conference on Learning Theory},
  year = {2023},
  url = {https://openreview.net/forum?id=8qeZjgT0Ww},
}
Figure