Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty

Felix Biggs, Benjamin Guedj

Abstract

We introduce a modified version of the excess risk, which can be used to obtain empirically tighter, faster-rate PAC-Bayesian generalisation bounds. This modified excess risk leverages information about the relative hardness of data examples to reduce the variance of its empirical counterpart, tightening the bound. We combine this with a new bound for [$-$1, 1]-valued (and potentially non-independent) signed losses, which is more favourable when they empirically have low variance around 0. The primary new technical tool is a novel result for sequences of interdependent random vectors which may be of independent interest. We empirically evaluate these new bounds on a number of real-world datasets.

Introduction

In machine learning theory, PAC-Bayesian generalization bounds provide a framework for quantifying the gap between a model's training performance and its expected performance on unseen data. A primary goal in this field is to derive "tight" bounds—numerical guarantees that are as close to the actual test error as possible.

A common strategy to achieve tighter, "fast-rate" convergence is to utilize excess risk. This approach compares the loss of a candidate model against a fixed reference model ($w^*$). When both models exhibit similar error patterns on the same data points, the variance of the empirical error decreases, leading to a tighter bound. However, traditional PAC-Bayesian theory requires that the reference model be chosen independently of the training data used to evaluate the bound. In practice, this often forces researchers to split their dataset: one half to select $w^*$ and the other half to compute the bound. This data-splitting effectively halves the sample size, often negating the theoretical gains of the excess risk approach.

Methodology

This research introduces a novel framework that captures the benefits of excess risk without the penalty of data splitting. The methodology rests on two primary innovations: online de-biasing and a refined mathematical bound.

1. De-biasing via Online Estimators

Instead of a single, static reference model, the authors employ a sequence of "online estimators." For each example $i$ in a dataset of size $m$, a reference model is used that has only been trained on the preceding $i-1$ examples. This martingale-based approach ensures that for every individual data point, the reference model remains "unseen" relative to that point's label. This allows the reference to adapt to the data's inherent difficulty as the sequence progresses, effectively "de-biasing" the loss by leveraging the relative hardness of examples without violating independence requirements. Consequently, the entire dataset can be used to calculate the bound, maximizing the effective sample size.

2. A Novel kl-type Bound

Most existing fast-rate bounds rely on Bernstein-type inequalities. While mathematically tractable, these often lose precision due to relaxations. The authors derive a new bound (Theorem 1) specifically designed for $[-1, 1]$-valued signed losses. By utilizing a 3-dimensional simplex to track positive errors, negative errors, and correct predictions, the authors prove that their formulation is strictly tighter than the popular "Unexpected Bernstein" bound. In specific edge cases, this new bound can even recover Maurer’s bound, which is widely considered a gold standard in the field.

Experimental Evaluation

The proposed bounds were evaluated using regularized logistic regression across eight binary classification datasets from the UCI Machine Learning Repository, including Adult (32k+ examples), Spambase, Mushroom, and Haberman. The performance was benchmarked against Maurer’s small-kl bound and the Unexpected Bernstein bound.

Key Findings

  • Performance on Large Datasets: The advantages of the new bound are most pronounced on larger datasets. For the Adult dataset, the new bound achieved a value of 0.211, significantly outperforming Maurer’s (0.234) and the Unexpected Bernstein bound (0.384).
  • Scaling with Sample Size: The de-biasing process improves as the sequence of online estimators grows. On very small datasets like Haberman, Maurer’s bound remains more competitive because the online estimators do not have sufficient data to become effective surrogates early in the sequence.
  • Mathematical Superiority: In all empirical tests, the new "kl-type" bound provided a tighter numerical guarantee than the Unexpected Bernstein bound, validating the theoretical claim that the simplex-based approach is a more precise mathematical tool for de-biased losses.

Discussion and Future Work

The core contribution of this work is the demonstration that not all training examples are equally informative. By using a learner that evolves through the dataset, the bound can "cancel out" the loss on easy examples that most reasonable models would predict correctly, focusing the complexity penalty on truly difficult instances.

However, the method's effectiveness is tied to algorithm stability. If a learning algorithm is highly sensitive to small changes in the training set, the online estimators may not correlate well with the final model, diminishing the de-biasing effect. Additionally, while the authors mitigated computational costs by updating estimators in chunks (every 150 examples), the approach remains more computationally intensive than standard single-model training.

Future research directions include integrating this framework with data-dependent priors and exploring the application of the underlying martingale results for interdependent random vectors to other areas of statistical learning theory.

Summary updated

Abstract

We introduce a modified version of the excess risk, which can be used to obtain empirically tighter, faster-rate PAC-Bayesian generalisation bounds. This modified excess risk leverages information about the relative hardness of data examples to reduce the variance of its empirical counterpart, tightening the bound. We combine this with a new bound for [$-$1, 1]-valued (and potentially non-independent) signed losses, which is more favourable when they empirically have low variance around 0. The primary new technical tool is a novel result for sequences of interdependent random vectors which may be of independent interest. We empirically evaluate these new bounds on a number of real-world datasets.
BibTeX
@inproceedings{biggs2023tighter,
  author = {Felix Biggs and Benjamin Guedj},
  title = {{Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=lQd8tEiC24},
}

Loading related content...

Figure