Winner’s Curse in Validation Risk Estimates

Derivation. Since \(X-Y\sim N(a-b,2\tau^2)\), \(P(X\leq Y)=p\). Thus the expected true risk of the selected candidate is \(ap+b(1-p)\). To obtain the selected estimate’s expectation, use \(\min(X,Y)=X\mathbf{1}_{\{X\leq Y\}}+Y\mathbf{1}_{\{Y<X\}}\). Equivalently, writing \(D=X-Y\), we have \(\min(X,Y)=Y+\min(D,0)\). For \(D\sim N(a-b,2\tau^2)\), direct integration of the normal density gives \(E[\min(D,0)]=(a-b)\Phi((b-a)/(\sqrt{2}\tau))-\sqrt{2}\tau\phi((b-a)/(\sqrt{2}\tau))\). Since \(E[Y]=b\), substitution yields the displayed formula for \(E[\min(X,Y)]\). Subtracting it from \(E[R_J]\) gives \(O\). \(\square\)

Equal-Risk Candidates and the Number of Choices

The winner’s curse is especially transparent when all \(M\) candidates have the same risk \(R\), and their validation errors are independent \(N(0,\tau^2)\). Write \(\hat R_j=R+\tau Z_j\), where \(Z_1,\ldots,Z_M\) are independent standard normal random variables. Because every candidate has true risk \(R\), the selected true risk is exactly \(R\), regardless of which candidate wins. Therefore \(O=R-E[\min_j\hat R_j]=\tau E[\max_j Z_j]\), using symmetry of the standard normal distribution.

How the Bias Grows with the Candidate Count

The exact integral for \(a_M\) can be evaluated numerically for any finite \(M\). Its leading growth has a simple form: \(a_M\) is asymptotic to \(\sqrt{2\log M}\). Thus, under the independent equal-risk Gaussian model, optimism is on the scale \(\tau\sqrt{2\log M}\). More candidates provide more opportunities for a very favorable noise realization.

Proof. For any \(t>0\), the pointwise inequality \(\exp(t\max_j Z_j)\leq\sum_{j=1}^M\exp(tZ_j)\) holds. Applying Jensen’s inequality to the logarithm, and using \(E[\exp(tZ_j)]=\exp(t^2/2)\), gives \(E[\max_j Z_j]\leq(\log M)/t+t/2\). Taking \(t=\sqrt{2\log M}\) yields the upper bound \(E[\max_j Z_j]\leq\sqrt{2\log M}\).

For the lower bound, fix \(0<\epsilon<1\) and let \(x_M=(1-\epsilon)\sqrt{2\log M}\). For \(x\geq1\), the standard normal upper tail satisfies \(1-\Phi(x)\geq c\phi(x)/x\) for some constant \(c>0\); for example, integrate the density over \([x,x+1/x]\) to obtain such a bound. Consequently, \(M\{1-\Phi(x_M)\}\to\infty\), since \(\phi(x_M)\) is proportional to \(M^{-(1-\epsilon)^2}\), up to a constant factor, while \(x_M\) grows only as \(\sqrt{\log M}\).

Independence now gives \(P(\max_j Z_j\geq x_M)=1-\Phi(x_M)^M\to1\). The negative part of \(\max_j Z_j\) has expectation tending to zero: on the event that all \(Z_j<0\), its absolute value is at most \(|Z_1|\), and \(E[|Z_1|\mathbf{1}_{\{Z_1<0\}}]\cdot 2^{-(M-1)}\to0\). It follows that \(\liminf_M E[\max_j Z_j]/\sqrt{2\log M]\geq1-\epsilon\). Since \(\epsilon\) can be arbitrarily small, combining this with the upper bound proves the limit. \(\square\)

Dependence and Interpretation

Validation errors for different predictors are usually dependent because every candidate is evaluated on the same validation observations. The independent Gaussian calculation is therefore a benchmark, not a universal formula. For example, suppose the standardized errors have an equicorrelated Gaussian representation \(Z_j=\sqrt{\rho}\,Z_0+\sqrt{1-\rho}\,Z'_j\), where \(0\leq\rho\leq1\) and \(Z_0,Z'_1,\ldots,Z'_M\) are independent standard normals. The shared term has expectation zero and does not affect which candidate is smallest. The expected minimum error is consequently \(-\tau\sqrt{1-\rho}\,a_M\), so optimism is \(\tau\sqrt{1-\rho}\,a_M\). As the common correlation approaches one, candidates move together and the selection advantage from comparing them vanishes.

In practice, validation losses need not be Gaussian, and their errors need not have equal variances. The exact formulas above require the stated distributional assumptions. The underlying selection mechanism is more general: choosing the smallest among unbiased estimates makes the reported minimum tend downward. The size of that effect depends on the noise distribution, its dependence across candidates, and how many candidates are compared.

A common mistake is to call \(E[\min_j\hat R_j]-\min_jR_j\) the optimism of the selected candidate. That quantity compares the minimum estimate with the best fixed risk; it is not generally \(E[R_J-\hat R_J]\), because the selected candidate itself can have risk above the minimum. In the two-candidate example, the expected minimum estimate is \(0.49497\), so its difference from the best risk \(0.50\) is about \(-0.00503\). But the selection optimism is \(0.02076\), calculated by comparing the selected candidate’s expected true risk \(0.51573\) with its expected estimate \(0.49497\). Keeping these targets separate is essential when interpreting validation results.