Leave-One-Out Cross-Validation for Bayesian Model Comparison in Large Data

Måns Magnusson, Aki Vehtari, Johan Jonasson, Michael Riis AndersenAISTATS 2020

Abstract

Comparing Bayesian models on massive datasets is computationally intensive, often requiring repeated model training or full-data log-predictive density calculations. This paper introduces a highly efficient framework for Leave-One-Out Cross-Validation (LOO-CV) using a difference estimator. By combining inexpensive surrogate approximations with accurate evaluations on small random subsamples, the proposed method achieves significant speedups and high accuracy. Crucially, the approach is model-agnostic, allowing the same subsample to be used for multiple model comparisons, making it ideal for large-scale statistical applications.

Introduction

In Bayesian statistics, Leave-One-Out Cross-Validation (LOO-CV) is the gold standard for assessing a model's predictive performance. However, for a dataset with $n$ observations, standard LOO-CV requires training the model $n$ times. While approximate methods like Pareto Smoothed Importance Sampling (PSIS-LOO) reduce this to a single model fit, they still require calculating log-predictive densities for every data point. When $n$ reaches millions, this calculation becomes a significant bottleneck. Previous subsampling attempts were often model-dependent, requiring unique subsamples for every model comparison, which hindered practical application in complex workflows.

Methodology: The Difference Estimator

The authors propose a framework based on the Difference Estimator, which leverages a "cheap" surrogate to approximate the LOO score. The process involves three primary steps:

  1. Surrogate Calculation ($\tilde{\pi}$): Compute a computationally inexpensive approximation of the LOO score for all $n$ data points.
  2. Subsample Correction: Draw a small random subsample ($m \ll n$) and calculate the "expensive" (accurate) LOO values for these specific points.
  3. Estimation: The final estimate is the sum of all cheap approximations plus a correction term derived from the average error found in the subsample.

The efficiency of this method depends on the surrogate's cost and its correlation with the true LOO values. Various surrogates, such as point-wise log-predictive density (plpd) or Taylor series expansions ($\Delta$WAIC), offer different trade-offs between speed and accuracy.

Computational costs of various surrogate approximations ($\tilde{\pi}$) used in the difference estimator.

Experimental Setup

The approach was validated across several scenarios to test scaling and complexity:

  • Simulated Data: Linear regression models with up to $10^6$ observations to evaluate computational scaling.
  • Radon Data: Approximately 12,000 measurements across 400 counties, used to test hierarchical models with varying intercepts and slopes.
  • Arsenic Wells Data: ~3,000 observations on well-switching behavior in Bangladesh, comparing logistic regression and spline models (GAMs).

Key Insights: Model-Agnostic Subsampling

A major advantage of the difference estimator is its use of Simple Random Sampling (SRS), making it model-agnostic. Unlike the Hansen-Hurwitz (HH) estimator, which requires model-specific sampling probabilities, the difference estimator allows researchers to use the same subsample to evaluate multiple models and their differences simultaneously.

Comparison of the difference estimator (diff) against Hansen-Hurwitz (HH) and Simple Random Sampling (SRS) for subsample estimation. The difference estimator shows significantly lower variance.

Furthermore, the authors found that including an estimate of the "effective number of parameters" ($p_{\text{eff}}$) in the surrogate significantly reduces variance by capturing model complexity that simpler point-estimates miss.

Results and Conclusion

The proposed method demonstrates orders-of-magnitude efficiency gains. In experiments using the Radon dataset, surrogates accounting for model complexity reduced standard errors by factors of 10 to 100 compared to basic point-estimates. On a dataset of 1 million points, a subsample of just $m=100$ was sufficient to accurately distinguish between complex priors.

While the method currently assumes factorizable likelihoods (independent observations given parameters), it provides a scalable solution for large-scale Bayesian model comparison. Future work includes extending these techniques to non-factorizable models, such as time-series or spatial data, and exploring more advanced stratified sampling strategies to further refine accuracy.

Summary updated

BibTeX
@inproceedings{magnusson2020leave,
  author = {Måns Magnusson and Aki Vehtari and Johan Jonasson and Michael Riis Andersen},
  title = {{Leave-One-Out Cross-Validation for Bayesian Model Comparison in Large Data}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure