Estimating the Maximum Expected Value: An Analysis of (Nested) Cross Validation and the Maximum Sample Average

Hado van HasseltarXiv 2013 · OpenReview

TL;DR

This paper dives deep into estimating the maximum expected value from a set of noisy measurements. It reveals that common methods like the maximum sample average (ME) are inherently biased upwards, while cross-validation (CV) can be biased downwards. Crucially, the paper shows that no single method is universally best, and the choice of estimator can drastically impact accuracy depending on the underlying data distributions.

What Problem Does This Paper Address?

Imagine you have several noisy estimates for different quantities, and you want to know the true maximum among them. This is a common problem in fields like optimization, reinforcement learning, and algorithmic evaluation. For example, when training a machine learning model, you might have multiple configurations, each with a noisy performance estimate. You want to estimate the performance of the best possible configuration. The challenge is that simply picking the highest noisy estimate (the "maximum sample average" or ME) leads to an overestimation of the true maximum. On the other hand, cross-validation (CV), a popular technique to mitigate this, can introduce its own biases and variances, sometimes leading to even worse results than the ME. This paper aims to systematically analyze these estimators, understand their biases and variances, and provide guidance on choosing the right one.

Methods

The authors analyze two main estimators:

  • Maximum Estimator (ME): This is the straightforward approach of taking the maximum of the noisy estimates. The paper derives bounds on its bias and variance, proving it has a non-negative bias.
  • Cross-Validation (CV): The paper examines both standard (low-bias) and a novel low-variance variant of CV. It introduces a formal framework for analyzing CV, splitting data into training and validation sets. The key novelty lies in analyzing how different CV configurations (e.g., number of folds, leave-one-out) affect bias and variance, and how these trade-offs play out. They provide theoretical bounds on the bias and variance of CV estimators.

Datasets

The paper uses simulated data for its experiments. Specifically:

  • Bernoulli variables: Used to illustrate unbiasedness of CV when means are equal and the positive bias of ME.
  • Regression problem: A synthetic dataset generated from a noisy sine wave function is used to fit polynomials. This experiment highlights how different CV strategies perform in a regression setting, and how the ME can sometimes outperform CV.

The paper does not introduce new benchmark datasets but rather uses controlled simulations to illustrate theoretical findings.

Key Insights and Ideas

  • No Unbiased Estimator: It's mathematically impossible to have a universally unbiased estimator for the maximum expected value when the underlying distributions are unknown.
  • ME's Inherent Overestimation: The maximum sample average (ME) always overestimates the true maximum, and this bias can be significant, especially with many variables.
  • CV's Double-Edged Sword: CV can indeed reduce bias compared to ME, but it often comes at the cost of significantly increased variance. In some cases, CV's bias can be larger in magnitude than ME's bias, albeit in the opposite direction (underestimation).
  • Problem-Dependent Performance: The "best" CV strategy (e.g., leave-one-out, k-fold, low-bias vs. low-variance) is highly dependent on the specific problem, including the number of variables (M) and the sample size. There's no one-size-fits-all CV approach.
  • The Importance of Distribution Knowledge: The paper emphasizes that without some knowledge about the distributions of the random variables, selecting an accurate estimator is non-trivial.

Key Results

  • Bias Bounds: The paper provides theoretical bounds for the bias of ME and CV estimators. ME has a non-negative bias, while CV has a non-positive bias.
  • Variance Bounds: Theoretical bounds on the variance of ME and CV are also derived.
  • Consistency: Both ME and CV are shown to be consistent estimators, meaning their accuracy improves as sample sizes increase.
  • Empirical Illustrations: Experiments with Bernoulli variables and a regression problem demonstrate that:
  • When all means are equal, CV is unbiased, and leave-one-out LVCV often yields the lowest MSE.
  • In more realistic scenarios with varying means, CV's bias becomes significant. For instance, with many variables, ME's bias can lead to overestimations of over 15%.
  • In a regression setting, the ME surprisingly outperformed all CV variants, with a much smaller bias than some CV methods.

Limitations and Future Work

  • No General Recommendation: The authors explicitly state that there is no single "best" estimator or CV configuration that works for all problems. This makes practical selection challenging.
  • Prior Knowledge: The paper suggests that incorporating prior knowledge about the distributions (e.g., through Bayesian inference) could lead to better estimators, but this is outside the scope of the current analysis.
  • Alternative Estimators: While the paper briefly mentions alternative approaches like using confidence bounds or information criteria (AIC/BIC), it focuses primarily on ME and CV. Further exploration of these alternatives could be valuable.
  • Conjecture on CV Bias: The paper presents a conjecture for a lower bound on the bias of CV, which is proven for M=2 but not in full generality. Proving this conjecture would strengthen the theoretical understanding of CV bias.

Summary updated

Abstract

We investigate the accuracy of the two most common estimators for the maximum expected value of a general set of random variables: a generalization of the maximum sample average, and cross validation. No unbiased estimator exists and we show that it is non-trivial to select a good estimator without knowledge about the distributions of the random variables. We investigate and bound the bias and variance of the aforementioned estimators and prove consistency. The variance of cross validation can be significantly reduced, but not without risking a large bias. The bias and variance of different variants of cross validation are shown to be very problem-dependent, and a wrong choice can lead to very inaccurate estimates.
BibTeX
@misc{hasselt2013estimating,
  author = {Hado van Hasselt},
  title = {{Estimating the Maximum Expected Value: An Analysis of (Nested) Cross Validation and the Maximum Sample Average}},
  year = {2013},
  eprint = {1302.7175},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1302.7175},
}
Figure