Expected Validation Performance and Estimation of a Random Variable’s Maximum (2021)

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 drawing robust conclusions when comparing different methods in natural language processing is central to scientific progress. if two research groups set up the same set of experiments, they should expect to get similar results. one area that has high impact, but is often underreported, is hyperparameter tuning @xcite @xcite . hyperparameter search is key to getting strong results; for example, roberta @xcite found stronger results than bert @xcite partly due to an increased budget for hyperparameter tuning. often researchers only report the performance of the single best-found model during a hyperparameter search @xcite @xcite . what if a future researcher has a smaller computational budget for training models? what performance should they expect to find? one way of reporting such results is expected validation performance @xcite . what is evp? assume a budget to train b models (e.g., b rounds of hyperparameter search), with resulting evaluation scores (e.g., accuracy) on the validation set x 1 . . . x b . standard practice would report the maximum result, x max , but this effectively hides the experiments which were required to achieve that maximum performance. using all b results, evp estimates what the maximum would have been if we had had a smaller budget n (where 1 ≤ @xmath0. this is estimating what the maximum of n trials would be, in expectation; this is thus a statistical estimation problem. the formulation was introduced by @xcite , who proposed a first estimator (defined as v b n in equation 2). this estimator was later shown to be biased by @xcite , who introduced an unbiased estimator (defined as u b n in equation 3 ) for the same expected maximum. in section 2 we use tools from combinatorics to derive both previously-introduced estimators, relate them to each other, and show that they make two opposing assumptions; we show that changing only one of these assumptions instead of both leads to a third estimator, w b n , and prove that this estimator is even more biased than v b n . unbiased estimators are generally preferred, all else equal, but only analyzing the bias provides an incomplete picture of the quality of an estimator. in section 3 we also measure the variance and mean squared error of these three estimators in synthetic experiments. we find that while u b n is unbiased (as expected) it has the highest variance, and that w b n is the most biased but has the lowest variance; v b n strikes a balance between the bias and variance, leading to the lowest mean squared error (so, the average squared distance to the true value being estimated is smallest). 1 finally, in section 4 we explore how these estimators impact a common use case of evp: comparing the results of hyperparameter searches for two models. specifically, we examine how frequently the estimators lead to incorrectly concluding that the worse model outperforms the better one (for a given budget), and find that the high-variance (but unbiased) u b n more frequently leads to such incorrect conclusions than the other lower variance (but biased) estimators. ## estimation of the expected maximum notation we begin by defining some notation. consider n i.i.d. random variables, x 1 , . . . , x n ∼ f , for some unknown f . 2 estimation of the expected maximum we consider the estimation of θ, the expected maximum. with a finite sample of b draws from f , we can estimate this quantity for 1 ≤ @xmath1. we begin with the definition of an expectation over a discrete set: this can be rewritten using order statistics. let x (i) denote the ith largest sample (distinct from x i ). then, this estimation depends on p (y @xmath2, the probability that a sample of size n has a maximum that is less than or equal to the kth order statistic. we can estimate this probability by counting: from our b points how many sets of size n are there which only include order statistics up to k, out of the total number of sets of size n? we turn to combinatorics, which provides tools for counting such sets. two key assumptions must be made: whether the sets will contain repetition or not and whether the items in the sets will be ordered or unordered. these assumptions will lead to different estimators. ordered subsets that allow repetition are known as strings, and there are b n strings of size n from b points. with these assumptions, we now have a closed form for p (y @xmath3, and plugging this into equation 1 we define our first estimator: this is exactly the estimator introduced in @xcite , derived using the plug-in estimator for the cdf (the empirical cdf). making the opposite two assumptions, unordered subsets without repetition are combinations, for which there are b n subsets of size n from b points. the corresponding estimator is this is the estimator of @xcite , which they derived as an unbiased estimator. what about changing only one of these assumptions? ordered subsets without repetition are permutations, for which there are b p n subsets of size n from b points. though these assumptions are different, the corresponding estimator is equivalent to u b n , since: finally, unordered subsets with repetition are multisets, the number of which is denoted b @xmath4 comparing estimators to compare these estimators we turn to the standard statistical tools of bias, variance, and mean squared error. u b n was shown to be unbiased, and bias (v b n ) ≤ 0 @xcite . we show that bias (w the left side of eq. 7 can be rewritten as: rewriting the right side of eq. 7 in a similar manner, we have this completes our proof. ## simulation experiment in the previous section we proved that w b n is at least as biased as v b ## incorrect conclusions while analyzing how close each estimator is to the true expected maximum for one model is important, in practice these curves are often used to compare two or more different models. for example, nlp practitioners may run hyperparameter searches for two different models, compute the expected validation curves for each, and select the model which