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:
- $V_n^B$ (The "Plug-in" Estimator): Assumes sampling with replacement; it is known to be biased (underestimating the true maximum).
- $U_n^B$ (The Unbiased Estimator): Assumes sampling without replacement; while mathematically unbiased, it can suffer from high variance.
- $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.
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.
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