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

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

In modern machine learning, reporting a single "state-of-the-art" result often obscures the significant computational effort required to find it. When a model's performance is the result of extensive hyperparameter optimization (HPO), a single accuracy score fails to inform researchers with different computational budgets. To address this, the concept of Expected Validation Performance (EVP) was introduced, estimating the maximum score expected for a budget of $n$ trials, given a total pool of $B$ trials.

Presented at EMNLP 2021, this research provides a rigorous statistical analysis of EVP estimators, revealing a critical tradeoff between mathematical unbiasedness and practical reliability.

A Unified Combinatorial Framework

The authors unify three distinct estimators for EVP through the lens of combinatorics. By viewing the problem as estimating the maximum of a subset of size $n$ from $B$ total results, the choice of how to "count" these subsets defines the estimator:

  1. $V^B_n$ (Strings): Assumes ordered subsets with replacement. This original estimator is biased, typically underestimating the true maximum.
  2. $U^B_n$ (Combinations): Assumes unordered subsets without replacement. This is a mathematically unbiased estimator.
  3. $W^B_n$ (Multisets): Assumes unordered subsets with replacement. This new estimator is even more biased than $V^B_n$.

The Bias-Variance Tradeoff

While "unbiased" is often considered the gold standard in statistics, this paper demonstrates that it is not always the most desirable property for reporting HPO results. The authors evaluate the estimators using the Bias-Variance Tradeoff. An unbiased estimator like $U^B_n$ may be correct on average, but if its variance is high, any single estimate is likely to be far from the truth.

Comparison of bias, variance, and MSE for the three EVP estimators.

As shown in the figure above, while $U^B_n$ (blue) tracks the "True EVP" most closely in expectation, it suffers from the highest variance. Consequently, the original biased estimator $V^B_n$ (orange) achieves the lowest Mean Squared Error (MSE), providing a more consistent and reliable estimate across different experimental runs.

Scientific Reliability in Model Comparison

The practical danger of high variance becomes clear when comparing two different models. If an estimator is "noisy," it is more likely to lead to an "incorrect conclusion"—a situation where the estimator wrongly predicts that an inferior model will outperform a superior one at a specific budget.

Percentage of incorrect conclusions when comparing models using different estimators.

In experiments on the Stanford Sentiment Treebank (SST-5) comparing CNN and Linear Bag-of-Embeddings models, the unbiased $U^B_n$ estimator consistently led to higher error rates in model comparison. The biased but lower-variance estimators ($V^B_n$ and $W^B_n$) proved much more robust for scientific decision-making.

Conclusion and Recommendations

The study concludes that for the purpose of reporting and comparing model performance in NLP, the original $V^B_n$ estimator is superior to the unbiased $U^B_n$. Its lower variance and lower MSE make it a more reliable tool for researchers to understand how a model will perform under varying computational constraints.

While this framework assumes independent and identically distributed (i.i.d.) trials—typical of random search—future work is needed to extend these insights to non-i.i.d. search strategies like Bayesian Optimization. For now, researchers are encouraged to adopt $V^B_n$ to ensure more reproducible and transparent reporting of HPO costs.

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