{"id":"3678c125-4ddb-4a3e-9505-5565f93fe614","arxiv_id":"2411.12029","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"ERM over a union of linear feature classes achieves excess risk within a factor of two of the oracle that knows the optimal feature map, asymptotically, under size conditions on the feature set.","lead":"This paper proves that, for regression with squared error, empirical risk minimization over a large set of candidate feature maps is asymptotically nearly as accurate as a procedure that already knows the best feature map, as long as the candidate set is not too large. A companion finite-sample bound shows how the influence of the candidate set decays with sample size, but that bound has a gap in its stated sample size condition.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's sample-size condition lacks squares on the expected suprema; as stated it is not sufficient for the Appendix F proof.","rationale":"The reader's rationale identifies the same load-bearing issue: Theorem 4's sample-size condition is not sufficient according to the Appendix F proof. I agree with that assessment and with the CONDITIONAL verdict. I do not fully agree with the reader's choice of weakest_assumption: the Glivenko-Cantelli/Donsker assumptions are explicitly scoped as 'T is not too large' restrictions and are not internally inconsistent, whereas the sample-size mismatch is a concrete algebraic error in a displayed theorem. The asymptotic core of the paper, Theorem 3, appears coherent: the localization proof via Lemma 4, the continuous-mapping arguments, and the quantile bounds are internally consistent, and the paper is transparent about limitations such as optimization and infinite-T estimates. The finite-sample theorem is a major part of the claimed contribution, so the missing squares on the expected suprema should be corrected before acceptance; once corrected, the proof appears to go through. Hence the paper should remain conditional rather than being rejected or accepted unconditionally.","tokens_in":27414,"tokens_out":11417,"duration_ms":122252,"concrete_test":"Re-derive the threshold in Appendix F by solving the proof's two displayed sufficient inequalities for n. Then test the theorem's condition with E[sup Λ_n] = 10, E[sup ∆_n] = 0, δ = 0.1, and the log term negligible: the stated condition allows n = 640, but substituting into the proof's bound gives 2·10/√640 ≈ 0.79 > 1/2, so the event A_n(t*) is not guaranteed. Independently, replace the linear terms by n ≥ 64(E[sup Λ_n])^2 + (128L+11)log(6/δ) + 144δ^{-2}(E[sup ∆_n])^2 and verify that the union-bound algebra in Appendix F closes; if it does, the concern is resolved and the theorem's statement can be corrected accordingly.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Appendix F proves Theorem 4 by making ||n^{-1/2}Λ_n||_{\\infty,+} ≤ 1/2 and ||n^{-1/2}∆_n(·,t*)||_{\\infty,+} ≤ 1/2, each on an event of probability at least 1−δ/6. The proof's own displayed inequalities are ||n^{-1/2}Λ_n||_+ ≤ 2n^{-1/2}E[sup Λ_n] + sqrt(2L log(6/δ)/n) + 4 log(6/δ)/(3n) and ||n^{-1/2}∆_n||_+ ≤ 6δ^{-1}n^{-1/2} E[sup ∆_n]. Requiring these to be at most 1/2 gives, up to the logarithmic term, n ≥ 64(E[sup Λ_n])^2 and n ≥ 144 δ^{-2}(E[sup ∆_n])^2. The theorem instead states n ≥ 64E[sup Λ_n] + (128L+11)log(6/δ) + 6δ^{-2}E[sup ∆_n], which is linear in the expected suprema. For a parameter value E[sup Λ_n] = 10, the stated condition passes at n = 640, while the proof's sufficient condition requires n = 6400. Thus the claimed implication 'if n satisfies ... then with probability at least 1−δ' is not established by the supplied argument. This is a load-bearing gap for the finite-sample guarantee and for the sample-size discussion in Example 1, although the asymptotic Theorem 3 and the localization message appear unaffected and the flaw is likely correctable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies empirical risk minimization (ERM) over the union of linear classes induced by a collection of feature maps (φ_t)_{t∈T}, with square loss. The main asymptotic result, Theorem 3, states that under Glivenko-Cantelli and Donsker assumptions on the empirical processes Λ_n, Δ_n and G_n, ERM selects near-optimal feature maps with probability tending to one, and the asymptotic quantiles of n times the excess risk are controlled from above and below by the extrema of a limiting Gaussian process over the set T* of optimal feature maps; with a unique optimal feature map the quantiles lie, up to a factor of two, between those of the oracle procedure. Theorem 4 gives a non-asymptotic localization bound in terms of iterated sublevel sets F_{n,δ}^k(T), and the finite-index case is made explicit in Corollaries 1 and 2. The paper closes with an application to best subset selection in sparse linear regression.","tokens_in":27702,"tokens_out":10486,"duration_ms":122177,"significance":"If the main results are correct, this is a substantial contribution. The asymptotic message that the global complexity of T disappears once T is 'not too large', leaving only the complexity of T*, is a strong and non-obvious localization statement for a non-convex learning problem. The paper also provides a generally applicable non-asymptotic template with explicit constants and no fitted parameters, and it gives new guarantees for best subset selection under general moment assumptions. The derivation of explicit estimates for finite T, including the use of expected suprema and matrix concentration, is a useful technical contribution. The two issues raised below are localized and do not undermine the overall research programme, but they do affect load-bearing statements and must be fixed before the paper can be accepted.","major_comments":[{"comment":"The quantile tail step is not justified as written. After obtaining the bound P(G_n^2(hat_t_n) > x) ≤ P(sup_{s∈T*(ε_k)} G_n^2(s) > x) + P(hat_t_n ∉ T*(ε_k)), the proof passes to the limit k→∞ by saying that the events {sup_{s∈T*(ε_k)} G^2(s)>x} are nested and using continuity from above, recalling that ∩_k T*(ε_k)=T*. In general these events do not converge to {sup_{s∈T*} G^2(s)>x}: if T contains points t_j with R(t_j,w*(t_j))-R*→0 and G(t_j)>x, while sup_{T*}G^2<x, then the event holds for every finite k but fails in the limit. The analogous lower-bound argument has the same problem in the opposite direction: the union of {inf_{s∈T*(ε_k)} G^2(s)>x} need not equal {inf_{s∈T*} G^2(s)>x}. This is not merely a cosmetic issue, because the theorem's conclusion is precisely an upper and lower quantile statement in terms of the sup and inf over T*. The proof needs an explicit epsilon argument, or an additional regularity condition on the behaviour of the limiting Gaussian process near T*\\T*, to control the contribution of near-optimal feature maps. The Glivenko-Cantelli assumption on Δ_n is a plausible source for such control, but it is not used in this part of the proof.","section":"Appendix D, proof of Theorem 3"},{"comment":"The sample-size condition in Theorem 4 is inconsistent with the proof in Appendix F. The proof requires the events ||n^{-1/2}Λ_n||_{∞,+} ≤ 1/2 and ||n^{-1/2}Δ_n(·,t*)||_{∞,+} ≤ 1/2 to hold with probability at least 1−δ/3, and obtains bounds of the form ||n^{-1/2}Λ_n||_{∞,+} ≤ 2n^{-1/2}E[sup Λ_n] + O(√(log(1/δ)/n)) and ||n^{-1/2}Δ_n(·,t*)||_{∞,+} ≤ 6δ^{-1}n^{-1/2} E[sup Δ_n]. Requiring these to be at most 1/2 forces, up to logarithmic terms, n ≥ C(E[sup Λ_n])^2 and n ≥ C'δ^{-2}(E[sup Δ_n])^2. The theorem instead states n ≥ 64E[sup Λ_n] + (128L+11)log(6/δ) + 6δ^{-2}E[sup Δ_n], which is linear in the expected suprema. For instance, with E[sup Λ_n]=10 the stated condition passes at n=640, while the proof's condition requires n=6400. Thus the implication 'if n satisfies ... then with probability at least 1−δ' is not established by the supplied argument. This affects the finite-sample guarantee of Theorem 4 and the sample-size discussion in Example 1, although the asymptotic Theorem 3 and the localization message appear unaffected. The fix is likely straightforward, but the statement and the proof must be aligned.","section":"Theorem 4 statement vs. Appendix F"}],"minor_comments":[{"comment":"In the definition of the event A_n(t*), the second norm is written as ||n^{-1/2}Δ_n(·,t*)|| ≤ 1/2 without the subscript ∞,+, unlike the first norm; the intended one-sided sup norm should be stated consistently.","section":"Appendix F"},{"comment":"There is a typo: 'Koltchinski i [Kol06]' should read 'Koltchinskii [Kol06]'.","section":"Appendix F"},{"comment":"The text 'We do not known of a matching non-asymptotic lower bound' contains a grammatical typo; it should read 'We do not know of'.","section":"Section 4"},{"comment":"The displayed support-recovery condition n > min_k {4k(γδ)^{-1} A(~F_{n,δ/2k}^{k-1}(T))} is asserted without derivation; a short explanation of how it follows from Corollary 2 would improve readability.","section":"Example 1"},{"comment":"Even after correcting the sample-size condition, the stated inequality is dimensionally suspicious because n is required to be at least a quantity that is linear in objects of order √n; the squared version suggested by Appendix F is more natural.","section":"Theorem 4 statement"}],"recommendation":"major_revision","confidential_remarks":"The Theorem 4 mismatch is an algebraic inconsistency that is clearly repairable. The Appendix D quantile tail gap is more delicate, but I do not think it is fatal: the uniform control on Δ_n provided by the Glivenko-Cantelli assumption is a plausible route to the missing epsilon argument. I recommend major revision rather than rejection, and I would expect the revised version to be acceptable if the two load-bearing points are addressed and the minor presentation issues are cleaned up."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The asymptotic result is the real contribution. Theorem 3 shows that, under Glivenko-Cantelli and Donsker assumptions, the excess risk quantiles of ERM over a union of feature classes are sandwiched between the extrema of a limiting Gaussian process on the optimal feature maps T*. With a unique optimal map, that gives the oracle risk up to a factor of two. That is a clean and genuinely new statement: the global complexity of T asymptotically drops out, leaving only the complexity of T*. The proof of Theorem 3, including the quantile tail argument, is basically sound; the small epsilon details in the Donsker step are routine. I believe this part of the paper.\n\nThe localization template in Theorem 4 is also a useful conceptual contribution, and the paper is honest about its limits: no optimization guarantees, no concrete infinite-T bounds, and the conclusion in Section 5 is appropriately cautious.\n\nNow the soft spot, and it is load-bearing. The statement of Theorem 4 says the sample size condition is linear in E[sup Λ_n] and E[sup Δ_n]. But the proof in Appendix F needs those quantities squared. Concretely, the proof requires ||n^{-1/2} Λ_n||_+ ≤ 1/2 and ||n^{-1/2} Δ_n||_+ ≤ 1/2 on high-probability events. The displayed inequalities give terms like 2 n^{-1/2} E[sup Λ_n] and 6 δ^{-1} n^{-1/2} E[sup Δ_n], so to get below 1/2 you need n ≥ c (E[sup Λ_n])^2 and n ≥ c δ^{-2} (E[sup Δ_n])^2. The stated condition passes at much smaller n. For a concrete value like E[sup Λ_n] = 10, the stated condition allows n = 640 when the proof needs n = 6400. So the finite-sample guarantee, as stated, is not established by the supplied argument. That also affects the sample-size discussion in Example 1, which relies on Corollary 2's version of this bound.\n\nThe good news: this is very likely a fixable error. The proof strategy works if the theorem is restated with squares, or if the proof is adjusted with a different concentration argument. The asymptotic Theorem 3 and the localization message do not depend on this particular sample-size condition.\n\nWho should read this: anyone working on ERM, localization, or feature learning theory. The asymptotic oracle equivalence is a solid benchmark result, and the paper is worth serious refereeing despite the finite-sample gap. I would accept it for peer review with a request to correct or weaken Theorem 4. If I were the editor, I would not desk-reject; I would send it out and let the referees check the fix.","headline":"The asymptotic oracle-equivalence result is new and worth engaging; the non-asymptotic Theorem 4 has a sample-size condition that the supplied proof does not establish, though the flaw looks correctable.","tokens_in":28243,"tokens_out":1428,"would_cite":true,"duration_ms":15824,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G20","62J05","62G08"],"pacs":[],"model":"deepseek-v4-flash","headline":"ERM pays no asymptotic price for learning the best feature map.","keywords":["feature learning","empirical risk minimization","excess risk","square loss","empirical processes","localization","best subset selection","sparse linear regression"],"falsifier":"Simulate a regression problem with a unique optimal feature map and a rival map whose suboptimality gap decays polynomially with $n$; Theorem 3 predicts that the quantiles of $n$ times the excess risk lie between $\\tfrac12 Q_Z$ and $Q_Z$ asymptotically and that the rival map is chosen with vanishing probability. Data showing persistent selection of the suboptimal map or quantile ratios outside this interval would falsify the claim.","tokens_in":27195,"feed_emoji":"📉","tokens_out":6404,"duration_ms":56198,"temperature":0.7,"pith_summary":"This paper asks how much statistical efficiency is lost when a model must also choose a feature map, rather than being handed the right one. In a regression setting with square loss, ERM over the union of linear classes induced by a collection of feature maps is shown to pay no asymptotic price for feature selection whenever the collection is not too large. The main asymptotic result says that the quantiles of the excess risk are sandwiched between half and once the oracle quantiles, where the oracle knows the optimal feature map in advance; with a unique optimal feature map, ERM is asymptotically equivalent to the oracle up to a factor of two. The non-asymptotic companion result shows that the influence of the global complexity of the feature map set decays with sample size and eventually depends only on the optimal feature maps, with rates governed by the sublevel sets of feature suboptimality. As an application, the paper derives new support recovery and excess risk guarantees for best subset selection in sparse linear regression.","feed_headline":"ERM learns optimal features at no asymptotic cost","feed_subtitle":"When candidate features are few enough, ERM's excess risk matches an oracle that knows the best map, up to a factor of two.","key_machinery":"The central objects are three $\\mathcal{T}$-indexed empirical processes: $\\Lambda_n(t)$ measures how far the sample covariance of feature map $t$ is from its population covariance, $G_n(t)$ is the scaled norm of the empirical risk gradient at the population minimizer, and $\\Delta_n(t,t_*)$ measures the relative deviation of an empirical suboptimality gap from the population gap for a suboptimal map $t$. A core lemma expresses the excess risk of ERM as $\\tfrac12 n^{-1} G_n^2(\\hat{t}_n)$ multiplied by factors involving the suprema of $\\Lambda_n$ and $\\Delta_n$, provided those suprema stay below one. This reduces the problem to controlling the upper tail of $G_n(\\hat{t}_n)$ near the optimal set $\\mathcal{T}_*$, which is where the Donsker assumption enters. The non-asymptotic analysis uses iterative localization: repeated applications of the set contraction $F_{n,\\delta}(S) = \\{t : R(t,w_*(t))-R_* \\le 2(n\\delta)^{-1} \\mathbb{E}[\\sup_{s\\in S} G_n^2(s)]\\}$ shrink the candidate set to $\\mathcal{T}_*$.","core_discovery":"Under Glivenko–Cantelli conditions on the $\\mathcal{T}$-indexed empirical processes $\\Lambda_n$, $\\Delta_n$ and $G_n$, and a Donsker condition on $G_n$, Theorem 3 shows that any sequence of empirical risk minimizers converges to the set $\\mathcal{T}_*$ of optimal feature maps in risk: $R(\\hat{t}_n, w_*(\\hat{t}_n)) - R_* \\to 0$ in probability. For the rescaled excess risk $n \\cdot E(\\hat{t}_n, \\hat{w}_n)$, the asymptotic quantiles satisfy $\\tfrac12 Q_{Z_-}(1-\\delta) \\le \\liminf_{n\\to\\infty} n \\cdot Q_{E(\\hat{t}_n,\\hat{w}_n)}(1-\\delta) \\le \\limsup_{n\\to\\infty} n \\cdot Q_{E(\\hat{t}_n,\\hat{w}_n)}(1-\\delta) \\le Q_{Z_+}(1-\\delta)$, where $Z_- := \\inf_{s\\in\\mathcal{T}_*} \\|Z(s)\\|_2^2$, $Z_+ := \\sup_{s\\in\\mathcal{T}_*} \\|Z(s)\\|_2^2$, and $(Z(t))_{t\\in\\mathcal{T}}$ is the limiting Gaussian process with covariance $\\Sigma^{-1/2}(t)G(t,s)\\Sigma^{-1/2}(s)$. When $\\mathcal{T}_* = \\{t_*\\}$, this says that asymptotically ERM performs as well as the oracle that already knows $t_*$, up to a factor of two.","pith_inferences":["One consequence the paper leaves implicit is that this localization mechanism may help explain why overparameterized models can generalize despite large model classes: after enough samples, the effective complexity is that of the near-optimal features, not the full parameterization.","The factor-two gap between the upper and lower asymptotic quantiles for infinite $\\mathcal{T}$ may be improvable in symmetric cases; a natural test is whether the exact asymptotic distribution is $\\tfrac12\\|Z\\|^2$ when $\\mathcal{T}_*$ is a singleton and $\\mathcal{T}$ is infinite but small in the required empirical-process sense.","The sublevel-set viewpoint suggests a concrete experimental probe: for a given feature library, measure the expected supremum of $G_n^2$ over sublevel sets of feature suboptimality; the theory predicts that this quantity, not the raw size of $\\mathcal{T}$, sets the excess risk."],"forward_implications":["Asymptotically, ERM selects a near-optimal feature map with probability approaching one, so feature selection does not degrade the rate of excess risk decay in the large-$n$ regime.","For finite collections of feature maps with a unique optimal map, $n$ times the excess risk converges in distribution to $\\tfrac12\\|Z\\|_2^2$, exactly the oracle limit, so there is no asymptotic price for feature learning.","The global complexity of $\\mathcal{T}$ enters the non-asymptotic bound only through shrinking sets $F_{n,\\delta}^k(\\mathcal{T})$, which converge to $\\mathcal{T}_*$; for moderate sample sizes the excess risk is of order $n^{-1}$ with constants determined by sublevel sets of the suboptimality function.","In sparse linear regression, best subset selection asymptotically recovers the true support, and its excess risk is bounded by $(\\sigma^2 s/n)a_n$ with $a_n \\to 1$, replacing the usual $\\log(d/s)$ factor by a factor that decays to one on a single instance."],"supporting_citations":[{"why":"Supplies the iterative localization method used to shrink the candidate set and prove the non-asymptotic bound.","marker":"[Kol06]"},{"why":"Provides the Glivenko-Cantelli and Donsker definitions and the empirical-process framework in which Theorem 3 is stated.","marker":"[VW96]"},{"why":"Gives the matrix Bernstein inequality used to control the spectral process $\\Lambda_n$ for finite $\\mathcal{T}$.","marker":"[Tro15]"},{"why":"Establishes that one-sided empirical-process control suffices for excess risk bounds, a principle the paper's non-asymptotic analysis builds on.","marker":"[Men14]"},{"why":"Provides the closest existing best-subset-selection guarantee that this paper's moderate-sample excess risk result sharpens.","marker":"[She+13]"},{"why":"Supplies the minimax benchmark $\\sigma^2 s \\log(d/s)/n$ for sparse regression that the paper's instance-dependent bound is compared against.","marker":"[RWY11]"}],"fun_headline_variants":["ERM nearly matches oracle in feature learning","Feature learning: ERM's risk at most 2x oracle","ERM learns optimal features at no asymptotic cost","ERM's excess risk: within a factor of two of the best","When features are few, ERM rivals an all-knowing oracle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the set of candidate feature maps is small enough, in the sense measured by the paper's empirical processes, that the error terms behave uniformly as the sample size grows; if that premise fails, ERM may keep selecting suboptimal feature maps and the oracle equivalence can break down.","fun_headline_variants_meta":{"raw":{"variants":["ERM nearly matches oracle in feature learning","Feature learning: ERM's risk at most 2x oracle","ERM learns optimal features at no asymptotic cost","ERM's excess risk: within a factor of two of the best","When features are few, ERM rivals an all-knowing oracle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000323,"raw_usage":{"total_tokens":1900,"prompt_tokens":1113,"completion_tokens":787,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":729,"completion_tokens_details":{"reasoning_tokens":704}},"tokens_in":729,"tokens_out":787,"duration_ms":7769,"temperature":1.0,"reasoning_tokens":704,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:00:57.223787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate a regression problem with a unique optimal feature map and a rival map whose suboptimality gap decays polynomially with $n$; Theorem 3 predicts that the quantiles of $n$ times the excess risk lie between $\\tfrac12 Q_Z$ and $Q_Z$ asymptotically and that the rival map is chosen with vanishing probability. Data showing persistent selection of the suboptimal map or quantile ratios outside this interval would falsify the claim.","supporting_citations":[],"review_version":1}