Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sample Guarantees

Jean Honorio, Tommi S. JaakkolaAISTATS 2014 · OpenReview

Abstract

We analyze the expected risk of linear classifiers for a fixed weight vector in the “minimax” setting. That is, we analyze the worst-case risk among all data distributions with a given mean and covariance. We derive the tightest possible bounds for both general and sub-Gaussian distributions, showing that these bounds are dimensionality-independent and fundamentally linked to the Fisher linear discriminant objective. Furthermore, we extend these results to finite-sample settings using the PAC-Bayes framework, providing guarantees that converge at the optimal rate.

Introduction

In statistical learning theory, the central challenge is understanding how a classifier trained on finite data will generalize to unseen examples. Traditional generalization bounds, such as those derived from VC dimension or Rademacher complexity, often suffer from two drawbacks: they can be numerically loose and frequently depend on the dimensionality of the feature space.

This research, originally presented at AISTATS 2014, addresses these issues by adopting a minimax perspective. Instead of assuming a specific distribution, the authors investigate the absolute worst-case risk a linear classifier could incur given only the first and second moments (mean and covariance) of the data. By establishing "tight" bounds—limits that are mathematically impossible to improve without further assumptions—this work provides a rigorous foundation for the performance of linear models.

Theoretical Framework

Minimax Risk Analysis

The study focuses on finding the supremum of the expected risk over the set of all distributions sharing a common mean ($\mu$) and covariance ($\Sigma$). The authors employ two distinct mathematical approaches based on the nature of the data tails:

  1. General Distributions: Using a simplified proof based on the one-sided Chebyshev inequality, the authors bound the risk for any distribution with finite moments.
  2. Sub-Gaussian Distributions: For distributions with lighter tails, a novel proof using the one-sided Chernoff bound is utilized to derive tighter exponential limits.

To prove that these bounds are truly tight, the authors construct adversarial "worst-case" distributions—specifically the "three-points" and "three-planes" distributions—where the actual error rate exactly matches the theoretical upper bound.

PAC-Bayes Finite-Sample Guarantees

To bridge the gap between asymptotic theory and practical machine learning, the authors apply the PAC-Bayes framework. This allows for "probably approximately correct" guarantees when only a finite sample size ($m$) is available. They introduce the "Gibbs-Fisher" function to quantify the performance of a distribution of classifiers, showing that the finite-sample guarantees converge at the standard rate of $O(1/\sqrt{m})$.

Key Insights

The Fisher Connection

A pivotal discovery in this work is the emergence of the Fisher linear discriminant objective ($F$) as the natural metric for risk. The Fisher function, defined as $F(w|\mu, \Sigma) = \frac{(w^T \mu)^2}{w^T \Sigma w}$, is shown to be the fundamental determinant of the minimax risk. This validates the Fisher objective not just as a heuristic for dimensionality reduction, but as a theoretically optimal criterion for minimizing worst-case risk.

Dimensionality Independence

Crucially, the derived bounds are independent of the number of features ($n$). This implies that the complexity of the feature space does not inherently degrade the worst-case performance of a linear classifier, provided the Fisher objective remains constant. This is a significant departure from VC-based bounds that scale with dimensionality.

Tail Behavior and Divergence Duality

The research highlights a sharp divide in risk decay based on distribution types:

  • General variables (polynomial tails) result in a risk bound of $\frac{1}{1 + F}$, which relates naturally to Chi-squared divergence.
  • Sub-Gaussian variables (exponential tails) enjoy a much faster decay of $e^{-F/2}$, relating more naturally to Kullback-Leibler (KL) divergence.

Conclusion

This paper establishes the tightest possible bounds for linear classifiers under moment constraints, proving that the Fisher linear discriminant is the optimal objective in a minimax sense. While the study is limited to linear models and requires the existence of certain moments, it provides a robust theoretical framework for understanding generalization. Future work may extend these minimax principles to non-linear models or apply them to transfer learning scenarios where training and testing distributions differ but share moment characteristics.

Summary updated

Abstract

We analyze the expected risk of linear classifiers for a fixed weight vector in the “minimax” setting. That is, we analyze the worst-case risk among all data distributions with a given mean and cov...
BibTeX
@inproceedings{honorio2014tight,
  author = {Jean Honorio and Tommi S. Jaakkola},
  title = {{Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sample Guarantees}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=JU4AVwEfNu4},
}
Figure