# The Limits of Assumption-free Tests for Algorithm Performance

arXiv: https://arxiv.org/abs/2402.07388 · HTML: https://mlsanity.com/paper/2402.07388/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 53 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 14 of 14)

- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Model Evaluation, Model Selection, and Algorithm Selection in Machine Learning](https://mlsanity.com/paper/1811.12808/) (2018)
- [Cross-validation: what does it estimate and how well does it do it?](https://mlsanity.com/paper/2104.00673/) (2021)
- [Cross-validation Confidence Intervals for Test Error](https://mlsanity.com/paper/2007.12671/) (2020)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Local permutation tests for conditional independence](https://mlsanity.com/paper/2112.11666/) (2021)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Black-box tests for algorithmic stability](https://mlsanity.com/paper/2111.15546/) (2021)
- [From Fixed-X to Random-X Regression: Bias-Variance Decompositions, Covariance Penalties, and Prediction Error Estimation](https://mlsanity.com/paper/1704.08160/) (2017)
- [Stability revisited: new generalisation bounds for the Leave-one-Out](https://mlsanity.com/paper/1608.06412/) (2016)
- [Distribution-Free Conditional Median Inference](https://mlsanity.com/paper/2102.07967/) (2021)
- [Confidently Comparing Estimators with the c-value](https://mlsanity.com/paper/2102.09705/) (2021)

## Built on by (most cited first, 3 of 3)

- [Are all models wrong? Fundamental limits in distribution-free empirical model falsification](https://mlsanity.com/paper/2502.06765/) (2025)
- [The Relative Instability of Model Comparison with Cross-validation](https://mlsanity.com/paper/2508.04409/) (2025)
- [Cross-Fitting Under Nonregularity: Normality and Inference via Locality](https://mlsanity.com/paper/2610.02944/) (2026)

## Abstract (arXiv)

Algorithm evaluation and comparison are fundamental questions in machine learning and statistics -- how well does an algorithm perform at a given modeling task, and which algorithm performs best? Many methods have been developed to assess algorithm performance, often based around cross-validation type strategies, retraining the algorithm of interest on different subsets of the data and assessing its performance on the held-out data points. Despite the broad use of such procedures, the theoretical properties of these methods are not yet fully understood. In this work, we explore some fundamental limits for answering these questions with limited amounts of data. In particular, we make a distinction between two questions: how good is an algorithm A at the problem of learning from a training set of size n, versus, how good is a particular fitted model produced by running A on a particular training data set of size n? Our main results prove that, for any test that treats the algorithm A as a ``black box'' (i.e., we can only study the behavior of A empirically), there is a fundamental limit on our ability to carry out inference on the performance of A, unless the number of available data points N is many times larger than the evaluation sample size n of interest. On the other hand, evaluating the performance of a particular fitted model can be easy when evaluating an algorithm is hard. We also ask whether an assumption of algorithmic stability might be sufficient to circumvent this hardness result. Surprisingly, we find that the same hardness result still holds for the problem of evaluating the performance of A, aside from a high-stability regime where fitted models are essentially nonrandom. Finally, we also establish similar hardness results for the problem of comparing multiple algorithms.