On the Double Descent of Random Features Models Trained with SGD
Authors: Fanghui Liu
Johan Suykens
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: random features
over-parameterized model
double descent
SGD

Abstract: We study generalization properties of random features (RF) regression in high dimensions optimized by stochastic gradient descent (SGD) in under-/over-parameterized regime. In this work, we derive precise non-asymptotic error bounds of RF regression under both constant and polynomial-decay step-size SGD setting, and observe the double descent phenomenon both theoretically and empirically. Our analysis shows how to cope with multiple randomness sources of initialization, label noise, and data sampling (as well as stochastic gradients) with no closed-form solution, and also goes beyond the commonly-used Gaussian/spherical data assumption. Our theoretical results demonstrate that, with SGD training, RF regression still generalizes well for interpolation learning, and is able to characterize the double descent behavior by the unimodality of variance and monotonic decrease of bias. Besides, we also prove that the constant step-size SGD setting incurs no loss in convergence rate when compared to the exact minimum-norm interpolator, as a theoretical justification of using SGD in practice.

On the Double Descent of Random Features Models Trained with SGD
Fanghui Liu" LIONS, EPFL
Johan A.K. Suykens
ESAT-STADIUS, KU Leuven j johan suykensesat.. kuleuven. be
fanghui -liu@epfl.ch
Volkan Cevher
LIONS, EPFL
volkan volkan.cevheree cewher@epf1.cc
Abstract
We study generalization properties of random features (RF) regression in high dimensions optimized by stochastic gradient descent (SGD) in under-/over- parameterized regime. this work, we derive precise non-asymptotic error bounds of RF regression under both constant and polynomial-decay step-size SGD setting, and observe the double descent phenomenon both theoretically and empirically. Our analysis shows how cope with multiple randomness sources of initialization, label noise, and data sampling (as well as stochastic gradients) with no closed- form solution, and also goes beyond the commonly-used Gaussian/spherical data assumption. Our theoretical results demonstrate that, with SGD training. RF regres- sion still generalizes well for interpolation learning, and able characterize the double descent behavior by the unimodality of variance and monotonic decrease of bias. Besides, we also prove that the constant step-size SGD setting incurs no loss in convergence rate when compared to the exact minimum- norm interpolator, as a theoretical justification of using SGD in practice.
Introduction
Over- parameterized models, e.g., linear/kernel regression 2 4 and neural networks [5 7 still generalize well even if the labels are pure noise [8. Such high sighccapactyy models have received significant attention recently they go against with classical generalization theory. A paradigm for understanding this important phenomenon double descent [ in which the test error first decreases with increasing number of model parameters in the aaddr-parameterizzed regime. They large error is yielded until interpolating the data, which is called the interpolation threshold. Finally, the test error decreases again the over-parameterized regime.
Our work partakes in this research vein and studies the random features (RF) model 10,, as simpli- fied version of neural networks, in the context of double descent phenomenon. Briefly, RF model samples random features {w; ) from a specific distribution, corresponding to kernel function. We then construct an explicit map: x E Rdd + a oWa)) x.) TR.", where W [,,,,.. wm.]" mx is the random features matrix and o(-) is the nonlinear (activation) function determined by the kernel. As result, the RF model can viewed as training a two-layer neural network where the weights in
the first layer are chosen randomly and then fixed ka. the random features) and only the output layer is optimized, striking a trade-off between practical performance and accessibility to analysis
Moot of this work was done when Fanghui was at KU Leuven. Correspondence to: Fanghui Liu <fanghui liu@epfl.ch.. ch>.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

An RF model becomes over over-varaannn parameterized model if we take the number of random features m larger than that of training data n. The literature on RF under the over-parameterized regime can be split into various camps according to different assumptions on the formulation of target function, data distribution, and activation functions 4 12 I
15] (see comparisons in Table in Appendix A The existing theoretical results demonstrate that the excess risk curve exhibits double descent.
Nevertheless, the analysis framework of previous work on RF regression mainly relies on the least- squares closed-form solution, including minimum-norm interpolator and ridge regressor. Besides, they often assume the data with specific distribution, e.g., to be Gaussian or uniformly spread on sphere. Such dependency on the analytic solution and relatively strong data assumption in fact mismatches practical neural networks optimized by stochastic gradient descent (SGD) based algorithms. Our work precisely bridges this gap: We provide new analysis framework for the generalization properties of RF models trained with SGD and general activation functions, also accommodating adaptive (i.e., polynomial decay) step-size selection, and provide -symmtttiiiic results in under-/over-pareen parrmmeoee-parrammetriiieedd regimes. We make the following contributions and findings:
First, we characterize statistical properties of covariance operators/matrices in RF, including Σm. 1 Ez (ar Wa/e a/vd)a (Wx/ Wa/vd)] Va)"] and expectation version 5.m == w [E.] We demonstrate vn that, under Gaussian initialization, if the activation function (-)) R ~ TR is Lipschitz continuous, Tr(Em) is sub-exponential random variable with O(1) sub-exponential norm; E. has only two distinct eigenvalues at (1)) and (1/mm) order, respectively. Such analysis on the spectra of Em
and E.m (without spectral decay assumption) is helpful to obtain sharp error bounds for excess risk. This is different from the least squares setting based on effective dimension 2 [6].
Second, based on the bias-variance decomposition in stochastic approximation, we take into account multiple randomness sources of initialization, label noise, and data sampling as well as stochastic gradients. We (partly) disentangle these randomness sources and derive non-asymptotic error bounds under the optimization effect: the error bounds for bias and variance as a function of the radio m/n n are monotonic decreasing and unimodal, respectively. Importantly, our analysis holds for both constant and polynomial-decay step-size SGD setting, and valid under sub-Gaussian data and general activation functions.
Third, our non-asymptotic results show that, RF regression trained with SGD still generalizes well for interpolation learning, and is able to capture the double descent behavior. In addition, we demonstrate that the constant step-size SGD setting incurs no loss on the convergence rate of excess risk when compared to the exact least-squares closed form solution. Our empirical evaluations support our theoretical results and findings.
Our analysis (technical challenges are discussed in Section 4) sheds light on the effect of SGD on high dimensional RF models in paraateeerddr regimes, and bridges the gap between the minimum-norey solution and numerical iteration solution in terms of optimization and generalization on double descent. It would be helpful for understanding large dimensional machine learning and neural network models more generally.
2 Related work and problem setting
This section reviews relevant works and introduces our problem setting of RF regression with SGD,
Notation:
The notation & denotes the tensor product of vector a. For two operators/matrices, A & means B- is positive semi-definite (PSD). For any two positive sequences {ar]i= and {b. 1 the notation a S b, means that there exists positive constant C independent of such that 0g < Cbe, and analogously for ~., Z, and 3. For any a, b E R, a A b denotes the minimum of a and b.
2.1 Related work
flurry of research papers are devoted to analysis of over- per-parmmeterize models on optimization
[17 [8 19], generalization (or their combination) under neural tangent kernel [20] [1] 22 and
mean-field analysis regime 23 24). We take unified perspective on optimization and generalization but work in the high-dimensional setting to fully capture the double descent behavior. By high- dimensional setting, we mean that m, n, and increase proportionally, large and comparable
422 11 J.].

---

Double descent in random features model: Characterizing the double descent of the RF model often
derives from random matrix theory (RMT) in high dimensional statistics [ I2 25| and from the replica method [1] 26 [4]. Under specific assumptions on data distribution, activation functions, target function, and initialization, these results show that the generalization error/excess risk increase when m/n < 1, diverge when m/n + 1, and then decrease when m/n > 1. Further, refined results are developed on the analysis of variance due to multiple randomness sources [I]] 27 [5]. We refer to comparisons in Table in Appendix A for further details. Technically speaking, since RF (least-squares) regression involves with inverse random matrices, these two classes of methods attempt to achieve similar target: how to disentangle the nonlinear activation function by the Gaussian equivalence conjecture. RMT utilizes calculus of deterministic equivalents (or resolvents) for random matrices and replica methods focus some specific scalar parameters that allows for circumventing the expectation computation. In fact, most of the above methods can be asymptotically equivalent to the Gaussian covariate model (28).
Non-asymptotic stochastic approximation: Many papers on linear peast-squares regression kernel regression [1 32), random features [К] with SGD often work in the mnder-parameterizee regime, where d is finite and much smaller than π. In the over-parameterized regime, under GD
setting, the excess risk of least squares is controlled by the smallest positíve eigenvalue in [4 Via
random matrix theory. Under the averaged constant step-size SGD setting, the excess risk in 35 on
least squares in high dimensions can be independent of d, and the convergence rate is built in [16].
This convergence rate is also demonstrated under the minimal-iterate [6) or last-iterate [7 setting in step-size SGD for noiseless least squares. We also notice concurrent work (38] on last-iterate
SGD with decaying step-size on least squares. Besides, the existence of multiple descent 33 40
beyond double descent and SGD implicit regularizer [41 42 can be traced to the above two lines
of work. Our work shares some similar technical tools with [1 and [16] but differs from them in several aspects. We detail the differences in Section
2.2 Problem setting
We study the standard problem setting for RF least-squares regression and adopt the relevant ter- minologies from learning theory: cf,, 43 31
33 25 for details. Let X C IRd be metric space and Y S R. The training data { 34) } are assumed to be independently drawn from a non- degenerate unknown Borel probability measure p on X x Y. The target finnction of p is defined by fa(=) = Jy y ddp æ), where p(- x) is the conditional distribution of at æ E X.
RF least squares regression: We study the RF regression problem with the squared loss follows:
minE(f))
(f(x) (f(x)-
((((z))))Ppppll ddp y) Ilf - follãa with f(x) = (0, <(()))
FEH
where the optimization vector 0 IRm and the feature mapping p(x) is defined as J.m |owwT Vm x/ a/)) oow // vva]]
1
1 mm"
(xx)
(Wa/V ERT
E
(I)
where W Ww,.... wm] E Raxd with Wi ~ NO0, 1) corresponds such two-layer neural network initialized with random Gaussian weights. Then, the corresponding hypothesis space H is reproducing kernel Hilbert space
{ [ 12 f(x) 1 ((0 Vm
H =
-
(2)
with 1 Sx 1f(x)) (dxx Emm'/H with the covariance operator Σ.. R + Rm
Σm / ((x) & (x))
actually defined in H that is isomorphic to Rm This is the usually (uncentered) covariance matrix in finite dimensions i..., Σm (x(((()) @ p(x)]. Define Jm Rm + L such th) (v, p())), Yo E T have Σm J Jm. where J denotes the adjoint operator of Jm-
IIn this paper, we do distinguish the notations En, and Em. This is also suitable to other opera- tors/matrices, e.g., Em.
3

---

Clearly, Im is random with respect to W, and thus its deterministic version is defined as Em Be.w (p(x) @ ((x)).
SGD with averaging: Regarding the stochastic approximation, we consider the one pass SGD with iterate averaging and adaptive step-size each iteration t: after training sample (#te, yt) p is observed, we update the decision variable as below (initialized at 00)
0 = 0 + nlye (0.-1, ((x)))((=))))(((())
t t= 1.2....,
where we use the polynomial decay step size "/- :- 7ot with ( E [0, 1). following [31. This setting also holds for the constant step-size case by taking (- 0. Besides, we employ the bath size = in an online setting style, which is commonly used in theory [31] 16 4el for ease of analysis, which captures the key idea of SGD by combining stochastic gradients and data sampling.
The final output is defined as the average of the iterates: 0, == Σ/= O.. Here we sum up {0, (0,)r-0
zs with n terms for notational simplicity. The optimality condition for Eq. 44) implies E (2 (
(0", (x())) [=)]] = O, which corresponds to f = Jm0" we assume that f argmin JEH {f) exists (see Assumption in the next section). Likewise, we have ft = Jm O, and fr = Jm Un.
In this paper, study the averaged excess risk f. f I12g "x follows
instead of E follig, that
as f* is the best possible solution in Ht and the mis-specification error Ilf fell. pales into insignificance. Note that the expectation used here is considered with
[3
45 33 25
xx
respect to the random features matrix W. and the distribution of the training data ((2),,))]==1 (note is itself a different expectation over px).
that fn - f 1l 1
3 Main results
In this section, we present our main theoretical results on the generalization properties employing error bounds for bias and variance of RF regression in high dimensions optimized by averaged SGD.
3.1 Assumptions
Before we present our result, we list the assumptions used in this paper, refer to Appendix B for more discussions.
Assumption 1. 44 high dimensional setting] We work in the large n, m regime with e & {d/n,, mnnnn/n & C for some constants c, C,C > O such that m, n, d are large and comparable. The data point x E Rd is assumed to satisfy || ~ ((d) and the sample covariance operator Σg == Ex x 8 a0) with bounded spectral norm [|Ea|]a (finite and independent of d).
Assumption 2. There exists f E H such that f argmin E(f) with bounded Hilbert norm.
Remark:
This bounded Hilbert norm assumption is commonly used in and d tend infinity. It holds true for linear functions with ||/ < 4m details.
47
48
even though n
49 see Appendix B for
Assumption 3. The activation function o()) is assumed to be Lipschitz continuous.
Remark:
This assumption is quite general cover commonly-usee activation functions used in random features and neural networks, e.g., ReLU, Sigmoid, Logistic, and sine/cosine functions.
Recall Σm = (xx)) @ x in Eq. B and its expectation Σn,. == Ew [_m]. we make the to analyse SGD for least squares.
following fourth moment assumption that follows 22 16 37
Assumption 4 (Fourth moment condition). Assume there exists some positive constants r' r > 1. such that for any PSD operator A, holds that
Ex (1v(2r)) @ ((=))) & ((x))) xo (T( < TT A) A)Em.
Ew Em AEm) & Ew
Remark: This assumption requires the data are drawn from some not-too-heavy--ailee distribution,
e.g., Σm x has sub-Gaussian tail, common in high dimensional statistics. This condition is weaker than most previous work on double descent that requires the data to Gaussian
[T] [1 27 12].
or uniformly spread on sphere [4] (50), see comparisons in Table D in Appendix A Note that the

---

assumption for any PSD operator is just for ease of description. In fact some certain PSD operators satisfying this assumption are enough for our proof. Besides, special case of this assumption with
A : 7 is proved by Lemma 3 and thus this assumption can be regarded as a natural extension, with more discussions in Appendix
Assumption 5 (Noise condition). There exists such that = == Ee (p(x)) x =
where the noise E := y (x).
Remark: This noise assumption standard in (m) (z) + with E[s] 0 and V[s] < oo [
31 16 and holds for the standard noise model
3.2 Properties of covariance operators
Before we present the main results, study statistical properties of Em and Em by the following lemmas (with proof deferred to Appendix C that will be needed for our main result. This is different from the least squares setting [2] [6] that introduces the effective dimension to separate the entire space into a "head" subspace where the error decays more quickly than the complement
"tail" subspace. Instead, the following lemma shows that Sm has only two distinct eigenvalues at (1) and (1/m) order, respectively. Such fast eigenvalue decay can avoid extra data spectrum assumption for tight bound. For description simplicity, we consider the single-output activation function: (.) R + R. Our results can be extended to multiple-output activation functions, see Appendix .2 for details.
Lemma Under Assumption andd 3 the expected covariance operator Σ,, := En & (p(=)) E mpmm has the same diagonal elements and the same non-diagonal element
(Em)a )a 1 Ex ToLE m
(Emly = m
Em ( (E ((1mm))
Accordingly, Em has only two distinct eigenvalues
A1 (Em)a + (m - 1mm)m 0(1). (Emss 10l4--2im -(m)) - E. [ O(1/m).
1
m
Remark: Lemma I iimlies tr(Em) < co. In fact, En V(o > 0 holds almost surely as ar.) is not constant, and thus Σm is positive definite.
Here we take the ReLU activation a (æ) = max 0} as one example, RF actually approximates the first-order arc-cosine kernel [5]] with <x(x) E R". We have (Em) = 1 Tr(Ea) and (Em)s = 2md
2mdr (),)) by recalling Eg := [xxe] and Tr(Ea)/d O(1). More examples can be found in Appendix C.I.2
Lemma 2. Under Assumptions lndd random variables ||Em ll,. |mm - E2. and Tr(Em) are sub-exponential,, and have aub-exponential norm at (1) order.
Remark: This lemma characterizes the sub- cobb-exooential property of covariance operator Em- which a fundamental result for our proof since the bias and variance involve them.
The following lemma demonstrates that the behavior the fourth moment can be bounded.
Lemma Under Assumptions 7 and there exists a constant r such that Eaw (5%) x
Ex, Fa,wiee (p)( @ ((x)) @ (p(x) @ [x)) < (Tr(Em))
Lemma 4. Under Assumptions
ladd) 3 we have Tr[E Ew (2 (().
We remark here that Lemma 3 is special case of Assumption if we take A := / and r = 1+0 (2)): and Lemma 4 is direct corollary of Lemma
3.3 Results for error bounds
Recall the definition of the noise E = [ei, [e]] with & = =t -)-(((())), averaged excess risk can be expressed
: /.
=1,2,..., the
fl -f" 1'1
Ex.wwelf.. 1'1 -Ex,w,eff fr, ",E =
="))=Ex,m w. (Tn Emn
5

---

where 7n = 1 Ei=o t with the centered SGD iterate ?h ft fr Following the standard
bias-variance decomposition in stochastic approximation [1 30, 16
it admits
" [T (a)( @
(*) mexs((r))
where the first term corresponds to the bias
blas
[ (p(())) p p(x:))mm bies
%
blas f
(5)
and the second term corresponds the variance
T) yar = [I (1(();)))) @ p(a:)lni + Ne)p(()))
170 var 0.
(6)
Accordingly, we have = T/( pias + n + f due to E.fn thise + f and fl
(f. mm
Proposition 1. Based on the above setting, the averaged excess risk admits the following bias- variance decomposition
1112, =Ex,w.elffa -ew.allfa-EerttBehf - f = Ex w (Thise Em bise
var Em Ta
Bias
-Vaiiance
By (partly) decoupling the multiple randomness sources of initialization, label noise, and data sampling (as well as stochastic gradients), we give precise non-asymptotic error bounds for bias and variance as below.
Theorem 1. (Error bound for bias) Under Assumptions
with r' > 1, if the step-size Tt = ma with Ç [0, 1) satisfies To S (TEE)..)) (1),, the Bias Proposition holds by
Bias S vor n 1|- 0 (n5-1).
The error bound for Bias is monotonically decreasing at ( rate. For the constant step-size setting, it converges O(1/n) rate, which is better than O( //oo n/n) in 22 relying closed-form solution under correlated features with polynomial decay on E.. Besides, our result on bias matches the exact formulation in [11] under the closed-fomm solution, i.e., monotonically decreasing bias. One slight difference is, their result on bias tends to a constant under the over- parameterized regime while our bias result can converge to zero.
Remark:
Theorem 2. (Error bound for variance) Under Assumptions 1 with r' 1, and Assumption 5 with > O, if the step-size ? == 7 with C E 1) satisfies To S "Tr((E.))) ~ O(1), the Variance defined in Proposition Iantiiionnool hoold
mn if 1 1 5-1 + n if m
Variance S yor'7?
Remark:
We make the following remarks:
The error bound for Variance demonstrated be unimodal: increasing with m the under- parameterized regime and decreasing with m in the over-parameterized regime, and finally converge to constant order (that depends on noise parameter 7²), which matches recent results relying on
closed-form solution for (refined) variance, e.g., [1] 27 15]
iî) When compared to least squares, our result can degenerate to this setting by choosing m = Our upper bound is able match the lower bound in [1] Corollary with the same order, which demonstrates the tightness our upper bound. Besides, our results can recover the result of [16] by taking the effective dimension k* min(n, d} (no data spectrum assumption is required here). More discussion on our derived results refers to Appendix A
Proof outline and discussion
In this section, first introduce the structure of the proofs with high level ideas, and then discuss our work with previous literature in terms of the used techniques and the obtained results.

---

excess risk Ex.w w.e tWeeWPre (Pr, PmmFhr)
Variance Ex,w. B. eiim Emifie
Ex. w (n Smnth hias
v1: fi O((5-im) m) O(1)
% if m n m >x
12: th mm ((((51mm) O(1)
va: Ti (((S-1m) On1 +1
B1: paaa On
nim
B2: Th O(
1ia 1)
th O11
decomposition in Lem. 7: 1/6
1/c
C7 in Lem,
CT Lem. 11
Ct in Lern. 10
111 bisa
||a
HI.
in Lem.
C7 with Ç ==1
| in
Fic 1
|| in Lem.
Figure 1: The roadmap of proofs.
4.1 Proof outline
We (partly) disentangle the multiple randomness sources the data X, the random features matrix W. the noise E, make full use of statistical properties of covariance operators Em and Σn,. in Section 3.2 and provide the respective (bias and variance) upper bounds in terms of multiple randomness sources, as shown in Figure
Bias: To bound Bias, we need some auxiliary notations. Recall En = Ex(s((x)) @ (p(x)] and Σm E.,, Fer.w/e (o.w(pp(a) (x) & (p())), define
W = (T - - Em )
bX =
(1 2 ) Y
bIW
DIV =
(7)
with the average क. := 1 Ei=o Th and f : 1 Σ/= 7/ Accordingly, Tu can regarded as a "deterministic" version of yiiis; we omit the randomness on X (data sampling, stochastic gradients) by replacing [p(()){(())]] with its expectation Σm Likewise, y/bи deterministic version of xy by replacing Em with its expectation En (randomness on initialization).
By Minkowski inequality, the Bias can be decomposed as Bias < B1 B2 + B3, where B1 := Ex.w (myias 7/bx Em (Tpias - T ))] and B2 : Ew [( - Tre Em > and B3
(nb.и En Tm.)))) Here B3 is deterministic quantity that is closely connected model (intrinsic) bias without any randomness; while B1 and B2 evaluate the effect of randomness from and W on the bias, respectively. The error bounds for them be directly found in Figure
To bound B3, we directly focus on its formulation by virtue of spectrum decomposition and integral Σr (n) ),bx)) where the key part
estimation. To bound B2, we have B2 J.2
v/² - 1// can be estimated by Lemma To bound B1, it can be further decomposed as (here we
inaccurate expression for description simplicity) B1 S Σ, |lvb Mx [ Σ, Ex H, || in
Lemma 7 where Hz-1 = D ((x;) @ (p(x) 1nbk The first term can be upper bounded by
E. ||mp 1 1 < Tr(E,)) n l [| in Lemma 8 and the second term admits Σ, Ex H 1| S
Tr(Em)]lff in Lemma
Variance: To bound Variance, need some auxiliary notations.
ni (I - E, " + (x)))())
nox 0,
(8) (9)
1/ := (I - 71 Em mi + )x)))
vIW O, 170
with the averaged quantities T7x := 1 Σrー xx T == - T Accordingly, 17 can be regarded "semi-stochastic" version of m/ var: we keep the randomness due to the noise but omit

---

the randomness on X (data sampling) by replacing (<xx))((x=" with its expectation Em. Likewise, "e can be regarded as a "seemisttchasttic" version of n by replacing Em with its expectation E... (randomness on initialization).
By virtue of Minkowski inequality, the Variance can be decomposed as Variance 5 V1 V2 v3, where V1 = x w. (T/2 172x (m - 1/, ))>)) )) V2 == .x, [ - Em - ( )) and V3 == I. x, w.W 7m xx Em 7. ). Though V1, V2,
still interact the multiple randomness, disentangles some randomness on data sampling, V2 discards some randomness on initialization, and v3 focuses on the "minimal" interaction between data sampling, label noise, and initialization. The enror bounds for them can be found in Figure
To bound V3, we focus on the formulation of the covariance operator C := Ex.emn & of in
Lemma 10 and the statistical properties of Em and Em- To bound V2, we need study the covariance
operator C wx-M == [x,=[(n] - m)(
@ (n - n admitting ||CØx-"|| 2 12 ( mm in
Lemma
11
To bound V1, we need study the covariance operator C7 = Ex [ m Ø
as function of Ç E [0.1), admitting
& Tr|C,- (0) in Lemma and
further
C7 x Tr(Em) / in Lemma 12
4.2
Discussion techniques
Our proof framework follows 31 that focuses on kernel regression with stochastic approximation in the under-ped patrreterrrzeedd regimes (d regarded as finite and much smaller than n). Nevertheless, even in the under-pauee under-parameterizan parameterized regime, their results not be direetly extended to random features model due to the extra randomness on W. For instance, their results depend on [29] Lemma 1] by taking conditional expectation to bridge the connection between [[lloeell [|a] and EE (o,, Em This is
valid for B1 but expires on other quantities.
Some technical tools used in this paper follow [66] that focuses on linear regression with constant step-size SGD for benign overfitting. However, our results differ from in 1) tackling multiple randomness, e.g., stochastic gradients, random features (Gaussian initialization), by introducing another type error decomposition and several determinisstccrraddonnes covariance operators. prove nice statistical properties of them for proof, which gets rid of data spectrum assumption in [16). 2) tackling non con-tonttatt step-size SGD setting by introducing new integral estimation techniques. Original techniques constant step-size in [16] are invalid due to non-hooogeneous update rules. The above two points make our proof relatively more intractable and largely different. Besides, their results demonstrate that linear regression with SGD generalizes well (converges with but has few findings on double descent. Instead, our result depends on n and m (where d is implicitly included in m), and is able to explain double descent.
Here we take the estimation for the variance in 16 under the least squares setting as an example to illustrate this.
Variance
11-
[Eq. (4. in 16
In this setting, the effective dimension tackle 7- -I (I->Ea))~ while our result is based fast eigenvalue decay of Em in Lemma] can direct to bound this. Besides, the homogeneous markov chain under the constant step-size setting is employed (16) for (I >Ea)"= which is naturally invalid under our decaying step-size setting. Instead, we introduce integral estimation techniques to tackle adaptive step-size, Appendix for details.
E
Numerical Validation
In this section, we provide some numerical experiments Figure to support our theoretical results and findings. Note that our results go beyond Gaussian data assumption and can be empirically validated on real-world datasets. More experiments can be found in Appendix
5.1 Behavior of RF for interpolation learning
Here we evaluate the test mean square error (MSE) of RFF regression on the MNIST data set [52]. following the experimental setting of [3 53,, to study the generalization performance of minimum-norm solution, see Figure ((a) More results regression dataset refer to Appendix H
8

---

SGO mon solution
B1
82
V2
Test MSE
B3
V3
109
0.5
10
0.5
1.5
0.5
1.5
m/n
m/h
(a) SGD vs. min- norm solution
(b) Bias
(c) Variance
Figure 2: Test MSE stt. of RF regression as a function of the ratio m/n on MNIST data set (digit 3 vs. 7) across the Gaussian kernel, for d 784 and n 600 (a). The interpolation threshold occurs at m/n 0.5 as the Gaussian kernel outputs the 2m--fature mapping (instead of m)) i.e., (War x) E R22m Under this setting, the trends Bias and Variance are empirically given in (b) and (c).
Experimental settings: We take digit 3 vs. 7 as example, and randomly select 300 training data in these two classes, resulting n 600 for training. Hence, our setting with n 600, d 784, and tuning m satisfies our realistic high dimensional assumption. The Gaussian kernel k(x, x') = exp(-1 - x' (2 ) is used, where the kernel width op is chosen as oî = d in high dimensional settings such that | /dd~~ ((1) in Assumption | In our experiment, the initial step-size is set to " = 1 and we take the initial point O, near the min-norm solution corrupted with zero-mean, unit-variance Gaussian noise. The experiments
repeated 10 times and the test MSE (mt. can be regarded as a function of the ratio m/n by tuning m. Results on different initialization and more epochs of SGD refer to Appendix H
SGD vs. minimal-norm solution: Figure ((a) shows the test MSE RF regression with averaged SGD (we take ( = 0.5 as example; red line) and minimal-norm solution (blue line). First, we observe the double descent phenomenon: a phase transition on the two sides of the interpolation threshold at 2m when these two algorithms are employed. Second, in terms of test error, RF with averaged SGD is slightly inferior to that with min-norm solution, but still generalizes well.
5.2 Behavior of our error bounds
We have experimentally validated the phase transition and corresponding double descent in the previous section, and here we aim to semi--uantitatively assess our derived bounds for Bias and Variance, see Figure 2(b) and 2(c) respectively. Results of these quantities on different step-size
refer to Appendix
Since the target function f*, the covariance operators Eg, Ems and the noise e are unknown on the MNIST data set, our experimental evaluation need some assumptions to calculate Bias and Variance. First, we assume the label noise (0, 1), which can in turn Second, the covariance matrices Σg and 2'm are estimated by the related sample covariance matrices. When using the Gaussian kernel, the
Experimental settings:
obtain f (a:) on both training and test data due to f=x
covariance matrix Σm can be directly computed, see the remark Lemma ! where the expectation on is approximated by Monte Carlo sampling with n training samples. Accordingly, based on the above results, we are ready to calculate vibise in Eq. (5) 1/ and 1), in Eq. 7 respectively, which 17 Em (7 - x (red line)
further used to approximately compute B1 = Ex w (
and B2 Ew [17h* - DxN Em, (77h - (blue line) and B3 (77 Σ Tbrw (green line). The
(approximate) computation for Variance can be similar achieved by this process.
Error bounds for bias: Figure 2(b) shows the trends of (scaled) B1, B2, and B3. Recall our error bound: B1, B2, B3 ~ O(15-1), we find that, all of them monotonically decreases at certain convergence rate when m increases from the under-paran siieerpprrmeterizeddd regime to the over-parameterized regime. These experimental results coincide with our error bound on them.
"I our numerical experiments, we only employ single-pass pass SGD, and thus the initialization is chosen close minimum solution, with more discussion Appendix H

---

shows the trends of (scaled) V1, V2, and V3. Recall our enor bound: in the under-pate parameteaate regime, V1, V2, and increase with m at a certain O(nS-Im) m) rate; and in the over-parameterized regime, V1 and V2 are in ((1) order while V3 decreases with m. Figure [ shows that, when 2m < n, and V2 monotonically increases with m and then remain unchanged when 2m > n. Besides, V3 is observed to be unimodal: firstly increasing when 2m < n, reaching to the peak at 2m = n, and then decreasing when 2m > n, which admits the Accordingly, these findings accord with our theoretical results, and also matches refined results in 1 15: the unimodality variance is a prevalent phenomenon.
Error bounds for variance: Figure 2(c)
phase transition 2m
6 Conclusion
We present non-asymptotic results for RF regression under the averaged SGD setting for understanding double descent under the optimization effect. Our theoretical and empirical results demonstrate that, the error bounds for variance and bias can be unimodal and monotonically decreasing, respectively, which is able recover the double descent phenomenon. Regarding constant/adaptive step-size setting, there is no difference between the constant step-size case and the exact minimal-nowe solution on the convergence rate; while the polynomial-deet step-size case will slow down the learning rate, but does not change the error bound for variance in werrpaarameterized regime that converges to O(1) order, that depends on noise parameter(s).
Our work centers around the RF model, which is still a bit far away from practical neural networks. Theoretical understanding the generalization properties of rreepparamtterized neural networks is fundamental but difficult problem. We believe that a comprehensive and thorough understanding of shallow neural networks, e.g., the RF model, is necessary first step. Besides, single-pass SGD in our work for simplicity rather than multiple-pass SGD used in practice. This is also an interesting direction for understanding the optimization effect of SGD in the double descent.
consider the
Besides, our results obtain the dimension-free bound under both non-asymptotic and asymptotic regimes. We also need to mention that, our results are also valid under the fixed d setting (which can be larger or smaller than n). This is more practical for real-world applications.
Acknowledgment
The research leading to these results has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation program: ERC Advanced Grant E- DUALITY (787960) and grant agreement n 725594 - time-data. This paper reflects only the authors' views and the Union not liable for any use that may be made of the contained information. This work was supported by SNF project- Deep Optimisation of the Swiss National Science Foundation (SNSF) under grant number 200021 20501 1: Research Council KU Leuven: Optimization frameworks for deep kernel machines C14/18/068; Flemish Government: FWO projects: GOA4917N (Deep Restricted Kernel Machines: Methods and Foundations), PhD/Postdoc grant. This research received funding from the Flemish Government (AI Research Program). This work was supported in part by Ford KU Leuven Research Alliance Project KUL0076 (Stability analysis and performance improvement of deep reinforcement learning algorithms), EU H2020 ICT-48 Network TAILOR (Foundations of Trustworthy AI Integrating Reasoning, Learning and Optimization), Leuven.AI Institute.
We also thank Zhenyu Liao and Leello Dadi for their helpful discussions on this work.
References
[1] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of Statistics, 50(2):949-986, 2022.
6
16
[8
19
[2] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. the National Academy of Sciences, 2020.
18
[3] Denny Wu and Ji Xu. On the optimal weighted &g regularization in overparameterized linear regression, In Advances in Neural Information Processing Systems, pages 101 2020.
10

---

[4] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
16 T9 41
[5] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. International Conference on Learning Representations, 2019.
[6] Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. In International Conference on Machine Learning, 2020. [
[7] Peizhong Ju, Xiaojun Lin, and Ness B. Shroff. On the generalization power of overfitted two-layer neural tangent kernel models. In International Conference on Machine Learning. pages 5137-5147. PMLR, 2020.
[8] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
[9] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biri-variance trade-off. the National Academy of Sciences,
1 (1633)):5549-111
2019. [
[10] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances
in Neural Information Processing Systems, pages 1177-1184, 2007. !
[11] Stéphane d'Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning, pages 2280-2290, 2020.
10 16
19
[12] Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang. Generalization of two-layer neural networks: an asymptotic viewpoint. In International Conference on Learning Representations, pages 1-8, 2020.
19
[13] Zhenyu Liao, Romain Couillet, and Michael Mahoney, random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent. In Neural Information Processing Systems, 2020. 2
40
[14] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pages 3452-3462, 2020. 16
[15] Licong Lin and Edgar Dobriban. What causes the test error? going beyond varianae via anova. Journal of Machine Learning Research, 22(155):1-82. 2021.
6
10
16
17
[16] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, 2021.
18
24
[17] Kenji Kawaguchi and Jiaoyang Huang. Gradient descent finds global minima for generalizable deep neural networks of practical sizes. In IEEE Conference on Communication, Control, and Computing, pages 92-99. IEEE, 2019. 2
[18] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019. 2
[19] Difan Zou and Quanquan Gu. An improved analysis of training over over-parameterized deep neural networks. Advances in Neural Information Processing Systems, 32:2055-2000 2019. 2
[20] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pages 8571-8580, 2018.
11

---

[21] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparaneeterized two-layer neural networks. International Conference Machine Learning, pages 322-332, 2019.
[22] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training differentiable pro- gramming. In Advances in Neural Information Processing Systems, pages 2933-2943, 2019.
[23] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2466 PMLR, 2019. 2
[24] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338, 2020.
[25] Zhu Li, Zhi-Hua Zhou, and Arthur Gretton. Towards understanding of benign overfitting in neural networks. arXiv preprint arXiv:2106.03212, 2021.
6 16 20
[26] Jason W Rocks and Pankaj Mehta. Memorizing without overfitting: Bias, variance, and interpolation in over-parameee wer-parameterized models. arXiv preprint arXiv:2010.13933, 2020. 3
[27] Ben Adlam and Jeffrey Pennington. Understanding double descent requires fine-grained variine decomposition. In Advances in Neural Information Processing Systems, 2020.
T6
19
[28] Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features.
arXiv preprint arXiv:2009.07669, 2020. 3 16
[29] Francis Bach and Eric Moulines. Non-strongly-conve smooth stochastic approximation with convergence rate o(1 /n). Advances in Neural Information Processing Systems, 26:773-781, 2013.
31
[30] Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18, 2018.
19
[31] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large 5
step-sizes. Annals of Statistics, 4464):1363-1399, 2016.
8
19 31
[32] Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. Journal of Machine Learning Research, 18(1):3520-
3570, 2017. 3
[33] Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with SGD and random features. In Advances in Neural Information Processing Systems, pages 10212-10223, 2018.
[34] Ilja Kuzborskij, Csaba Szepesvári, Omar Rivasplata, Amal Rannen-Trike and Razvan Pascanu. On the role of optimization in double descent: least squares study. In Advances in Neural Information Processing Systems, 2021. 3
[35] Xi Chen, Qiang Liu, and Xin T Tong. Dimension independent generalization error by stochastic gradient descent. arXiv preprini arXiv:2003. / 2020.
3
[36] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. In Advances in Neurul Information Processing Systems, volume 33, pages 2576-2586, 2020. 19
[37] Aditya Vardhan Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion. Last iterate conver- gence of sgd for least-squares in the interpolation regime. Advances in Neural Information Processing Systems, volume 34, pages 21581-21591, 2021.
3
19
12

---

[38] Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last it- erate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International Conference on Machine Learning, pages 14280-24314 PMLR, 2022. 3 [8
[39] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. In Advances in Neural Information Processing Systems, volume 34, pages 8898-89 8912, 2021.
[40] Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-non norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, pages 2683-2711, 2020.
18
[41] Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint 1705.:1705.03000 2017.
[42] Samuel L.. Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization in stochastic gradient descent. In International Conference on Learning Representations, 2020.
[43] Felipe Cucker and Dingxuan Zhou. Learning theory: an approximation theory viewpoint, volume 24. Cambridge University Press, 2007.
[44] Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. International Conference on Learning Representations, 2020.
[45] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random
features. In Advances in Neural Information Processing Systems, pages 3215-3225, 2017.
[46] Noureddine El Karoui. The spectrum of kernel random matrices. Annals of Statistics, 38(1):1-50
2010. A
[47] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can
generalize. Annals of Statistics, 48(3):1329-1347, 2020. 18
[48] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 2021.
Generalization error of random
48
[49] Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(1):629 681, 2017. I8
[50] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. Annals of Statistics, 4902):1029-104,, 2021. 4
19
[51] Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, pages 342-350, 2009. T8
[52] Yann Lecun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 (6:11)) 2324, 1998. g
[53] Michat Dereziáski, Feynman Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In Advances in Neural Information Processing Systems, volume 33, pages 5152-5164, 2020.
40)
[54] Oussama Dhifallah and Yue Lu. precise performance analysis of learning with random features. arXiv preprint arXiv:2008. / /904, 2020. 16
[55] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007. 17
13

---

[56] Fanghui Liu, Zhenyu Liao, and Johan A.K. Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In International Conference on Artificial Intelligence and Statistics, pages 649-657, 2021. 18
[57]
Konstantin Donhauser, Mingqi Wu, and Fanny Yang. How rotational invariance of common kernels prevents generalization in high dimensions. In International Conference on Machine Learning, pages 2804-2814, PMLR. 2021. 18
[58] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018. [8
[59] Christopher KI Williams. Computation with infinite neural networks. Neural Computation, 1065)1203-1216, 1998. T9
[60] Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks. The Annals of Applied Probability, 28(2):1190-12460 2018. T9
[61] Martin J Wainwright. High- figh-diimessonal statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019. 20
[62] Salomon Bochner. Harmonic Analysis and the Theory of Probability. Courier Corporation, 2005.
20
[63]
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint arXiv:1710.09430, 2017. 22
23 24
[64] Samuel L. Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization in stochastic gradient descent. In International Conference on Learning Representations,
2021. 41
[65] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In International Conference on Artificial Intelligence and Statistics, pages 1204. PMLR, 2019. 41
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We clearly discuss the limitation
of this work in Conclusion.
(c) Did you discuss any potential negative societal impacts your work? [No] Our work is theoretical and generally will have no negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] The assump- tions are clearly stated and well discussed.
(b) Did you include complete proofs of all theoretical results? [Yes] All of the proofs can be found in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "tHRtg3UzA8y", "reviewer": "Reviewer_NMXc", "summary": "This paper studies the generalization properties of random features (RF) regression in high dimensions using SGD and derived non-asymptotic error bounds of RF regression under both constant and polynomial-decay step-size SGD settings. The analysis can be used to theoretically study the double descent phenomenon and does not restricted to Gaussian/spherical data assumption.\nIn addition, the authors also showed that the constant step-size SGD setting incurs no loss in convergence rate when compared to the exact minimal-norm interpolator, as a theoretical justification for using SGD in practice.\n", "questions": "Currently, almost all experiments have been conducted on the simple MNIST dataset or synthetic dataset. What prevents extending experiments to more difficult datasets such as CIFAR-10 or ImageNet?\n", "limitations": "Overall, this is an interesting paper trying to explain the double descent phenomenon theoretically. I feel the numerical validation is a little bit weak, considering it was conducted on MNIST. However, this looks like a standard-setting that has been used in many previous papers. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies a very important phenomenon: the double descent for the over-parameterized model. They provided both theoretical analysis as well as empirical validation to show that the error bounds for variance and bias can be unimodal and monotonically decreasing, respectively, which is able to recover the double descent phenomenon. The presented analysis requires a weaker assumption on data distribution and holds for more general data distribution under the SGD setting. It provides a useful tool to understand the highly over-parameterized deep neural networks in general. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fLc-UP3c0wR", "reviewer": "Reviewer_zi7u", "summary": "This paper derives the excess risk bounds for random feature (RF) model optimized by SGD, with polynomial-decay stepsize (including constant stepsize). Excess risk is decomposed into bias and variance errors, and it is shown that bias error decreases monotonically with the increase of the number of random features, while the variance error demonstrates unimodal behavior.", "questions": "1. The key finding of Zou et al. (2021) is that an effective dimension is established. How is the results of this paper related to the effective dimension?", "limitations": "The limitations are well evaluated by the authors.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Stengths:\n1. The double descent phenomenon is theoretically characterized.\n\nWeaknesses:\n1. The paper lacks discussion apart from the descent phenomenon. For example, how is RF different from the setting of linear regression? How does the input dimension $d$ affect the result ($d$ does not explicitly appear in the main theorems)?\n2. The technique of the paper is quite similar to Zou et al. (2021), except that other sources of randomness are considered. Therefore, the paper is not technically strong.\n3. The main theorems still have terms like $\\mathbb{E}[1-\\gamma_0r'\\mathrm{Tr}(\\Sigma_m)]^2$ and $\\mathbb{E}[1-\\gamma_0r'\\mathrm{Tr}(\\Sigma_m)]^4$ which require further analysis.\n\nReferences\nDifan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "McL2lnQJN7U", "reviewer": "Reviewer_2MfL", "summary": "This paper studies the variance and bias induced by using SGD to fit a linear model on random features from a theoretical point of view. They allow the data distribution to be non-Gaussian, but require bounded 4th moments. The main contributions appear to be some proof techniques for the analysis of SGD.", "questions": "There are other issues with the writing, that hide the potential significance of the work and make the paper difficult to read. For example, many technical lemmas are given before the main result, but it is unclear to the reader at the time why these may be important. The paper does not adequately help the reader digest the results and their significance. What is the significance of these results, and what is the purpose of having them before the main results in the paper?", "limitations": "N/A, the paper is theoretical in nature and does not have any significant direct social impact.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe paper appears to provide some new results on SGD for models linear in the parameters, generalizing recent work [36], although I am not an expert on these proof techniques to critically assess their originality.\n\n## Weaknesses\n\nThe paper is not particularly clear, sweeping a lot of details under the rug in the main paper. This is unfortunate, as the devil is in the details for this topic. For example, while most papers on random feature models study the bias and variance of the model itself, usually assuming that training finds the empirical loss minimizer, this paper focuses on the bias and variance of the SGD procedure itself. For example, they consider the approximation error with respect to the best model _conditional on the RKHS selected by the random features_, as opposed to considering the RKHS that the random features are approximating.\n\nThis makes it more comparable to other papers on SGD, which there are many, but which I am not appropriately qualified to assess the significance of this work in the context of. It's unclear what the significance of random feature model is for the paper. Additionally, while the paper specifically mentions that the results are similar in nature to those in [36], they are able to generalize to the stochastic setting with changing learning rate. To me, this suggests that the main contributions are in the proof techniques. However, these are all deferred to the appendix.\n\nUpdates following author discussion: The writing has improved slightly, but the overall point of the paper still does not come through, and is mostly buried among technical points of unclear significance. I am increasing my rating slightly, if the other reviewers feel strongly about the paper, but overall, think that it is a bit lacking in clarity of writing or significance.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7eEITwARTjy", "reviewer": "Reviewer_XDPQ", "summary": "This work gives a novel analysis of the excess risk of a random features regression which is solved by SGD. The result is relevant in the overparmeterized high dimensional setup. The analysis demonstrates the existence of the double decent phenomena in this setup and is more general than existence theory with regard to the data distribution. The theory is supported by experiments on real data.     ", "questions": "1) In line 120 $\\Sigma_m$ is said to be an operator $\\mathbb{R}^m \\to \\mathbb{R}^m$ but operates on $\\mathcal{H}$ which is maybe isomorphic to $\\mathbb{R}^m$ but it is not mentioned. \n\n\n2) It would be helpful to define ⊗ in the notations section. \n\n3) Even though the work deals with finite dimensional regression is uses a functional terminology. Is that really helpful for the representation of the results? why wouldn't we describe everything in the parameters space, for example, use covariance of features terminology instead of covariance operator. isn't it over-sophistication?   ", "limitations": "There is a quite significant discussion on neural networks in the introduction. However, as the random features method consists only a single trainable layer it is essentially linear and the theoretical result has a small contribution to the understanding of the excess risk in neural networks.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: the work expands the exiting known theory regarding expected test error of an SGD learner by requiring weaker assumption on the data. \nIt also expands the exiting known theory  regarding the expected test error of random feature regression to non closed form solution e.g. SGD optimization.\n\nQuality: the work is technically sound in my views. I did not check the proofs, however. \n\nClarity: the paper is clear and well written.\n\nSignificance: The result helps to understand the relation between the numerical SGD solution and the closed form minimal norm solution of the regression problem and is significant.        \n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept