On Agnostic PAC Learning using L2-polynomial Regression and Fourier-based Algorithms

Mohsen Heidari, Wojciech SzpankowskiarXiv 2021 · arXiv

Introduction

In machine learning theory, the Probably Approximately Correct (PAC) learning model serves as the standard for defining algorithmic success. However, the "agnostic" setting introduces significant complexity by removing the assumption that a perfect classifier exists within the hypothesis class. In such scenarios, the goal is to find a hypothesis that performs nearly as well as the best possible classifier in the class.

In their research, Mohsen Heidari and Wojciech Szpankowski from Purdue University address a long-standing gap in agnostic learning: the discrepancy between the mathematically "unfriendly" 0-1 loss (used for classification) and the computationally efficient square loss (used for regression). By leveraging a Hilbert space framework, they provide new mathematical foundations that significantly tighten the error bounds for fundamental learning algorithms.

The Hilbert Space Framework

The authors move the agnostic learning problem into the realm of Hilbert Spaces, specifically $L_2(D)$, where $D$ represents the joint distribution of features and labels. Within this framework, they treat true labels ($Y$) and predictors ($c$) as members of a joint function space.

Geometric Equivalence

A core contribution of the paper is the proof of a geometric equivalence between classification error and $L_2$ distance. They demonstrate that the 0-1 generalization error of a classifier is directly proportional to the squared $L_2$ distance between the label and the classifier: $$\mathbb{P}\{Y \neq c(\mathbf{X})\} = \frac{1}{4} \|Y - c\|^2_{2,D}$$ This insight allows the authors to treat binary classification as an optimization problem in function space, bridging the gap between regression and classification theory.

Proposed Algorithms

The paper focuses on two primary algorithmic approaches to exploit this geometric relationship:

1. L2-Polynomial Regression (Algorithm 1)

This algorithm follows a three-step process to bridge square loss and 0-1 loss:

  • Empirical Minimization: Find a polynomial $\hat{p}$ that minimizes the empirical square loss.
  • Optimal Thresholding: Unlike standard regression, this algorithm searches for an optimal threshold $\theta$ to shift the polynomial. This step is critical for minimizing the final classification error.
  • Classification: Return the sign of the shifted polynomial as the final classifier.

2. Fourier-Based Learning (Algorithm 2)

This approach generalizes Linial’s "low-degree" algorithm. It is designed to work for non-uniform product distributions on the Boolean cube by estimating Fourier coefficients. It effectively projects the target function onto a low-dimensional subspace of low-degree polynomials.

Key Results and Breakthroughs

The most significant finding is the improvement of the generalization error bound. Historically, theoretical analysis suggested that regression-based learners might have an error as high as $8 \times$ the optimal error ($8P_{opt}$).

Heidari and Szpankowski prove that $L_2$-polynomial regression and Fourier-based algorithms achieve a generalization error of at most $2P_{opt} + \epsilon$. This is the tightest known bound for these methods, particularly when the optimal error $P_{opt}$ is less than 0.2.

Performance Across Hypothesis Classes

  • Polynomial-Approximated Classes: For functions that can be closely mimicked by a degree-$k$ polynomial, the $L_2$ regression approach achieves an expected error of approximately $2P_{opt} + 3\epsilon$.
  • Half-spaces: Under uniform or Gaussian distributions, the authors show that $L_2$ regression learns half-spaces (linear separators) while maintaining the $2P_{opt}$ guarantee.
  • Fourier Algorithm: On the Boolean cube with product distributions, the Fourier-based approach hits the $2P_{opt}$ mark, provided the feature means are bounded away from the extremes of -1 and 1.

Discussion and Limitations

While the $2P_{opt}$ bound represents a major theoretical advancement, the research highlights several nuances:

  • Structural Dependence: The success of square-loss methods depends heavily on the geometrical properties of the hypothesis class. The $L_2$ approach is most effective when a class can be projected onto low-dimensional subspaces.
  • Distributional Assumptions: Many of the strongest results rely on specific distributions, such as Gaussians or product distributions. While the authors provide a general theorem using VC dimension, practical efficiency often requires structural knowledge of the input distribution.
  • The 0.2 Threshold: The current bounds are most advantageous when the optimal error $P_{opt}$ is low (under 0.2). Future work may explore how these bounds behave in high-noise settings where $P_{opt}$ is larger.

Conclusion

By reframing agnostic PAC learning within a Hilbert space, Heidari and Szpankowski have demonstrated that $L_2$-based regression is a much more powerful tool for classification than previously theorized. Their reduction of the error bound from $8P_{opt}$ to $2P_{opt}$ provides a stronger theoretical justification for using regression proxies in binary classification tasks.

Summary updated

Abstract

We develop a framework using Hilbert spaces as a proxy to analyze PAC learning problems with structural properties. We consider a joint Hilbert space incorporating the relation between the true label and the predictor under a joint distribution $D$. We demonstrate that agnostic PAC learning with 0-1 loss is equivalent to an optimization in the Hilbert space domain. With our model, we revisit the PAC learning problem using methods based on least-squares such as $\mathcal{L}_2$ polynomial regression and Linial's low-degree algorithm. We study learning with respect to several hypothesis classes such as half-spaces and polynomial-approximated classes (i.e., functions approximated by a fixed-degree polynomial). We prove that (under some distributional assumptions) such methods obtain generalization error up to $2opt$ with $opt$ being the optimal error of the class. Hence, we show the tightest bound on generalization error when $opt\leq 0.2$.
BibTeX
@misc{heidari2021agnostic,
  author = {Mohsen Heidari and Wojciech Szpankowski},
  title = {{On Agnostic PAC Learning using L2-polynomial Regression and Fourier-based Algorithms}},
  year = {2021},
  eprint = {2102.06277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.06277},
}
Figure