The error rate of learning halfspaces using Kernel-SVMs

Amit Daniely, Nati Linial, Shai Shalev-ShwartzarXiv 2012 · arXiv · OpenReview

Abstract Many popular learning algorithms, including Kernel SVMs, Kernel Ridge Regression, and Fourier-transform based methods, operate by reducing learning problems to convex optimization over a vector space of functions. These "generalized linear methods" represent the state-of-the-art for central problems such as learning halfspaces and DNFs. However, the fundamental limits of these algorithms have remained largely uncharacterized. We study the performance of this approach in the context of agnostically and improperly learning halfspaces with margin $\gamma$. We demonstrate that for any efficient algorithm in this family, the approximation ratio must be at least $\Omega\left(\frac{1/\gamma}{\text{poly}(\log(1/\gamma))}\right)$. This result essentially matches the best known upper bound, establishing a "hard ceiling" on the power of convex surrogate-based learning for this task.

Introduction

Learning a halfspace—a linear classifier that partitions data into two categories—is a foundational problem in machine learning. While this task is computationally simple when data is perfectly separable by a margin $\gamma$, real-world data is rarely so clean. In the "agnostic" setting, where noise is present and no perfect linear separator exists, finding the optimal classifier is NP-hard.

To circumvent this hardness, practitioners typically turn to generalized linear methods. These methods map input data into a high-dimensional feature space (often via a kernel) and solve a convex optimization problem, such as minimizing Hinge Loss or Squared Loss. Despite their ubiquity, there has been a significant gap in our theoretical understanding: can these efficient convex approximations ever truly approach the performance of the optimal (but hard to find) linear classifier?

The Problem: Agnostic Learning with Margin

Let $\mathcal{D}$ be a distribution over labeled examples. We define the $\gamma$-margin error of a hyperplane $h$ as the probability that an example falls on the wrong side of $h$ or within a distance $\le \gamma$ from it. We denote the error of the best possible hyperplane as $\mathrm{Err}_\gamma(\mathcal{D})$.

An $\alpha(\gamma)$-approximation algorithm is one that, given $\gamma$ and $\epsilon$, outputs a classifier with an error rate $\le \alpha(\gamma)\mathrm{Err}_\gamma(\mathcal{D}) + \epsilon$. An algorithm is considered efficient if its sample complexity and runtime are polynomial in $1/\gamma$ and $1/\epsilon$. Prior to this work, the best known efficient algorithm achieved an approximation ratio of $O\left(\frac{1/\gamma}{\sqrt{\log(1/\gamma)}}\right)$.

Methodology

This research establishes lower bounds through a sophisticated mathematical framework that constrains the behavior of any learner relying on inner products and convex losses.

1. Dimensionality and Norm Constraints

Using a variation of John’s Lemma, the authors first prove that for any learner using a polynomial number of samples, the complexity of the resulting classifier (specifically its norm in the Reproducing Kernel Hilbert Space) must be bounded. This implies that "efficient" learners cannot use arbitrarily complex functions to fit the noise.

2. Adversarial Distributions

The core of the proof involves constructing a "nasty" one-dimensional distribution. In this distribution, any low-degree polynomial or function with a small norm is forced to output nearly identical values for points at $+\gamma$ and $-\gamma$. This makes it impossible for the algorithm to distinguish between the two classes effectively without a massive increase in complexity.

3. Harmonic Analysis on the Sphere

To extend the 1D result to high-dimensional space, the authors employ harmonic analysis, specifically utilizing Legendre and Chebyshev polynomials. They show that on a high-dimensional unit sphere $S^{d-1}$, the behavior of a kernel-based learner is fundamentally constrained by the same polynomial limitations identified in the 1D case.

4. Symmetrization

Finally, a new symmetrization technique is introduced. This shows that if a kernel-based algorithm is designed to be robust across all distributions, it must necessarily fail on the specifically constructed adversarial distributions. The geometric nature of kernels—their reliance on inner products—becomes their Achilles' heel in the face of symmetrized noise.

Key Results

The paper establishes two major lower bounds for the approximation ratio $\alpha(\gamma)$:

  • Kernel-based Learners: Every efficient kernel algorithm must have an approximation ratio $\geq \Omega\left(\frac{1/\gamma}{\text{poly}(\log(1/\gamma))}\right)$. This effectively closes the gap between theory and practice, as it matches the best-known upper bounds.
  • Finite-Dimensional Learners: For algorithms mapping to a fixed $m$-dimensional space, the lower bound is $\geq \Omega\left(\frac{1/\sqrt{\gamma}}{\text{poly}(\log(1/\gamma))}\right)$.
  • The Complexity Trade-off: The authors prove that to achieve a constant approximation ratio (beating the $1/\gamma$ barrier), the complexity of the kernel method must grow exponentially in $1/\gamma$, rendering it computationally intractable for large-scale applications.

Discussion and Implications

These results suggest that the "gold standard" of machine learning—convex optimization over Hilbert spaces—has reached its theoretical limit for learning simple linear separators in noisy environments. The $1/\gamma$ gap is not a failure of current algorithm design, but a fundamental property of the generalized linear family.

To surpass these limits, researchers may need to look beyond standard kernel methods. This points toward the necessity of non-convex approaches or architectures that do not rely solely on inner products in a fixed feature space, such as deep neural networks with learned, non-linear hidden layers. While SVMs and ridge regression remain powerful tools, this work defines the boundary where their efficiency meets its match in complexity.

Summary updated

Abstract

Many popular learning algorithms (E.g. Regression, Fourier-Transform based algorithms, Kernel SVM and Kernel ridge regression) operate by reducing the problem to a convex optimization problem over a vector space of functions. These methods offer the currently best approach to several central problems such as learning half spaces and learning DNF's. In addition they are widely used in numerous application domains. Despite their importance, there are still very few proof techniques to show limits on the power of these algorithms. We study the performance of this approach in the problem of (agnostically and improperly) learning halfspaces with margin $\gamma$. Let $\mathcal{D}$ be a distribution over labeled examples. The $\gamma$-margin error of a hyperplane $h$ is the probability of an example to fall on the wrong side of $h$ or at a distance $\le\gamma$ from it. The $\gamma$-margin error of the best $h$ is denoted $\mathrm{Err}_\gamma(\mathcal{D})$. An $\alpha(\gamma)$-approximation algorithm receives $\gamma,\epsilon$ as input and, using i.i.d. samples of $\mathcal{D}$, outputs a classifier with error rate $\le \alpha(\gamma)\mathrm{Err}_\gamma(\mathcal{D}) + \epsilon$. Such an algorithm is efficient if it uses $\mathrm{poly}(\frac{1}{\gamma},\frac{1}{\epsilon})$ samples and runs in time polynomial in the sample size. The best approximation ratio achievable by an efficient algorithm is $O\left(\frac{1/\gamma}{\sqrt{\log(1/\gamma)}}\right)$ and is achieved using an algorithm from the above class. Our main result shows that the approximation ratio of every efficient algorithm from this family must be $\ge \Omega\left(\frac{1/\gamma}{\mathrm{poly}\left(\log\left(1/\gamma\right)\right)}\right)$, essentially matching the best known upper bound.
BibTeX
@misc{daniely2012error,
  author = {Amit Daniely and Nati Linial and Shai Shalev-Shwartz},
  title = {{The error rate of learning halfspaces using Kernel-SVMs}},
  year = {2012},
  eprint = {1211.0616},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.0616},
}
Figure