# Are all models wrong? Fundamental limits in distribution-free empirical model falsification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 10 Feb 2025.

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

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Theoretical Foundations of Conformal Prediction](https://mlsanity.com/paper/2411.11824/) (2024)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Black-box tests for algorithmic stability](https://mlsanity.com/paper/2111.15546/) (2021)
- [Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression](https://mlsanity.com/paper/2202.09889/) (2022)
- [Estimating Learnability in the Sublinear Data Regime](https://mlsanity.com/paper/1805.01626/) (2018)
- [Distribution-Free Conditional Median Inference](https://mlsanity.com/paper/2102.07967/) (2021)
- [Limitations on approximation by deep and shallow neural networks](https://mlsanity.com/paper/2212.02223/) (2022)
- [The Limits of Assumption-free Tests for Algorithm Performance](https://mlsanity.com/paper/2402.07388/) (2024)

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

- [Is Memorization Helpful or Harmful? Prior Information Sets the Threshold](https://mlsanity.com/paper/2602.09405/) (2026)
- [Learning to Outgrow a Theory: Experimental Discovery Beyond the Initial Hypothesis Space](https://mlsanity.com/paper/2610.07627/) (2026)

## Abstract (arXiv)

In statistics and machine learning, when we train a fitted model on available data, we typically want to ensure that we are searching within a model class that contains at least one accurate model -- that is, we would like to ensure an upper bound on the model class risk (the lowest possible risk that can be attained by any model in the class). However, it is also of interest to establish lower bounds on the model class risk, for instance so that we can determine whether our fitted model is at least approximately optimal within the class, or, so that we can decide whether the model class is unsuitable for the particular task at hand. Particularly in the setting of interpolation learning where machine learning models are trained to reach zero error on the training data, we might ask if, at the very least, a positive lower bound on the model class risk is possible -- or are we unable to detect that "all models are wrong"? In this work, we answer these questions in a distribution-free setting by establishing a model-agnostic, fundamental hardness result for the problem of constructing a lower bound on the best test error achievable over a model class, and examine its implications on specific model classes such as tree-based methods and linear regression.