Pith. sign in

REVIEW 6 minor 1 cited by

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

T0 review · 0 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that in a distribution-free setting, every valid lower bound on a model class's best risk is trivial once the class can interpolate data sets of size far larger than $n^2$, and that the $n^2$ threshold is sharp.

desk verdict Clean distribution-free hardness result for lower-bounding model class risk, with a tight threshold at interpolation capacity n^2; deserves serious refereeing. read the letter →

arxiv 2502.06765 v2 pith:CZXSHLTB submitted 2025-02-10 math.ST cs.LGstat.MLstat.TH

Manuel M. Müller , Yuetian Luo , Rina Foygel Barber This is my paper · ORCID
classification math.STcs.LGstat.MLstat.TH MSC 62G0562G1068T05
keywords distribution-freeinferencemodelclassrisklowerboundsinterpolationlearningfalsificationoverparameterization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether data alone can certify that a model class contains no perfect model — that is, whether a valid distribution-free lower bound on the model class risk $R_P(\mathcal{F}) = \inf_{f\in\mathcal{F}} R_P(f)$ can ever be positive. The answer is governed by the largest sample size the class can interpolate. If the class can interpolate a data set of size $N \gg n^2$, every valid lower bound is trivial: the probability it exceeds zero is at most $\alpha + n^2/(2N)$, so the popular refrain 'all models are wrong' cannot be verified empirically. If the class cannot interpolate the training data, a positive lower bound always exists; in between, nontrivial bounds are possible for some classes and impossible for others. These results matter because they delimit when model misspecification can be detected without distributional assumptions.

What carries the argument

The key object is the interpolation capacity $N(\mathcal{F}, P)$: the largest sample size for which the model class achieves zero empirical risk almost surely. The key identity is the sample–resample total variation bound, which says that sampling $n$ points with replacement from a population of size $N$ differs from sampling without replacement by at most $n^2/(2N)$ in total variation; the proof of Theorem 4 applies a valid lower bound to the empirical distribution of an arbitrarily large sample and then switches to a subsample of size $n$, forcing the bound to be small. In the low-complexity regime, a simple Markov-inequality argument shows $\alpha \cdot \hat{R}(\mathcal{F}, D_n)$ is already a valid lower bound, so positive empirical risk yields positive certified lower bounds.

What would settle it

Take a model class with interpolation capacity $N \gg n^2$ — for instance, piecewise constant functions on $N$ distinct regions — and a distribution with non-atomic marginals; if any proposed lower bound returns a positive value more often than $\alpha + n^2/(2N)$ on samples of size $n$, Theorem 4 would be contradicted.

Watch

Extended reading notes

Core claim

The paper's central discovery is a model-agnostic hardness theorem: for any valid distribution-free lower bound $\hat{L}_\alpha(\mathcal{F}, \cdot)$, the empirical risk $\hat{R}(\mathcal{F}, D_N)$ of a larger sample of size $N \ge n$ can exceed the bound only with probability at most $\alpha + n^2/(2N)$ (Theorem 4). Consequently, if the model class interpolates data sets of size $N(\mathcal{F}, P) \gg n^2$, then $P\{\hat{L}_\alpha(\mathcal{F}, D_n) > 0\} \le \alpha + o(1)$ for every valid lower bound (Corollary 5), meaning no meaningful falsification of the model class is possible. The paper shows the threshold is tight: piecewise constant functions with up to $m \propto n^2$ components admit a nontrivial valid lower bound (Theorem 6), while linear models with dimension $d \gg n$ admit only trivial lower bounds over a broad class of distributions (Theorem 7 and Corollary 9). Hence there is no universal phase transition at interpolation capacity $n^2$ itself; the in-between regime depends on the structure of $\mathcal{F}$.

Load-bearing premise

The argument requires the lower bound to be valid simultaneously for every distribution on the data; if one only needs guarantees for a restricted family of distributions, the impossibility result can fail.

Editorial extensions

If this is right

  • In the hyper-interpolation regime (capacity $\gg n^2$), no distribution-free procedure can certify $R_P(\mathcal{F}) > 0$ more often than $\alpha + o(1)$; attempts to detect that 'all models are wrong' are futile in that regime.
  • When the model class cannot interpolate the training sample, a positive valid lower bound always exists, so empirical falsification of the class is possible with no distributional assumptions.
  • Between these extremes, feasibility depends on the structure of $\mathcal{F}$: piecewise constant classes allow nontrivial lower bounds with capacity up to order $n^2$, while linear classes with dimension $d \gg n$ allow only trivial bounds.
  • The $n^2$ threshold is tight, so the hardness result cannot be improved by a more clever universal construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Read as an inference: for modern overparameterized architectures whose interpolation capacity vastly exceeds $n^2$, the result suggests that data alone cannot reveal misspecification; any such claim requires distributional assumptions or external benchmarks.
  • The threshold depends on the birthday-effect collision probability $n^2/(2N)$, which hints that a different complexity measure — effective dimension rather than raw interpolation capacity — might yield a sharper phase transition for structured classes.
  • A testable extension: in a fixed model class with known interpolation capacity, one can measure the empirical frequency of positive lower bounds under repeated resampling and check it against $\alpha + n^2/(2N)$.
  • The contrast between piecewise-constant and linear classes implies tree ensembles and kernel machines could behave very differently as falsification targets at similar interpolation capacities.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies when it is possible to construct a valid distribution-free lower bound on the model class risk R_P(F) = inf_{f∈F} R_P(f) from an i.i.d. sample D_n. The main contributions are threefold. First, in the low-complexity regime, if the model class cannot interpolate the training data (Rhat(F,D_n)>0 almost surely), then a positive valid lower bound always exists, e.g. Lhat = α·Rhat(F,D_n) (Theorem 2 and Corollary 3). Second, in the high-complexity regime, if the model class can interpolate N ≫ n^2 points, then every valid distribution-free lower bound is trivial: P{Lhat(F,D_n)>0} ≤ α + n^2/(2N) (Theorem 4 and Corollary 5). Third, the paper exhibits two examples in the intermediate regime N ∈ [n, O(n^2)]: piecewise constant functions admit nontrivial lower bounds even when the interpolation capacity is of order n^2 (Theorem 6), while linear models do not when the feature dimension d ≫ n under Gaussian marginals (Theorem 7 and Corollary 9). All proofs are provided, with detailed appendices for the sharper bounded-loss lower bound, the piecewise-constant extensions, and the linear-model reparameterization argument.

Significance. If the results are correct, this is a clean and useful characterization of when empirical model falsification is possible without distributional assumptions. The hardness result in Theorem 4 is model-agnostic and has a remarkably simple proof via the sample–resample total-variation bound; the bound is explicit with no hidden constants. The examples are well chosen: the piecewise-constant construction shows that the n^2 threshold is sharp as a scaling law, and the linear-model analysis shows that the intermediate regime is genuinely model-dependent rather than an artifact of the proof technique. The paper also contributes a careful reparameterization argument (Proposition 8 and Corollary 9) that may be of independent interest. The distribution-free scope is stated precisely in Definition 1, and the authors are appropriately careful about what their impossibility result does and does not say. Overall, this is a solid theoretical contribution that likely will be useful in the overparameterized-learning and distribution-free-inference literatures.

minor comments (6)
  1. [§4.2 / Appendix C] The symbol P_X is used both for the marginal distribution of X (e.g., 'its marginal P_X is nonatomic' in §4.1 and 'P_X = N(0,Σ)' in Corollary 9) and for the projection matrix onto the row space of X in the proof of Proposition 8; this notational clash is confusing and should be resolved, for instance by writing Π_x or P_row(x) for the projection.
  2. [Theorem 6 and Lemma B.1] The condition m ≤ n(n−1)/(2 log(1/α_0)) forces n ≥ 2, yet the theorem states 'Fix any n ≥ 1'; please either add the assumption n ≥ 2 or note that the statement is vacuous for n = 1.
  3. [§3.3, Theorem 4] The total-variation bound n^2/(2N) is stated in the theorem without a reference; the proof later cites Stam (1978) and Angelopoulos et al. (2024, Lemma 4.15), but adding the citation at the theorem statement would help the reader gauge the provenance of the constant.
  4. [§5.1] The sentence describing Kong and Valiant (2019, Theorem 3) is terse; adding one sentence explaining how their impossibility result relates to the quantity λ_{n,d}(P) would make the connection clearer.
  5. [Lemma A.3] The lemma statement does not mention the degenerate case μ = 0, which is handled only inside the proof; adding a short sentence to the statement would improve readability.
  6. [Figure 1] The horizontal axis of the schematic is not labeled; adding 'interpolation capacity N(F,P)' would make the figure self-contained.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; only a minor non-load-bearing self-citation in an auxiliary appendix bound.

full rationale

The derivation chain is self-contained with respect to circularity. Theorem 4 is a conditional statement valid for any lower bound satisfying Definition 1; its proof applies that validity condition to the empirical distribution of an arbitrary N-tuple and then uses the external Stam sample-resample total-variation bound. Corollary 5 is an immediate substitution of the interpolation capacity, not a restatement of the target. Theorem 2 uses only Markov's inequality together with the elementary E[inf] <= inf E inequality. The piecewise-constant construction in Theorem 6 relies on a standard occupancy bound (Lemma B.1, proved via Munford's uniformity result); the linear-model hardness results use total-variation mixtures, Pinsker's inequality, Goodman's Wishart determinant distribution, and standard concentration tools. No fitted parameter is renamed as a prediction, no uniqueness theorem from the authors' prior work is invoked, and no ansatz is smuggled in via self-citation. The only self-citation, Lee and Barber (2021, Lemma 4), appears in Appendix B.2 to lower-bound E[r(Y)] in the auxiliary extension Lemma B.3; it is a parameter-free technical inequality, and the paper's central claims do not depend on it. Thus there is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard probability tools and no fitted parameters. The only domain-specific assumption is that validity is required for all distributions P, which is part of the problem definition rather than an ad hoc restriction. The paper introduces definitions such as interpolation capacity N(F,P) and N+(F,P) to state the regimes, but these are formal objects, not invented physical or algorithmic entities.

assumptions (5)
  • standard math Total variation distance between sampling n times with replacement and without replacement from a population of size N is at most n^2/(2N).
    Used in the proof of Theorem 4 in Appendix A.2 to compare the original sample with a re-sample from an empirical distribution.
  • standard math Pinsker's inequality: for a nonnegative random variable Z with E[Z] = 1, 1/2 E|Z-1| <= sqrt(1/2 E log(1/Z)).
    Used in Corollary 9 to bound the total variation distance lambda_n,d(P) in the Gaussian linear-model example.
  • standard math Goodman's Wishart determinant result: det(W) for W ~ W_n(I_n, d) is distributed as a product of independent chi-square random variables.
    Used in Corollary 9 to compute expectations of the determinant-based quantity h(X).
  • standard math Markov's inequality and the multiplicative Chernoff bound for sums of bounded random variables.
    Used in Theorem 2 and in the proof of the sharper lower bounds in Appendix A.1.
  • standard math Munford's result that the probability of n distinct observations in an m-category occupancy problem is maximized by the uniform distribution.
    Used in Lemma B.1 to bound the number of unique values observed in the piecewise-constant example.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Are all models wrong? Fundamental limits in distribution-free empirical model falsification." pith.science (2026). https://pith.science/paper/CZXSHLTB

@misc{pith2026250206765,
  author       = {Pith},
  title        = {Pith review of: Are all models wrong? Fundamental limits in distribution-free empirical model falsification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CZXSHLTB}},
  note         = {Machine review of arXiv:2502.06765}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2502.06765 by the authors.

Figure 1
Figure 1. A schematic depiction of the role of the complexity of [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Is Memorization Helpful or Harmful? Prior Information Sets the Threshold

    stat.ML 2026-02 accept novelty 6.0 of 10

    For any smooth prior in overparameterized Bayesian linear regression, training error of order J_πσ⁴ (memorization) is forced when σ² ≲ J_π^{-1}, and training error below σ² − V_π (harmful overfitting) is forbidden whe...

Reference graph

Works this paper leans on

39 extracted references · 32 canonical work pages · cited by 1 Pith paper

  1. [1]

    N., Barber, R

    Angelopoulos, A. N., Barber, R. F., and Bates, S. (2024). Theoretical foundations of conformal prediction. arXiv preprint arXiv:2411.11824

    arXiv 2024

  2. [2]

    N., Bates, S., Cand \`e s, E

    Angelopoulos, A. N., Bates, S., Cand \`e s, E. J., Jordan, M. I., and Lei, L. (2025). Learn then test: Calibrating predictive algorithms to achieve risk control . The Annals of Applied Statistics , 19(2):1641--1662

    work page 2025

  3. [3]

    N., Bates, S., Fisch, A., Lei, L., and Schuster, T

    Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L., and Schuster, T. (2023). Conformal risk control. arXiv preprint arXiv:2208.02814

    arXiv 2023

  4. [4]

    Bahadur, R. R. and Savage, L. J. (1956). The nonexistence of certain statistical procedures in nonparametric problems. The Annals of Mathematical Statistics , 27(4):1115--1122

    work page 1956

  5. [5]

    Barber, R. F. (2020). Is distribution-free inference possible for binary regression? Electronic Journal of Statistics , 14:3487--3524

    work page 2020

  6. [6]

    F., Cand \`e s, E

    Barber, R. F., Cand \`e s, E. J., Ramdas, A., and Tibshirani, R. J. (2021). The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA , 10(2):455--482

    2021

  7. [7]

    Barron, A. R. (1994). Approximation and estimation bounds for artificial neural networks. Machine learning , 14:115--133

    work page 1994

  8. [8]

    L., Boucheron, S., and Lugosi, G

    Bartlett, P. L., Boucheron, S., and Lugosi, G. (2002). Model selection and error estimation. Machine Learning , 48:85--113

    work page 2002

Show all 39 references
  1. [9]

    L., Long, P

    Bartlett, P. L., Long, P. M., Lugosi, G., and Tsigler, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences , 117(48):30063–30070

    2020

  2. [10]

    Bates, S., Angelopoulos, A., Lei, L., Malik, J., and Jordan, M. (2021). Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM) , 68(6):1--34

    2021

  3. [11]

    Belkin, M., Hsu, D., Ma, S., and Mandal, S. (2019a). Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences , 116(32):15849--15854

    2019

  4. [12]

    J., and Mitra, P

    Belkin, M., Hsu, D. J., and Mitra, P. (2018). Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate . Advances in neural information processing systems , 31

    2018

  5. [13]

    Belkin, M., Rakhlin, A., and Tsybakov, A. B. (2019b). Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics , pages 1611--1619. PMLR

    2019

  6. [14]

    Ben-Hamou, A., Boucheron, S., and Ohannessian, M. I. (2017). Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications. Bernoulli , 23(1):249--287

    2017

  7. [15]

    and Bousquet, O

    Bottou, L. and Bousquet, O. (2007). The Tradeoffs of Large Scale Learning . In Advances in Neural Information Processing Systems , volume 20. Curran Associates, Inc

    2007

  8. [16]

    Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence

    2013

  9. [17]

    Box, G. E. (1976). Science and statistics. Journal of the American Statistical Association , 71(356):791--799

    1976

  10. [18]

    Cheng, C., Duchi, J., and Kuditipudi, R. (2022). Memorize to generalize: on the necessity of interpolation in high dimensional linear regression. In Conference on Learning Theory , pages 5528--5560. PMLR

    2022

  11. [19]

    DeVore, R., Hanin, B., and Petrova, G. (2021). Neural network approximation. Acta Numerica , 30:327–444

    2021

  12. [20]

    Devroye, L., Gy \"o rfi, L., and Lugosi, G. (1996). A probabilistic theory of pattern recognition , volume 31. Springer Science & Business Media

    1996

  13. [21]

    Goodman, N. (1963). The distribution of the determinant of a complex wishart distributed matrix. The Annals of Mathematical Statistics , 34(1):178--180

    1963

  14. [22]

    Gordon, L. (1994). A stochastic approach to the gamma function. The American Mathematical Monthly , 101(9):858--865

    1994

  15. [23]

    Hoeffding, W. (1962). Probability inequalities for sums of bounded random variables. Institute of Statistics, Mimeo Series No. 326

    1962

  16. [24]

    and Barber, R

    Kim, B. and Barber, R. F. (2023). Black-box tests for algorithmic stability. Information and Inference: A Journal of the IMA , 12(4):2690--2719

    2023

  17. [25]

    and Zhivotovskiy, N

    Klochkov, Y. and Zhivotovskiy, N. (2021). Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n) . In Advances in Neural Information Processing Systems , volume 34, pages 5065--5076. Curran Associates, Inc

    2021

  18. [26]

    and Valiant, G

    Kong, W. and Valiant, G. (2019). Estimating learnability in the sublinear data regime. arXiv preprint arXiv:1805.01626

    2019 arXiv

  19. [27]

    and Barber, R

    Lee, Y. and Barber, R. (2021). Distribution-free inference for regression: discrete, continuous, and in between. Advances in Neural Information Processing Systems , 34:7448--7459

    2021

  20. [28]

    and Wasserman, L

    Lei, J. and Wasserman, L. (2014). Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology , 76(1):71--96

    2014

  21. [29]

    and Barber, R

    Luo, Y. and Barber, R. F. (2024). The limits of assumption-free tests for algorithm performance. arXiv preprint arXiv:2402.07388

    2024

  22. [30]

    McDiarmid, C. (1998). Concentration. In Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., and Reed, B., editors, Probabilistic Methods for Algorithmic Discrete Mathematics , volume 16, pages 195--248. Springer

    1998

  23. [31]

    and Cand \`e s, E

    Medarametla, D. and Cand \`e s, E. (2021). Distribution-free conditional median inference. Electronic Journal of Statistics , 15(2):4625--4658

    2021

  24. [32]

    and Ga\" ffas, S

    Mourtada, J. and Ga\" ffas, S. (2022). An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. Journal of Machine Learning Research , 23(31):1--49

    2022

  25. [33]

    Munford, A. (1977). A note on the uniformity assumption in the birthday problem. The American Statistician , 31(3):119--119

    1977

  26. [34]

    and Wojtaszczyk, P

    Petrova, G. and Wojtaszczyk, P. (2023). Limitations on approximation by deep and shallow neural networks. Journal of Machine Learning Research , 24(353):1--38

    2023

  27. [35]

    and Ben-David, S

    Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms . Cambridge University Press

    2014

  28. [36]

    Stam, A. J. (1978). Distance between sampling with and without replacement. Statistica Neerlandica , 32(2):81--91

    1978

  29. [37]

    Tropp, J. A. (2012). User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics , 12:389--434

    2012

  30. [38]

    and Schölkopf, B

    von Luxburg, U. and Schölkopf, B. (2011). Statistical learning theory: Models, concepts, and results. In Gabbay, D. M., Hartmann, S., and Woods, J., editors, Inductive Logic , volume 10 of Handbook of the History of Logic , pages 651--706. North-Holland

    2011

  31. [39]

    Vovk, V. (2012). Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning , volume 25, pages 475--490. PMLR

    2012

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.