REVIEW 2 major objections 5 minor 10 references
On the Efficiency of ERM in Feature Learning
T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read ERM pays no asymptotic price for learning the best feature map.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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}_*$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Appendix D, proof of Theorem 3] 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.
- [Theorem 4 statement vs. Appendix F] 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.
minor comments (5)
- [Appendix F] 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.
- [Appendix F] There is a typo: 'Koltchinski i [Kol06]' should read 'Koltchinskii [Kol06]'.
- [Section 4] 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'.
- [Example 1] 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.
- [Theorem 4 statement] 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.
Circularity Check
No significant circularity: the central derivation is self-contained, and the few self-citations are standard external lemmas that are not load-bearing.
full rationale
The paper's main results, Theorems 3 and 4, are derived from explicit assumptions on the data distribution and on the Glivenko–Cantelli/Donsker properties of the empirical processes Lambda_n, Delta_n, and G_n. The proofs use Lemma 4, which is established directly from the definitions of the processes, the quadratic structure of square loss, and elementary linear algebra; no fitted constants or data-dependent parameters are introduced. Theorem 4's sample-size condition and the iterative localization argument are driven by Markov's inequality, Bousquet's concentration inequality, and Koltchinskii's localization method, all applied to the stated empirical processes. The self-citations (EE23, EME24) are used only for standard facts such as Gaussian concentration bounds and properties of quantile functions, not to assume the conclusions of the paper. The paper does not rename a known empirical pattern as a prediction, and it does not fit a parameter to a subset of data and then predict a closely related quantity. The reviewer's concern about Theorem 4's sample-size condition is a correctness or proof-gap issue, not a circularity issue, and does not affect the score.
Assumptions & free parameters
assumptions (5)
- domain assumption For all t in T, the covariance matrix Σ(t) is invertible; equivalently, the support of φ_t(X) is not contained in any hyperplane.
- domain assumption The empirical processes Λ_n, Δ_n, and G_n are separable and T is countable.
- domain assumption The sequences (Λ_n), (Δ_n), and (G_n) are Glivenko-Cantelli, and (G_n) is Donsker.
- domain assumption Assumption 1 bounds the expectations E[sup Λ_n], E[sup Δ_n], and E[sup G_n^2] by constants independent of n.
- domain assumption Finite moments: E[Y^2] < ∞ and E[φ_{t,j}^4] < ∞ for all t and j.
Cite this review
Pith. "Pith review of On the Efficiency of ERM in Feature Learning." pith.science (2026). https://pith.science/paper/X2LNCXAC
@misc{pith2026241112029,
author = {Pith},
title = {Pith review of: On the Efficiency of ERM in Feature Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/X2LNCXAC}},
note = {Machine review of arXiv:2411.12029}
}
abstract
Given a collection of feature maps indexed by a set $\mathcal{T}$, we study the performance of empirical risk minimization (ERM) on regression problems with square loss over the union of the linear classes induced by these feature maps. This setup aims at capturing the simplest instance of feature learning, where the model is expected to jointly learn from the data an appropriate feature map and a linear predictor. We start by studying the asymptotic quantiles of the excess risk of sequences of empirical risk minimizers. Remarkably, we show that when the set $\mathcal{T}$ is not too large and when there is a unique optimal feature map, these quantiles coincide, up to a factor of two, with those of the excess risk of the oracle procedure, which knows a priori this optimal feature map and deterministically outputs an empirical risk minimizer from the associated optimal linear class. We complement this asymptotic result with a non-asymptotic analysis that quantifies the decaying effect of the global complexity of the set $\mathcal{T}$ on the excess risk of ERM, and relates it to the size of the sublevel sets of the suboptimality of the feature maps. As an application of our results, we obtain new guarantees on the performance of the best subset selection procedure in sparse linear regression under general assumptions.
Reference graph
Works this paper leans on
-
[3]
Using properties of the quantile function (e.g
Therefore, for all k ∈ N, lim sup n→∞ P ( G2 n(ˆtn) > x ) ≤ P ( sup s∈T∗ (εk) G2(s) > x ) Taking the limit as k → ∞, noticing that the events{ sup s∈T∗ (εk) G2(s) > x } are nested, using the continuity of probability from above, and recalling that ∩k≥1T∗(εk) = T∗ gives lim sup n→∞ P ( G2 n(ˆtn) > x ) ≤ P ( sup s∈T∗ G2(s) > x ) . Using properties of the qu...
-
[10]
and ( 24) in the above inequalities, concluding the proof. 20 G Proof of Lemma 2 We prove a slightly more general result, from which Lemma 2 can be immediately deduced. Lemma 5. Let n, d ∈ N and let T be a finite set. F or each (i, t) ∈ [n] × T , let Zi,t ∈ Rd be random vectors such that for each t ∈ T , (Zi,t )n i=1 are i.i.d. with the same distribution a...
-
[17]
Then the statements ( 16) together with the continuous mapping theorem show that limn→∞ P(Bn(ε)) = 0
is strictly larger than ε. Then the statements ( 16) together with the continuous mapping theorem show that limn→∞ P(Bn(ε)) = 0 . Therefore, again by ( 17), we have P ( R(ˆtn, w∗(ˆtn)) − R∗ > ε ) ≤ P(Bn(ε)) + P(Ac n), and taking n → ∞ proves ( 15). Asymptotic quantiles. We start with the upper bound. We have the simple decompositi on n · [ R(ˆtn, ˆwn) − R...
-
[21]
to obtain that on An(t∗) ∩ Bn, 1 R(ˆtn, w∗(ˆtn)) − R∗ ≤ 2 · n−1 · sup t∈Fn,δ/ 2k(T ) G2 n(t). Iterating the procedure we just described k times, we obtain that on an event An(t∗) ∩ (∩k j=1Bn,j ), where P(Bn,j ) ≥ 1 − δ/2k for all j ∈ [k] ˆtn ∈ F k n,δ/ 2k(T ) = Sn,δ,k . (23) Another application of Markov’s inequality yields that on a n event C which holds...
-
[22]
With this knowl- edge, we now reuse the bound (
yields that on the event An(t∗) ∩ Bn, 1, R(ˆtn, w∗(ˆtn)) − R∗ ≤ 4k · (nδ)−1 · E[sup t∈T G2 n(t)], which shows that on this event, ˆtn ∈ Fn,δ/ 2k(T ), by definition of the map Fn,δ/ 2k. With this knowl- edge, we now reuse the bound (
-
[23]
proves the first statement of the theorem. For the second sta tement, we have on the same event An(t∗) ∩ (∩k j=1Bn,k ) ∩ C , and combining the two upper bounds from Lemma 4, E(ˆtn, ˆwn) ≤ 4 · n−1 · G2 n(ˆtn) ≤ 4 · n−1 · sup t∈Sn,δ,k G2 n(t) ≤ 24 · (nδ)−1 · E[ sup t∈Sn,δ,k G2 n(t)], where we used (
-
[2012]
Learning the Kernel Matrix with Semidefinite Programming
URL . [Lan+04] G. R. G. Lanckriet, N. Cristianini, P . Bartlett, L. E. Ghaoui, and M. I. Jordan. “Learning the Kernel Matrix with Semidefinite Programming”. In: Journal of Machine Learning Research (2004). URL . 12 [LBH15] Y . LeCun, Y . Bengio, and G. Hinton. “Deep Learning”. In: Nature (May 28, 2015). DOI : 10.1038/nature14539. [LC06] E. L. Lehmann and G...
-
[2016]
Random Design Ana lysis of Ridge Regression
DOI : 10.1109/CVPR.2016.90. [HKZ12] D. Hsu, S. M. Kakade, and T. Zhang. “Random Design Ana lysis of Ridge Regression”. In: Proceedings of the 25th Annual Conference on Learning Theory. June 16, 2012. URL . [HMS22] H. Hazimeh, R. Mazumder, and A. Saab. “Sparse Regres sion at Scale: Branch-and- Bound Rooted in First-Order Optimization”. In: Mathematical Pro...
Show all 10 references
-
[2019]
When Do Neural Networks Outperform Kernel Methods?
URL . [Gho+20] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montan ari. “When Do Neural Networks Outperform Kernel Methods?” In: Advances in Neural Information Processing Systems
-
[2020]
Persistence in High-Di mensional Linear Predictor Selection and the Virtue of Overparametrization
URL . [GN15] E. Giné and R. Nickl. Mathematical F oundations of Infinite-Dimensional Statist ical Models. 2015. DOI : 10.1017/CBO9781107337862. [GR04] E. Greenshtein and Y . Ritov. “Persistence in High-Di mensional Linear Predictor Selection and the Virtue of Overparametrizatio...
2015
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.