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:
- $V^B_n$ (Strings): Assumes ordered subsets with replacement. This original estimator is biased, typically underestimating the true maximum.
- $U^B_n$ (Combinations): Assumes unordered subsets without replacement. This is a mathematically unbiased estimator.
- $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.
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.
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