Minimum Excess Risk in Bayesian Learning

Aolin Xu, Maxim Raginsky

Abstract

In Bayesian learning, performance is often evaluated through the lens of posterior computation rather than fundamental performance limits. This paper introduces a formal framework for Minimum Excess Risk (MER), defined as the unavoidable performance gap resulting from ignorance of the true underlying model parameters. By establishing algorithm-independent upper bounds rooted in information theory and parameter estimation error, we provide a principled method for quantifying epistemic uncertainty and characterizing its decay as data volume increases.

Introduction

Frequentist machine learning has long relied on the concept of "excess risk" to measure the performance gap between a learned model and the best possible model within a fixed class. In contrast, Bayesian learning has traditionally focused on the mechanics of posterior inference—such as Markov Chain Monte Carlo (MCMC) or Variational Inference—often overlooking the fundamental limits of achievable performance.

This research addresses this conceptual gap by formalizing the "price of ignorance." We distinguish between aleatoric uncertainty (the inherent stochasticity of the system) and epistemic uncertainty (the error stemming from a lack of data). By defining Minimum Excess Risk (MER), we provide a mathematical foundation to bound the best possible performance any Bayesian learner can achieve, regardless of the specific algorithm employed.

Defining Minimum Excess Risk (MER)

The authors define MER as the difference between the Bayes risk given the observed data and the Bayes risk that would be achievable if the true model parameters were known. This framework allows for a rigorous decomposition of uncertainty:

  1. Aleatoric Uncertainty: The fundamental limit of Bayes risk, representing the irreducible noise in the environment.
  2. Epistemic Uncertainty (MER): The "Minimum Epistemic Uncertainty," representing the additional risk incurred because the parameters are estimated rather than known.

Methodological Framework

To analyze MER, the paper proposes two primary mathematical toolsets:

1. Information-Theoretic Bounds

For specific loss functions, most notably log-loss, the MER is shown to be directly proportional to the conditional mutual information between the model parameters and the quantity being predicted. This connection implies that for log-loss, the MER is exactly equivalent to the information gain about the parameters. This allows the application of information theory to determine the "speed limit" of learning as the dataset size ($n$) grows.

2. Functional Continuity and Estimation

In scenarios where information-theoretic tools are less applicable, the authors relate MER to the Minimum Mean Square Error (MMSE) of parameter estimation. If a decision rule is "smooth" (mathematically continuous) relative to the parameters, then the error in parameter estimation translates predictably into a bounded increase in risk. This approach bridges the gap between parameter estimation accuracy and predictive performance.

Theoretical Insights and Convergence

The framework yields several significant insights into the nature of Bayesian learning:

  • Convergence Rates: For a $d$-dimensional parameter space, the MER generally decays at a rate of $O(d/n)$ for smooth loss functions (e.g., quadratic or log-loss) and $O(\sqrt{d/n})$ for less smooth functions (e.g., zero-one loss).
  • The VC Dimension Connection: The research demonstrates that the Vapnik-Chervonenkis (VC) dimension—a cornerstone of frequentist theory—also dictates the convergence rate of Bayesian learning in binary classification. This provides a rare theoretical bridge between frequentist and Bayesian perspectives.
  • Algorithm Independence: Because MER is defined using the infimum over all possible decision rules, these bounds represent the absolute best any algorithm (MCMC, SGD, or exact integration) could ever perform.

Validation via Synthetic Testbeds

As a theoretical contribution, the framework was validated using standard probabilistic generative models to demonstrate the tightness of the derived bounds:

  • Linear and Nonlinear Regression: Used to demonstrate bounds for quadratic loss and the impact of feature geometry.
  • Logistic Regression and Binary Classification: Used to analyze log-loss and connect Bayesian MER to classical VC dimension.
  • Gaussian Processes: Used to extend the theory to nonparametric settings, showing how the framework scales to infinite-dimensional models.

Limitations and Future Directions

While the MER framework provides a robust starting point for understanding Bayesian limits, several areas remain for future exploration:

  • Tightness of Bounds: The current work focuses primarily on upper bounds. Developing tight lower bounds (the "best of the best") is necessary for a complete theoretical picture.
  • Computational Risk: The MER assumes the ability to calculate the Bayesian optimal predictor perfectly. In practice, approximations like Variational Inference introduce "computational risk" that is not yet captured by this framework.
  • Model Misspecification: The current theory assumes the true data-generating process lies within the chosen model family. Extending MER to misspecified settings is a critical next step for real-world applicability.

Summary updated

Abstract

We analyze the best achievable performance of Bayesian learning under generative models by defining and upper-bounding the minimum excess risk (MER): the gap between the minimum expected loss attainable by learning from data and the minimum expected loss that could be achieved if the model realization were known. The definition of MER provides a principled way to define different notions of uncertainties in Bayesian learning, including the aleatoric uncertainty and the minimum epistemic uncertainty. Two methods for deriving upper bounds for the MER are presented. The first method, generally suitable for Bayesian learning with a parametric generative model, upper-bounds the MER by the conditional mutual information between the model parameters and the quantity being predicted given the observed data. It allows us to quantify the rate at which the MER decays to zero as more data becomes available. Under realizable models, this method also relates the MER to the richness of the generative function class, notably the VC dimension in binary classification. The second method, particularly suitable for Bayesian learning with a parametric predictive model, relates the MER to the minimum estimation error of the model parameters from data. It explicitly shows how the uncertainty in model parameter estimation translates to the MER and to the final prediction uncertainty. We also extend the definition and analysis of MER to the setting with multiple model families and the setting with nonparametric models. Along the discussions we draw some comparisons between the MER in Bayesian learning and the excess risk in frequentist learning.
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