When Shared Inputs Prevent Heavy Tails from Slowing Model Selection: A Minimax Separation

Selecting among models with similar performance can require many evaluations, especially when rare large losses affect their ranking. We study how evaluating models on common inputs changes the optimal rate of selection by Expected Shortfall (ES), the average loss over a fixed upper-tail fraction, and what remains achievable from independent evaluations. For $K$ candidates and one reference, we characterize model selection under synchronized evaluation on common inputs and independent evaluation, using the same marginal loss distributions and $n$ observations per model. The reference loss has a bounded $p$th moment, with $1<p<2$, while differences between candidate and reference losses on the same input have uniformly bounded $L^r$ norms, with $2\le r\le \infty$. Over this class with fixed moment bounds, we establish matching minimax rates for expected simple regret, defined as the expected ES gap between the selected candidate and the best candidate. The rates are $\sqrt{\log K/n}$ under synchronized evaluation and $(\log K/n{)}^{\gamma (p,r)}$ under independent evaluation, where $\gamma (p,r)=p(1-1/r)/(p+2-2p/r)<1/2$. The slower minimax rate under independent sampling persists with bounded loss differences, even when the reference marginal and every model's population quantile at the ES level are known. In controlled experiments, we compare how many evaluations are needed to select the best model with the same accuracy. As models become closer in tail risk, this number grows faster with independent samples than with shared inputs. Comparisons on fixed distributions isolate the effect of sampling. On held-out medical claims, synchronization raises the probability of correct selection from $0.144$ to $0.831$ at equal evaluation cost; language model benchmarks also show gains from synchronized sampling. These results guide evaluation design: coordinating inputs across models can reduce the budget needed to achieve a given expected ES gap from the best candidate.