On the Efficiency of ERM in Feature Learning
Authors: Ayoub El Hanchi
Chris J. Maddison
Murat A Erdogdu
Venue: NeurIPS 2024 poster (2024)
Keywords: Empirical risk minimization
Feature learning
Learning theory
Sparse linear regression
Primary area: learning_theory

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.

On the Efficiency of ERM in Feature Learning
Ayoub El Hanchi University of Toronto & Vector Institute aelhan0cs. toronto. edu
Chris J. Maddison University of Toronto & Vector Institute cmaddis@cs. wor.oto...oooooooooooooooooooo..
Murat A. Erdogdu
University of Toronto Vector Institute
erdogduucs toronto. edu
Abstract
Given collection of feature maps indexed by a set 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 linear predictor. We start by studying the asymptotic quantiles of the excess risk of sequences empirical risk minimizers. Remarkably, we show that when the set T is not too large and when there is 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 priori this optimal feature map and deterministically outputs empirical risk minimizer from the associated optimal linear class. We complement this asymptotic result with non-asymptotic analysis that quantifies the decaying effect of the global complexity of the set T on the excess risk ERM, and relates it to the size of the sublevel sets of the suboptimality of the feature maps. As application of our results, we obtain new guarantees on the performance of the best subset selection procedure in sparse linear regression under general assumptions.
Introduction
A central idea in modern machine learning is that of data-driven feature learning. Specifically, instead of performing linear prediction top of handcrafted 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 -aasnndg-basedd based models?
In this paper, we investigate this question a general setting. We study the performance of empirical risk minimization (ERM) 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 set X, and let (ot)EET, &x X + Rd, be collection of feature maps indexed by a T. For given regression task and i.i.d. samples, our aim is to understand the performance of ERM over the class of predictors ULeT + (w, (xx))
Idd function of the sample size, the distribution of the data, and relevant properties of the collection of feature maps (Φt)ETT.
Classical mniform-convvegennce based analyses would suggest that the performance of ERM 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.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Formal setup. We briefly formalize our problem here. Let X be the random input taking value in a set X, and let (or) 9t : X - R.. be a collection of feature maps indexed by set T. Let Y E IR 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 predictors {x - (we, (x)) (t, w)) E T x ]. We evaluate the quality of single prediction ý given the ground truth y through the loss function {(D v) :- (Ú- -
ho)--///2 /)2 and the overall quality of predictor
(1, w)) E TTx x IRd through its risk
R(I, E[e((w,, (z) Y)
R, inf R((,w). w).
(L.))TxRR
We assume that we have access to n i...d samples (X,, Yi) with the same distribution as (X, Y), and perform empirical risk minimization
(fn, wa) E argmin (t, w) where (t, == n Σ (X,)), Y,). (f,w)ETxR<
Our goal is to characterize the excess risk E(i,, úx) == Miin, (6n) - R..
Related work. The study of upper bounds on the excess risk of ERM in general setting is 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 [Ta196] and its refinements [e.g. BLMO0; Bou02], literature emerged that provided more fine-grat fine-grained control of the excess risk of ERM [e.g. BBM05; Ko106; BM06]. A key idea emerging from this line of work is localization. This concept, and in particular the iterative localization method of Koltchinskii [Ko106], plays an important role in our development. We refer the reader to the books [Koll1; Wai19], as well as the recent articles [LRS15; 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; JRTO8; LM09], linear [e.g. LM16b; 0lil6; Mou22], and convex classes [e.g. LM16a; Men LRS15]. A key development in this area over the last decade has been the realization that such bounds be obtained under much weaker assumptions than previously thought, owing to the fact that only one-sided control of certain empirical process is needed, and which be obtained under very weak assumptions [Men14; KM15; 0li The line of work most closely related to ours is the one on random-desige linear regression [AC1]; HKZ12; Oli16; LM16b; Saul& Mou22; EE23], and view our work as an extension of this literature. We review these results in more detail in Section 2.
Finally, and more conceptual level, our work is related to the recent effort to understand the effect of feature learning on the performance of neural networks [c.g. Bac Gho+20; Ba+22]. Beyond this conceptual connection however, our work is quite distinet 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 multiple kernel learning [e.g. Lan+04; GA11; SD16), although 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 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 Tiindexed empirical processes, which in the linear setting reduce to single random variables that are casily dealt with.
Organization. The rest of the paper is organized as follows. In Section 2, we review known results 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 Section with brief discussion.
'We assume without loss of generality that if E T with t + s, then di and 6. induce different linear classes of functions, ie. there is matrix A such that (x(x)) = A6.(x) for all E X.

---

2 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 7 indexing the feature maps is singleton. As such, to avoid introducing further notation, we use the one from the previous section, while dropping the dependence on & 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, define
Σ = E[((X)
Σn
TE E (X.)d(X.))
and let w, denote the unique minimizer of the risk R(w).² Then, elementary calculation shows that when En is invertible, there is a unique empirical risk minimizer and satisfies
Sn wh 2 (w,.).
(1)
Furthermore, since the risk is quadratic function of whose gradient vanishes, replacing R(wx) by the equivalent exact second order Taylor expansion around w, yields
R((r.) R(w.) = l - w. |1 (w,))
(2)
2
While exact, this expression is not readily interpretable. For example, how fast does this excess risk go to as a function of the sample size? The following classical result from asymptotic statistics [e.g. Whi82; LC06; Vaa98] makes this rate more explicit. To state it, define
g(X,)) == ((w, ((X)) Y);
G = F==F[g(>> [ V) (x, V)?
Theorem Assume for all j E [d. E (X)) Then, 00,
oC, E
< oo, and (X co.
4 1
n (w..)
2 1|
where Z Σ E1 In particular, for any 5 E (0, 0.1).
lim Qe((in) (1 8) EXlgg(X, Y)I +I+ (I log(1))))
where Qx (p) (ar TR P(X S x) 2 p} is the quantile function of random variable X, and where we write a x b to mean that there exists absolute constants C, e such that e b S S C In the above statement, they can be taken as C = 1 and e 1/32.
We provide a proof in Appendix for completeness. For our purposes, this theorem is most easily interpreted follows: for large enough n and small enough 8, if the excess risk of ERM is bounded by some quantity with probability at least 1 - 8, then this quantity is, up to a constant, least as large as the right-hand side of the second displayed equation divided by While our primary interest in non-asymptotic bounds, this asymptotic result, by virtue of its exactness, provides us with benchmark against which such bounds can be compared. In particular, it identifies the quantity E[]l((X, 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 needs be for this expression be accurate. This motivates non-asymptotic analysis of the excess risk of ERM, which has been carried out numerous times in recent years [e.g. Oli16: LM16b; EE23].
A goal of this literature has been 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 [Men 14]. The following theorem is comparable to the best known result in this area. We leave the proof to Appendix B. To state it, we define
V (-122(X))((() 1/2-)) 27
sup E (1.--1126))) vCSá-1
L
Throughout, we assume without loss of generality that the support of the distribution of 6(X)) ) is not contained any hyperplane, which implies the invertibility of I and the uniqueness of w. [ef. Mou22].
3

---

Theorem 2. Assume that all j [d], [[)] < oc, E[r3] < xc, and Ellg(x, Y) <|< 80.
Let å E (0. 1). If
n 2 (512Amux (V) + log + (128L 11)
then with probability least 1 8,
EX) E((r,) $ 4- (
At a high-level, this result says that above a certain explicit minimal sample size, the asymptotic expression of the excess risk of Theorem is correct, up significantly worse dependence on d. The restriction on the sample size almost the best one can hope for. To see why, note that to get guarantees the excess risk of any empirical risk minimizer, we need least that Σ, 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 Amin (E 1/21/2 1/3). We refer the reader to more detailed discussion in [EME24, Section 5].
This result has two key qualities, which we aim to reproduce in our results. First, it is assumption- lean, requiring nothing more than fourth moment assumption on the coordinates of the feature map compared to Theorem Second, it recovers the right dependence on the intrinsic parameter (X, Y) - identified in Theorem 1. A downside of this generality is the bad dependence on 8. 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].
3
Main Results
In this section we state our main results. They are most easily seen as extensions of Theorems 1 and 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
E(t = (())()())
(t)(t == Σ de (x.))),,
We define the following collection of minimizers,
w. (1) := argmin R(1, w),
T. == argmin R(L, w. (1)),
wERe
TET
the first is uniquely defined, while the second is set-valued in general. We define the gradient of the loss these minimizers and their corresponding covariance matrices
gtt, Y)) = (x Y),
8(t,)) = [[g(t, (X, Y))g(s, (X, V))].
Finally, we introduce the following processes which play key role in development
An( == Vū-Amax 1e-Ammxx (I-E - (1),, as well as, for ta E T. and 1 T T.,
Gz)()) == vn- Rt, (0))) (3)
An ((t,tt))= = vn. (1 Ry, (t, Rn We (tx)) R(t, W. (t)) R.
(4)
We note that the process (A, (l, (a,ET)) is an empirical process (see [VW96] for an introduction). while (t) and (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, p. p.305-306] for 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, assume that T is countable.

---

Finally, in line with the literature on the theory of empirical processes [VW96], we say that sequence of empirical processes is Cantenko-Cantelli if, when rescaled by n 11/2, the supremum of their absolute value taken over their index set converges zero in probability as n co. other words, the weak law of large numbers holds uniformly over the index set. Similarly, we say that sequence of empirical processes is Donsker if converges in distribution to its limiting Gaussian process. In other words, the central limit theorem holds uniformly over the index set.
3.1 Asymptotic result
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 To * Ø and for some to E Tu, assume that the empirical processes Seivenko-Cantell Then, for all 0,
(O))E)).. (A(t,ta))ETTT. and (G.(t))eET
lim P(R((nn (eRlf, (fn)) - R. =.)=== n-000
Furthermore, if the sequence of processes (Gn(t))ET is Donsker, then for any 8 E (0, 1),
2 Qz (1 (1- -
& lim inf n Qe(tr)e))) (1 - 8) limsup n. QE(En 6) S Qz (1 8):
n
n+000
where 7- := ST. 1 Z+ == SuP.ET. (+) and (Z(1))TT is a mean-zero Gaussian for all t, T..
process with covariance function =
We note that, up to a factor of two in the upper bound on the asymptotic quantiles, Theorem reduces Theorem when T is singleton, with the exact same assumptions. We are not aware of comparable results in the literature. The proof of Theorem 3 can be found Appendix D.
Remark 1. For small 6, the upper bound admits the more interpretable expression
Qz (1 - 8) = E sup [z) + (o/( sup Amax ( (=))((( SET.
(5)
L
Furthermore, if T, is finite, the first term can be upper bounded as
E max (s) < 80 - Tol) max (illo(s, (X, (X,Y))--
(6)
SET.
To see why Theorem is surprising, let us first focus on the case where T. has a unique element tu. so that Z+ 2_ d |2112 where Z (0, oracle procedure, which knows beforehand what the optimal feature map t. is, and outputs t. and minimizer of R,,, (t_, w). Theorem says that, up factor of two, the asymptotic quantiles of the excess risk of ERM, which needs learn the large class UseT (x + (w, (x())) w RRd. coincide with those of the oracle procedure (by Theorem 1), which only needs to learn over the linear class {ar + (w, (x:) w IRd]!
Now consider the
More generally, Theorem establishes that asymptotically, any ERM picks a ncar-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 the extrema of the limiting Gaussian process of (G,, (t))eT
the set of optimal feature maps T.. This is surprising, it implies that asymptotically, and outside its role in determining whether the assumptions of Theorem hold, the global complexity of the set T is irrelevant to the excess risk of ERM.
Finally, we note that the Sibrenko-CCantllee and Donsker assumptions Theorem 3 can equivalently be viewed restrictions on the size of 'T. for distribution and process dependent notions of size. We refer the reader to the books [VW96; GN15) for more on this connection. With this observation, the main takeaway from Theorem 3 can be stated as follows.
Asymptotically, T is not too large, the excess risk of ERM depends, worst, only on the complexity of the set of optimal feature maps T., and is independent of the global complexity of T.
See [VW96, Section 2.1] the proof of Theorem 3 for precise definition.
5

---

3.2 Non-asymptotic result
The result in Theorem 3 hints dramatic localization phenomenon, whereby the influence of the size and complexity of the collection of feature maps (Øt)ETT on the excess risk of ERM vanishes as n + oo 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 the rate of decay of the excess risk of ERM non-asymptotically" (iii) What properties of the feature maps (Ør)LTT 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 parameter
(E LET
(())))))(())())))) -1)
: sup
where the supremum is taken over vectors (V))ET such that ΣiET 11el 1. For E N and 5 E (0, 1), we define the set function Fu,s, for any subset S C T,, by
{ t T R(t, w. (t)) R. S 2 (no) Elsup (+) sES
F =
(7)
This map acts as a contraction as shown in the next lemma, whose proof is deferred to Appendix E. For function f, we use fk to denote f*(x) == f(sk (x)) with (xx) ==
Lemma 1. Let n E N, E (0, 1), and assume that T. + Ø. Then for all (N(
(T) F (T).
* 3f B such that ElsupreT (t)(t]] S B for all n 2 no, then Mm21 n.o (T) T.
With these definitions, we now state the second main result of the paper. A proof is in Appendix F. Theorem 4. Assume that T. * Ø, E| < oc, v(t,j) E T x [d]. [X)] < oc, and co. Ler 8 E (0. and l E N. If. for some t, E Ta, satisfies
El (x, (X,Y))l ca.
n 2 64E/sup (t)] + (128L + 11) (ogg6/666 + E[ sup An(t, EET..
EET
then, with probability at least 1 - 8.
in ( =: Sn,b.k
and
Elf,, wn) S 24 (n8) EEj sup (%
sE.n.s.k
where the processes An, An. and G, are in (3) and (4).
We make few remarks before interpreting the content of the theorem. First, we note that when the index set T is singleton, the last term the sample size restriction vanishes, while the first matches the sample size restriction from Theorem 2 after an application of Lemma below; further taking& k = 1 in Theorem 4 recovers the upper bound on the excess risk of Theorem 2 up to constant factor. Theorem 4 may therefore be viewed 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 bound of Theorem as can be seen from (5), in the same way that Theorem 2 achieves this when compared with Theorem 1. Finally, the statement of Theorem 4 very general, and in fact, too general for us to be able interpret precisely. As such, we will discuss it in the context of the following assumption.
broad generalization of Theorem 2. Second, under
Assumption There exists constants CA. Ca. and CG independent of the sample size, but possibly dependent on the remaining parameters of the problem, such that for all n E N,
E(sup Ar (t) S CA. TET
sup t,, LETVT.
CCs.
Elsup G (t)] S Ca. tET
where An, An. and G, are as in (3) and (4).

---

These assumptions can be equivalently viewed as a restriction on the appropriately measured size of the index set T [VW96; GN15], and are slightly stronger than the assumptions of Theorem 3. They always hold for finite index sets, and we will derive in Section 4 explicit estimates of the constants in Assumption in terms of moments of the feature maps and target as well as the cardinality of T.
Let us now interpret the content of Theorem 4, which comes with free parameter k, in the context of Assumption 1. We fix k here, and discuss its choice below. First, recalling the definition of Fn.5. 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 the beginning of the section. Second, this result provides an upper bound on the excess risk of ERM that depends on the index set only through the size of shrinking subsets S, which might be large for small n. but which by Lemma converge to the set of optimal feature maps T. as + co. 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 &,,,,k. this result identifies the size of the sublevel sets of the suboptimality function R(1, w. w. (t)) R. defined over feature maps as a relevant property of the collection of feature maps (dy, ) that influences the rate of convergence of the excess risk 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 & balances the following trade-off:: on the one hand, for small k. upplications of F,,, .,.6//k constrain the input set more severely, but only few iterations are performed: on the other hand, larger values of allow more iterations, but the cost of more weakly constraining the input set per application.
Stepping back, there two main takeaways from Theorem 4. Firstly, and conceptual level, it shows that feature learning is easy when the suboptimality function Rit,, w. (t)) - R., defined over the set of features maps, has small sublevel sets. Secondly, and on technical level, it provides 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- corviiivial task, and cannot be done at the level of generality we have been operating at. The case of finite T however tractable general setting as we discuss in the next section.
4 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 slight strengthening of Theorem 3, whose assumptions reduce simple moments conditions when T is finite. The straightforward proof can be found in Appendix H.
Corollary 1. Assume that 'T is finite, for all (f, E T x [d], E. F. (X)) oc, E < oo, and for all t E T, Elllg(t, (X, (X,Y) < co. Then
lim P(t, T.) O. n-
Furthermore, for any 6 E (0,
1 2 Q2 51 S lim inf n Qe (.,) (1 8) limsup (1( 8) 5 Qz+ (1 -8), +00
n
where Z- := min,ET. 11. Z+ = max,eT. Z and the random vectors (Z))ET are jointly
Gaussian with mean zero and covariance E[Z,Z!] = Σ (-)))())((tss))=-1333 particular, Tf [tx). then
all t, E T. In
n n E(f,,, w.
d 2
|
where Z~ ~ -/
The conclusions of Corollary differ from those of Theorem two aspects. First, the feature map picked by ERM is guaranteed to be optimal rather than near-optimal with probability converging to
7

---

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. a singleton.
Making Theorem 4 more explicit is a more laborious task. We recall here two known results that allow to accomplish this. We start with the following bounds on the expectation of the supremum of finitel-innexxed empirical process, which we will later use to bound the suprema of the processes (G,, (5)) SES and (An (t, LET,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 (Zi)i=1 be i.dd samples with the same distribution as Z. Let F be a finite collection of Rd -valued measurable functions. Define
1/2
o² (²( == max (())(()) ())()) (F) = E
max [1((%)) ([](
JEF
(6.f)elm)x
and let Fn]( = Vn. (n-1 E (()) - ([]( Then, we have
1
Tn (F)
1/2
(n( Vn
2 (FF +
S E
max
Fn
S <(()
o(F) + ((F))
4
JEF
where c(m) == 5v + 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 related discussion in [Tro16]. Finally, while the term r (F) might grow with n, by bounding the maximum with the sum, it grows most as y Vn. In many applications however, the random vectors fZZ are bounded almost surely, so that rn (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 (A, (U))ET appearing in Theorem 4. We do not known of a matching non-asympiotic lower bound, but asymptotic one is known [EME24, Proposition 17J. 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 E N and for each i E [n)]. let Ze E Radxd be i.i.d. posilive semi-defiitt matrices with the same distribution as Z. Define
V E ( 2
Wa = Vu- (E1Z)-
21
n
Then, we have
Amax (E(Z)) log(ed)
E Amax (Wn)) S V 2Amax (V) log(ed) +
//
Equipped with these estimates, may now control the expected suprema of the empirical processes appearing in Theorem 4. To apply Lemma 2, define the following classes, for S c T and t. E T.
9(8) (w, + Σ 1/2 (/)9/(()) v)) &ES].
D(t.): (z. v) ellw, (x)))) v) (((ww(t)). Se. (x)),,) t tE T TTT }
R(t, (t) - Rs
Applying Lemma 2 G(S) bounds the expected supremum of the process (Gn (s))sEs while applying it on (t=.) bounds that of (tn(t, t, DeTT.. To control the supremum of (An (1)ET.. the key idea is to notice that it can be expressed as the maximum eigenvalue of block diagonal matrix whose blocks are Vn(T - E-1/2(() (()E)((())/((()))) Looking at Lemma 3, the relevant parameter is therefore block diagonal matrix with the following blocks
v(I) = E (3=00000066000000000000000000000
As the bound in Lemma depends only on the maximum eigenvalue of V. the ordering of the blocks does not matter. Putting together these estimates, we arrive at fully explicit version of Theorem 4.
8

---

Corollary 2. Assume that T is finite and for all (t.j) E Tx Ei < co, E < <0..
Let ô E (0, 1), & E [1 + IT T. and
Tr) in Lemma 2. If. for some t, E T.,
n 2 (512)mux (V) + 6) log ed (T) + (1281. + 11) (6/6)
24..0
1 1/2 10..)11..2((7))) (8)
then, with probability at least 1 -
in Fik n,6/22( =: Sn..k
and
E(tn, wn) s 24. (1d) A((Sn.s.),
where, for C. T.
A(S) :- (S)) (o(g(S)) + c(S) r.(9(S)) 2 vi
and (S) the same as (S) defined in (7) but with A(S) replacing Elsup C,((s).
We make 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 a as well as the excess risk, has pleasantly simple form. To first order, and ignoring constants, is given by
(1 + log(Sl) max E [Ia(s, (X, [())-
SES
As such, as + do 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 (6). As the sets Sn.8. 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 most that many iterations, a fixed point is reached, and further iterations worsen the bound. We conclude this section with an example of an application of our results.
Example 1 (Sparse linear regression). Consider the sparse linear regression problem, and in particular the best subset selection (BSS) procedure [Mi102; HTF09]. This procedure corresponds ERM over the restricted linear class {z + (w, ((x)) || lo _ $} in the linear regression setup of Section 2, where [/l/ is the number of non non-zero entries of w and s E [d] is a user-chosen sparsity level.
The problem of computing the BSS procedure has attracted a lot of attention recently. While hhrd [Nat95], Bertsimas al. [BKM16] showed that it can be
and therefore difficult in the worst tractable on practical instances of moderate size. Since then, a rich literature has emerged that devises increasingly efficient methods (e.g. Hua+18 18; BP20; HMS22; Guy+24). By comparison, the statistical performance of the BSS procedure is not yet completely understood as we discuss below.
To see how the sparse linear regression problem fits in our feature learning setting, notice that {a + (w, <xx)) [|wlo 5) = (a - (c, (x()) (t, v) E T x [R*} where T is the set of all sub- sets of [d] of size and (x(x) ;= (6), (z), 1z (z). ...., Oj (r)) E where (j1, I.) are the elements of t in increasing order. As such, Corollaries and are immediately applicable and provide general statements the performance of an arbitrary BSS procedure. To simplify the discussion, assume for the rest of the example that there is a unique risk minimizer w, satisfying |lw.llo = s.
On the recovery side, the first item of Corollary I guarantees that we asymptotically exactly recover the support of w., Non-asymptotically, the first item of Corollary 2 shows that if n further satisfies
n > min { 4k (18) 11 kE[()]
A(E
5,5/2 (T))
where
y= min {R(t, w. (t))) R.). LET
then with probability at least 1 - 8, the BSS procedure recovers the support of w., Equivalently, these two statements say that for large enough n, the BSS procedure coincides with the oracle procedure which knows the support of w, priori and outputs an ERM from the optimal linear class.
In practice however, the interesting regime is when n is only moderately large. Corollary 2 provides our guarantee in this case, and as such, we turn our attention to the sample size restriction (8). Typically, we expect the main restriction to come from the first term, which this case is given by Amax (V) log(d/ss), s),, up to constants and lower order terms. This is because if an intercept is

---

included. i.e. (x( = 1, then (V) 2 s, so the first term scales as s² log(d/s) at least, while the remaining terms typically grow more slowly with s. As concrete example, when (XX) + 1, so in this case the estimate s² log(d/s) is tight. Under this sample size restriction, and if E == Y - (w,, ((X)) satisfies E م x S o², Corollary 2 upper bounds the excess risk by sa2s/n /n) an for a sequence of decreasing distribution distribution-deeendeett constants an converging to one as n + oo, ignoring the dependence on á and absolute constants.
is a Gaussian vector, Amax (V)
The closest existing result in the literature we are aware of is due to Shen et al. [She+13] 13), who arrived at comparable conclusions but in substantially different setting. In particular, their result was obtained in the setting n. d - oc, 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 Raskutti et al. [RWY11] II] who showed that the minimax expected excess risk in a well-specified fixed-design setting is, up to constants, o² log(d/s)/re see also [Bac24, Chapter 8). Our results show that for moderate n, in the random mesonn setting, and when focusing on a single instance, the log(d/s) s) factor can be replaced with another factor that decays to one as n + DC.
Coming back to the sample size restriction discussion, we strongly suspect that the factor s log(d) is suboptimal, but we unsure what the correct dependence is, even under Gaussian (X). Indeed, this factor comes from the logarithmic factor in Lemma 3, when applied to the block diagonal matrix (t)), (() (t)) One can improve this factor by instead using versions
with blocks of this inequality based the intrinsic dimension [Tro15, Chapter 7]. However, this is also unlikely to be tight. Roughly speaking, this is because such logarithmic factors are tight only when the eigenvalues of the random matrix are near-independent. This is certainly not the case for the block diagonal matrix we are considering, since its blocks are sample covariance matrices of sub-vectors of the same random vector o(X). Capturing this dependence is beyond our reach and likely requires new tools; we refer the interested reader to the recent articles [vHan17; LvHY 18; BBvH23J.
5 Conclusion
Broadly speaking, there are two main conclusions one can draw from this work. Firstly, in the large sample regime, and if the set of candidate feature maps is not too large under an appropriate measure of size, asking model to additionally pick 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 appropriately measured size of the sublevel sets of the suboptimality function 1 + R((, 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]. 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 generic collection of leaeeeeeeannnnbbaaea offering explanations for this apparent paradox (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.
models. While there are many works
We conclude by outlining a few limitations of our work. Firstly, we do not deal with the question of how to solve the ERM problem. Our focus is on understanding its statistical performance, and our setting is so general that such question cannot be meaningfully tackled. Continuing on this last point, while the generality of our results is desirable in some aspects, it is detrimental in others. As an example, it would be desirable to specialize our results from Section 3 to specific infinite collections of feature maps used in practice. Let us also 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 required if one can control the error term from above and below. It is known how to do this for many loss functions [c.g. OB21; EE23]. and most importantly for logistic regression [Bac 10; Bac14p 14]. We have purposefully selected generic notation to make translating such arguments casier.
10

---

Acknowledgments and Disclosure of Funding
Resources used in preparing this research were provided in part by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. CM acknowl- edges the support the Natural Sciences and Engineering Research Council of Canada (NSERC), 1GPIN-2021-03444 MAE was partially supported by NSERC Grant [2019-06167], CIFAR AI Chairs program, and CIFAR AI Catalyst grant.
References
[ACI1]
J.-Y. Audibert and O. Catoni. "Robust Linear Least Squares Regression" In: The Annals
of Statistics (2011). URL.
[Aud07]
J.-y. Audibert. "Progressive Mixture Rules Are Deviation Suboptimal". In: Advances in Neural Information Processing Systems. 2007. URT..
[Ba+22]
J. Ba, M. Erdogdu, T. Suzuki, Wang. Wu, and Yang. "High-Dimension Dimensiinnl Asymptotics of Feature Learning: How One Gradient Step Improves the Representation".
In: Advances in Neural Information Processing Systems (Dec. 6, 2022). URL.
[Bac10]
F. Bach. "Self-Concordant Analysis for Logistic Regression". In: Electronic Journal of
Statistics (Jan. 2010). DOI: 10. 1214/09-EJS522
[Bac14]
F. Bach. " "Adaptivity of Averaged Stochastic Gradient Descent Local Strong Convexity for Logistic Regression". In: Journal of Machine Learning Research (2014). URL..
[Bac17]
F. Bach. "Breaking the Curse of Dimensionality with Convex Neural Networks". In: Journal of Machine Learning Research (2017). URL.
[Bac24]
Bach. Learning Theory from First Principles. Dec. 24, 2024.
[BBM05]
L. Bartlett, O. Bousquet, and S. Mendelson. "Local Rademacher Complexities". In:
The Annals of Statisties (Aug. 2005). DOI: 10.
[BBvH23]
A. S. Bandeira, M. T. Boedihardjo, and R. van Handel. "Matrix Concentration In- equalities and Free Probability". In: Inventiones mathematicae (Oet. 1, 2023). DOI: 10. 1001000// 000000000002222222 020-0033---0 022-01204-6.
[ВКМ16]
D. Bertsimas, King. and R. Mazumder. "Best Subset Selection via Modern Opti- mization Lens". In: The Annals of Statistics (Apr. 2016). DOT: 10. 10111111111111 2144/55-AS1388 S. Boucheron, G. Lugosi, and P. Massart. "A Sharp Concentration Inequality with Applications". In: Random Structures & Algorithms (2000). DO1: 10. 1002/ (SICI) 1098-2418 2012221122000 (200005) 36:3<277: AID AID-RSA4>3 0. 00;
[BLM00]
[BLM13]
S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: Nonasymptotic Theory of Independence. Feb. 7, 2013.
[BM06]
P. L. Bartlett and S. Mendelson. "Empirical Minimization". In: Probability Theory and
Related Fields (July 1, 2006). DO1: 10. 0000:/0000400000-445500
[BMR21]
P. L. Bartlett, A. Montanari, and A. Rakhlin. "Deep Learning A Statistical Viewpoint".
In: Acta Numerica (May 2021). DO1: 10. 10117/50096449222000007
[Bou02]
O. Bousquet. "A Bennett Concentration Inequality and Its Application to Suprema of Empirical Processes". In: Comples Rendus Mathematique (Jan. 1, 2002). DOI: 10.
(02) 02292-6.
[BP20]
D. Bertsimas and B. V. Parys. "Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions". In: The Annals of Statistics (Feb. 2020). DOI:
10. 2214/18-A0S1800
[BPV20]
D. Bertsimas, Pauphilet, and B. Van Parys. "Sparse Regression: Scalable Algorithms and Empirical Performance". In: Statistical Science (2020). URL.
[COB19]
L. Chizat, E. Oyallon, and F. Bach. "On Lazy Training in Differentiable Programming". In: Advances in Neural Information Processing Systems. 2019, URL.
[DI7]]
G. David and Z. Ilias. "High Dimensional Regression with Binary Coefficients. Estimat- ing Squared Error and a Phase Transtition". In: Proceedings of the 2017 Conference on Learming Theory. June 18, 2017. URL.
[EE23]
A. El Hanchi and M. A. Erdogdu. "Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression". In: Advances in Neural Information Processing Systems (Dec. 15, 2023). URL.

---

[EME24] A. EI Hanchi, C. Maddison, and M. Erdogdu. "Minimax Linear Regression under the Quantile Risk". In: Proceedings of Thirty Seventh Conference on Learning Theory. June 30, 2024. URT..
[GA11]
M. Gönen and E. Alpaydin. "Multiple Kernel Learning Algorithms". In: Journal of Machine Learning Research (2011). URL.
[Gho+19]
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. "Limitations of Lazy Training of Two-layers Neural Network". In: Advances in Neural Information Processing Systems. 2019, URL.
[Gho+20]
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. "When Do Neural Networks Outperform Kernel Methods?" In: Advances in Neural Information Processing Systems. 2020. URL.
[GN15]
E. Giné and R. Nickl. Mathematical Foundations of Infinite- Ciminit-Dimmesiionall Statistical Models. 2015. DOE: 10.
[GR04]
E. Greenshtein and Y. Ritov. "Persistence in Nigh-Diimesional Linear Predictor Selec- tion and the Virtue of Overparametrizationn In: Bernoulli (Dec. 2004). DOI: 30.3150/
bj bj/11063148B
[Gre06]
E. Greenshtein. "Best Subset Selection, Persistence in High-Dimensional Statistical Learning and Optimization under I.1 Constraint". In: The Annals of Statistics (Oct. 2006). DOT: 10. 1214000095300000007755
[Guy+24]
T. Guyard, C. Herzet, C. Elvira, and A.-N. Arslan. "A New Branch-and and-Bound Pruning Framework for &u fy-Regularized Problems". In: Proceedings of the 41 International Conference on Machine Learning. July 2024. URL.
[Hc+16]
K. He, X. Zhang, S. Ren, and Sun. "Deep Residual Learning for Image Recognition". In: 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR). June
2016. DOI: 10. 1ww11110//VV// 2016.90.
[HKZ12]
D. Hsu, S. M. Kakade, and T. Zhang. "Random Design Analysis 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 Regression at Scale: Branch-and- Bound Rooted in First-Order Optimization". In: Mathematical Programming (Nov. 1, 2022). DOL: 10.
(HTF09)
T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition. Aug. 26, 2009.
[Hua+18)
J. Huang, Y. Jiao, Y. Liu, and X. Lu. "A Constructive Approach to Lo Penalized Regression". In: Journal of Machine Learning Research (2018). URI..
[JRTO8]
A. Juditsky, P. Rigollet, and A. B. Tsybakov. "Learning by Mirror Averaging". In: The Annals of Statistics (Oct. 2008). DOI: 10. 1214/07-A0S546
[Kel+23]
J. Kelner, Kochler, R. Meka, and D. Rohatgi. "Feature Adaptation for Sparse Linear Regression". In: Advances in Neural Information Processing Systems (Dec. 15, 2023). URL.
[KM15)
Koltchinskii and Mendelson. "Bounding the Smallest Singular Value of a Random Matrix Without Concentration". In: International Mathematics Research Notices (Jan. 1, 2015). DOI: 10. 1093/ htt///imm/rnvvvs
[Ko106]
V. Koltchinskii. "Local Rademacher Complexities and Oracle Inequalities in Risk Minimization". In: The Annals of Statistics (Dec. 2006). DOI: 10 009053606000001019.
1214 /
[Ko111]
V. Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D' É'éé de Probabilités de Saint-Flour XXXVIII-0008. July 29, 2011. V. Kanade, P. Rebeschini, and T. Vaskevicius. Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition. Feb. 23, 2022. DOI: 10. 48550/ arxiv fer.ii.2022...... 2202.11461.
[RV22]]
[KSH12]
A. Krizhevsky. I. Sutskever, and G. E. Hinton. "ImageNet Classification with Deep Con- volutional Neural Networks". In: Advances in Neural Information Processing Systems. 2012. URL.
12

---

[Lan+04]
G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan. "Learning
the Kemel Matrix with Semidefinite Programming" In: Journal of Machine Learning Research (2004). URT.
[LBH15]
Y. LeCun, Y. Bengio, and G. Hinton. "Deep Learning.. In: Nature (May 28, 2015). DOI:
10. eaturen 14539.
[LC06]
E. L. Lehmann and G. Casella. Theory of Point Estimation. May 2. 2006.
[LL20]
G. Lecué and M. Lerasle. "Robust Machine Learning by Median-of-Meamm Theory and Practice". The Annals of Statisticy (Apr. 2020). DOI: 10.
[LM09]
G. Lecué and S. Mendelson. "Aggregation via Empirical Risk Minimization". In: Proba-
bility Theory and Related Fields (Nov. 1, 2009). DOI: 10.
[LM16a]
G. Lecué and S. Mendelson. Learning Subgaussian Classes Upper and Minimax Bounds. Sept. 17. 2016. DOI: 10. 40550/550//a arivv 1305 4825.
[LM16b]
G. Lecué and S. Mendelson. "Performance of Empirical Risk Minimization in Linear Aggregation".. In: Bernoulli (Aug. 2016). DOI: 10. 15-50/15-BBJ7011
[LM19]
G. Lugosi and S. Mendelson. "Risk Minimization by Median-of-Mean Tournaments". In: Journal of the European Mathematical Society (Dec. 16, 2019). DOr: /4.111 tems/937.
[LRS15]
T. Liang, A. Rakhlin, and K. Sridharan. "Learning with Square Loss: Localization through Offset Rademacher Complexity". In: Proceedings of The 28th Conference on Learning Theory. June 26, 2015. URL.
[LvHY18]
R. Latala, R. Handel, and P. Youssef. "The Dimension-Free Structure of Nonho- mogeneous Random Matrices". In: Inventiones mathematicae (Dec. 1, 2018). DOE:
10. 1007 00000/000222--008 0817-x.
[Men14]
Mendelson. "Learning without Concentration". In: Proceedings of The 27th Confer- ence on Learning Theory. May 29, 2014. URL.
[Mil02]
A. Miller. Subset Selection in Regression. Apr. 14, 2002. DOE: 10.
1201 /
9781420035933.
[Mou22]
J. Mourtada. "Exact Minimax Risk for Linear Least Squares, and the Lower Tail of Sample Covariance Matrices". In: The Annals of Statistics (Aug. 2022). DOE: 10.
22 22-A00218..
[Na195]
B. K. Natarajan. "Sparse Approximate Solutions to I Linear Systems". In: SIAM Journal on Computing (Apr. 1995). DOI: 10. 10.1117//80975533922200000
[OB21]
D. M. Ostrovskii and F. Bach. "Finite "Finite-Sample Analysis of M-Estimators Using Self- Concordance". In: Electronic Journal of Statistics (Jan. 2021). DOI: 10. 1214/20- EJS17800
[Oli16]
R. I. Oliveira. "The Lower Tail of Random Quadratic Forms with Applications to Ordinary Least Squares". In: Probability Theory and Related Fields (Dec. 1, 2016). DOI: 10. 1007000////0 1000/0000400-0--0 011-400-----0-8-9-.
[PG99]
V. de la Peña and E. Giné. Decoupling: From Dependence to Independence. 1999.
[PWE15]
M. Pilanci, M. J. Wainwright, and El Ghaoui "Sparse Learning via Boolean Relax- ations". In: Mathematical Programming (June 1, 2015). DOI: 10. 00.1007/s10107-10000 0894-1.
[RWY1I]
G. Raskutti, M. J. Wainwright, and B. Yu. "Minimax Rates of Estimation for High- Dimensional Linear Regression Over e, -aals"" In: IEEE Transactions Information Theory (Oct. 2011). DOI: 10. 1109/TIT, 2011. 21657999
[Sau18]
A. Saumard. "On Optimality of Empirical Risk Minimization in Linear Aggregation".
In: Bernoulli (2018). URT..
[SD16]
A. Sinha and J. C. Duchi. "Learning Kernels with Random Features". In: Advances in Neural Information Processing Systems. 2016. URL.
[Shc+13]
X. Shen, W. Pan, Y. Zhu, and H. Zhou. "On Constrained and Regularized High- Dimensional Regression". In: Annals of the Institute of Statistical Mathematics (Oct. 1, 2013). DOL: 10. 1007/ s 11413-012---11 012-0396-3.
[SPZ12]
X. Shen, W. Pan, and Y. Zhu. "Likelihood-Baan -ased Selection and Sharp Parameter Es- timation". In: Journal of the American Staristical Association (June 11, 2012). DOI: 10. 1100//0000011111 2011 645783.
13

---

[Ta196]
M. Talagrand. "New Concentration Inequalities in Product Spaces". In: Inventiones mathematicae (Nov. 1996). DOI: 1007/18002220000000.
[Tro15]
J. A. Tropp. "An Introduction to Matrix Concentration Inequalities", In: Found. Trends Mach. Learn. (May 1, 2015). DOI: 10. 1561 1561/2200000488.
[Tro16]
J. A. TropP "The Expected Norm of Sum of Independent Random Matrices: An Elementary Approach". In: High Dimensional Probability VII. Ed. by C. Houdré, D. M. Mason, Reynaud-Bouree Bouuret, and J. Rosiñisi. 2016. DOE: 10. 110.000077778---9--10
3_8.
[Vaa98]
A. W. van der Vaart. Asymptotic Statistics, 1998. DOT: 10. 1011001///0 00.1007//B00990011822555
[Vas+17]
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. ukasz Kaiser, and I. Polosukhin. " "Attention Is All You Need". In: Advances in Neural Information Processing Systems. 2017. URL.
[VC74]
Vapnik and A. Chervonenkis. Theory of Pattern Recognition. 1974.
[vHan17]
van Handel. "Structured Random Matrices", In: Convexity and Concentration. 2017.
DOE: 10. 1007 90007/978-11 1
[VW96]
A. der Vaart and A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Mar. 14, 1996.
[Wai19]
M. J. Wainwright, Iligh-Dimensional Statistics: Non-Asymplotic Viewpoint. 2019.
DOE: 10. 1017/9781 1017/97781006277711
[Whi82]
H. White. "Maximum Likelihood Estimation Misspecified Models". In: Econometrica
(1982). DOI: 10. 2307 1912526.
[Zha+21]
Zhang, Bengio, M. Hardt, B. Recht, and O. Vinyals. "Understanding Deep Learning (Still) Requires Rethinking Generalization" In: Commun. ACM (Feb. 22, 2021). DO1:
10. 1144//4446676.
[Zhu+20]
J. Zhu, C. Wen, Zhu, H. Zhang, and X. Wang. "A Polynomial Algorithm for Best- Subset Selection Problem". In: Proceedings of the National Academy of Sciences (Dec. 29, 2020). DOI: 10. 1073/pnas..... 2014241117.
[ZWJ14]
Y. Zhang, M. J. Wainwright, and M. I. Jordan. "Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression", In: Proceedings of The 27th Conference on Learning Theory. May 29, 2014. URL.
[ZWJ17]
Y. Zhang, J. Wainwright, and M. I. Jordan. "Optimal Prediction for Sparse Linear Models? Lower Bounds for Soordinate-Separabbe M-cstimatorss. In: Electronic Journal of Statistics (Jan. 2017). DOI: 10. -
[ZZ12]
C.-H. Zhang and T. Zhang. "A General Theory of Concave Regularization for High- Dimensional Sparse Estimation Problems". In: Statistical Science (Nov. 2012). DOI: 10. 121121122-1399999
14

---

A Proof of Theorem 1
Let An denote the event that Σn is invertible. By the weak law of large numbers, 2, converges to Σ in probability so that 1o0 P(A 0. Now on the event An, have by (1)
vn. (w, w.) - (vn (w=)).
By the continuous mapping theorem, nn converges to E-1 in probability and by the central limit theorem
Vn. (w.) S0(00)).
Therefore, by Slutsky's theorem
Vn- (w,, ww.) N
Now since the risk is quadratic and the gradient vanishes at W..
( R(w.)) )] = Ilv (6 w. 4 1 17
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 consequence of concentration bounds for the norm of Gaussian vectors [c.g. EME24, Corollary 33].
B
Proof of Theorem 2
Denote by An the event that
Amin
Σ 1/2 Σn
11/
2 2
We show that under the sample size restriction, P(An) 2 1 - 8/2. Indeed we have the variational representation
n 1 1- (v,
Amax - 1/2)) = sup
i=1
Each clement in the sum is upper bounded by 1, and the variance parameter in Bousquet's concentra- tion incquality [Bou02] is given by the parameter the statement of the theorem. Applying this inequality yields that with probability at least - 6/2
2L 12g(2/8)
log 4lo((2/5)
Amax (I - 1/",,,,,, 1/2) s 2E Amax M- 1/2 1/2,,,,,,,,,1111 +
n
3n
Using Lemma 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,,) 2 5/2 for all sample sizes allowable by the theorem. Now on this event we have, using (2),
1 R(w,) R(w.) = 5 || VR, (w. ) 2. (R.
An elementary calculation shows
V Rm, (w,)
12 = = " .].
so that an application of Markov's 's inequality yields that there is an event B,, that holds with probability least - 8/2 and on which
[v,n(w.))) S 2- (no) E[llg(X, Y .].
The union bound P(A, Br) 1- P(A, U Br) - finishes the proof.
15

---

C
Main Lemma
We state here core lemma, which we use in many of our proofs. To state we define, for function : - R on subset S T,
| = sup sup]F(()), || == sup{-F(s)) [un)----=) .ES
| == sup F(s),
.ES
sEB
where the first quantity is the 8 norm the function F. and the remaining are one-sided variants of it. The processes appearing in the next statement are defined in (3) and (4).
Lemma 4. Assume that T. f and let L. E T. On the event that ||| 1/2 (12An(: lo loooutt < 1 land
1oo, ||11//AAnloo.t
[| 1/2 ||111/2, 1//////lllla
we have
1
1
R(G,, w- (In)) R. S
1- 1111111/A,, 110, (n G
2
1 -
n 10-1/2A, (1,44))) (1
and
(L Ann-1/2A, Alc,, )
G
S R(in, w.) R(lns w. (fx) S (1 | Am bo,,)
2 (1 +
Proof. To lighten the notation, we drop the dependence on n. and write instead of tn. We start with the first statement. First, we note that if E Ta, then the statement holds trivially as the left-hand side zero, so we only consider the other case in what follows. For any E T, define
w(t) E argmin R, (t, w),
wEB*
where the choice of minimizer arbitrary. With this definition, we have wn = wf). Now, by definition of ERM,
R2 (f. w(f) - (t.: w. (t.)) S O.
(9)
On the other hand, for any E T T., we have the decomposition
Rn, (4, (() (n( w.) = [R.. i()) [L,(, w- (()) + [R., (1, w.(() Rullo, w. (1-)))
(10)
We study each of the terms of (10) separately, and we start with the first. Note that since we in the event
1oo,+ > 0, inf Amin (2' 1/2 2t) (/9 1--1lp 1--ln2 1-11//11//// 1/2
the sample covariance matrices nn (t) are invertible for all t E T, so that (t) is uniquely defined and satisfies
(tt)) = (t) (t) (t)).
(11)
Furthermore, since the function w - (t, w) quadratic in w and its gradient vanishes at its minimizer (t) we have
(1, w()) (t. w. (1)) = [l(((1) - w. (1) = 1 - Rw (1, w- (()) (12)
where the last equality follows from (11). To bound this last term, define
En(()= = Σー 1/2 (1)0,
Then we have,
E (/)1 R (n,t, (t,w, T (110
|V Ry (t, w. (t))l )0)
< Amax =-1(()) V RS (t, w. (t))
(n GG)(())
Amax (1 (t)
< 1 In 1/2 1/2AA (n-)))((t)
(13)
16

---

Finally, the second term of (10) is lower bounded by
(t, wx (t)) Rr, (tx, w (t.)))
(1 n 1/2 1/2 (t, w.(()) R.
2 (1 |1 || 1,.1//A,(: (+, (1,4.))) +o),) [R((, w. (1) - R.]
(14)
Combining (13) and (12) lower bounds the first term of (10), while (14) lower bounds the second. Combining the resulting lower bound on (10) with (9) and rearranging yields the first statement. For the upper bound the second statement, note that for all TT.
R(t, (t)) R(t, w.((())
||á(()) w. (t)ll(e)
2 | (t) Rm (t))
5
2 Amax (Σ,² | Rm (1. w. (t))
(1- |||n-/11// 1/2 )2 (n (t).
where the second line follows from (11). In particular the inequality holds for i. The lower bound holds by a similar argument.
D Proof of Theorem 3
Consistency of in. We want to show that, + 00.
R(fn. we wx((()))) (fn)) - Rs 0.
(15)
Using the notation introduced in Appendix C, the Sivvenko-Cantelly assumptions in Theorem amount to the statements that, for some to T., and as n + 20.
An-1//An 3 0,
| A, ll 40 -n-11/2Gnll- 0. 0.
(16)
Let A, denote the event that both ||n ||2-1//A, A, bl and 1n and (16) show that
The union bound
lim P(4A) =
120000
Furthermore, on the event A,, the first bound of Lemma 4 holds, and bounding n (-.G)(( by || ||2n ,n 1l yields that on An
1
R(fn, w. (fm)) - R. S
|11 1/22Gnll (17)
1I -1/AA,1 1/22, 1 1/2A,
Now let E >> O, and denote by (n( the event that the right hand side of (17) is strictly larger than Then the statements (16) together with the continuous mapping theorem show that lim (().(E)) 0. Therefore, again by (17), we have
P( we w-(()) R. E) s PP), +P(A))
and taking + oo proves (15).
Asymptotic quantiles. We start with the upper bound. We have the simple decomposition
n [[ff,, wi.) R.] = n [R(E,, u..) R(f., w. (f.))) + n. [R(f.,, w. (f.)) - R.].
(18)
Now on the event A, defined above, we have, by an application of Lemma 4, combining the two bounds in the lemma along with (18), that the rescaled excess risk is upper bounded by
1
1|12 11 ) C2((E))
1
-1/2 An (3 (sb))llo + 1- I| 1/2
(19)
1 1n- 1,
17

---

From the Glivenko-Cand Cantelli assumptions (16), the first three factors converge in probability to 1. Our aim will be bound the upper tail of the last factor, which will imply bound on the upper tail of the rescaled excess risk.
We briefty make explicit the Donsker assumption before deriving this bound. Both define and note Gt,(t, v) == vn (v, Σ (zVV (t,,, w. (t)),,
G.((t)
sup G,,(t, vES4-1
where St-1 is the Euclidean unit sphere in IR As pointed out in Section 3, the processes (t) are partial suprema of the empirical processes (t, u). The Donsker assumption of the theorem states that the empirical processes G,, v) take value in the space of bounded functions on T x S6-1, equipped with the (T 5u-1) norm and the metric it induces, and converge weakly to their unique Gaussian limit (G(t,
Sd-11 as n + 20. By inspecting their finite dimensional
distributions, it is straightforward to verify that (G(t, (.) x55-1 d ((0, (t))))(..)))xxx) (x8-- where (Z()))eTT is the I8 -aluee Gaussian process defined in the statement of Theorem 3. Finally, we define G(t) == sup G(t, v) in analogy with the definition of (t).
We now upper bound the upper tail of (f,) in (19). Let (ex) be a decreasing sequence of positive numbers such that E +
+ DC, and define the sets
Te(e)= = {1 E R((, (I) R. S {e}
(20)
as well as the function FE (T x Sd-1) R
Fx(2) = sup
sup 2() s (E))
Note on the one hand that 0421 (.(E)) T., and on the other that F& is continuous for all k N. and in fact Lipschitz. Indeed, let z E (T 2u-1). Then
[F((2) Fx((')]=
sup 2(5, r) .ET.(en) vEg--1
sup
sup sup 2'(8, s 1| 1---21 511=-2'00 SET.(E))
2'
Now let k E N and 00). Then
((G > m) P( (fm) x) n (hn E ((([))))
o) (tn & T((x)))
S PP(( > x² ffn T((x))) + +P((nn & Te(s))))
SP
sup
()) > + +P(R(la w. (fz)) - R. > Ex)
(ET)
= (G > x) + PP((tt wa(()) R. > Ek)
taking the limit as - oo, the first term converges, by the continuous mapping theorem, to the probability of the event [F2 > x} where G is the limiting Gaussian process discussed above, while the second term vanishes by the first part of Theorem 3. Therefore, for all & N,
lim sup P (G r) < n-
G (ET.(Ek)
sup
Taking the limit as k + co, noticing that the events
(2(x) > x
sup
(ET)
are nested, using the continuity of probability from above, and recalling that (x2ITA(EL) = To gives
lim sup P(G (f.) > x) < sup G²(s)> > n
SET.
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,
[R(6, wn)) R.) 2 n [R(f,, w..) R((n, w. (f,))
1
1
(1 + Il 1/2A,, b0. (Z,)
2
18

---

By the Glivenko-Cantee assumption on An, 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 (e+) be decreasing sequence of positive numbers such that & -> 0 as k > oo, and define H2 f (T x 1 + R by
(2) == inf sup v(1,v),
rET-(eN) vES--1
where the subsets (Ex) are defined in (20). Clearly, for 2, E (T x 1d-1),
[Hx(z) - Hz((')) = || - 21100
so H3 is Lipschitz and therefore continuous. Now
(f 2) 2 P((G x} { E T((Ex)))
2 P inf ( > x) -((( & (e(a))))
(ET.(sx)
= > x) P(((E, w. (fn)) R. > ER)
By the same argument above, we obtain, + and for all k E N.
lim (f., > x) 2 P n-+00
inf (ET.
G > x
Taking the limit as k + 0o, and noticing that
inf (())>0)
inf (s))>
(TT)(s))
BET.
proves that
imminf Pn P inf (3(s) > SET.
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 are a consequence of standard Gaussian concentration, see le.g. EME24, Appendix A.3]. Finally, for the second statement in Remark 1,
1/p
E max EET.
[s)]
E
Σ TET.
[2(3)
<
E [2))
TT
1/P
< 32 p
Σ
B[|[Z(s]]
where the last estimate follows from Gaussian concentration. Taking p = + log To), and recalling that for E Rd. ||~||p S | yields the result.
E Proof of Lemma 1
We prove the first statement by induction. For k 0, this follows directly from the fact that by definition Fo (7) T and (T) CT Now let l E N and assume that the statement holds for
k 1. Let E pk+1 (1)+1(7). Then by definition
9.5
R(s, w. (s)) R. (no) E sup (T)
(R((s)] S (no) El sup
GZ
sEF
where the second inequality follows from the fact that by the induction hypothesis, Fk (T) C n.8 (T), and that the supremum is increasing. Therefore s E F since the last incquality the defining inequality for Fk (T). We now turn the second statement. Fix and 8. On the one hand, T. S 5 F (T). On the other, for any t E 0m21 (T), we have for all n 2 no. R(t, w. wt) R. 2B (n6)-1. Therefore R(t, (t)) R. O, and hence e T..
19

---

Proof of Theorem 4
Recall the notation introduced in Appendix C. Let (t.).. be the event that:
|| | Anlloo,+ S 1/2, and
||n ||m An f.)ll - 1/2.
We start by showing that under the sample size inequality stated in the theorem, there exists a t, E such that P(A (t.)) 2 1 - 8/33. Indeed, we have
1(1 (0, || - 1/2 Am Aoll (t,))e(7x5**
sup
The 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 - 8/6
|| 1/2 1/2 An. 1oo,,o S
E sup An (0) + LETT
2L log(6/0)
4log(6/0)
1/2
n
3n
Furthermore, by Markov's inequality, with probability at least 666
6- E.ESuppETT.. (tt, t+)
|/2 1//2A(ttt)lla
1/2
Hence, when the inequality the sample size stated in the theorem holds for some 4,, the event (t.) holds with probability at least - 5/3. Now on this event, the first bound of Lemma applies, and we have
A(tn, we (t.)) R. 2 (Em).
(21)
Now we use the iterative localization method of Koltchinskii [Ko106]. Initially, we have no informa- tion about where f is located aside from belonging to T, so we start with the bound
R(fn, (f.)) R. n sup G (t).
(22)
ET
Using Markov's inequality, have an event B which holds with probability least 1 6/2kk sup G (1) 2k 8-1 1-1 Elsup G (1)
1ET
TET
Replacing in (22) yields that on the event A, A,, (t..) n Br,1.
RlEn, wa((x)) R4 < 4k (nd) Elsup G TET
which shows that on this event, in E (n,5/22(T), by definition of the map F2,5/2k- With this knowledge, we now reuse the bound (21) to obtain that on An(t.) n Br,1
sup R(fn, w. (f,.) R. 2 (/F),
G
Iterating the procedure we just described & times, we obtain that on event (1 where P(Bn.)) 2 1 5/2k for all j E [k]
in E Fhh (.8 (T) = Sn,..-
(23)
Another application of Markov's inequality yields that event O which holds with probability at least 1 5/6
sup 56 El sup (t)(t) tESm,5,k
(24)
LES..A.
Since
8/3 3
Σ j=1
8/2k-8/6 8/6
equation (23) proves the first statement of the theorem. For the second statement, have on the
same event A, (t.) ) n (n Br, n', and combining the two upper bounds from Lemma 4,
E(in, w.) < 4 n ((, < 4- -1, sup (g (no)-1 El sup G2 tES.,6.
BES.,,,k
where we used (23) 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.
and T be a finite set. For each (i, 1) E [n] T, let Zis E RRd be random vectors such that for each L E ET, (Za,)i=z are ii.d with the same distribution Zr For all i T, assume that Z = O, and define
Lemma 5. Let n,
1/2
o² (T)
sup F. Z 12 LET
(T) =
sup (i.))E|))x
1Z
Then
27 1/2
1
(TT)
In
(
n//2 + +C² (T)
+
sup (ET
Z
I C(T)
2
1/2
4
n
71
where C(T) = 5. + T!
To prove Lemma 5, need to recall few preliminary results. The first is classical symmetrization inequality, see c.g. [BLM13, Lemma 11.4] or [Wail9, Proposition 4. for a proof.
Lemma 6. For each (i, E [n]] x T, let W E Id be random vectors such that for each t E T, (W1,))== are i..dd. with the same distribution as W.. Let (ei) independent Rademacher random
variables, independent of the collection of random vectors Wi,. Define W., = Wi, E[ W) Then
27 1/2
1/2
1/2
sup TET
W
sup SE
Σ 1.
$ 2
sup TET
W
71
IET
11
71
The second result we recall is the Beinchin-Kahane inequality, the specific form we require is obtained from Peña and Giné [PG99, Theorem 1.3.1] by setting and p 2 in that theorem, see also Boucheron et al. [BLM13, page 141].
For i E [n]. let 2; E IRd be fixed vectors. Let (ei)²=1 be independent Rademacher random Lemma 7.
variables. Then for all p 2 2,
1/P
1/2
E
Σ
E
VP 1.
Σ 12111
straightforward consequence Lemma is the following result, which follows from the elementary observation that for a vector x E Rd, || I ||>||p S ////o//
Lemma For (i,t) t) E [n] XT, let zi, Rdd be fixed vectors. Let (E:) be independent Rademacher random variables. Then
1/2
E sup ET
Σ
E:74,
< V +
log|
sup EET
P 1
1=1
Proof. Let p 2 1. Then, by Jensen's inequality and Lemma 7
1/87
E
sup
E
S
Σ
Σ
Ei
E
1ET
i=1
2p
1/8
12
<
Σ
Σ
IET
1/P
< -2p 1) 1).
113
Recalling that ||>||p S d1/P|////ooo for all x d and taking = + log T yields the result.
21

---

Finally, we need the following consequence of Lemmas 6 and 8. The proof idea is taken from [Tro16].
Lemma 9. For each (i.t) in] T, ler a I be random variables such that for each t T, (Wi,)== are i.d. with the same distribution as Wt, with We 2 0 almost surely. Then
1/2
1/2
1/2
sup
Wa
S
sup TET
B[
5 log
E
sup [6.0EM]
W
IET
Proof.
We have by Jensen's 's inequality and Lemma 6,
sup 1ET
Wi
E
sup
Wi
E[W,,e]
+ sup IET
elW..h
1/2
S 2
sup
Σ s We.
sup
E[W.d]-
(25)
tET
TT
Conditioning on the random vectors Wi,s, we have by Lemma 8 and the assumption W., 2 0 a.s.
1/2
2
sup EE
& W
S 55 (1 log
sup 1ET
W
1,t
i=1
1=1
1/2
1/2
S 55 log/T]
sup ((.))
Wa
sup
W
LET
1=1
Taking expectation with respect to Wi,,, and using the Cauchy-Schwartz inequality yields
1/2
1/2
1/2
2E sup
W.W.
66 log E
sup (1A))())
Zz
E
sup
W
(ET
LET
i=1
Replacing in (25) 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 hand
sup tET
Zi
sup E >
Zi,
= (T())
(26)
EET
i=1
1=1
On the on other hand, by Lemma 6, we have
1/2
1/2
E sup
Z
E sup tET
Z 1.
tT
i=1
i=1
Define the random index
I argmax max
11,113 FET
iE[n]
Conditioning Zi,,, have by Jensen's inequality
12r,e113
12.
sup tET
E,
Zz,
2 sup E IET
E
E
7
sup EET
sup (6.0)(m)
71
71
n²
T
n²
i=1
2
:=1
22

---

where in the inequality, the outer expectation is with respect to Ej, and the inner one is with respect (Ei)igr. Taking expectation with respect to Z gives
1/2
n
1 (T)
sup LET
Σ 2 n
(27)
Averaging the lower bounds (26) and (27) yields the desired lower bound. We turn the upper bound. We have by Lemmas 6 and 8.
27
1/2
1/2
7
R2
sup tET
Zi
S
sup LET
Zi,t
71
n
27
1/2
1
5v
+ log]
7
EE
sup TET
Zi
78
2
Applying Lemma 9 on the last term yields the desired upper bound.
H Proof of Corollary
The Glivenko-Cantelll 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 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 {R(t, w. (t)))) R.)
LENVT.
Then > 0, and by the first item of Theorem 3,
lim Pf T.)
lim P(R(En. (fx))) - R. > =/2) 0.
(28)
It remains prove the improved upper bound on the asymptotic quantiles. For this, referring the proof Theorem 3, and in particular to (18), is enough to show that
lim P(n [R(ins w. ([x)) R. > 0) = 0, 2-000
but this follows directly from (28).
I Proof of Corollary 2
The statement follows from the same argument as Theorem with only few simple modifications. As explained in the main text, we use Lemma to bound the quantity E[maxYe7 (t) by constructing a block diagonal matrix. We use Lemma 2 to control, for any subset S, E [max.es G (s)]. The only minor deviation from Theorem 4 that we bound the second moment
E
sup (t, t.) LETXT.
instead of the first. This explains the slightly better dependence on ó in the sample size restriction of Corollary 2 compared to Theorem 4.
23

---

NeurIPS Paper Checklist
1. Claims
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 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 long is clear that these goals are not attained by the paper.
2. Limitations
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 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
24

---

Answer: [Yes]
The proofs of all the statements we claimed are new can be found in the appendix. For known statements, we provided direct references them.
Justification:
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wtips.cc/ppblccc//eccccccpcppppp getic//guuee...e CoodeSummii www.nnoolicciooeooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
26

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: ptttps://neuul http///eurrrpppeeee
Answer: [Yes]
Justification:
We have reviewed the guidelines and confirm that our work adheres to them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration 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 applica- tions, which is why do not foresee any direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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.
27

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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, scraped datasets)?
Question:
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 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 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "SfUmOFRCod", "reviewer": "Reviewer_qDCv", "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.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The motivation of this paper is. The key results and directly related results in prior works, along with their intuition behinds, are explained very clearly and concisely. There are a few potential typos (see Weaknesses) but it should not be a problem. The proofs look good to me, though I did not check very carefully. \n\nOverall, I enjoy reading the paper. The only reason why I do not give a higher score is that the setting is too niche (see Weaknesses), which makes the results not so ground-breaking. However, it is still a good paper, and I advocate to accept it.", "weaknesses": "The main concern about this paper.\n1. 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\"?\n\n2. 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.\n\nComments on the Conclusion.\n1. 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.\n\nMinor comments\n1. In the Appendix, it might be helpful if the authors first give a proof sketch for each result for readability. \n\nMinor typos:\n 1. Line 164, a comma missing after the inequality.\n 2. Line 501, should the RHS be $\\frac{1}{2}||\\nabla{R(w^*)}||_{\\Sigma^{-1}}$? \n 3. Multiple commas, dots after (in)equalities missing in the Proof of Theorem 1, 2. \n\nAfter 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and detailed feedback. We will make sure to fix the typos for the final version of the paper. We address the reviewer's main concern below.\n\n---\n\n***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\"?***\n\nPlease note that our usage of the term \"feature learning\" in our setting is aligned with recent theoretical work, e.g. [Ba+22, Dam+22, Fre+23].\n\nIn plain terms, every predictor in the model classes we consider is jointly determined by a choice of feature map and a linear predictor on top of it, and as such, every learning method that operates on such model classes learns a feature map, i.e. it is performing feature learning.\n\nWe agree that other methods exist to learn feature maps outside of the supervised setting we consider, and under different data access models such as transfer learning or self-supervised learning. Nevertheless, this does not exclude our setting, which captures arguably the simplest instantiation of the feature learning idea.\n\nFinally, we agree that it would be nice to obtain performance guarantees within our newly proposed framework in settings other than the supervised learning setup we consider, and we are excited to see what can be done with the new abstractions we introduce in our work. However, given that the framework we propose is new, and studying the performance of ERM on the function classes we introduce already requires the development of new ideas, we leave this to future work.\n\n---\n\n***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.***\n\nWe argue that in the scenario described by the reviewer, one does not know that the **learned** feature map is good. This feature map is itself learned from data through some procedure, which incurs an estimation error. In the simplest case (our case), through ERM on data from the given task, but more generally, through ERM on data from another task in transfer learning as an example, or through contrastive learning in self-supervised learning as another example. Quantifying the estimation error of this learned feature map is an important problem, and part of our work is dedicated to answering this question in our setting (e.g. first statements in Theorems 3 and 4).\n\n---\n\n***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.***\n\nWe agree with the reviewer that we did not establish a formal link between our results and DNNs; see e.g. lines 336-337\n\n*\"Formally connecting our statements to these experiments is beyond what we achieved\nhere, yet, we believe that the new perspective we took might generate useful insights in this area.\"*\n\nWe pointed out in a paragraph in the conclusion that our results show a disconnect between the complexity of the function classes we consider (which share the ability to select a feature map in a data-dependent way with DNNs), and the excess risk of ERM on them, which is one of the main surprising empirical findings in the experiments of [Zha+21]. To the best of our knowledge, there is currently no consensus or overwhelming evidence for any of the existing explanations of the results of these experiments, and the paragraph we included is meant as an invitation to the reader to look at the problem from the lense of the new framework we introduced. \n\nIf the reviewer believes our wording is misleading, we are open to suggestions on how to make our message clearer.\n\n---\n**References**\n\n[Ba+22]: Ba, Jimmy, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. \"High-dimensional asymptotics of feature learning: How one gradient step improves the representation.\"\n\n[Dam+22]: Damian, Alexandru, Jason Lee, and Mahdi Soltanolkotabi. \"Neural networks can learn representations with gradient descent.\"\n\n[Fre+23]: Frei, Spencer, Niladri S. Chatterji, and Peter L. Bartlett. \"Random feature amplification: Feature learning and generalization in neural networks.\"\n\n[Zha+21]: Zhang, Chiyuan, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. \"Understanding deep learning (still) requires rethinking generalization.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tmauqckcfP", "reviewer": "Reviewer_9KPn", "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.", "questions": "See weaknesses.", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The author propose a setting for feature learning that is novel and I find it interesting.\n\n- The result in this setting very satisfying. To the best of my knowledge, this is the first result that shows that the excess risk (or at least the upper bound on the excess risk) depends on the size of \"optimal\" features.\n\n- The proof outline and strategy seems correct. I have not fully checked all the details of the proofs. But, the ones I have checked are all correct and solid. The paper is also very well written.", "weaknesses": "- 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. \n\n- 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?\n\n- 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).\n\n- Can the authors comment on the tightness of Theorem 3 and 4? An the potential challenges of coming up with lower bounds?\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and for their positive evaluation. We address their comments below.\n\n---\n\n***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.***\n\nAt a high-level, we agree. Our guarantees are for the worst-case ERM and it is conceivable that a learning algorithm can avoid such worst-case scenario. Please note however that, as we have briefly hinted at in the conclusion, it is difficult to discuss learning algorithms in our setting given its extreme generality: the index set $\\mathcal{T}$ is not even equipped with a topology. One way to study a notion of \"(implicit) bias\" in our setting is to introduce some ordering on the set $\\mathcal{T}$ and consider the procedure that picks the smallest ERM in this ordering. However, we strongly believe that it is more appropriate to study this question for specific model classes and learning algorithms of interest, rather than in the general setting we consider here, as the insights obtained for the above-described procedure might not be transferrable to cases of practical interest.\n\n---\n\n***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?***\n\nWe agree with the reviewer on this limitation; the current Theorem 4 yields interpretable results only in the finite case. Obtaining interpretable results in the non-finite regime is an interesting and important direction that we leave for future work. One way forward would be to consider for example any set $\\mathcal{T}$ satisfying a metric entropy estimate (in an appropriately selected metric). One may then use an $\\varepsilon$-net argument along with our finite-case results and an argument that controls the approximation error to obtain an upper bound on the expected suprema of Theorem 4. However this approach only provides an upper bound, and requires some work for it to be practically interesting.\n\n---\n\n***Can the authors comment on the tightness of Theorem 3 and 4? An the potential challenges of coming up with lower bounds?***\n\nOn the asymptotic side, when the optimal feature map is unique, the second statement of Corollary 1 (of Theorem 3) already provides matching upper and lower bounds on the asymptotic excess risk (and the gap between the bounds is a factor of two). \n\nThe 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. \n\nRoughly 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. If the reviewer thinks the above-discussed lower-bound is interesting, we would be happy to include it in the final version.\n\nOn 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.\n\n---\n\n***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.***\n\nOne example we wanted to include of some practical relevance is the following. A popular statistical learning problem, which motivates the LASSO procedure, asks the following question: in a regression problem under the square loss, learn the best linear predictor from a $d$-dimensional feature map, knowing that the optimal linear predictor is $k$-sparse, i.e. the optimal weights have only $k$ non-zero entries for $k \\ll d$. \n\nOur results allow us to tackle the following more general problem: under no assumptions on the optimal weight vector, learn the best linear predictor from a subset of size $k$ of the $d$ features. This problem fits in our framework neatly by taking $\\mathcal{T}$ to be given by the set of all subsets of size $k$ of $[d]$ with $|\\mathcal{T}| = {d \\choose k}$, and our theorems imply, among other things, that the asymptotic quantiles of the excess risk of ERM on this problem are, up to a factor of two, the same as the oracle procedure that knows a priori the best subset of size $k$ of the $d$ features (assuming it is unique).\n\n---\n\n**References**\n\n[Kol06]: Koltchinskii, Vladimir. \"Local Rademacher complexities and oracle inequalities in risk minimization.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2MugtfYGBv", "reviewer": "Reviewer_pWnU", "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.", "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": "No limitations are stated.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results in this paper is both novel and significant. They show that even though non-optimal feature map exists in training process, the actual upper bound of the excess risk depends on the size of optimal feature maps. \nFrom theoretical perspective, the proofs are solid.\nThe writing is also good, clearly states the results and the intuition, and how their results improve beyond previous classical results where the feature map set is a singleton. Case study is also provided, giving a comprehensive review of how their general framework can be applied.", "weaknesses": "It will be good if more case studies are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading our paper and for their positive comments. We address their question and comments below.\n\n***It will be good if more case studies are provided.***\n\nAs mentioned in another comment, one additional example we wanted to include of some practical relevance is the following. A popular statistical learning problem, which motivates the LASSO procedure, asks the following question: in a regression problem under the square loss, learn the best linear predictor from a $d$-dimensional feature map, knowing that the optimal linear predictor is $k$-sparse, i.e. the optimal weights have only $k$ non-zero entries for $k \\ll d$. \n\nOur results allow us to tackle the following more general problem: under no assumptions on the optimal weight vector, learn the best linear predictor from a subset of size $k$ of the $d$ features. This problem fits in our framework neatly by taking $\\mathcal{T}$ to be given by the set of all subsets of size $k$ of $[d]$ with $|\\mathcal{T}| = {d \\choose k}$, and our theorems imply, among other things, that the asymptotic quantiles of the excess risk of ERM on this problem are, up to a factor of two, the same as the oracle procedure that knows a priori the best subset of size $k$ of the $d$ features (assuming it is unique).\n\n---\n\n***Is it possible to consider some infinite feature map set with some structure, so that you can also compute the constants in your results?***\n\nAs we described in another comment, upper bounds on the various expected suprema appearing in our results can be obtained under an assumption on the metric entropy of the set $\\mathcal{T}$ under an appropriately chosen metric. One may then use an $\\varepsilon$-net argument along with our finite-case results and an argument that controls the approximation error to obtain an upper bound on these expected suprema. However, obtaining such metric entropy estimates is a highly non-trivial task for any given problem, and requires specialized techniques that leverage the particular structure of the problem. We are currently trying to derive such entropy estimates for two-layer neural networks but we have yet to succeed. We believe that this is a good direction for future work.\n\n---\n***Limitations***\n\nPlease also note that we discussed the limitations of our work in the last paragraph of the paper. If the reviewer thinks something is missing, we would be happy to discuss it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UbNNtpPhvU", "reviewer": "Reviewer_rL5m", "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.", "questions": "Please address my concerns in the weaknesses part.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The statistical theory of this paper regarding feature learning is solid, and the results of the main theorems (Theorem 3 and Theorem 4) seem to be correct, even though I have not had time to check the detailed proofs. In fact, the Glivenko-Cantelli assumptions on the empirical processes and the finite moment assumptions are widely used in learning theory, and the rate $1/n\\delta \\approx O(1/\\sqrt{n})$ seems to be correct.", "weaknesses": "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.\n\n2. 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.\"\n\n3. 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.\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. We address some of their concerns below.\n\n---\n\n***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,...***\n\nWe thank the reviewer for bringing this line of work to our attention; we will carefully discuss their relevance in the final version of the paper. That said, our work is squarely in the realm of statistical learning theory (STL), and as such we have focused our effort on reviewing the STL literature, outlining existing results and techniques, and explaining what is challenging in our newly proposed setting.\n\n---\n\n***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.***\n\nThe only two sentences that relate our work to the experiments of [Zha+21] are:\n\n1- *\"The most tantalizing aspect of our results is their **potential** in explaining the experiments in [Zha+21]\".*\n\n2- *\"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.\"*\n\n\nWe believe the first sentence above leads to a misinterpretation of what we intended, and we will carefully revise this statement for clarity.\n\n---\n\n***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.***\n\nWe agree with the reviewer's second remark that our paper is indeed purely theoretical. However, our work provides a new perspective on the analysis of ERM and feature learning, and has the following main message:\n\n    Learning feature maps is easy when only a small subset of them is good, as the bad ones are quickly discarded by the ERM procedure.\n\nWe are not aware of prior works with the same conclusion. \n\n---\n\n***It would also be better for the authors to emphasize more technical difficulties compared to ERM without feature learning.***\n\nWe have a brief discussion about this in lines 72-78. We will elaborate more on these technical difficulties in the revised paper.\n\n---\n\n\n***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.***\n\nWe will clarify the technical contributions and the novelty of the analysis in more detail in the revision. We briefly remark here that\nwhile Theorem 3 vastly extends Theorem 1, this extension is by no means straightforward:\n1. It requires a new decomposition (eq. 19) of the excess risk that separates the error coming from the choice of feature map and the error coming from the choice of linear predictor. This is in contrast with Theorem 1 where the feature map is fixed, and there is only one source of error coming from the choice of linear predictor. \n2. It requires an independent proof that asymptotically, the feature map chosen by ERM is an optimal one. In Theorem 1, we have a single fixed feature map, so there is no analogue to this statement in the proof of Theorem 1.\n3. It requires a new limiting argument that relies on tools from empirical process theory (limiting gaussian process, continuous mapping theorem) to show that the excess risk is controlled by the complexity of the set of optimal feature maps $\\mathcal{T}_{\\*}$. The analogous step in the proof of Theorem 1 only requires studying a *single* empirical average, which is readily achieved by an application of the Central limit theorem.\n\nSimilarly, while Theorem 4 is an extension of Theorem 2, this extension is again not straightforward:\n1. It requires a new proof that bounds the suboptimality of the feature map picked by ERM non-asymptotically and relies on a localization argument of Koltchinskii [Kol06]. In Theorem 2, the feature map is fixed, so no analogous step exists in its proof.\n2. It requires bootstrapping this localization result to show that the excess risk of ERM does not depend on the full complexity of the function class, but rather on the complexity of shrinking subclasses of it. This is done by studying the supremum of a certain empirical process. In Theorem 2, the analogous step requires controlling a *single* empirical average using Markov's inequality.\n3. It requires showing that the shrinking subclasses of functions whose complexity controls the excess risk of ERM converges to the class of functions induced by the set of optimal feature maps (Lemma 1), recovering the result of Theorem 3 asymptotically. This is also new and unrelated to the proof of Theorem 2 where the feature map is fixed.\n\n---\n\nWe would be happy to answer any questions that may arise during the discussion period.\n\n---\n\n**References**\n\n[Zha+21]: Zhang, Chiyuan, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. \"Understanding deep learning (still) requires rethinking generalization.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3NZDYoOFhG", "reviewer": "Reviewer_bjqG", "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.\n\nEDIT: 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.", "questions": "Can the authors please explain why the localization phenomenon presented in this work is surprising?", "limitations": "(1) Weak dependence on error probability $\\delta$\n(2) Possible limitations due to the Donkser assumption\n(3) Restricted to the linear setting", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This paper has a number of strengths that make it compelling. \n\n(1) The formalism studies is **exceptionally** clean and natural. It lends itself to study well in other settings as well. \n(2) The authors provide both asymptotic and nonasymptotic results, and the asymptotic ones are rather \"sharp\" in that they provide insight into both the limiting distributions, and do so in terms of universal, Gaussian empirical processes. \n(3) The authors proofs are effective and succinct, and demonstrate great command of the relevant technical machinery. \n(4) The authors use of asymptotic bounds allows them to build considerable intuition in the presentation, before introducing the non-asymptotic bounds which are considerably more involving to parse.", "weaknesses": "There are a couple weaknesses, however, that temper my excitement. \n\n(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 \n\n$\\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 \n\n$\\bigcup_{t \\in \\mathcal{T}^\\star} \\mathcal{F}_t$\n\nIt is nice to quantify this rigorously, but again, the phenomenon does not seem to be to bring fundamentally new insight. \n\n(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. \n\n(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...\n\n(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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for engaging with our paper and for their feedback. We address some of their concerns below.\n\n---\n\n***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}\\_{\\*}$, and moreover, the risk of an $f \\in \\mathcal{F}\\_{t}$ where $t \\notin \\mathcal{T}\\_{\\*}$ 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}\\_{\\*}}\\mathcal{F}\\_{t}$. It is nice to quantify this rigorously, but again, the phenomenon does not seem to be to bring fundamentally new insight.***\n\nIf one believes on some level that the performance of ERM is related to the complexity of the class on which it is performed,  then our results are quite surprising. Our understanding is that this is a commonly held belief in the machine learning community.\n\nFor a reader very familiar with localization, we can see how they would be skeptical that the above statement holds once the setting we propose is presented to them. For such a reader, perhaps the most surprising aspect of our result is that one can get away with extremely weak assumptions on certain empirical processes yet still obtain a strong localization phenomenon. Conversely, and perhaps just as surprising to such a reader, is that without such assumptions, the localization phenomenon can completely vanish.\n\nHere is a counter-example to the reviewer's statement (as we understood it, please correct us if we missed something) that we hope makes this last point clear. Let $\\mathcal{F} := \\\\{x \\mapsto \\langle w, \\phi(x) \\rangle \\mid w \\in \\mathbb{R}^{d}\\\\}$ be a linear class induced by a feature map $\\phi$. We can write this $d$-dimensional subspace of functions as the union of its $1$-dimensional subspaces. More explicitly, let $\\mathcal{T}$ be the half of the unit Euclidean sphere in $\\mathbb{R}^{d}$ with non-negative first coordinate, let $\\phi\\_{t}(x) := \\langle t, x\\rangle$ for all $t \\in \\mathcal{T}$, and set $\\mathcal{F}\\_{t} := \\\\{x \\mapsto a \\cdot \\phi\\_{t}(x) \\mid a \\in \\mathbb{R}\\\\}$, then $\\mathcal{F} = \\bigcup\\_{t \\in \\mathcal{T}} \\mathcal{F}\\_{t}$. Now consider a well-specified linear regression problem under square loss over $\\mathcal{F}$, i.e. $Y = \\langle w\\_{\\*} , \\phi(X) \\rangle + \\varepsilon$ for some $w\\_{\\*} \\in \\mathbb{R}^{d}$ and $\\varepsilon  \\sim \\mathcal{N}(0, \\sigma^{2})$ independent of $X$. Then the optimal feature map is $t\\_{*} = \\pm w\\_{\\*}/ \\\\|w\\_{\\*}\\\\|\\_{2}$, and for each $f \\in \\mathcal{F}\\_{t}$ for $t \\neq t\\_{\\*}$, the excess risk of $f$ is lower bounded away from zero, so if the statement of the reviewer held, the excess risk should be of order $1$ (proportional to the complexity of the class corresponding to the optimal feature map $\\mathcal{F}\\_{t\\_{\\*}}$, which is one dimensional). Yet, it is a classical result that the excess risk in this problem is of order $d$, i.e. it depends on the complexity of the full class $\\mathcal{F}$. \n\nThis example shows that the intuitive reasoning that because we have a function class expressed as the union of other function classes we should expect localization might be misleading. More is needed, but perhaps the surprising thing is that not too much is needed: Glivenko-Cantelliness/Donskerity of certain empirical processes.\n\nTo a certain extent, we agree that the most significant contribution of our work is to propose a tractable framework where feature learning can be studied rigorously, and we are excited to see how it can be applied to study other problems beyond the supervised learning setting we considered in this paper. Even if our results are not surprising to the reviewer, we hope that the simplicity and usefulness of the framework we introduce and the rigor of our work convinces them that the ideas in this paper are worth sharing.\n\n***The non-asymptotic dependence on the probability of error 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.***\n\n\nWe note that, as discussed in line 133, under our *very weak assumptions*, this is the best dependence on $\\delta$ one can obtain for the performance of ERM. In fact, this bad dependence on $\\delta$ has spurred the development of a susbtantial literature that aims at designing procedures with better dependence on $\\delta$; please refer to the works cited in line 133.\n\nWe chose to present our results under the weakest assumptions possible in order to maximize their range of applicability. We agree with the reviewer that under more stringent assumptions (e.g. boundedness of $X$ and $Y$), our analysis would yield a much improved dependence on $\\delta$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)