acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 candidates and one reference, we characterize model selection under synchronized evaluation on common inputs and independent evaluation, using the same marginal loss distributions and observations per model. The reference loss has a bounded th moment, with , while differences between candidate and reference losses on the same input have uniformly bounded norms, with . 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 under synchronized evaluation and under independent evaluation, where . 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 to 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.

Primary area:
learning theory
Keywords:
model selection, minimax rates, heavy-tailed distributions, expected shortfall (CVaR), synchronized evaluation, best-arm identification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_WKdcOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper explains Expected Shortfall (ES) and how to choose the smallest ES difference among K models. It compares “synchronized evaluation” and “independent evaluation”. The paper proves a matching minimax rate for expected regret. There are corresponding experiments on MMLU-Pro and ARC-Challenge.

Critical strengths
  1. The minimax characterization and its formulation, derivation is interpretable and explicit.
  2. Theorem 1 has both upper bound and lower bound, and they both depend on logK, which is strong result.
Critical weaknesses

My main concern is that the evidence does not directly support the paper’s main claim. Also, the visualization of numbers and figures is not very good. Details are in the questions.

Questions for authors
  1. Conventional model selection in ML compares mean performance such as accuracy. The experiments reach that regime by pairing unbounded losses (correct-answer NLL / absolute error) with a 0.95-ES criterion, but the paper motivates ES only in general terms and does not explain when practitioners would select models this way. In what instances do we choose a model with this strategy?
  2. The introduction explains that the paper adaptively chooses when to evaluate and stop, and I found the related derivation in Appendix I. However, there seems to be no experiment of the optimally chosen algorithm/heuristic value.
  3. Figure readability is poor. The style of the figure makes it hard to read. (Fig. 1’s a, b bolded black marker, blue and orange title, different style of (a)(b) in Fig. 2, Fig. 2 (b) showing slope difference but not clear of interpretation)
  4. Fig. 3 is also hard to figure out why this figure is important. The graph of independent and synchronized does not show a tendency between the four graphs. Should I interpret that orange is constantly bigger than blue, or in some setting the gap is bigger? Linear y-axis and slope, no marker; the figure is talking about Kn, but the writing is talking about n, which makes it hard to interpret.
  5. Table 1 is the only table that contains real data results, but it is hard to interpret. PCS 0.144 → 0.831, regret 4.227 → 0.126 is not sufficient to support the main content’s claim.
  6. How big are the constants in the real experiments? Are the bounds informative at that scale?
  7. The fixed-budget lower bounds require K >= 8. Does the separation also hold for K=2, the common case of comparing two models?
  8. Can you generalize this tendency to another setting and explain better why this is an important problem?
5 comments
AuthorsOpenReview ↗

Response to Reviewer WKdc

Thanks for your feedback. We understand your concern about how the experiments support our main claim. We address your questions below.

Main claim and evidence. To clarify, Theorem 1 establishes that the observation protocol itself changes the minimax ES-selection rate: shared inputs achieve a faster rate than independent evaluation under the same moment bounds and evaluation cost. It predicts that, as ES gaps shrink, independent evaluation requires budgets that grow faster than synchronized evaluation.

Since these are worst-case rates over a class of distributions, this difference in budget scaling need not appear on every distribution. We therefore examine the predicted scaling on the hard families used to establish the lower bounds. Figure 2(b) shows that, as the ES gap shrinks, the number of evaluations needed to reach the same probability of correct selection grows faster under independent evaluation, consistent with the theory.

Because these experiments use different hard families, we then compare the two protocols on the same loss distribution, with the same selector and budget. Synchronization still improves selection, providing further evidence for the benefit of shared inputs. We finally show that this benefit also appears in real evaluations using medical claims and language-model benchmarks.

We have revised the opening of Section 5 to explain the purpose of each experiment and make its connection to the theoretical result clearer.

Why ES and what Table 1 shows. As you note, model selection usually focuses on average performance. However, a model with good average performance can still make severe errors on a small fraction of cases. ES is useful when these errors matter for the decision, as studied in risk-sensitive learning (Holland & Haress, 2021). For example, in medical-cost forecasting, large prediction errors can affect budgeting and reserve planning. In language-model evaluation, ES allows us to assess performance on questions where the correct answer receives very low probability. Our study examines how to select models efficiently when this tail-risk criterion matters.

For Table 1, we compare both protocols on the same medical data, using the same models, ES criterion, selection rule, and evaluation budget. The key difference is whether the models share evaluation inputs. Since large medical claims can affect all models' errors, sharing inputs makes their comparisons more reliable. The higher PCS and lower regret provide real-data evidence for this benefit at a fixed budget. Section 5.2 now also reports PCS across budgets: as the number of records per candidate increases 64-fold, synchronized PCS rises to 0.9680.968, while independent PCS remains near the 1/71/7 chance level.

The K=2K=2 case. Thanks for raising this question. The separation also holds for K=2K=2. We have added a binary-testing proof in Appendix G.4 and summarized the result in Section 3. The minimax expected regret rates are n−1/2n^{-1/2} under synchronized evaluation and n−γ(p,r)n^{-\gamma(p,r)} under independent evaluation.

Adaptive stopping and constants. Our main result concerns fixed-budget minimax selection, which is also the focus of our experiments. The adaptive procedures extend the theory by establishing expected evaluation-cost guarantees when the ES gaps are unknown. The constants in both the fixed-budget regret bounds and the adaptive expected-cost guarantees have not been numerically calibrated. We have clarified the role of the adaptive procedures in Section 4 and Appendix I.

Readability of Figures 1 and 2. We have standardized the panel labels in Figure 1 and clarified the interpretation of Figure 2(b)'s slope difference in its caption.

Figure 3 interpretation. For Figure 3, the main purpose is to show whether sharing inputs improves model selection at the same evaluation cost on real language-model benchmarks. Each panel compares the two protocols within one benchmark and reference setting. A lower mean regret means the selected model is closer to the best model in ES. The benefit is clear on ARC-Challenge and on MMLU-Pro with OpenOrca excluded. On MMLU-Pro with Mistral excluded, the confidence interval for the difference includes zero.

To make the comparison easier to follow, we added markers at the tested budgets and clarified the panel titles. We also clarified that nn is the number of questions per candidate, while the horizontal axis shows the total number of candidate–question evaluations across all 27 candidates.

Generalizability. Beyond medical claims and LLM benchmarks, our framework can also be useful for selecting among fixed policies by tail risk using common simulated scenarios, such as reinforcement-learning policies evaluated using shared random seeds.

We hope these clarifications and revisions address your concerns.

Thank you for clarifying the K=2 case and for adding the proof. I still have three concerns.

  1. I still find Figure 2, especially panel (b), difficult to interpret. I understand that a positive slope difference means the required evaluation budget grows faster under independent sampling as the gap shrinks. What should the reader learn from seeing 'all six', 'smallest four', and 'largest four' side by side? Current figures 1,2,3 all are hard to interpret by reading the paper.

  2. In the medical claims experiment, synchronization increases the probability of selecting the best model. However, the best and second-best models differ by <1$ in the 0.95-ES of ABS prediction error. I remain unclear about the practical importance of distinguishing models. Why is this decision important?

  3. I found the intuition behind the experiments hard to follow in the main text. Several passages report estimates and 95% intervals in succession, leaving the reader to infer which comparison matters most. It would help to state the question each experiment answers and its main finding in plain language before presenting the numerical details.

I appreciate the revisions, but these concerns remain, so I am keeping my current rating.

AuthorsOpenReview ↗

Follow-up to Reviewer WKdc

Thank you for the follow-up. We address the three concerns below.

1. Interpretation of Figure 2(b).

“All six” is the main fit using all six ES gaps. “Smallest four” excludes the two largest gaps, and “largest four” excludes the two smallest. These overlapping fits check whether the conclusion depends on the gap range used for fitting. All three simultaneous 95% intervals lie above zero, showing that the positive slope difference persists after either end of the tested range is excluded. We plan to make this purpose explicit in the labels and caption.

2. Importance of the medical comparison.

You are correct that the best and second-best models differ by only 0.530 dollars in ES. This case study does not establish that distinguishing these two models has substantial economic value.

However, the practical evaluation question is whether we can reliably select a model with near-minimal tail prediction error under a limited evaluation budget, even when the two leading models are treated as equivalent. In the without-replacement experiment with 8,192 records per candidate, the estimated probability of selecting a model within 1 dollar of the best ES is 96.9% under synchronization versus 29.6% under independent sampling, at the same evaluation cost. Thus, the gain in selection reliability persists without requiring us to distinguish between the two leading models.

3. Presentation of the experiments.

We agree that main findings should come before the numerical details. In Section 5.1, we plan to bring the budget-growth finding forward. In Section 5.3, we will first summarize where synchronization improves selection and where the difference is inconclusive. We will make the medical tolerance result more prominent in Section 5.2. The estimates and confidence intervals will follow these main findings.

Remaining soundness concern.

Finally, your original review assigned a soundness score of 1. We would appreciate clarification on whether any specific concern about the correctness of our theoretical results or the validity of our experiments remains. We would be glad to address it directly. Thank you.

Reviewer_zw8EOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies selection among fixed candidate models when performance is measured by Expected Shortfall (ES). It compares synchronized evaluation on common inputs with independent marginal sampling, using the same number of evaluations per model. The independent lower bound remains valid when the reference distribution and all relevant population quantiles are known. The upper bounds use relative Rockafellar–Uryasev (RU) scores, with separate treatments of quantile fitting and tail truncation. Further results establish the sufficiency of candidate-reference pairing, a tuning-free empirical-ES selector under bounded contrasts, and adaptive fixed-confidence guarantees. Experiments examine scaling on hard families, sampling design on fixed distributions, and finite-population medical and language-model evaluations, including the benefits and failures of evaluating a reference on previously collected candidate inputs.

Critical strengths
  1. The common-class minimax comparison is a meaningful advance over the usual argument for paired evaluation. Theorem 1 establishes matching upper and lower bounds under the same moment restrictions and evaluation accounting. The lower-bound constants do not grow with the number of candidates or sample size. The scaling argument completing the theorem on p. 23 places both hard families inside any prescribed positive moment bounds. This matters because otherwise an apparent advantage could come from making the independent problem's distribution class progressively harder. The independent exponent is particularly interesting. Although the candidate-reference coupling is unobserved under independent sampling, the contrast assumption still restricts the marginal distributions. The result explains both why independent sampling can improve on the exponent (p−1)/p(p-1)/p from marginal moments alone and why it still cannot recover the synchronized exponent. This is more informative than showing that one paired estimator outperforms one independent estimator.

  2. The treatment of quantiles makes the synchronized result substantially more robust than a direct plug-in argument would suggest. ES differences are not ES of loss differences, so cancellation of a shared heavy-tailed component is not automatic. The paper works with RU score differences and explicitly includes the error from fitting each model's quantile. In Lemma 3, the fitted threshold is constrained to [−Q,Q][-Q,Q], and subtracting the score at a fixed threshold removes the unbounded part that is constant in the threshold. The resulting empirical process is controlled by the empirical CDF. This controls objective excess without requiring the quantile estimate itself to converge quickly, a positive density at the threshold, or a unique RU minimizer. The allowance for atoms is therefore supported by the proof rather than merely stated in the setup.

  3. The experiments include controls that are important for the paper's actual claim. The scaling studies use different hard families, as appropriate for the separate minimax lower bounds. The fixed-distribution comparisons further isolate the effect of sampling design. The initial construction permits exact identification after a tail observation, while the additional random-residual construction addresses this favorable feature.

Critical weaknesses
  1. The finite-range scaling results need further interpretation, though they do not raise a substantial soundness concern. For r=∞r=\infty, Table 2 reports an independent slope of 2.6362.636 with a 95% interval of [2.509,2.769][2.509,2.769], above the predicted exponent 17/7≈2.42917/7\approx2.429. However, the smallest-four-gap interval does not exclude the predicted exponent, and the reported intervals concern finite-grid slopes rather than asymptotic rates. A variance-based diagnostic using the paper's Gaussian mixture gives slopes of approximately 2.6582.658 across all six gaps and 2.6182.618 across the smallest four, suggesting that finite-gap effects could explain much of the discrepancy. This diagnostic does not reproduce the full selection experiment. A brief discussion of these finite-range effects would clarify the empirical evidence for the theoretical scaling.

  2. The practical calibration of the fixed-confidence procedures remains unclear. The adaptive guarantees rely on sufficiently large constants in the confidence radii (Equations (49)–(50)) and a sample-size threshold that are not numerically instantiated. The restart construction also discards previous runs. These choices are valid for theoretical achievability but leave the practical stopping costs uncertain. Although the fixed-budget experiments demonstrate the benefits of synchronization, and Appendix M.1 shows that winsorization can improve selection under heavy tails, neither evaluates the proposed adaptive stopping procedures. A worked example with valid confidence constants and an implied stopping threshold would help establish their practical relevance. Alternatively, the authors could more explicitly characterize these procedures as theoretical achievability constructions rather than immediately practical algorithms.

Questions for authors
  1. Can the authors explain the finite-range independent slopes using the mixture's actual score variances or another finite-gap analysis? The variance diagnostic suggests that the observed value need not be surprising even when the asymptotic power is correct. An answer identifying the relevant correction would clarify what Figure 2 validates and whether the smaller-gap point estimate being closer to the predicted exponent reflects preasymptotic effects. A brief analysis of the existing construction would address the concern. Exact agreement with the proxy is not required.

  2. Are the restarted procedures intended mainly to establish the attainable expected-cost exponents, or also as directly usable stopping rules? For the latter interpretation, one numerical choice of valid radius constants and the implied sample threshold at a specified gap and confidence level would clarify their practical reach. For the former, a clearer statement of that role would be sufficient. This would strengthen the interpretation of the adaptive results without changing the favorable assessment of the fixed-budget theorem.

2 comments
AuthorsOpenReview ↗

Response to Reviewer zw8E

Thank you for the careful reading and suggestions. We really appreciate it. We address the two questions you raised below.

Finite-range slopes. The discrepancy you identified is real. Following your suggestion, we computed the population RU-score variances for the original mixtures at the six ES gaps. The variances of a suboptimal candidate (V0V_0) and the best candidate (V1V_1) give the sample-size proxy (V0+V1)/Δ2(V_0+V_1)/\Delta^2. The resulting proxy slopes closely match the observed slopes.

  • All six gaps (2.6362.636 observed, 2.6582.658 proxy).
  • Smallest four gaps (2.5782.578 observed, 2.6182.618 proxy).
  • Largest four gaps (2.6942.694 observed, 2.7062.706 proxy).

At the tested tail scales (2.0462.046 to 4.4904.490), the quantile thresholds and unit tail shift still affect how the score variances change with the gap, explaining much of the finite-gap discrepancy. The observed and proxy slopes for the smallest four gaps are both closer to 17/717/7, consistent with this explanation. Figure 2(b) also shows a positive slope difference between independent and synchronized sampling across the tested gaps. We have added this explanation to Section 5.1, with the calculations in Appendix L.1.

Fixed-confidence procedures. The restarted procedures are theoretical constructions that establish achievable rates for expected evaluation cost when the ES gaps are unknown. The restarts keep the expected cost under control even when confidence bounds fail. We have now clarified this purpose in Section 4, with the detailed construction and guarantees in Appendix I.

Thank you again for your careful review.

Thank you for the clarifications and revisions. They address my concerns.

Reviewer_ut1COpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies sampling from KK candidate models and a reference model to identify the candidate with the lowest Expected Shortfall (ES). The reference model is used to define loss differences between each candidate and the reference, which are assumed to have stronger moment bounds than the individual losses. Two sampling paradigms are considered: 1) all candidates and the reference are evaluated jointly on the same n inputs; and 2) each candidate and the reference are evaluated separately on n independently sampled inputs. Both strategies use (K+1)n(K+1)n model evaluations. The appendix also considers sampling each candidate together with the reference on the same inputs, using independent sets of inputs for different candidates. However, this requires 2Kn2Kn model evaluations.

The paper proposes an estimator for each sampling strategy and provides matching upper and lower bounds on expected simple regret. The upper bounds are for the proposed estimators, while the lower bounds apply to any selection rule under the corresponding protocol and assumptions. It is established that joint sampling leads to a square-root rate, while independent sampling leads to a slower rate depending on the moment assumptions.

The estimators use the Rockafellar–Uryasev representation of ES. Half the samples are used to estimate the quantiles, and the other half to estimate the ES differences using these quantiles. This keeps fitting and evaluation independent. In the symmetric versions, they swap the two halves and average the estimates. The upper-bound analysis uses moment bounds and concentration inequalities, with clipping to control heavy tails. For independent sampling, they also bound the relative truncation bias. The lower bounds use information-theoretic arguments. Extensive numerical results are also provided, although some experiments do not directly test the theoretical results.

Critical strengths
  1. The problem setup is interesting. It allows individual losses to have infinite variance, while loss differences between each candidate and the reference have stronger moment bounds. This captures a useful setting in which sharing inputs can help model selection despite heavy tails.

  2. The paper provides matching upper and lower bounds on minimax expected simple regret for both sampling strategies, using the same number of model evaluations. The lower bounds apply to any selection rule under the stated assumptions. The analysis also accounts for estimating the quantiles needed for ES evaluation. The treatment is thorough. The authors address several natural questions beyond the main theorem, including pairwise sampling. They also show that the lower bound for independent sampling still holds when the reference distribution and population quantiles are known. These results help explain where the separation comes from.

Critical weaknesses

My main comments are:

∙\bullet The presentation is a main weakness. I found the main story difficult to follow in places:

  1. The introduction moves quickly into the problem setup. A clearer explanation early on of the research question, why the proposed approach was chosen, and the main contribution would help.

  2. Related work appears near the end. Discussing the closest work earlier would help clarify how the contribution differs from previous results.

  3. It would help to bring the explanation of the evaluation criterion and its motivation earlier in the paper, alongside the research question. This would make the purpose of the analysis clearer from the start.

  4. The paper addresses many useful questions, but some explanations, including the reasons behind the design choices, are difficult to locate within the dense discussion.

∙\bullet It may be useful to discuss connections to anomaly detection.

∙\bullet Another limitation is that the analysis assumes inputs are i.i.d. across time. A discussion of how temporal dependence might affect the comparison would help clarify the scope of the results.

Questions for authors
  1. In the controlled scaling experiment, the independent-sampling exponent moves closer to the predicted value when smaller gaps are used. Is there evidence that it approaches 17/717/7 as the gap decreases? How sensitive is this behavior to the ES percentile and the number of observations from the informative rare component in each evaluation fold?

  2. As an optional extension, what happens when each model is evaluated on each input with some probability pp, keeping the expected evaluation cost fixed? This would help clarify how partial overlap between samples affects the comparison. Temporally dependent inputs are another natural extension.

2 comments
AuthorsOpenReview ↗

Response to Reviewer ut1C

Thank you for the constructive comments. We really appreciate it. We address your main comments below.

Presentation and motivation. We have revised the Introduction to make the research question clearer before introducing the technical assumptions. It explains why we use ES and now clarifies how our setting differs from earlier work that uses shared inputs for selection by means or bounded scores. To make the estimator design easier to follow, we now explain why we fit quantiles and evaluate scores on separate folds and how the fitting error enters the regret bound (Section 4). The opening of Section 5 also explains what each experiment is meant to show.

Scaling and sensitivity. Following your question about the smaller gaps, we calculated the population RU-score variances for the original mixtures at the six ES gaps. The variances of a suboptimal candidate (V0V_0) and the best candidate (V1V_1) give the sample-size proxy (V0+V1)/Δ2(V_0+V_1)/\Delta^2. The resulting proxy slopes closely match the observed slopes.

  • All six gaps (2.6362.636 observed, 2.6582.658 proxy).
  • Smallest four gaps (2.5782.578 observed, 2.6182.618 proxy).

At the tested tail scales (2.0462.046 to 4.4904.490), the quantile thresholds and unit tail shift still affect how the score variances change with the gap. Both slopes move closer to 17/717/7 over the smallest four gaps, consistent with the finite-gap explanation.

We also checked the two sensitivities you raised.

  • ES level. Recomputing the population variance proxy gives slopes 2.5392.539, 2.6582.658, 2.7492.749, and 2.8512.851 at α=0.90\alpha=0.90, 0.950.95, 0.9750.975, and 0.990.99, respectively.
  • Rare observations. At the reconstructed budgets for 90% correct selection, the expected number of rare-component observations per model per evaluation fold ranges from 198.3198.3 to 1198.31198.3. The probability of observing none in such a fold is below 10−8610^{-86}, so missing the rare component is unlikely to explain the discrepancy.

We have added the finite-gap discussion to Section 5.1, with the sensitivity calculations and observation counts in Appendix L.1.

Thank you again for your helpful suggestions.

Thank you for the clarifications and revisions. I will leave my score as is.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.