Minimum Excess Risk in Bayesian Learning

Aolin Xu, Maxim Raginsky

Abstract

This paper introduces and analyzes Minimum Excess Risk (MER), a novel framework for quantifying the "epistemic uncertainty" in Bayesian learning. By defining MER as the gap between the best possible prediction with data versus the best possible prediction with the true model parameters, the authors provide rigorous upper bounds using information theory and parameter estimation error. This work bridges a long-standing gap between Bayesian and frequentist learning theory, demonstrating that Bayesian learning rates are governed by similar complexity measures as their frequentist counterparts.

Introduction

In machine learning, uncertainty is typically categorized into two types: aleatoric (inherent randomness in the data) and epistemic (uncertainty due to a lack of knowledge about the model). While frequentist learning theory has a rich library of "excess risk" bounds to analyze performance, Bayesian learning theory has historically been more fragmented.

The authors tackle a fundamental question: How much performance do we lose because we have to learn the model from finite data instead of knowing the true model parameters from the start? They formalize this loss as the Minimum Excess Risk (MER). This provides a principled way to measure the difficulty of a learning problem and understand how quickly predictions improve as more data is collected.

Theoretical Framework

The paper derives MER bounds through two primary lenses: information theory and estimation theory.

1. Information-Theoretic Approach

The authors demonstrate that for many loss functions, such as log-loss, the MER is directly related to the Conditional Mutual Information (CMI) between the model parameters ($W$) and the target variable ($Y$), given the observed data ($Z^n$) and features ($X$). Specifically, for logarithmic loss, the MER is exactly equal to the CMI: $$MER = I(W; Y | X, Z^n)$$ This allows the application of tools from universal source coding and information theory to derive asymptotic rates of convergence.

2. Estimation-Theoretic Approach

For predictive models, the authors relate MER to the Minimum Mean Square Error (MMSE) of estimating the model parameters. If it is inherently difficult to estimate the parameters (high MMSE), that difficulty translates into higher excess risk. By utilizing functional and distributional continuity—such as Wasserstein distance—the paper shows how parameter estimation error "leaks" into prediction error. This approach suggests that "plug-in" decision rules (estimating parameters first, then predicting) are often near-optimal.

3. Realizable Models and Complexity

In "realizable" settings, where the true relationship is contained within the model class, the authors bridge the gap with frequentist theory by incorporating the VC dimension. While it is often assumed that Bayesian methods ignore complexity measures because they rely on priors, this paper shows that the VC dimension naturally emerges as a governing factor for the rate at which MER decays in classification tasks.

Key Results and Asymptotic Rates

The paper provides several fundamental limits for learning performance:

  • Standard Rates: Under standard regularity conditions, the MER for log-loss and quadratic loss typically scales as $O(d/n)$, where $d$ is the parameter dimension and $n$ is the number of samples.
  • Classification: For binary classification (zero-one loss), the MER scales as $O(\sqrt{d/n})$ in general settings, but improves to $O(d/n)$ in realizable settings.
  • Model Selection: The framework extends to scenarios involving multiple model families. In these cases, the MER includes a term representing the error probability of selecting the incorrect model family, which is analogous to "approximation error" in frequentist settings.

Discussion and Limitations

While the paper provides a comprehensive set of upper bounds, it leaves the establishment of formal lower bounds as an open problem. Additionally, the analysis focuses on the best achievable performance (the Bayes risk) and does not account for the computational complexity of performing Bayesian inference, such as the costs associated with MCMC or Variational Inference.

Finally, the current analysis assumes the prior is "correct" in a Bayesian sense. Future work is required to explore MER in misspecified settings, where the model family does not contain the true distribution, and the KL-divergence to the truth does not vanish.

By providing a rigorous mathematical definition for epistemic uncertainty, this work offers a unified language for understanding the cost of learning in Bayesian systems.

Summary updated

BibTeX
@article{xu2022minimum,
  author = {Aolin Xu and Maxim Raginsky},
  title = {{Minimum Excess Risk in Bayesian Learning}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2022.3176056},
}
Figure