On the Efficiency of ERM in Feature Learning

Authors: ayoub  el
chris j maddison
murat a erdogdu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 20:54:16

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 characterize the performance of the best subset selection procedure in sparse linear regression under general assumptions.

Main paper: 
 introduction: 
 A central idea in modern machine learning is that of data-driven feature learning. Specifically, instead of performing linear prediction on top of hand-crafted features, the current dominant paradigm suggests to use models that select useful features for linear prediction in a data-dependent way [e.g. KSH12; LBH15; He+16; Vas+17] . Of course, by putting the burden of picking a feature map on the model and data, we should expect that the resulting learning problem will require more samples to be solved. But just how many more samples do we need to learn such feature-learning-based models?In this paper, we investigate this question in a general setting. We study the performance of empirical risk minimization (ERM) on regression tasks with square loss and over model classes induced by arbitrary collections of features maps. More precisely, let X be the random input taking value in a set X , and let (ϕ t ) t∈T , ϕ t : X → R d , be a collection of feature maps indexed by a set T . For a given regression task and i.i.d. samples, our aim is to understand the performance of ERM over the class of predictors ∪ t∈T x → ⟨w, ϕ t (x)⟩ | w ∈ R d as a function of the sample size, the distribution of the data, and relevant properties of the collection of feature maps (ϕ t ) t∈T .Classical uniform-convergence-based analyses would suggest that the performance of ERM in this setting is determined by the size of the model class, appropriately measured. The main message of this paper is that in this case, this is wrong in a strong sense. Specifically, we prove an upper bound on the excess risk of ERM on this problem whose dependence on the size of the model class decays monotonically with the sample size, and eventually depends only on the size of the model class induced by the collection of optimal feature maps, which is typically much smaller.Formal setup. We briefly formalize our problem here. Let X be the random input taking value in a set X , and let (ϕ t ) t∈T , ϕ t : X → R d , be a collection of feature maps indexed by a set T . 1Let Y ∈ R be the output random variable, jointly distributed with the input X. Our goal is to learn to predict the output Y given the input X as well as possible within the class of predictorsx → ⟨w, ϕ t (x)⟩ | (t, w) ∈ T × R d . We evaluate the quality of a single prediction ŷ given the ground truth y through the loss function ℓ(ŷ, y) := (ŷ -y) 2 /2, and the overall quality of a predictor (t, w) ∈ T × R d through its risk R(t, w) := E[ℓ(⟨w, ϕ t (X)⟩, Y )],R * := inf (t,w)∈T ×R d R(t, w).We assume that we have access to n i.i.d. samples (X i , Y i ) n i=1 with the same distribution as (X, Y ), and perform empirical risk minimization ( tn , ŵn ) ∈ argmin(t,w)∈T ×R d R n (t, w) where R n (t, w) := 1 n n i=1 ℓ(⟨w, ϕ t (X i )⟩, Y i ).Our goal is to characterize the excess risk E( tn , ŵn ) := R( tn , ŵn ) -R * .Related work. The study of upper bounds on the excess risk of ERM in a general setting is a classical topic. It was initiated by Vapnik and Chervonenkis [VC74] who established a link between the excess risk of ERM and the uniform convergence of the underlying empirical process. More recently, and fuelled by the development of Talagrand's concentration inequality [Tal96] and its refinements [e.g. BLM00; Bou02], a literature emerged that provided more fine-grained control of the excess risk of ERM [e.g. BBM05; Kol06; BM06]. A key idea emerging from this line of work is localization. This concept, and in particular the iterative localization method of Koltchinskii [Kol06] , plays an important role in our development. We refer the reader to the books [Kol11; Wai19] , as well as the recent articles [LRS15b; KRV22] for more on this idea.Focusing on the task of regression with square loss, upper bounds on the excess risk of ERM are available for many classes of predictors, including finite [e.g. Aud07; JRT08; LM09], linear [e.g. LM16b; Oli16; Mou22], and convex classes [e.g. LM16a; Men14; LRS15a]. A key development in this area over the last decade has been the realization that such bounds can be obtained under much weaker assumptions than previously thought [Men14; Oli16] , owing to the fact that only one-sided control of a certain empirical process is needed [Men14; KM15; Oli16] , and which can be obtained under very weak assumptions. The line of work most closely related to ours is the one on random-design linear regression [AC11; HKZ12; Oli16; LM16c; Sau18; Mou22; EE23], and we view our work as an extension of this literature. We review these results in more detail in Section 2.Finally, and on a more conceptual level, our work is related to the recent effort to understand the effect of feature learning on the performance of neural networks [e.g. COB19; Gho+19; Ba+22]. Beyond this conceptual connection however, our work is quite distinct from this literature. Among other things, our setting is more general since we consider arbitrary features maps. In the same vein, it is worth mentioning the line of work on multiple kernel learning [e.g. Lan+04; GA11; SD16], although we are not aware of results from this literature that are directly relevant to our setup.Challenges. Our class of predictors is somewhat unstructured (e.g. it is in general non-convex), so that off-the-shelf results from the above literature are not directly applicable. Nevertheless, the analysis of the performance of ERM on linear classes provides a good starting point as we review in Section 2. Compared to that setting however, we are faced with two additional challenges. First, we need to control an additional source of error arising from the fact that ERM might select a suboptimal feature map. Second, we are lead to study the suprema of certain T -indexed empirical processes, which in the linear setting reduce to single random variables that are easily dealt with.Organization. The rest of the paper is organized as follows. In Section 2, we review known result on the excess risk of linear regression under square loss. In Section 3, we state our main results that hold for the excess risk of ERM for general index sets T . In Section 4, we specialize our analysis to the case where the index set T is finite, obtain more explicit guarantees, and discuss their implications on the sparse linear regression problem. We conclude in Section 5 with a brief discussion.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The main claims made in the abstract and introduction are supported by our main results of Section 3 and 4 directly.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: 
 The goal of this section is to provide more context for our results. We review known results on the excess risk of ERM over linear classes, which corresponds in our setting to the special case where the set T indexing the feature maps is a singleton. As such, to avoid introducing further notation, we use the one from the previous section, while dropping the dependence on t whenever it occurs.In the setting of linear regression with square loss, and when the sample covariance matrix of the feature map is invertible, there is a unique empirical risk minimizer and its excess risk admits an explicit expression. Specifically, defineEQUATIONand let w * denote the unique minimizer of the risk R(w). 2 Then, an elementary calculation shows that when Σ n is invertible, there is a unique empirical risk minimizer and it satisfiesEQUATIONFurthermore, since the risk is a quadratic function of w whose gradient at w * vanishes, replacing R( ŵn ) by the equivalent exact second order Taylor expansion around w * yieldsEQUATIONWhile exact, this expression is not readily interpretable. For example, how fast does this excess risk go to 0 as a function of the sample size? The following classical result from asymptotic statistics [e.g. Whi82; LC06; Van00] makes this rate more explicit. To state it, we defineg(X, Y ) := ∇ w ℓ(⟨w * , ϕ(X)⟩, Y ), G := E g(X, Y )g(X, Y ) T . (4) Theorem 1. Assume that for all j ∈ [d], E ϕ 2 j (X) < ∞, E Y 2 < ∞, and E[∥g(X, Y )∥ 2 Σ -1 ] < ∞. Then, as n → ∞, n • E( ŵn ) d → 1 2 • ∥Z∥ 2 2 ,where Z ∼ N (0, Σ -1/2 GΣ -1/2 ). In particular, for any δ ∈ (0, 0.1),lim n→∞ n • Q E( ŵn) (1 -δ) ≍ E[∥g(X, Y )∥ 2 Σ -1 ] + 2λ max (Σ -1/2 GΣ -1/2 ) log(1/δ),where Q X (p) := inf{x ∈ R | P(X ≤ x) ≥ p} is the quantile function of a random variable X, and where we write a ≍ b to mean that there exists absolute constants C, c such that c • b ≤ a ≤ C • b. In the above statement, they can be taken as C = 1 and c = 1/32.We provide a proof in Appendix A for completeness. For our purposes, this theorem is most easily interpreted as follows: for large enough n and small enough δ, if the excess risk of ERM is bounded by some quantity with probability at least 1 -δ, then this quantity is, up to a constant, at least as large as the right-hand side of the second displayed equation divided by n. While our primary interest is in non-asymptotic bounds, this asymptotic result, by virtue of its exactness, provides us with a benchmark against which such bounds can be compared. In particular, it identifies the quantityE[∥g(X, Y )∥ 2 Σ -1] as an intrinsic parameter determining the excess risk of ERM on this problem. For large enough n, Theorem 1 gives an interpretable expression for the excess risk. However, it says nothing about how large n needs to be for this expression to be accurate. This motivates a non-asymptotic analysis of the excess risk of ERM, which has been carried out numerous times in recent years [e.g. Oli16; LM16c; EE23]. A goal of this literature has been to obtain upper bounds on the excess risk of ERM that hold in probability under weak moment assumptions, building on the observation that this is indeed possible [Men14] . The following theorem is comparable to the best known result in this area. We leave the proof to Appendix B. To state it, we defineV := E Σ -1/2 ϕ(X)ϕ(X) T Σ -1/2 -I 2 , L := sup v∈S d-1 E ⟨v, Σ -1/2 ϕ(X)⟩ 2 -1 2 .2 Throughout, we assume without loss of generality that the support of the distribution of ϕ(X) is not contained in any hyperplane, which implies the invertibility of Σ and the uniqueness of w * [cf. Mou22].Theorem 2. Assume that for all j ∈[d], E ϕ 4 j (X) < ∞, E Y 2 < ∞, and E[∥g(X, Y )∥ 2 Σ -1 ] < ∞. Let δ ∈ (0, 1). If n ≥ (512λ max (V ) + 6) log(ed) + (128L + 11) log(2/δ),then with probability at least 1 -δ,E( ŵn ) ≤ 4 • (nδ) -1 • E[∥g(X, Y )∥ 2 Σ -1 ].At a high-level, this result says that above a certain explicit minimal sample size, the asymptotic expression of the excess risk of Theorem 1 is correct, up to a significantly worse dependence on δ.The restriction on the sample size is almost the best one can hope for. To see why, note that to get guarantees on the excess risk of any empirical risk minimizer, we need at least that Σ n is invertible, otherwise there exists an empirical risk minimizer arbitrarily far away from w * . To get quantitative guarantees, we need slightly more control in the form of a lower bound on λ min (Σ -1/2 Σ n Σ -1/2 ).We refer the reader to a more detailed discussion in [EME24, Section 5].This result has two key qualities, which we aim to reproduce in our results. First, it is assumptionlean, requiring nothing more than a fourth moment assumption on the coordinates of the feature map compared to Theorem 1. Second, it recovers the right dependence on the intrinsic parameterE[∥g(X, Y )∥ 2 Σ -1 ] identified in Theorem 1.A downside of this generality is the bad dependence on δ. Without further assumptions, this cannot be improved; we refer the reader to the recent literature on robust linear regression for more on this issue [e.g. LM19; LL20; EME24].Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The last paragraph of the conclusion explicitly discusses the limitations of this work.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
main results: 
 In this section we state our main results. They are most easily seen as extensions of Theorems 1 and 2 for general index sets T . In Section 3.1, we study the asymptotics of the excess risk of ERM in our setting, and in Section 3.2, we present a non-asymptotic upper bound on the excess risk.To state our results, we require additional definitions and notation. We start with the population and the sample covariance matricesΣ(t) := E ϕ t (X)ϕ t (X) T , Σ n (t) := n -1 n i=1 ϕ t (X i )ϕ t (X i ) T .We define the following collection of minimizers, w * (t) := argminw∈R d R(t, w), T * := argmin t∈T R(t, w * (t)),the first is uniquely defined, while the second is set-valued in general. We define the gradient of the loss at these minimizers and their corresponding covariance matricesg(t, (X, Y )) := ∇ w ℓ(⟨w * (t), ϕ t (X)⟩, Y ), G(t) := E g(t, (X, Y ))g(t, (X, Y )) T .Finally, we introduce the following processes which play a key role in our developmentEQUATIONas well as, for t * ∈ T * and t ∈ T \ T * ,EQUATION)We note that the process (∆ n (t, t * )) t∈T \T * is an empirical process (see [VW96] for an introduction), while (Λ n (t)) t∈T and (G n (t)) t∈T are partial suprema of empirical processes. In the sequel, we will slightly abuse this terminology, and call all of these empirical processes, with the understanding that they can be viewed as one with more indexing. We will further assume that these processes are separable; see [BLM13, for a definition. This covers a wide range of applications, while avoiding delicate measurability issues. The suprema of such separable processes, which is the only way they enter our results, can be studied by taking the supremum over a countable dense subset of the index set. Therefore, without loss of generality, we assume that T is countable.Finally, in line with the literature on the theory of empirical processes [VW96] , we say that a sequence of empirical processes is Glivenko-Cantelli if, when rescaled by n -1/2 , the supremum of their absolute value taken over their index set converges to zero in probability as n → ∞. In other words, the weak law of large numbers holds uniformly over the index set. Similarly, we say that a sequence of empirical processes is Donsker if it converges in distribution to its limiting Gaussian process. 3 In other words, the central limit theorem holds uniformly over the index set.Our first main result is an asymptotic characterization of the quantiles of the excess risk of any sequence of empirical risk minimizers in our setting, which vastly generalizes that of Theorem 1. Theorem 3. Assume that T * ̸ = ∅ and for some t * ∈ T * , assume that the empirical processes (Λ n (t)) t∈T , (∆(t, t * )) t∈T \T * and (G n (t)) t∈T are Glivenko-Cantelli. Then, for all ε > 0,lim n→∞ P R( tn , w * ( tn )) -R * > ε = 0.Furthermore, if the sequence of processes (G n (t)) t∈T is Donsker, then for any δ ∈ (0, 0.1),1 2 • Q Z -(1 -δ) ≤ lim inf n→∞ n • Q E( tn, ŵn) (1 -δ) ≤ lim sup n→∞ n • Q E( tn, ŵn) (1 -δ) ≤ Q Z + (1 -δ),where Z -:= inf s∈T * Z 2 (s), Z + := sup s∈T * Z 2 (s), and (Z(t)) t∈T is the limiting Gaussian process of the empirical process (G n (t)) t∈T .4 Remark 1. For δ ∈ (0, 0.1), the upper bound admits the more interpretable expressionEQUATIONFurthermore, if T * is finite, the first term can be upper bounded asEQUATIONWe note that, up to a factor of two in the upper bound on the asymptotic quantiles, Theorem 3 reduces to Theorem 1 when T is a singleton, with the exact same assumptions. We are not aware of comparable results in the literature. The proof of Theorem 3 can be found in Appendix D.To see why this result is surprising, let us first focus on the case where T * has a unique element t * , so thatZ + = Z - d = ∥Z∥ 2 2 where Z ∼ N (0, Σ -1/2 (t * )G(t * )Σ -1/2 (t * )). Now consider the oracle procedure, which knows beforehand what the optimal feature map t * is, and outputs t * and a minimizer of R n (t * , w). Theorem 3 says that, up to a factor of two, the asymptotic quantiles of the excess risk of ERM, which needs to learn over the large class ∪ t∈T x → ⟨w, ϕ t (x)⟩ | w ∈ R d , coincide with those of the oracle procedure (by Theorem 1), which only needs to learn over the linearclass x → ⟨w, ϕ t * (x)⟩ | w ∈ R d !More generally, Theorem 3 establishes that asymptotically, any ERM picks a near-optimal feature map with probability one. It furthers shows that the asymptotic quantiles of the excess risk of any sequence of ERMs is controlled from above and below by those of the extrema of the limiting Gaussian process of (G n (t)) t∈T on the set of optimal feature maps T * . This is surprising, as it implies that asymptotically, and outside of its role in determining whether the assumptions of Theorem 3 hold, the global complexity of the set T is irrelevant to the excess risk of ERM.Finally, we note that the Glivenko-Cantelli and Donsker assumptions in Theorem 3 can equivalently be viewed as restrictions on the size of T , for distribution and process dependent notions of size. We refer the reader to the books [VW96; GN21] for more on this connection. With this observation, we state the main takeaway from Theorem 3 as follows.Asymptotically, if T is not too large, the excess risk of ERM depends, at worst, only on the complexity of the set of optimal feature maps T * , and is independent of the global complexity of T .The result in Theorem 3 hints at a dramatic localization phenomenon, whereby the influence of the size and complexity of the collection of feature maps (ϕ t ) t∈T on the excess risk of ERM vanishes as n → ∞ under appropriate assumptions. The root of this localization phenomenon is the first statement of Theorem 3: eventually, ERM picks near-optimal feature maps with probability approaching one. For small enough sample sizes however, it is clear that ERM is likely to select suboptimal feature maps, so that this localization phenomenon cannot hold uniformly over n. This raises a host of questions: (i) How fast, as measured by the sample size, does ERM learn the optimal feature map? (ii) What is the effect of this localization on the rate of decay of the excess risk of ERM non-asymptotically? (iii) What properties of the feature maps (ϕ t ) t∈T influence these rates?Our answers to these questions in this very general setting are formally expressed in Theorem 4 below. To state it, we define the following parameterEQUATION)where the supremum is taken over vectors (v t ) t∈T such that t∈T ∥v t ∥ 2 2 = 1. For n ∈ N and δ ∈ (0, 1), we define the set function F n,δ , for any subset S ⊂ T , byEQUATIONThis map acts as a contraction as shown in the next lemma, whose proof is deferred to Appendix E. For a function f , we usef k to denote f k (x) := f (f k-1 (x)) with f 0 (x) := x. Lemma 1. Let n ∈ N, δ ∈ (0, 1), and assume that T * ̸ = ∅. Then for all k ∈ N ∪ {0}, • F k+1 n,δ (T ) ⊆ F k n,δ (T ). • If ∃ n 0 , B such that E[sup t∈T G 2 n (t)] ≤ B for all n ≥ n 0 , then n≥1 F k n,δ (T ) = T * .With these definitions, we now state the second main result of the paper. A proof is in Appendix F. Theorem 4. Assume thatT * ̸ = ∅, E[Y 2 ] < ∞, ∀(t, j) ∈ T × [d], E[ϕ 2 t,j (X)] < ∞, and E[∥g(t, (X, Y ))∥ 2 Σ -1 (t) ] < ∞. Let δ ∈ (0, 1) and k ∈ N. If, for some t * ∈ T * , n satisfies n ≥ 64 E[sup t∈T Λ n (t)] + (128L + 11) log(4/δ) + 2 • δ -2 • E[ sup t∈T \T * ∆ n (t, t * )], then, with probability at least 1 -δ, tn ∈ F k n,δ/2k (T ) =: S n,δ,k , and E( tn , ŵn ) ≤ 8k • (nδ) -1 • E[ sup s∈S n,δ,k G 2 n (s)],where the processes Λ n , ∆ n , and G n are as in ( 5) and (6).We make a few remarks before interpreting the content of the theorem. First, we note that when the index set T is a singleton, the last term in the sample size restriction vanishes, while the first matches the sample size restriction from Theorem 2 after an application of Lemma 3 below; further taking k = 1 in Theorem 4 recovers the upper bound on the excess risk of Theorem 2 up to a factor of two. Theorem 4 may therefore be viewed as a broad generalization of Theorem 2. Second, under Assumption 1 below, and by the second item of Lemma 1, the upper bound on the excess risk in Theorem 4 eventually matches the main term in the asymptotic rate of Theorem 3 as can be seen from ( 7), in the same way that Theorem 2 achieves this when compared with Theorem 1. Finally, the statement of Theorem 4 is very general, and in fact, too general for us to be able to interpret it precisely. As such, we will discuss it in the context of the following assumption. Assumption 1. There exists constants C Λ , C ∆ , and C G independent of the sample size, but possibly dependent on the remaining parameters of the problem, such that for all n ∈ N,E[sup t∈T Λ n (t)] ≤ C Λ , E sup t∈T \T * ∆ n (t, t * ) ≤ C ∆ , E[sup t∈T G 2 n (t)] ≤ C G ,where Λ n , ∆ n , and G n are as in ( 5) and (6).These assumptions can be equivalently viewed as a restriction on the appropriately measured size of the index set T [VW96; GN21], and are slightly stronger than the assumptions of Theorem 3. Nevertheless, they always hold for finite index sets, and we will derive in Section 4 explicit estimates of the constants in Assumption 1 in terms of moments of the feature maps and target.Let us now interpret the content of Theorem 4, which comes with a free parameter k, in the context of Assumption 1. We fix k here, and discuss its choice below. First, recalling the definition of F n,δ , this result says that above a certain sample size, both the suboptimality of the feature map picked by ERM and its excess risk decay at the fast rate n -1 , answering the first question we raised at the beginning of the section. Second, this result provides an upper bound on the excess risk of ERM that depends on the index set T only through the size of shrinking subsets S n,δ,k , which might be large for small n, but which by Lemma 1 converge to the set of optimal feature maps T * as n → ∞. This transparently shows the effect of the localization phenomenon on the rate of decay of the excess risk of ERM, answering the second question we raised. Finally, looking at the definition of S n,δ,k , this result identifies the size of the sublevel sets of the suboptimality function R(t, w * (t)) -R * defined over feature maps as a key proprety of the collection of feature maps (ϕ t ) t∈T that influences the rate of convergence of the excess risk of ERM in this setting, answering the final question we raised.Finally, let us turn to the choice of k. Practically, we select the one that minimizes the bound on the excess risk. Looking at the first item of Lemma 1, this optimal k balances the following trade-off: on the one hand, for small k, applications of F n,δ/2k constrain the input set more severely, but only a few iterations are performed; on the other hand, larger values of k allow more iterations, but at the cost of more weakly constraining the input set per application.Stepping back, there are two main takeaways from Theorem 4. Firstly, and on a conceptual level, it shows that feature learning is easy when the suboptimality function R(t, w * (t)) -R * , defined over the set of features maps, has small sublevel sets. Secondly, and on a technical level, it provides a template which can be used to derive more explicit excess risk bounds on ERM given estimates on the expected suprema of the relevant empirical processes. Deriving such accurate estimates for infinite T is a highly non-trivial task, and cannot be done at the level of generality we have been operating at.The case of finite T however is tractable in a general setting as we discuss in the next section.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our paper is heavily theoretical, and is quite far removed from direct applications, which is why do not foresee any direct societal impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
case study: finite index sets: 
 In this section, we focus on the case where the index set T is finite, and aim, among other things, at establishing explicit estimates on the various expected suprema appearing in Theorem 4 in terms of moments of the feature maps and of the target. This problem becomes tractable in the case of finite T because, roughly speaking, a worst-case analysis still yields non-trivial upper bounds. This is decidedly not the case when T is infinite, in which case these expected suprema can be infinite.We start with a slight strengthening of Theorem 3, whose assumptions reduce to simple moments conditions when T is finite. A proof is in Appendix H.Corollary 1. Assume that T is finite, for all (t, j) ∈ T × [d], E ϕ 2 t,j (X) < ∞, E Y 2 < ∞, and for all t ∈ T , E[∥g(t, (X, Y ))∥ 2 Σ -1 (t) ] < ∞. Then lim n→∞ P tn / ∈ T * = 0.Furthermore, for any δ ∈ (0, 1),1 2 • Q Z -(1 -δ) ≤ lim inf n→∞ n • Q E( tn, ŵn) (1 -δ) ≤ lim sup n→∞ n • Q E( tn, ŵn) (1 -δ) ≤ 1 2 • Q Z + (1 -δ),where Z -:= min s∈T * ∥Z s ∥ 2 2 , Z + := max s∈T * ∥Z s ∥ 2 2 , and the random vectors (Z t ) t∈T are jointly Gaussian with mean zero andE Z t Z T s = E Σ -1/2 (t)g(t, (X, Y ))g(s, (X, Y )) T Σ -1/2 (s) for all t, s ∈ T . In particular, if T * = {t * }, then n • E( tn , ŵn ) d → 1 2 • ∥Z∥ 2 2 ,whereZ ∼ N (0, Σ -1/2 (t * )G(t * )Σ -1/2 (t * )).The conclusions of Corollary 1 differ from those of Theorem 3 in two aspects. First, the feature map picked by ERM is guaranteed to be optimal rather than near-optimal with probability converging to one. Second, the upper bound on the asymptotic quantiles is improved by a factor of two, yielding the exact distribution of the rescaled excess risk when T * is a singleton.Making Theorem 4 more explicit is a more laborious task. We recall here two known results that allow us to accomplish this. We start with the following bounds on the expectation of the supremum of a finitely-indexed empirical process, which we will later use to bound the suprema of the processes (G n (s)) s∈S and (∆ n (t, t * )) t∈T \T * appearing in Theorem 4. A proof can be found in Appendix G. Lemma 2. Let n, d ∈ N, and let Z be a random element taking value in a set Z, and let (Z i ) n i=1 be i.i.d. samples with the same distribution as Z. Let F be a finite collection of R d -valued measurable functions. Defineσ 2 (F) := max f ∈F E ∥f (Z) -E[f (Z)]∥ 2 2 , r(F) := E max (i,f )∈[n]×F ∥f (Z i ) -E[f (Z)]∥ 2 2 1/2,and let E n (f ) := √ n • (n -1 n i=1 f (Z i ) -E[f (Z)]). Then, we have 1 2 • σ(F) + 1 4 • r(F) √ n ≤ E max f ∈F ∥E n (f )∥ 2 2 1/2 ≤ c(|F|) • σ(F) + c 2 (|F|) • r(F) √ n ,where c(m):= 5 √ 1 + log m.Lemma 2 allows us to compute the expected supremum of a finitely-indexed empirical process, up to log factors in the size of the index set. It is known that these factors cannot be removed from the upper bound nor added to the lower bound without more assumptions, we refer the reader to a related discussion in [Tro16] . Finally, while the term r(F) might grow with n, by bounding the maximum with the sum, it grows at most as √ n. In many applications however, the random vectors f (Z) are bounded almost surely, so that r(F) is of order one, which justifies our presentation choice.The second result we recall is the expectation version of a one sided Matrix Bernstein inequality due to Tropp [Tro15] . We use it below to bound the supremum of the process (Λ n (t)) t∈T appearing in Theorem 4. We do not known of a matching non-asymptotic lower bound, but an asymptotic one is known [EME24, Proposition 17]. Upper and lower bounds similar to those of Lemma 2 hold if one considers the expected operator norm instead of only the maximum eigenvalue [Tro16, Section 7]. Lemma 3 ([Tro15], Theorem 6.6.1.). Let n, d ∈ N and for each i ∈ [n], let Z i ∈ R d×d be i.i.d. positive semi-definite matrices with the same distribution as Z. DefineV := E (E[Z] -Z) 2 , W n := √ n • E[Z] - 1 n n i=1 Z i .Then, we haveE[λ max (W n )] ≤ 2λ max (V ) log(ed) + λ max (E[Z]) log(ed) 3 √ n .Equipped with these estimates, we may now control the expected suprema of the empirical processes appearing in Theorem 4. To apply Lemma 2, define the following classes, for S ⊂ T andt * ∈ T * G(S) := (x, y) → Σ -1/2 (s)g(s, (x, y)) s ∈ S , D(t * ) := (x, y) → ℓ(⟨w * (t), ϕ t (x)⟩, y) -ℓ(⟨w * (t * ), ϕ t * (x)⟩, y) R(t, w * (t)) -R * t ∈ T \ T * .Applying Lemma 2 on G(S) bounds the expected supremum of the process (G n (s)) s∈S while applying it on D(t * ) bounds that of (∆ n (t, t * )) t∈T \T * . To control the supremum of (Λ n (t)) t∈T , the key idea is to notice that it can be expressed as the maximum eigenvalue of a block diagonal matrix whose blocks are√ n(I -Σ -1/2 (t)Σ n (t)Σ -1/2 (t)). Looking at Lemma 3, the relevant parameter is therefore a block diagonal matrix V with the following blocksEQUATION)As the bound in Lemma 3 depends only on the maximum eigenvalue of V , the ordering of the blocks does not matter. Putting together these estimates, we arrive at a fully explicit version of Theorem 4.Corollary 2. Assume that T is finite and that for all (t, j)EQUATIONE( tn , ŵn ) ≤ 8k • (nδ) -1 • A( S n,δ,k ),where, for S ⊂ T ,A(S) := c 2 (S) • σ(G(S)) + c(S) • r(G(S)) √ n 2 ,and F n,δ (S) is the same as F n,δ (S) defined in (10) but withA(S) replacing E[sup s∈S G 2 n (s)].We conclude this section with a few remarks about Corollary 2; a proof sketch is in Appendix I. The set function A(S) controlling the contraction rate of the map F n,δ as well as the excess risk, has a pleasantly simple form. To first order, and ignoring constants, it is given by(1 + log|S|) • max s∈S E ∥g(s, (X, Y ))∥ 2 Σ -1 (s) .As such, as n → ∞ and by Lemma 1, the upper bound on the excess risk in Corollary 2 matches the main term in the asymptotic rate derived in Theorem 3, as can be seen from ( 8). As the sets S n,δ,k are shrinking with n, the above expression clearly shows the decaying effect of the global complexity of T on the excess risk. Finally, we note that the restriction on k in Corollary 2 is there only because after at most that many iterations, a fixed point is reached, and further iterations worsen the bound.Example 1 (Sparse linear regression). Consider the classical sparse linear regression problem, and in particular the best subset selection procedure [Mil02] . This procedure corresponds to ERM over the restricted linear class {x → ⟨w, ϕ(x)⟩ | ∥w∥ 0 ≤ s} in the linear regression setup of Section 2, where ∥w∥ 0 is the number of non-zero entries of w and s ∈ [d] is a user-chosen sparsity level.The literature on sparse linear regression is too vast for us to survey it in detail here. We briefly mention that there has been a strong renewed interest in the best subset selection procedure starting with the work of Bertsimas, King, and Mazumder [BKM16] who showed that it can be computed in reasonable time on moderately-sized instances despite being NP-hard [Nat95] . Since then, a large literature has emerged that devises increasingly efficient methods for its computation [e.g. Hua+18; BV20; HM20]. Our interest here however is in the statistical performance of the best subset selection procedure; we discuss the closest results in this direction below.To see how the sparse linear regression problem fits in our feature learning setting, notice that{x → ⟨w, ϕ(x)⟩ | ∥w∥ 0 ≤ s} = {x → ⟨v, ϕ t (x)⟩ | (t, v) ∈ T × R s }where T is the set of all subsets of [d] of size s, and ϕ t (x) := (ϕ j1 (x), ϕ j2 (x), . . . , ϕ js (x)) ∈ R s where (j 1 , j 2 , . . . , j s ) are the elements of t in increasing order. Each (t, v) ∈ T × R s is associated to a unique w ∈ R d satisfying ∥w∥ 0 ≤ s given by w ji = v i for (j 1 , . . . , j s ) the increasing elements of t and i ∈ [s], and zero otherwise. As such, Corollaries 1 and 2 are immediately applicable and provide general statements on the performance of an arbitrary empirical risk minimizer.In particular, when there is a unique risk minimizer w * satisfying ∥w * ∥ 0 = s, the first item of Corollary 1 guarantees that we asymptotically exactly recover the support of w * . Furthermore, if the model is well-specified, i.e. ε := ⟨w * , ϕ(X)⟩-Y is independent of X and satisfies E ε 2 = σ 2 < ∞, then the second item of Corollary 1 yields, for any δ ∈ (0, 0.1),lim n→∞ n • Q E( ŵn) (1 -δ) ≍ σ 2 (s + log(1/δ)).Non-asymptotically, the first item of Corollary 2 shows that if the sample size n further satisfiesn > 2 • (γδ) -1 • A( F k-1 n,δ/2k (T )),where γ := min t∈T \T * {R(t, w * (t)) -R * } > 0, then with probability at least 1 -δ, ERM coincides with the oracle procedure which knows beforehand the support of w * , and performs ERM on the optimal s-dimensional linear class.The closest existing result in the literature is due to [She+13] , who arrived at comparable conclusions but in a substantially different setting. In particular, this result was derived in the setting n, d → ∞, with an implicit assumption on the distribution of ϕ(X) [She+13, Equation (2)], and dealt with the in-sample prediction risk instead of the excess risk. Another closely related result is due to [RWY11] who showed that the rescaled expected minimax risk in a well-specified fixed-design setting is, up to constants, σ 2 s log(d/s), see also [Bac24, Chapter 8] . Our results show that for large enough n, in the random-design setting, and when focusing on a single instance, the log(d/s) factor is unnecessary. 
conclusion: 
 Broadly speaking, there are two main conclusions one can draw from this work. Firstly, in the large sample regime and under mild assumptions, asking a model to additionally pick a feature map on top of learning a linear predictor has a negligible effect on the excess risk of ERM on regression problems with square loss. Secondly, for moderate sample sizes, the magnitude of this effect depends on the size of the sublevel sets of the suboptimality function t → R(t, w * (t)) -R * . Plainly, learning feature maps is easy when only a small subset of them is good, as the bad ones can be quickly discarded.The most tantalizing aspect of our results is their potential in explaining the experiments in [Zha+21] . It was shown there that complex neural networks trained by ERM were able to achieve good performance despite being expressive enough to fit random labels. This is paradoxical if one assumes that the performance of ERM is driven by the complexity of the model class. Our results refute this assumption for feature-learning-based models, of which neural networks are an example. While there are many works offering explanations for this (see e.g. [BMR21] for a survey), we are not aware of one that shows the vanishing influence of the size of the model class on the excess risk as Theorems 3 and 4 show. Formally connecting our statements to these experiments is beyond what we achieved here, yet, we believe that the new perspective we took might generate useful insights in this area.We conclude by outlining a few limitations of our work. First, we do not deal with the question of how to solve the ERM problem. Our setting is so general that such a question cannot be meaningfully tackled. Second, we mention that it is a priori unclear whether ERM is an optimal procedure, in a minimax sense, for the model classes we consider; we suspect that recently developed tools might be relevant to address this question [Mou22] . Finally, while we focused on the case of regression with square loss, this was mostly done to simplify the presentation. Indeed, the only property of the loss used in the proofs is the exactness of its second order Taylor expansion. This is however not necessary if one can control the error term from above and below. It is known how to do this for many loss functions [e.g. OB21; EE23], and most importantly for logistic regression [Bac10; Bac14]. We have purposefully selected generic notation to make translating such arguments easier. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]Justification: We have cited all the relevant work we are aware of, but we do not use any existing code, data, or models in this work.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Let A n denote the event that Σ n is invertible. By the weak law of large numbers, Σ n converges to Σ in probability so that lim n→∞ P(A c n ) = 0. Now on the event A n , we have by (2)√ n • ( ŵn -w * ) = Σ -1 n • ( √ n • ∇R n (w * )).By the continuous mapping theorem, Σ -1 n converges to Σ -1 in probability and by the central limit theorem√ n • ∇R n (w * ) d → N (0, G).Therefore, by Slutsky's theorem√ n • ( ŵn -w * ) d → N (0, Σ -1 GΣ -1 ).Now since the risk is quadratic and the gradient vanishes at w * ,n • [R( ŵ) -R(w * )] = 1 2 • ∥ √ n • ( ŵ -w * )∥ 2 Σ d → 1 2 ∥Z∥ 2 2 ,where Z is as in the theorem, and where the last statement follows by the continuous mapping theorem. This proves the first statement. The bounds on the quantiles are a consequence of concentration bounds for the norm of Gaussian vectors [e.g. EME24, Corollary 33].Denote by A n the event thatλ min Σ -1/2 Σ n Σ -1/2 ≥ 1 2 .We show that under the sample size restriction, P(A n ) ≥ 1 -δ/2. Indeed we have the variational representationλ max (I -Σ -1/2 Σ n Σ -1/2 ) = sup v∈S d-1 1 n n i=1 1 -⟨v, Σ -1/2 ϕ(X i )⟩ 2 .Each element in the sum is upper bounded by 1, and the variance parameter in Bousquet's concentration inequality [Bou02] is given by the parameter L in the statement of the theorem. Applying this inequality yields that with probability at least 1 -δ/2λ max (I -Σ -1/2 Σ n Σ -1/2 ) ≤ 2 E λ max (I -Σ -1/2 Σ n Σ -1/2 ) + 2L log(2/δ) n + 4 log(2/δ) 3n .Using Lemma 3 to upper bound the above expectation, and replacing the sample size n in the resulting inequality with the minimal allowed by the theorem proves that P(A n ) ≥ 1 -δ/2 for all sample sizes allowable by the theorem. Now on this event we have, using (3),R( ŵn ) -R(w * ) = 1 2 • ∥Σ -1 n ∇R n (w * )∥ 2 Σ ≤ 2 • ∥∇R n (w * )∥ 2 Σ -1 .An elementary calculation showsE ∥∇R n (w * )∥ 2 Σ -1 = n -1 E ∥g(X, Y )∥ 2 Σ -1 ,so that an application of Markov's inequality yields that there is an event B n that holds with probability at least 1 -δ/2 and on which∥∇R n (w * )∥ 2 Σ -1 ≤ 2 • (nδ) -1 • E ∥g(X, Y )∥ 2 Σ -1 .n ∩ B n ) = 1 -P(A n ∪ B n ) ≥ 1 -δ finishes the proof.We state here a core lemma, which we use in many of our proofs. To state it, we define, for a functionF : S → R on a subset S ⊆ T , ∥F ∥ ∞ := sup s∈S |F (s)|, ∥F ∥ ∞,-:= sup s∈S {-F (s)}, ∥F ∥ ∞,+ := sup s∈S F (s),where the first quantity is the ℓ ∞ norm of the function F , and the remaining are one-sided variants of it. The processes appearing in the next statement are defined in (5) and (6).Lemma 4. Assume that T * ̸ = ∅ and let t * ∈ T * . On the event that ∥n -1/2 ∆ n (•, t * )∥ ∞,+ < 1 and ∥n -1/2 Λ n ∥ ∞,+ < 1, we haveR( tn , w * ( tn )) -R * ≤ 1 2 • 1 1 -∥n -1/2 ∆ n (•, t * )∥ ∞,+ • 1 1 -∥n -1/2 Λ n ∥ ∞,+ • (n -1 G 2 n ( tn )),and1 2 n -1 G 2 n ( tn ) (1 + ∥n -1/2 Λ n ∥ ∞,-) 2 ≤ R( tn , ŵn ) -R( tn , w * ( tn )) ≤ 1 2 • n -1 G 2 n ( tn ) (1 -∥n -1/2 Λ n ∥ ∞,+ ) 2 .Proof. To lighten the notation, we drop the dependence on n, and write t instead of tn . We start with the first statement. First, we note that if t ∈ T * , then the statement holds trivially as the left-hand side is zero, so we only consider the other case in what follows. For any t ∈ T , defineŵ(t) ∈ argmin w∈R d R n (t, w),where the choice of minimizer is arbitrary. With this definition, we have ŵn = ŵ( t). Now, by definition of ERM, R n ( t, ŵ( t)) -R n (t * , w * (t * )) ≤ 0.(13) On the other hand, for any t ∈ T \ T * , we have the decompositionR n (t, ŵ(t)) -R n (t * , w * ) = [R n (t, ŵ(t)) -R n (t, w * (t))] + [R n (t, w * (t)) -R n (t * , w * (t * ))].(14) We study each of the terms of (14) separately, and we start with the first. Note that since we are in the event inft∈T λ min (Σ -1/2 (t)Σ n (t)Σ -1/2 (t)) = 1 -∥n -1/2 Λ n ∥ ∞,+ > 0,the sample covariance matrices Σ n (t) are invertible for all t ∈ T , so that ŵ(t) is uniquely defined and satisfiesŵ(t) = w * (t) -Σ -1 n (t)∇ w R n (t, w * (t)).(15) Furthermore, since the function w → R n (t, w) is quadratic in w and its gradient vanishes at its minimizer ŵ(t), we haveEQUATION) where the last equality follows from (15). To bound this last term, defineΣ n (t) := Σ -1/2 (t)Σ n (t)Σ -1/2 (t).Then we have,EQUATIONFinally, the second term of ( 14) is lower bounded byEQUATIONCombining ( 17) and ( 16) lower bounds the first term of (14), while (18) lower bounds the second.Combining the resulting lower bound on ( 14) with (13) and rearranging yields the first statement.For the upper bound in the second statement, note that for all t ∈ T ,R(t, ŵ(t)) -R(t, w * (t)) = 1 2 • ∥ ŵ(t) -w * (t)∥ 2 Σ(t) = 1 2 • ∥Σ -1 n (t)∇ w R n (t, w * (t))∥ 2 Σ(t) ≤ 1 2 • λ max ( Σ -2 n (t)) • ∥∇ w R n (t, w * (t))∥ 2 Σ -1 (t) = 1 2 • 1 (1 -∥n -1/2 Λ n ∥ ∞,+ ) 2 • (n -1 G 2 n (t)).where the second line follows from (15). In particular the inequality holds for t. The lower bound holds by a similar argument.Consistency of tn . We want to show that, as n → ∞,EQUATION)Using the notation introduced in Appendix C, the Glivenko-Cantelli assumptions in Theorem 3 amount to the statements that, for some t * ∈ T * , and as n → ∞,EQUATION)Let A n denote the event that both ∥n -1/2 Λ n ∥ ∞ < 1 and ∥n -1/2 ∆ n (•, t * )∥ ∞ < 1. The union bound and (20) show thatlim n→∞ P(A c n ) = 0 (21)Furthermore, on the event A n , the first bound of Lemma 4 holds, and boundingEQUATION)Now let ε > 0, and denote by B n (ε) the event that the right hand side of ( 22) is strictly larger than ε. Then the statements (20) together with the continuous mapping theorem show that lim n→∞ P(B n (ε)) = 0. Therefore, again by ( 22), we haveP R( tn , w * ( tn )) -R * > ε ≤ P(B n (ε)) + P(A c n ), and taking n → ∞ proves (19).Asymptotic quantiles. We start with the upper bound. We have the simple decompositionEQUATION)Now on the event A n defined above, we have, by an application of Lemma 4, combining the two bounds in the lemma along with (23), that the rescaled excess risk is upper bounded byEQUATION)From the Glivenko-Cantelli assumptions (20), the first three factors converge in probability to 1. Our aim will be to bound the upper tail of the last factor, which will imply a bound on the upper tail of the rescaled excess risk.We briefly make explicit the Donsker assumption before deriving this bound. Both define and noteG n (t, v) := √ n • ⟨v, Σ -1/2 (t)∇ w R n (t, w * (t))⟩, G n (t) = sup v∈S d-1 G n (t, v),where S d-1 is the Euclidean unit sphere in R d . As pointed out in Section 3, the processes G n (t) are partial suprema of the empirical processes G n (t, v). The Donsker assumption of the theorem states that the empirical processes G n (t, v) take value in the space of bounded functions on T × S d-1 , equipped with the ℓ ∞ (T × S d-1 ) norm and the metric it induces, and converge weakly to their unique Gaussian limit (Z(t, v)) (t,v)∈T ×S d-1 as n → ∞. We define the partial supremum with respect to v ∈ S d-1 of the latter by Z(t) := sup v∈S d-1 Z(t, v) in analogy with the definition of G n (t).We now upper bound the upper tail of G 2 n ( tn ) in (24). Let (ε k ) ∞ k=1 be a decreasing sequence of positive numbers such that ε k → 0 as k → ∞, and define the setsT * (ε) := {t ∈ T | R(t, w * (t)) -R * ≤ ε} (25)as well as the functionF k : ℓ ∞ (T × S d-1 ) → R by F k (z) := sup s∈T * (ε k ) sup v∈S d-1 z(s, v).Note on the one hand that ∩ k≥1 T * (ε k ) = T * , and on the other that F k is continuous for all k ∈ N, and in fact Lipschitz. Indeed, let z, z ′ ∈ ℓ ∞ (T × S d-1 ). Then|F k (z) -F k (z ′ )| = sup s∈T * (ε k ) sup v∈S d-1 z(s, v) -sup s∈T * (ε k ) sup v∈S d-1 z ′ (s, v) ≤ ∥z -z ′ ∥ ∞ Now let k ∈ N and x ∈ [0, ∞). Then P G 2 n ( tn ) > x = P G 2 n ( tn ) > x ∩ tn ∈ T * (ε k ) + P G 2 n ( tn ) > x ∩ tn / ∈ T * (ε k ) ≤ P G 2 n ( tn ) > x ∩ tn ∈ T * (ε k ) + P tn / ∈ T * (ε k ) ≤ P sup s∈T * (ε k ) G 2 n (s) > x + P R( tn , w * ( tn )) -R * > ε k = P F 2 k (G n ) > x + P R( tn , w * ( tn )) -R * > ε k taking the limit as n → ∞, the first term converges, by the continuous mapping theorem, to the probability of the event F 2 k (Z) > x , where Z is the limiting Gaussian process discussed above, while the second term vanishes by the first part of Theorem 3. Therefore, for all k ∈ N,lim sup n→∞ P G 2 n ( tn ) > x ≤ P sup s∈T * (ε k ) Z 2 (s) > xTaking the limit as k → ∞, noticing that the eventssup s∈T * (ε k ) Z 2 (s) > xare nested, using the continuity of probability from above, and recalling thatEQUATION)Using properties of the quantile function (e.g. [EME24, Lemma 20]) finishes the proof of the upper bound. For the lower bound, we make a similar argument. We have, by an application of Lemma 4,n • [R( tn , ŵn ) -R * ] ≥ n • [R( tn , ŵn ) -R( tn , w * ( tn ))] ≥ 1 2 • 1 (1 + ∥n -1/2 Λ n ∥ ∞,-) 2 • G 2 n ( tn ).By the Glivenko-Cantelli assumption on Λ n , the first two factors converge to 1/2. For the third, we will lower bound its upper tails, which will imply a lower bound on the upper tails of the rescaled excess risk. We let (ε k ) ∞ k=1 be a decreasing sequence of positive numbers such that ε k → 0 as k → ∞, and defineH k : ℓ ∞ (T × S d-1 ) → R by H k (z) := inf t∈T * (ε k ) sup v∈S d-1 z(t, v),where the subsets T * (ε k ) are as defined in (25). Clearly, for z, z′ ∈ ℓ ∞ (T × S d-1 ), |H k (z) -H k (z ′ )| ≤ ∥z -z ′ ∥ ∞ so H k is Lipschitz and therefore continuous. Now P G 2 n ( tn ) > x ≥ P G 2 n ( tn ) > x ∩ tn ∈ T * (ε k ) ≥ P inf s∈T * (ε k ) G 2 n (s) > x -P tn / ∈ T * (ε k ) = P H 2 k (G n ) > x -P R( tn , w * ( tn )) -R * > ε kBy the same argument as above, we obtain, as n → ∞, and for all k ∈ N,lim inf n→∞ P G 2 n ( tn ) > x ≥ P inf s∈T * (ε k ) Z 2 (s) > xTaking the limit as k → ∞, and noticing thatk≥1 inf s∈T * (ε k ) Z 2 (s) > x = inf s∈T * Z 2 (s) > x proves that lim inf n→∞ P G 2 n ( tn ) > x ≥ P inf s∈T * Z 2 (s) > x .Using properties of the quantile function (e.g. [EME24, Lemma 20]) finishes the proof of the lower bound. The estimates on the quantiles of Z + in Remark 1 are a consequence of standard Gaussian concentration, see [e.g. EME24, Appendix A.3]. Finally, the second statement in Remark 1 can be derived as follows. By definition, Z(s)d = ∥Z s ∥ 2 where Z s ∼ N (0, Σ -1/2 (s)G(s)Σ -1/2 (s)), so E max s∈T * Z 2 (s) ≤ E   s∈T * Z 2p (s) 1/p   ≤ s∈T * E Z 2p (s) 1/p ≤ 32 • p • s∈T * E Z 2 (s) p 1/pwhere the last estimate follows from Gaussian concentration. Taking p = 1 + log|T * |, and recalling that for x ∈ R d , ∥x∥ p ≤ d 1/p ∥x∥ ∞ yields the result.We prove the first statement by induction. For k = 0, this follows directly from the fact that by definition F 0 n,δ (T ) = T and F n,δ (T ) ⊆ T . Now let k ∈ N and assume that the statement holds fork -1. Let s ∈ F k+1 n,δ (T ). Then by definition R(s, w * (s)) -R * ≤ 2 • (nδ) -1 • E[ sup s∈F k n,δ (T ) G 2 n (s)] ≤ 2 • (nδ) -1 • E[ sup s∈F k-1 n,δ (T ) G 2 n (s)].where the second inequality follows from the fact that by the induction hypothesis, F k n,δ (T ) ⊆ F k-1 n,δ (T ), and that the supremum is increasing. Therefore s ∈ F k n,δ (T ) since the last inequality is the defining inequality for F k n,δ (T ). We now turn to the second statement. Fix k and δ. On the one hand, T * ⊆ n≥1 F k n,δ (T ). On the other, for any t ∈ n≥1 F k n,δ (T ), we have for all n ≥ n 0 , R(t, w * (t)) -R * ≤ 2B • (nδ) -1 . Therefore R(t, w * (t)) -R * = 0, and hence t ∈ T * .Recall the notation introduced in Appendix C. Let A n (t * ) be the event that:∥n -1/2 Λ n ∥ ∞,+ ≤ 1/2, and ∥n -1/2 ∆ n (•, t * )∥ ≤ 1 2 .We start by showing that under the sample size inequality stated in the theorem, there exists a t * ∈ T * such that P(A n (t * )) ≥ 1 -δ/2. Indeed, we have∥n -1/2 Λ n ∥ ∞,+ = sup (t,v)∈(T ,S d-1 ) 1 n n i=1 1 -⟨v, Σ -1/2 (t)ϕ t (X i )⟩ 2The elements of this sum are bounded by 1, and the variance parameter of Bousquet's inequality [Bou02] is given by L as defined in Section 3.2. Applying this inequality yields that with probability at least 1 -δ/4EQUATIONFurthermore, by Markov's inequality, with probability at least 1 -δ/4∥n -1/2 ∆(•, t * )∥ ∞,+ ≤ 4 • E[sup t∈T \T * ∆(t, t * )]n 1/2 • δ Hence, when the inequality on the sample size stated in the theorem holds for some t * , the event A n (t * ) holds with probability at least 1 -δ/2. Now on this event, the first bound of Lemma 4 applies, and we haveEQUATIONNow we use the iterative localization method of Koltchinskii [Kol06] . Initially, we have no information about where tn is located aside from belonging to T , so we start with the boundEQUATIONUsing Markov's inequality, we have on an event B n,1 which holds with probability at least 1 -δ/2ksup t∈T G 2 n (t) ≤ 2k • δ -1 • E[sup t∈T G 2 n (t)].Replacing in (28) yields that on the eventA n (t * ) ∩ B n,1 , R( tn , w * ( tn )) -R * ≤ 4k • (nδ) -1 • E[sup t∈T G 2 n (t)],which shows that on this event, tn ∈ F n,δ/2k (T ), by definition of the map F n,δ/2k . With this knowledge, we now reuse the bound (27) to obtain that onA n (t * ) ∩ B n,1 R( tn , w * ( tn )) -R * ≤ 2 • n -1 • sup t∈F n,δ/2k (T ) G 2 n (t).Iterating the procedure we just described k times, we obtain that on an eventEQUATIONas well as supEQUATIONSinceEQUATIONproves the first statement of the theorem. For the second statement, we have on the same event E, and combining the two upper bounds from Lemma 4,E( tn , ŵn ) ≤ 4 • n -1 • G 2 n ( tn ) ≤ 4 • n -1 • sup t∈S n,δ,k G 2 n (t) ≤ 8k • (nδ) -1 • E[ sup t∈S n,δ,k G 2 n (t)],where we used (29) and (30) in the above inequalities.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. For each (i, t) ∈ [n] × T , let Z i,t ∈ R d be random vectors such that for each t ∈ T , (Z i,t ) n i=1 are i.i.d. with the same distribution as Z t . For all t ∈ T , assume that E[Z t ] = 0, and defineσ 2 (T ) := sup t∈T E ∥Z t ∥ 2 2 , r(T ) := E sup (i,t)∈[n]×T ∥Z i,t ∥ 2 2 1/2 . Then 1 2 • σ(T ) n 1/2 + 1 4 • r(T ) n ≤ E   sup t∈T 1 n n i=1 Z i,t 2 2   1/2 ≤ C(T ) • σ(T ) n 1/2 + C 2 (T ) • r(T ) n ,where C(T ) := 5 1 + log|T |.To prove Lemma 5, we need to recall a few preliminary results. i,t . Define W i,t := W i,t -E[W t ]. Then 1 2 E   sup t∈T 1 n n i=1 ε i W i,t 2 2   1/2 ≤ E   sup t∈T 1 n n i=1 W i,t 2 2   1/2 ≤ 2 E   sup t∈T 1 n n i=1 ε i W i,t 2 2   1/2.The second result we recall is the Khinchin-Kahane inequality, the specific form we require is obtained from De la Pena and Giné [DG12, Theorem 1.3.1] by setting q = p and p = 2 in that theorem, see also Boucheron, Lugosi, and Massart [BLM13, page 141]. Lemma 7. For i ∈ [n], let z i ∈ R d be fixed vectors. Let (ε i ) n i=1 be independent Rademacher random variables. Then for all p ≥ 2,E n i=1 ε i z i p 2 1/p ≤ p -1 • n i=1 ∥z i ∥ 2 2 1/2 .A straightforward consequence of Lemma 7 is the following result, which follows from the elementary observation that for a vector x ∈ R d , ∥x∥ ∞ ≤ ∥x∥ p ≤ d 1/p ∥x∥ ∞ . Lemma 8. For (i, t) ∈ [n]×T , let z i,t ∈ R d be fixed vectors. Let (ε i ) n i=1 be independent Rademacher random variables. ThenE   sup t∈T n i=1 ε i z i,t 2 2   1/2 ≤ 5 2 1 + log|T | • sup t∈T n i=1 ∥z i,t ∥ 2 2 1/2 .Proof. Let p ≥ 1. Then, by Jensen's inequality and Lemma 7E   sup t∈T n i=1 ε i z i,t 2 2   ≤ E      t∈T n i=1 ε i z i,t 2p 2   1/p    ≤   t∈T E   n i=1 ε i z i,t 2p 2     1/p ≤ (2p -1) • t∈T n i=1 ∥z i,t ∥ 2 2 p 1/p .Recalling that ∥x∥ p ≤ d 1/p ∥x∥ ∞ for all x ∈ R d and taking p := 1 + log|T | yields the result.Finally, we need the following consequence of Lemmas 6 and 8. The proof idea is taken from [Tro16] .Lemma 9. For each (i, t) ∈ [n] × T , let W i,t ∈ R be random variables such that for each t ∈ T , (W i,t ) n i=1 are i.i.d. with the same distribution as W t , with W t ≥ 0 almost surely. ThenE sup t∈T n i=1 W i,t 1/2 ≤ sup t∈T n i=1 E[W i,t ] 1/2 + 5 1 + log|T | • E sup (i,t)∈[n]×T W i,t 1/2 .Proof. We have by Jensen's inequality and Lemma 6,EQUATIONConditioning on the random vectors W i,t , we have by Lemma 8 and the assumption W i,t ≥ 0 a.s.2 E   sup t∈T n i=1 ε i W i,t 2   1/2 ≤ 5 (1 + log|T |) • sup t∈T n i=1 W 2 i,t 1/2 , ≤ 5 1 + log|T | • sup (i,t)∈[n]×T W i,t 1/2 • sup t∈T n i=1 W i,t 1/2.Taking expectation with respect to W i,t , and using the Cauchy-Schwartz inequality yields2 E   sup t∈T n i=1 ε i W i,t 2   1/2 ≤ 6(1 + log|T |) • E sup (i,t)∈[n]×T Z i,t 1/2 • E sup t∈T n i=1 W i,t 1/2 .Replacing in (31) and solving the resulting quadratic inequality yields the result.Equipped with these results, we now prove Lemma 1. The proof idea is taken from [Tro16] .Proof of Lemma 1. We start with the lower bound. We have on the one handEQUATIONOn the on other hand, by Lemma 6, we haveE   sup t∈T 1 n n i=1 Z i,t 2 2   1/2 ≥ 1 2 E   sup t∈T 1 n n i=1 ε i Z i,t 2 2   1/2 . Define the random index I ∈ argmax i∈[n] max t∈T ∥Z i,t ∥ 2 2 .Conditioning on Z i,t , we have by Jensen's inequalityE   sup t∈T 1 n n i=1 ε i Z i,t 2 2   ≥ sup t∈T E   E 1 n n i=1 ε i Z i,t 2 2   = sup t∈T ∥Z I,t ∥ 2 2 n 2 = sup (i,t)∈[n]×T ∥Z i,t ∥ 2 2 n 2 ,where in the inequality, the outer expectation is with respect to ε I , and the inner one is with respect to (ε i ) i̸ =I . Taking expectation with respect to Z i,t givesEQUATIONAveraging the lower bounds (32) and (33) yields the desired lower bound. We now turn to the upper bound. We have by Lemmas 6 and 8.E   sup t∈T 1 n n i=1 Z i,t 2 2   1/2 ≤ 2 E   sup t∈T 1 n n i=1 ε i Z i,t 2 2   1/2 ≤ 5 1 + log|T | • E sup t∈T n i=1 1 n Z i,t 2 2 1/2Applying Lemma 9 on the last term yields the desired upper bound.The Glivenko-Cantelli and Donsker assumptions of Theorem 3 follow directly from the moment assumptions of the corollary, the weak law of large numbers, and the central limit theorem, and therefore the conclusions of Theorem 3 hold. For the first statement of the corollary, we may assume without loss of generality that T * ̸ = T , otherwise the statement holds trivially. Define ε := min The statement follows from the same argument as Theorem 4 with only a few simple modifications. As explained in the main text, we use Lemma 3 to bound the quantity E[max t∈T Λ n (t)] by constructing a block diagonal matrix. We use Lemma 2 to control, for any subset S, E max s∈S G 2 n (s) . The only minor deviation from Theorem 4 is that we bound the second momentE sup t∈T \T * ∆ 2 n (t, t * )instead of the first. This explains the slightly better dependence on δ in the sample size restriction of Theorem 2 compared to Theorem 4.We assume without loss of generality that if t, s ∈ T with t ̸ = s, then ϕt and ϕs induce different linear classes of functions, i.e. there is no linear map A such that ϕt(x) = Aϕs(x) for all x ∈ X .See [VW96, Section 2.1] or the proof of Theorem 3 for a more precise definition.See the proof of Theorem 3 in Appendix D for a precise definition of the process (Z(t))t∈T . 


Decision: The paper investigates the performance of empirical risk minimization (ERM) in the context of feature learning. The predicted function first maps the input into the feature space, and then derives the output through a linear mapping. An asymptotic upper bound of the excess risk of ERM, and a non-asymptotic upper bound are derived. The paper is technically sound with rigorous proofs. Concerns, nonetheless, include the narrow setting of the main results (see the review and comments by Reviewers qDCv and rL5m), the lack of a minimax lower bound (see the review and comments by Reviewers rL5m and 9KPn), and the 1/δ term in the non-asymptotic upper bound (see the review and comments by Reviewers 9KPn and bjqG). I strongly encourage the author(s) to take the reviewers' comments inside and address these points in the final version.

Reviews: review: paper_summary: paper_summary: The paper considers a linear regression problem where an ERM learner tries to learn a linear predictor and a feature map (over a countable set of feature maps) under some specific assumptions on the set of feature maps and the property of minimizers. The paper analyzes both asymptotic and non-asymptotic behaviors of the excess risk in the problem above and suggests that it matches the rate of the case when we only learn linear predictors on top of a fixed feature map, which is surprising.
strength_weakness: strength_weakness: The main concern about this paper.
1. The setting is narrow: when I think about feature learning, I imagine we first learn a feature map that gives a good representation of the data. We then want to use the learned feature map that adapts it to a downstream task, which is a linear regression with squared loss in this case. The setting this paper proposed is somewhat the way around: (1) Given a feature map, learn the best linear predictor, (2) Select the best feature map. It seems to me that this paper is considering a non-linear regression problem, not feature learning. More precisely, the paper is trying to solve the problem learn the best feature map specified for the linear regression task. What can we tell about the learned feature map on other downstream tasks? Why the title of the paper is "On the Efficiency of ERM in Feature Learning", instead of "On the Efficiency of ERM in Non-linear Regression"?

2. If we look at the picture from that perspective, prior results (Theorem 1, Theorem 2) seem good enough for me. Given a learned feature map, under some conditions, I have a fast rate of learning a linear predictor. Of course, it is not feature learning at all, but it tells something about the learned feature map on a specific downstream task (linear regression), which is fair enough. There is no need (at least for me) for a result explaining if I learn a linear predictor with squared loss along with a feature map specifically designed for linear regression, what the sample complexity is.

Comments on the Conclusion.
1. The claims on potential explanations for generalization in DNNs: To the best of my knowledge, the reason behind that should be explained by the geometry of the loss landscape of over-parameterized models and the implicit bias of (stochastic) optimization algorithms used. I would not go into detail since it goes beyond the scope of this paper. However, this paper: (1) considers an optimization oracle for ERM, and (2) does not assume any geometry of the set of feature maps indexed by $\mathcal{T}$. Therefore, linking the results in this paper to generalization in DNNs seems unnecessary and inappropriate for me.

Minor comments
1. In the Appendix, it might be helpful if the authors first give a proof sketch for each result for readability. 

Minor typos:
 1. Line 164, a comma missing after the inequality.
 2. Line 501, should the RHS be $\frac{1}{2}||\nabla{R(w^*)}||_{\Sigma^{-1}}$? 
 3. Multiple commas, dots after (in)equalities missing in the Proof of Theorem 1, 2. 

After all, it might be too harsh to undervalue this paper based on the points above. I still think it is a good paper, and the results do not have to be connected to Feature Learning and Generalization to be meaningful.
questions: questions: See Weaknesses.
limitations: limitations: See Weaknesses.
paper_summary: paper_summary: This paper studies the novel setting where we are give  a collection of predefined feature maps (indexed by a set T) and we choose one of these feature maps and then, learn a linear predictor on top of the chosen feature map. The authors derive upper bounds on the excess risk that depend on the number (size) of "optimal" feature maps and not the size of the set T.
strength_weakness: strength_weakness: - The analysis ignores the role of the learning algorithm and looks at the problem from a purely statistical perspective. The role of implicit bias of the algorithm is not seen here. On a high level, from the set of optimal features, some features are easier to learn/ achieve than others. This might also shrink the effective size of the features. 

- The suprema term in the expression of Theorem 4 is not very interpretable. The case of finite features in the next section makes it more clear. However, I find the finite case not that interesting. Is there an interesting non-finite case that one can analyze to get an interpretable result?

- In general, the features are also learned from data and this gives extra dependencies and goes beyond the setting of this paper (unless some sample splitting is done).

- Can the authors comment on the tightness of Theorem 3 and 4? An the potential challenges of coming up with lower bounds?

- The paper will greatly benefit from a simulation result to support the main finding of the paper. For example, for a simple finite feature case. A theoretical example can also help.
questions: questions: See weaknesses.
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_summary: This paper consider the problem of regression over the linear classes induced by a collection of feature maps. They study both the asymptotic and the non-asymptotic behavior of the empirical risk minimizer. Surprisingly, although the linear classes has a complexity much higher than that of only one linear map, the authors find that when there is a unique optimal feature map, ERM actually behaves similar with the oracle procedure (knows a priori the optimal feature map). General results for non-unique or even infinite feature map is also provided. The authors also apply their non-asymptotic result on finite feature map cases.
strength_weakness: strength_weakness: It will be good if more case studies are provided.
questions: questions: Is it possible to consider some infinite feature map set with some structure, so that you can also compute the constants in your results?
limitations: limitations: No limitations are stated.
paper_summary: paper_summary: This paper investigates the learning theory of empirical risk minimization (ERM) with feature learning. Under the setting where the optimal finite-sample feature is selected by minimizing the empirical risk over a class of features, the authors show that ERM with feature learning implies convergence of the excess risk under certain assumptions. Moreover, other statistical properties, such as asymptotic normality, are also derived.
strength_weakness: strength_weakness: 1. The title "On the Efficiency of ERM in Feature Learning" seems misleading. Initially, it suggests that ERM should aid feature learning. However, after reading the paper, it appears that the authors are discussing the statistical performance of ERM in the context of feature learning, without clearly demonstrating how ERM aids in feature learning.

2. The authors have reviewed many statistical theory papers. However, in terms of feature learning or representation learning, they didn't conduct a thorough literature review. Specifically, for the final-layer feature, recent studies show that the last-layer feature will converge to an Equiangular Tight Frame (optimal feature for classification problems), which is known as neural collapse, as proposed by Papyan et al. in their paper "Prevalence of neural collapse during the terminal phase of deep learning training." There are some subsequent studies that show that the optimal feature is indeed the minimizer of a regularized ERM. These studies include but are not limited to "Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training" (Fang et al., 2021); "A Geometric Analysis of Neural Collapse with Unconstrained Features" (Zhu et al., 2021); and "Neural Collapse in Multi-label Learning with Pick-all-label Loss" (Li et al., 2024). For different loss functions, the authors may refer to "Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path" by Han et al. Regarding learning theory, the sample complexity under neural collapse is investigated by Wang et al. (2024) in their work "Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning."

3. Some of the claims are confusing and may be over-claimed. Specifically, in the Conclusion, the authors claim that their theory might be used to explain the double descent phenomenon and generalization of deep learning with label noise in Zhang et al., 2021. However, the feature learning setting in this paper is far from being extended to the deep learning setting. Indeed, their assumptions here, such as the moment assumption, should hold for all feature maps in the hypothesis class, which is not verified for deep neural networks. However, existing feature or representation learning theory such as the Neural Collapse theory can partially explain the phenomenon in Zhang et al., such as the overfitted model can still generalize.

4. As the theory is not as enlightening as the authors claimed in their paper since their setting is not practical, this should be regarded as a purely theoretical paper. As a theoretical paper, there should be some room for improvement, such as verifying the assumptions for all feature maps (such as the moment assumptions in Theorem 4) for a certain class. Moreover, as a purely statistical theory paper, a lower bound showing that the obtained finite-sample rate is optimal is necessary for a high-quality publication. It would also be better for the authors to emphasize more technical difficulties compared to ERM without feature learning. In fact, under the Glivenko-Cantelli assumptions and the finite sample assumptions, both the asymptotic theory (Theorem 3) and the non-asymptotic theory (Theorem 4) look like a simple extension of Theorem 1 and Theorem 2 without feature learning, while Theorem 1 and Theorem 2 are not novel in learning theory.
questions: questions: Please address my concerns in the weaknesses part.
limitations: limitations: Yes
paper_summary: paper_summary: This paper considers a "feature learning" setting equivalent to structural risk minimization over a set of hypotheses of the form $\langle w, \phi_t(x)\rangle$. It demonstrate that the statistical error of this procedure converges to a quantity that depends on a natural empirical process defined *only* in terms of the classes which contain an optimal predictor. Thus, it is claimed that ERM is "efficient" at feature learning in a natural way.

EDIT: I raise my score from a 5 to a 6. I encourage the authors to include the counterexample presented to me in the rebuttal in the main text as a form of motivation, and as a didactic example to express "what goes wrong". The authors can also remark about situations under which better dependence on $\delta$ is achievable. Thank you to authors for addressing my points.
strength_weakness: strength_weakness: There are a couple weaknesses, however, that temper my excitement. 

(1) I apologize for the directness, but I do not find the qualitative finding particularly surprising. We know that ERM localizes, and as a consequence, if I have a predictor class of the form 

$\mathcal F= \bigcup_{t \in \mathcal{T}} \mathcal{F}_t$, and all optimal predictors lie in $\mathcal F_t, t \in \mathcal{T}^{\star}$, and moreover, the risk of an  $f \in \mathcal{F}_t$ where, $t \notin \mathcal{T}^{\star}$ is lower bound away from zero, then localization should force the limiting behavior of the problem to only depend on the statistical complexity of 

$\bigcup_{t \in \mathcal{T}^\star} \mathcal{F}_t$

It is nice to quantify this rigorously, but again, the phenomenon does not seem to be to bring fundamentally new insight. 

(2) The non-asymptotic dependence on the probability of error $\delta$ is quite bad. Indeed, an $O(1/\delta)$ dependence is not even integrable, obviating in expectation bounds (perhaps in-expectation in too much to ask for, given the possibility that the covariance matrices become singular. Still, this seems like a major limitation. 

(3) While the problem setting is remarkably clean, Theorem 4 is not. This seems inevitable, and the authors both (a) explain its intuition and (b) instantiate it for a natural class of problems...

(4) I think the authors should include some more intuition about the relevant increments and terms defined in the paper ($G_n(t)$, $\Lambda_n(t)$) and so forth. Citing that "such and such is just such and such in Bos[02]" does not help with intuition building. The authors might consider adding a section in the appendix that elaborates further, and also provides formal definitions of what it means for a class to be Glivenko Cantelli (this was relatively clear) and, more importantly, Donsker (as a reader with the relevant background, I know what is meant, but this could be less accessible to others). The authors might also consider remarking on what limitations the Donkser-ity of the problem entail (e.g. sufficient restriction on metric entropy).
questions: questions: Can the authors please explain why the localization phenomenon presented in this work is surprising?
limitations: limitations: (1) Weak dependence on error probability $\delta$
(2) Possible limitations due to the Donkser assumption
(3) Restricted to the linear setting

Comments: title: Following up
discussion
Reply to the rebuttal
Rebuttal (continued)
comment: Thank you, authors, for your detailed feedback. As indicated in my updated review, I raised my score to reflect that my concerns were addressed.
Thanks for your reply.
Dear Reviewer bjqG,

Thank you very much for submitting your review report. The author(s) have posted responses to your review. Could you kindly provide comments on whether your concerns have been adequately addressed?

Best regards, AC
1. Please delete the discussion about the potential to explain [Zha+21]. In fact, [Zha+21] shows that even though the training procedure may overfit the training data, the trained model can still generalize (a.k.a., double descent), which motivates the idea of representation learning, such as neural collapse. However, I do not see the potential of using this paper to explain the double descent phenomenon in deep learning.

2.Regarding optimality, STL focuses more on sample complexity in the non-asymptotic sense, such as the minimax optimal rate, which is also mentioned by the author in the introduction. The minimax lower bound is not provided in the current version, which I believe should be the most interesting aspect of an STL paper.


Overall, the derived theory does not significantly contribute to the field of representation learning, and regarding STL, the bound is not minimax optimal. Therefore, I will keep my score as is.
We thank the reviewer for their response.

---

***The representation learning theory, such as neural collapse, is more related to [Zha+21], as I mentioned. Thus, it is connected to statistical learning theory (STL) since STL aims to derive statistical properties of certain phenomena in machine learning, not just the asymptotic properties or the error bounds. BTW, they can partially explain some phenomena occurring in deep learning, whereas classical (asymptotic or non-asymptotic) learning theory may fail to do so.***

Our work is most closely related to the literature that aims at understanding machine learning procedures through upper and lower bounds on their performance, which we called *statistical learning theory*, but we understand that we might be using the term differently from the reviewer. This will be clarified in the paper once we include a discussion of the additional line of work pointed out by the reviewer.

Our comments on the relationship between our work and the experiments [Zha+21] are a minor aspect of our paper. They should be seen merely as an invitation to the reader to look at the problem of explaining these experiments through a new perspective.

---

***The most important part I mentioned, the sharpness of the derived bound, is currently not discussed in the rebuttal (maybe due to the limited space?). As I said, once the theoretical framework is formalized, a lower bound that matches the upper bound is essential for a purely theoretical paper, which I believe is common sense in STL (such as in those papers published in AOS).***

The second statement of Corollary 1 in our paper provides matching upper and lower bounds on the asymptotic quantiles of the excess risk of ERM, and the gap between these bounds is a factor of *two*.

The general statement of Theorem 3 only contains an upper bound, but it is straightforward to check that the argument behind the lower bound in Corollary 1 immediately extends to the general case. In this case however, it yields a lower bound on the quantiles of the excess risk of the same form as the upper bound in Theorem 3, but with the supremum replaced by an infimum.

Roughly speaking, this gap is due to the fact that the sequence of ERMs can “oscillate” between optimal feature maps. This problem already appears if one considers only two features maps which are both optimal, and to the best of our knowledge no matching upper and lower bounds on the quantiles of the excess risk are known even in this simple case.

On the non-asymptotic front, we note that even in the linear regression case, Theorem 2, there is no known matching lower bound to the upper bound we presented. One may sacrifice interpretability and instead use a tighter upper bound in terms of the quantiles of $\||g(X, Y)\||_{\Sigma^{-1}}^{2}$, which can be reversed up to an absolute constant and a different dependence on $\delta$, under the sample size restriction of the theorem. Moving from the linear regression setting to the case of multiple feature maps we study is more delicate however, and the iterative localization method of [Kol06] we used only yields upper bounds, and sheds little light on lower bounds. Despite this shortcoming, as we have emphasized in the paper, the upper bound we derived in Theorem 4 is asymptotically tight in that it is consistent with the asymptotic behavior of the excess risk we derived in Theorem 3 and Corollary 1.

If the reviewer thinks the above discussion on lower-bounds is interesting, we would be happy to include it in the final version.
We thank the reviewer for their feedback and appreciate their comments. We will make use of the additional space in the final version of the paper to address the two points raised by the reviewer.
1. The representation learning theory, such as neural collapse, is more related to [Zha+21], as I mentioned. Thus, it is connected to statistical learning theory (STL) since STL aims to derive statistical properties of certain phenomena in machine learning, not just the asymptotic properties or the error bounds. BTW, they can partially explain some phenomena occurring in deep learning, whereas classical (asymptotic or non-asymptotic) learning theory may fail to do so.

2. The most important part I mentioned, the sharpness of the derived bound, is currently not discussed in the rebuttal (maybe due to the limited space?). As I said, once the theoretical framework is formalized, a lower bound that matches the upper bound is essential for a purely theoretical paper, which I believe is common sense in STL (such as in those papers published in AOS).
I thank the authors for the detailed feedback. I am still not convinced with the "feature learning" setting and for me, it is more of a non-linear regression setting. I am also aware of the works that the authors refer to, but to be honest, I do not really like those works and their settings. However, I know that I am being biased, and it also does not affect the contributions of this paper. 

As for the conclusion, it would be nice if the authors spent more time discussing the linking between the results and generalization in DNNs in multiple views: (1) how it (potentially) explains generalization (2) the drawback of current settings (and assumptions) and how it conflicts with other potential explanations of generalization in DNNs. 

Overall, I still find it a good paper, and I will keep my origin evaluation.
I thank the authors for their very thorough response. 

The only reason I'm not giving a higher score is that as I discussed in my review, the setting of the paper is very general (as the authors also point out in their paper) and I'm not 100% sure how much the results of this very general setting can shed light on what is happening in practical scenarios. However, this is a very solid paper, giving theoretically neat results for a very general setting, and should be accepted at NeurIPS.
***I think the authors should include some more intuition about the relevant increments and terms defined in the paper ($G\_{n}(t)$, $\Lambda\_{n}(t)$) and so forth. Citing that "such and such is just such and such in Bos[02]" does not help with intuition building.  The authors might also consider remarking on what limitations the Donkser-ity of the problem entail (e.g. sufficient restriction on metric entropy).***

We will aim at providing more intuition when defining our terms in the final version of our paper. In particular, we will replace the particular passage referred to by the reviewer by the following sentence:

*"The parameter $L$ characterizes the deviation of the supremum of the empirical process $\Lambda\_{n}(t)$ from its mean."*

As for Donskerity, we have refrained from referring to metric entropy in the paper except very briefly in lines (229-230). Our hope was to keep the paper accessible, and as such we preferred to describe Donskerity by analogy to the central limit theorem (lines 157-158). We will briefly mention that Donskerity can be established under appropriate metric entropy restrictions in the main paper, and defer a more in depth discussion to the Appendix.

***The authors might consider adding a section in the appendix that elaborates further, and also provides formal definitions of what it means for a class to be Glivenko Cantelli (this was relatively clear) and, more importantly, Donsker (as a reader with the relevant background, I know what is meant, but this could be less accessible to others).***

We agree with the reviewer's suggestion, and we will add such a section in the Appendix.