On the Complexity of PAC Learning in Hilbert Spaces

Sergei ChubanovAAAI 2023 · DOI

TL;DR

This paper introduces new algorithms for learning convex polyhedra (intersections of halfspaces) to solve binary classification problems in both finite and infinite-dimensional Hilbert spaces. By leveraging a "margin" assumption, the author achieves tighter computational complexity bounds than previous state-of-the-art methods, specifically improving the exponent in the running time for "proper" PAC learning.

What Problem Does This Paper Address?

In machine learning, binary classification is often visualized as drawing a line (a hyperplane) between two groups of data. However, real-world data is rarely that simple. A more powerful approach is to use a convex polyhedron—an intersection of multiple "halfspaces"—to wrap around one class of data.

While expressive, finding the "best" polyhedron (one with the minimum number of halfspaces) is notoriously difficult; even separating data with just two halfspaces is NP-hard. To make this tractable, researchers use the Probably Approximately Correct (PAC) framework and assume a $\gamma$-margin: a "buffer zone" where no data points reside.

The gap addressed here is twofold:

  1. Existing algorithms for this problem often have high computational costs.
  2. Most previous work focuses on finite-dimensional Euclidean spaces, whereas many modern kernel-based methods operate in infinite-dimensional Hilbert spaces.

Methods

The author proposes two main algorithmic paths based on a modified version of von Neumann’s algorithm for linear programming:

  • Algorithm 1 (The LP Engine): A foundational linear programming algorithm that iteratively updates a candidate halfspace. It uses "progress-contributing steps" to ensure that with every iteration, the candidate moves significantly closer to a valid solution.
  • Algorithm 2 (Proper Learning): This algorithm attempts to find a polyhedron defined by exactly $t$ halfspaces (a $t$-polyhedron). It uses a search tree to "assemble" these halfspaces, branching whenever a data point is incorrectly classified.
  • Algorithm 3 (Improper Learning): This version relaxes the requirement to find exactly $t$ halfspaces. It focuses on finding any consistent classifier efficiently, even if its description is more complex than the hypothetical "ground truth."

Crucially, these algorithms rely only on inner products and norms. This allows them to function in Reproducing Kernel Hilbert Spaces (RKHS) without needing the Johnson-Lindenstrauss (JL) transform—a common dimensionality-reduction tool used in prior work that can complicate theoretical analysis.

Datasets

This is a theoretical paper focused on computational complexity and provable bounds. Consequently, no empirical datasets (like MNIST or CIFAR) were used for training or evaluation. The "data" discussed consists of abstract sets $X$ within a Hilbert space $H$ that satisfy specific margin conditions.

Key Insights and Ideas

  • The Power of the Margin: The $\gamma$-margin isn't just a safety buffer; it's the mathematical key that bounds the search. The number of "progress steps" needed to find a separating hyperplane is inversely proportional to the square of the margin ($\gamma^{-2}$).
  • Smarter Search Trees: By carefully encoding the search path as a vector, the author proves that the number of nodes in the search tree doesn't explode as fast as previously thought.
  • Universal Applicability: The paper notes that any binary classification problem can be reduced to polyhedral separation if you choose the right kernel. This makes these polyhedral bounds relevant to a vast range of kernel-based learning tasks.
  • Avoiding JL Transforms: By working directly with the geometry of Hilbert spaces, the algorithm remains "kernel-friendly" and avoids the potential information loss or analytical overhead associated with projecting data into lower dimensions.

Key Results

The paper provides a significant theoretical speedup over the previous best results (Gottlieb et al. 2022):

  • Proper Learning Speedup: For a sample size $m$, $t$ halfspaces, and margin $\gamma$, the running time is $m^{O(t\gamma^{-2})}$. This improves on prior work by removing a $\log(\gamma^{-1})$ factor from the exponent.
  • Improper Learning Efficiency: The running time for improper learning is substantially better than proper learning, though it comes at the cost of a sample complexity that is exponential in $\gamma^{-2}$.
  • Hilbert Space Generalization: The author proves that these bounds hold even when the dimensionality of the space is infinite, provided the data is "well-behaved" (e.g., the image of a compact set under a continuous kernel).

Limitations and Future Work

  • Exponential Dependence on Margin: While the bounds are improved, the complexity still scales exponentially with $1/\gamma^2$. If the margin is very small, the algorithm remains computationally expensive.
  • Ground Truth Assumption: The analysis assumes a "ground truth" $t$-polyhedron exists with a known margin $\gamma$. In practice, these parameters are rarely known upfront and would likely need to be estimated via cross-validation.
  • Sample Complexity in Improper Learning: The improper learning algorithm is fast but requires a very large number of samples (exponential in the margin) to guarantee accuracy, which might be impractical for some applications.

Summary updated

BibTeX
@inproceedings{chubanov2023complexity,
  author = {Sergei Chubanov},
  title = {{On the Complexity of PAC Learning in Hilbert Spaces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25878},
}
Figure