Expected Validation Performance and Estimation of a Random Variable's Maximum

Jesse Dodge, Suchin Gururangan, Dallas Card, Roy Schwartz, Noah A. Smith

Abstract

Research in NLP is often supported by experimental results, and improved reporting of such results can lead to better understanding and more reproducible science. In this paper we analyze three statistical estimators for expected validation performance, a tool used for reporting performance (e.g., accuracy) as a function of computational budget (e.g., number of hyperparameter tuning experiments). Where previous work analyzing such estimators focused on the bias, we also examine the variance and mean squared error (MSE). In both synthetic and realistic scenarios, we evaluate three estimators and find the unbiased estimator has the highest variance, and the estimator with the smallest variance has the largest bias; the estimator with the smallest MSE strikes a balance between bias and variance, displaying a classic bias-variance tradeoff. We use expected validation performance to compare between different models, and analyze how frequently each estimator leads to drawing incorrect conclusions about which of two models performs best. We find that the two biased estimators lead to the fewest incorrect conclusions, which hints at the importance of minimizing variance and MSE.

Introduction

In modern Natural Language Processing (NLP), state-of-the-art results are often the product of massive hyperparameter searches. However, researchers typically only report the single best result found ($X_{max}$). This practice is problematic for reproducibility and fair comparison, as it hides the computational "cost of admission" and can make a model look superior simply because it was tuned more extensively.

Expected Validation Performance (EVP) addresses this by estimating the expected maximum score if a researcher were to run only $n$ trials, given a larger pool of $B$ total trials. This paper evaluates three statistical estimators for EVP:

  1. $V_n^B$ (The "Plug-in" Estimator): Assumes sampling with replacement; it is known to be biased (underestimating the true maximum).
  2. $U_n^B$ (The Unbiased Estimator): Assumes sampling without replacement; while mathematically unbiased, it can suffer from high variance.
  3. $W_n^B$ (The Multiset Estimator): A new estimator introduced in this paper that assumes unordered sampling with replacement; it is more biased than $V_n^B$.

The Bias-Variance Tradeoff

The core finding of this research is a classic bias-variance tradeoff. While unbiased estimators like $U_n^B$ are theoretically appealing, they are highly sensitive to the specific samples drawn. In contrast, biased estimators like $V_n^B$ are more consistent across different samples.

Figure 1: Comparison of estimators on synthetic data, illustrating the tradeoff between bias (expectation), variance, and Mean Squared Error (MSE).

As shown in Figure 1, $U_n^B$ accurately tracks the True EVP but exhibits the highest variance. $W_n^B$ has the lowest variance but the highest bias. $V_n^B$ strikes the most effective balance, consistently achieving the lowest Mean Squared Error (MSE) across synthetic experiments. This suggests that minimizing MSE is more important for reliable reporting than achieving zero bias.

Stability in Model Comparison

The practical impact of these estimators was tested by comparing two real-world models on the SST-5 dataset: a Convolutional Neural Network (CNN) and a Linear Bag-of-Embeddings (LBoE). The goal was to see how often each estimator led to an "incorrect conclusion"—predicting that the inferior model would outperform the superior one at a given budget.

Figure 4: The rate of incorrect conclusions when comparing models, showing that lower-variance estimators ($V_n^B, W_n^B$) are more reliable than the unbiased $U_n^B$.

As illustrated in Figure 4, the high variance of the unbiased $U_n^B$ leads to a higher rate of incorrect conclusions (approximately 11% at a budget of $B=15$). The biased estimators, by virtue of their lower variance and MSE, provide much more stable and reliable comparisons between architectures.

Conclusion and Recommendations

The authors recommend $V_n^B$ as the standard for reporting EVP because it minimizes the risk of drawing incorrect scientific conclusions. While this study focused on random search, future work is needed to adapt these estimators for non-random strategies like Bayesian Optimization, where the independent and identically distributed (I.I.D.) assumption does not hold.

Summary updated

Abstract

Research in NLP is often supported by experimental results, and improved reporting of such results can lead to better understanding and more reproducible science. In this paper we analyze three statistical estimators for expected validation performance, a tool used for reporting performance (e.g., accuracy) as a function of computational budget (e.g., number of hyperparameter tuning experiments). Where previous work analyzing such estimators focused on the bias, we also examine the variance and mean squared error (MSE). In both synthetic and realistic scenarios, we evaluate three estimators and find the unbiased estimator has the highest variance, and the estimator with the smallest variance has the largest bias; the estimator with the smallest MSE strikes a balance between bias and variance, displaying a classic bias-variance tradeoff. We use expected validation performance to compare between different models, and analyze how frequently each estimator leads to drawing incorrect conclusions about which of two models performs best. We find that the two biased estimators lead to the fewest incorrect conclusions, which hints at the importance of minimizing variance and MSE.
BibTeX
@inproceedings{dodge2021expected,
  author = {Jesse Dodge and Suchin Gururangan and Dallas Card and Roy Schwartz and Noah A. Smith},
  title = {{Expected Validation Performance and Estimation of a Random Variable's Maximum}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=IfaJDPfcAao},
}
Figure