Locally minimax optimal confidence sets for the best model

Ilmun Kim, Aaditya RamdasarXiv 2025 · DOI · arXiv

Abstract

This paper addresses a fundamental problem in statistical inference: identifying the index (or indices) corresponding to the smallest component of an unknown mean vector $\boldsymbol{\mu}$ based on $n$ observations. We reduce this problem to a series of hypothesis tests to determine if a specific model $r$ is the best. Building on the sample splitting and self-normalization techniques of Kim and Ramdas (2024), we propose "dimension-agnostic" tests that maintain validity regardless of the number of models $d$ or the presence of ties. Our approach requires only mild moment conditions and accommodates strong dependencies between coordinates. We establish the local minimax separation rate for this problem, showing that our tests adapt to the size of the "confusion set." Furthermore, we introduce robust variants for heavy-tailed distributions and demonstrate that multi-split aggregation effectively recovers the power lost to sample splitting. Empirical evaluations on simulated and real-world datasets confirm that our method provides superior error control and tighter confidence sets compared to existing benchmarks.

Introduction

In many modern scientific and engineering workflows, researchers must select the best-performing model or treatment from a large pool of candidates. This task, known as discrete argmin inference, is ubiquitous in machine learning (e.g., selecting the best LLM for a task) and clinical trials.

Traditional methods for constructing confidence sets for the best model often struggle with three primary challenges:

  1. High Dimensionality: The number of models $d$ may be much larger than the sample size $n$.
  2. Correlation: Models are typically evaluated on the same test set, leading to highly correlated performance scores.
  3. Distributional Assumptions: Many existing tests rely on strict Gaussianity or specific parametric forms that do not hold in practice.

This paper introduces a framework that is robust to these issues, providing a fast, dimension-agnostic solution that achieves theoretical optimality.

The Dimension-Agnostic (DA) Framework

The core of the proposed approach is a two-stage procedure utilizing sample splitting and self-normalization to test the null hypothesis that a specific model $r$ is the best.

1. Selection (First Half of Data)

The first half of the data is used to identify a "runner-up" model—the strongest competitor to the target model $r$. The authors propose two selection strategies:

  • Plug-in Estimator: Selecting the model with the lowest empirical mean.
  • Noise-Adjusted Estimator: Selecting the model that maximizes the signal-to-noise ratio relative to $r$, accounting for the variance of each model. This is particularly effective in heteroskedastic settings.

2. Inference (Second Half of Data)

The second half of the data is used to conduct a one-sided, self-normalized t-test. By comparing model $r$ only against the selected runner-up, the test avoids the "look-ahead" bias and maintains validity regardless of the total number of models $d$.

To mitigate the power loss inherent in using only half the data for inference, the authors employ multi-split aggregation. By repeating the split multiple times and aggregating the resulting p-values, the method achieves high statistical power while maintaining strict Type I error control.

Theoretical Guarantees

A key contribution of this work is the characterization of the local minimax separation rate. The difficulty of identifying the best model depends on the "confusion set"—the group of models whose performance is nearly identical to the true best. The authors prove that their DA test is locally minimax optimal, meaning it adapts its sensitivity to the specific geometry of the means and the size of the confusion set, rather than relying on a pessimistic global bound.

Additionally, the paper introduces robust variants using Median-of-Means (MoM) estimators. These variants extend the validity of the confidence sets to heavy-tailed distributions where only a finite second moment is assumed, ensuring reliability even in the presence of extreme outliers.

Empirical Performance

Simulations

In synthetic tests using multivariate Normal and heavy-tailed $t$-distributions, the DA framework demonstrated:

  • Strict Error Control: Unlike competing methods like Leave-One-Out (LOO), which can be overly liberal, the DA tests consistently respected the nominal Type I error rate.
  • Superior Power: The noise-adjusted variant with multi-split aggregation (DA-adjx10) outperformed existing methods, especially in high-dimensional and heteroskedastic scenarios.

Real-World Application

The method was applied to classification competition datasets from 2023 and 2024. In the 2023 dataset (comprising 44 models), the proposed method generated a 95% confidence set containing an average of 17.3 models. In contrast, traditional methods like the Model Confidence Set (MCS) or csranks returned much larger, less informative sets (often including nearly all 44 models).

Furthermore, the DA method is computationally efficient. While bootstrap-based MCS methods can take several minutes to compute, the DA tests execute in less than 0.01 seconds, making them suitable for large-scale model selection tasks.

Conclusion

The dimension-agnostic framework provides a robust and theoretically grounded solution for discrete argmin inference. By combining sample splitting with noise-adjusted selection and multi-split aggregation, the authors provide a tool that is both mathematically optimal and practically superior to existing benchmarks. Future research may extend this logic to rank-$k$ inference or explore thresholding techniques to further enhance power in complex model landscapes.

Summary updated

Abstract

This paper tackles a fundamental inference problem: given $n$ observations from a distribution $P$ over $\mathbb{R}^d$ with unknown mean $\boldsymbolμ$, we must form a confidence set for the index (or indices) corresponding to the smallest component of $\boldsymbolμ$. By duality, we reduce this to testing, for each $r$ in $1,\ldots,d$, whether $μ_r$ is the smallest. Based on the sample splitting and self-normalization approach of Kim and Ramdas (2024), we propose "dimension-agnostic" tests that maintain validity regardless of how $d$ scales with $n$, and regardless of arbitrary ties in $\boldsymbolμ$. Notably, our validity holds under mild moment conditions, requiring little more than finiteness of a second moment, and permitting possibly strong dependence between coordinates. In addition, we establish the \emph{local} minimax separation rate for this problem, which adapts to the cardinality of a confusion set, and show that the proposed tests attain this rate. Furthermore, we develop robust variants that continue to achieve the same minimax rate under heavy-tailed distributions with only finite second moments. While these results highlight the theoretical strength of our method, a practical concern is that sample splitting can reduce finite-sample power. We show that this drawback can be substantially alleviated by the multi-split aggregation method of Guo and Shah (2025). Finally, empirical results on simulated and real data illustrate the strong performance of our approach in terms of type I error control and power compared to existing methods.
BibTeX
@misc{kim2025locally,
  author = {Ilmun Kim and Aaditya Ramdas},
  title = {{Locally minimax optimal confidence sets for the best model}},
  year = {2025},
  eprint = {2503.21639},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.21639},
  howpublished = {arXiv},
}
Figure