Abstract
We introduce a modified version of the excess risk, which can be used to obtain tighter, fast-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, generalisation bounds provide mathematical guarantees that a model's performance on unseen data will remain close to its performance on the training set. The PAC-Bayes framework is a powerful tool for deriving these guarantees, yet researchers often face a frustrating trade-off. Standard bounds, such as McAllester’s, are frequently too "loose" to be practically useful. Conversely, "fast-rate" bounds like Maurer’s offer much tighter guarantees but typically require the model to achieve near-zero training error—a condition rarely met in complex, real-world scenarios.
To bridge this gap, researchers often turn to "excess risk" bounds, which compare a candidate model to a fixed reference model ($w^*$). However, to maintain statistical validity, $w^*$ must be independent of the data used to calculate the bound. This usually necessitates splitting the dataset in half: one portion to find $w^*$ and the other to compute the bound. This effectively discards half the available data, weakening the resulting guarantee. This paper introduces a method to achieve fast-rate convergence using the entire dataset by leveraging the relative difficulty of individual data examples.
Methodology: Online Debiasing and Martingale Theory
The core innovation of this work is a technique termed Online Debiasing. Rather than comparing the final model to a single, static reference model, we compare it to a sequence of evolving "online estimators."
The Online Approach
As the algorithm processes the dataset, it uses the first $i-1$ examples to construct a temporary reference model. This model is then used to "predict" the loss on the $i$-th example. This process accounts for the inherent difficulty of each data point; if an example is naturally "hard" (i.e., most models fail on it), the candidate model is not penalised as heavily for an incorrect prediction. This "de-biasing" reduces the variance of the empirical risk estimate, leading to tighter bounds.
Martingale PAC-Bayes
Because these online estimators depend on previous data points, the standard assumption of independent and identically distributed (i.i.d.) variables is violated. To address this, we developed a new result for sequences of interdependent random vectors using martingale theory. This allows us to maintain mathematical rigor while using the entire dataset ($N$ samples) in the denominator of our bound, rather than the $N/2$ required by traditional data-splitting methods.
Vector-Valued KL Divergence
To further refine the tightness, we decompose the excess risk into a vector of different error types (for instance, cases where the candidate model is incorrect but the reference is correct, and vice versa). By applying a specialised version of the Kullback-Leibler (KL) divergence to this vector, we can extract more information from the data distribution than a simple scalar loss would allow.
Empirical Evaluation
We evaluated the proposed bounds using Logistic Regression on eight classic benchmarks from the UCI Machine Learning Repository, ranging from small datasets (Haberman, Breast-C) to larger ones (Spambase, Adult). This variety allowed us to observe how the online nature of the bound scales with sample size.
Key Results
Our empirical analysis compared the new bound against two industry standards: Maurer’s bound and the Unexpected Bernstein (UB) bound.
- Uniform Improvement over UB: The proposed bound provided a tighter numerical guarantee than the Unexpected Bernstein bound across every single test case.
- Scaling with Data: On larger datasets, such as Adult and Spambase, our bound outperformed Maurer’s bound. This is a significant result, as Maurer’s is widely considered one of the tightest available bounds for bounded losses.
- Numerical Tightness: On the Adult dataset, where the actual test error was 0.170, Maurer’s bound provided a guarantee of 0.234. Our new bound tightened this guarantee to 0.211, significantly narrowing the gap between theory and observed performance.
Discussion and Limitations
While the method shows clear advantages, it is most effective when the online learning algorithm is stable. If reference models fluctuate wildly with each new data point, the correlation between the model and the reference weakens, loosening the bound. Furthermore, on very small datasets (e.g., Haberman), the online estimators do not have sufficient data to become "informed" quickly enough to outperform simpler bounds like Maurer’s.
There is also a computational trade-off: updating the model continuously is more intensive than a single training pass. We mitigated this by updating the estimators every 150 examples, suggesting that the frequency of updates can be tuned to balance computational cost and bound tightness.
Conclusion
By leveraging example difficulty through online debiasing and martingale theory, we have developed a PAC-Bayesian framework that provides fast-rate bounds without the need for data splitting. This approach consistently outperforms existing benchmarks on large-scale datasets. Future research will explore directly optimising this new bound as a training objective, potentially producing models with even stronger inherent generalisation guarantees.
Summary updated