{"id":"a4f8c6f8-428a-44d0-b536-88c87ea830c6","arxiv_id":"2502.06765","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Distribution-free lower bounds on the best risk achievable in a model class are provably trivial once the class can interpolate far more than n squared points.","lead":"This paper proves a fundamental information-theoretic limit: when a model class can perfectly interpolate far more than n squared data points, no distribution-free lower bound derived from n samples can certify that the class contains no perfect model. The authors map out exactly where such falsification is possible, and show that in a middle regime the answer depends on the model class.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Theorem 4's proof is sound and the distribution-free scope is explicit.","rationale":"The paper's central claim is a distribution-free impossibility theorem. I verified the proof of Theorem 4: for any fixed finite population, validity of the lower bound for the empirical distribution yields the with-replacement inequality, and the TV bound transfers it to without-replacement; exchangeability then gives the result. Corollary 5 follows immediately. The in-between examples are consistent: piecewise constant functions allow nontrivial lower bounds at capacity ~ n^2 because of a birthday-type repetition argument, while linear models are hard for d >> n via a total-variation argument. The reader's weakest assumption is correctly identified as the universal quantifier in Definition 1; this is the load-bearing scope condition, but it is explicit and appropriately handled. No technical error found; verdict unchanged.","tokens_in":29579,"tokens_out":23713,"duration_ms":212097,"concrete_test":"Independently re-derive the total-variation step in the proof of Theorem 4 by computing, for small N and n, the exact TV distance between sampling with and without replacement from an empirical distribution, and verify it is at most n^2/(2N); additionally, simulate the piecewise-constant construction with n=100, m=5000, alpha=0.05 and a non-atomic distribution, confirming the lower bound is positive with empirical frequency at least 0.95.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the sample–resample proof of Theorem 4 (Appendix A.2) and the tightness constructions in Section 4. The universal validity condition in Definition 1 is the key assumption: it is used in the proof to apply the lower bound to the empirical distribution of an arbitrary N-point population. This is a strong guarantee, and the impossibility result would not hold for methods required to be valid only over, e.g., continuous distributions. The paper is explicit about this scope, and the linear-model result (Corollary 9) shows that a nontrivial form of the hardness persists for Gaussian marginals, so the conclusion is not an artifact of discrete distributions. I found no internal gap, circular step, or unsupported technical leap in the main argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29667,"tokens_out":14266,"duration_ms":126437,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§4.2 / Appendix C"},{"comment":"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.","section":"Theorem 6 and Lemma B.1"},{"comment":"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.","section":"§3.3, Theorem 4"},{"comment":"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.","section":"§5.1"},{"comment":"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.","section":"Lemma A.3"},{"comment":"The horizontal axis of the schematic is not labeled; adding 'interpolation capacity N(F,P)' would make the figure self-contained.","section":"Figure 1"}],"recommendation":"minor_revision","confidential_remarks":"This is a well-executed theory paper with correct and complete proofs. The only issues I found are local presentation matters, chiefly a notation clash and a few clarifying statements. The distribution-free scope is the crucial assumption and is stated clearly; I do not see any hidden circularity or unsupported step. The paper fits the scope of a mathematical statistics journal well."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the punchline: this paper gives a clean answer to when a distribution-free lower bound on the model class risk can be nontrivial. The main result—Theorem 4—says that if the class can interpolate N data points with N >> n^2, then any valid lower bound is trivial: it is positive with probability at most alpha + n^2/(2N). That is new and it is proved correctly. I checked the sample–resample argument in Appendix A.2; the use of the universal validity condition to apply the bound to the empirical distribution of a large pool is legitimate, and the total variation bound between sampling with and without replacement is standard.\n\nThe paper also does a few things well. It cleanly separates the low-complexity regime, where the empirical risk itself gives a positive lower bound via Markov, from the high-complexity regime, where nothing nontrivial is possible. The two in-between examples are well chosen: piecewise constant functions show the n^2 threshold is tight, while linear models show that even with interpolation capacity ~ n, a nontrivial bound can be impossible. The related work discussion is careful; the target here is genuinely different from risk of a fitted algorithm.\n\nThe main soft spot is the strength of the distribution-free requirement. Definition 1 demands validity uniformly over every P. If you restrict to a family like smooth distributions with separation, the impossibility can break. The paper states this scope explicitly, so it is not a hidden flaw, but it is the reason the result is about distribution-free inference rather than inference in general. Minor: the appendix computations for the Gaussian case, especially the digamma bounds in Corollary 9, are dense. I did not find an error, but that is where a careful referee should spend time. The open question about a universal complexity notion for the in-between regime is left open, honestly.\n\nOverall, the argument is coherent, the claims are appropriately scoped, and there is no post-hoc fitting. I would bring it to a reading group and would send it to a serious referee.","headline":"Clean distribution-free hardness result for lower-bounding model class risk, with a tight threshold at interpolation capacity n^2; deserves serious refereeing.","tokens_in":30228,"tokens_out":2182,"would_cite":true,"duration_ms":20007,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G05","62G10","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["distribution-free inference","model class risk","lower bounds","interpolation learning","model falsification","risk bounds","overparameterization"],"falsifier":"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.","tokens_in":29377,"feed_emoji":"📉","tokens_out":8597,"duration_ms":70428,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hyper-interpolation makes model falsification impossible","feed_subtitle":"Distribution-free lower bounds on a model class's best risk are trivial once it can interpolate far more than n^2 points.","key_machinery":"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.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the sample–resample strategy used in the proof of Theorem 4.","marker":"Angelopoulos et al. (2024)"},{"why":"Gives the total-variation bound $n^2/(2N)$ between sampling with and without replacement.","marker":"Stam (1978)"},{"why":"Bounds the maximum probability of all $n$ occupied cells being distinct in the piecewise-constant construction.","marker":"Munford (1977)"},{"why":"Provides a lower bound on the expected occupied-cell count used in the sharper piecewise-constant lower bound.","marker":"Lee and Barber (2021)"},{"why":"Gives the Wishart determinant distribution used to compute the Gaussian bound for linear models.","marker":"Goodman (1963)"},{"why":"Supplies the digamma integral representation used to evaluate the Gaussian bound.","marker":"Gordon (1994)"}],"fun_headline_variants":["All models might be wrong, but you can't prove it","Model falsification impossible beyond interpolation threshold","Distribution-free falsification fails beyond n^2 interpolation","When model classes interpolate too much, falsification is futile","Hardness theorem: no valid lower bound for interpolating classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["All models might be wrong, but you can't prove it","Model falsification impossible beyond interpolation threshold","Distribution-free falsification fails beyond n^2 interpolation","When model classes interpolate too much, falsification is futile","Hardness theorem: no valid lower bound for interpolating classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00134,"raw_usage":{"total_tokens":5481,"prompt_tokens":1017,"completion_tokens":4464,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":4385}},"tokens_in":633,"tokens_out":4464,"duration_ms":30108,"temperature":1.0,"reasoning_tokens":4385,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:27:15.383528+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the total-variation bound $n^2/(2N)$ between sampling with and without replacement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bounds the maximum probability of all $n$ occupied cells being distinct in the piecewise-constant construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Wishart determinant distribution used to compute the Gaussian bound for linear models."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the digamma integral representation used to evaluate the Gaussian bound."}],"review_version":1}