The Three Stages of Learning Dynamics in High-dimensional Kernel Methods
Authors: Nikhil Ghosh
Song Mei
Bin Yu
Venue: ICLR 2022 Poster (2022)
Keywords: training dynamics
kernels
SGD
deep bootstrap
gradient flow
random features
high-dimensional asymptotics
random matrix theory

Abstract: To understand how deep learning works, it is crucial to understand the training dynamics of neural networks. Several interesting hypotheses about these dynamics have been made based on empirically observed phenomena, but there exists a limited theoretical understanding of when and why such phenomena occur. 

In this paper, we consider the training dynamics of gradient flow on kernel least-squares objectives, which is a limiting dynamics of SGD trained neural networks. Using precise high-dimensional asymptotics, we characterize the dynamics of the fitted model in two “worlds”: in the Oracle World the model is trained on the population distribution and in the Empirical World the model is trained on an i.i.d finite dataset. We show that under mild conditions on the kernel and $L^2$ target regression function the training dynamics have three stages that are based on the behaviors of the models in the two worlds. Our theoretical results also mathematically formalize some interesting deep learning phenomena. Specifically, in our setting we show that SGD progressively learns more complex functions and that there is a "deep bootstrap" phenomenon: during the second stage, the test error of both worlds remain close despite the empirical training error being much smaller. Finally, we give a concrete example comparing the dynamics of two different kernels which shows that faster training is not necessary for better generalization.

Under review as a conference paper at ICLR 2022
THE THREE STAGES OF LEARNING DYNAMICS IN HIGH-DIMENSIONAL KERNEL METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
To understand how deep learning works, it is crucial understand the training dynamics of neural networks. Several interesting hypotheses about these dynam- ics have been made based on empirically observed phenomena, but there exists a limited theoretical understanding of when and why such phenomena occur.
In this paper, we consider the training dynamics of gradient flow on kernel least- squares objectives, which is limiting dynamics of SGD trained neural networks. Using precise high-dimensional asymptotics, we characterize the dynamics of the fitted model in two "worlds"; in the Oracle World the model is trained on the pop- ulation distribution and in the Empirical World the model is trained on a sampled dataset. We show that under mild conditions the kernel and L target regression function the training dynamics undergo three stages characterized by the behav- iors of the models in the two worlds. Our theoretical results also mathematically formalize some interesting deep learning phenomena. Specifically, in our setting we show that SGI) progressively learns a "deep bootstrap" phenomenon: during the second stage, the test error of both worlds remain close despite the empirical training error being much smaller. Fi- nally, we give a concrete example comparing the dynamics of two different kernels which shows that faster training is not necessary for better generalization.
complex functions and that there is
INTRODUCTION
In order to fundamentally understand how and why deep learning works, there has been much effort understand the dynamics of neural networks trained by gradient descent based algorithms. This effort has led to the discovery of many intriguing empirical phenomena (e.g. Frankle et al. (2020); Fort et al. (2020): Nakkiran al. (2019a;b; 2020)) that help shape our conceptual framework for un- derstanding the learning process in neural networks. Nakkiran et al. (2019b) provides evidence that SGD starts by first learning linear classifier and over time learns increasingly complex functions. Nakkiran et al. (2020) introduces the "deep bootstrap" phenomenon: for some deep learning tasks the empirical world test error remains close to the oracle world error for many SGD iterations, even if the empirical training and test errors display large gap. To better understand such phenomena, it useful to study training dynamics related but mathematically tractable settings.
One approach for theoretical investigation is to study kemnel methods, which were recently shown to have a tight connection with over- over--arannn parameterized neural networks (Jacot et al., 2018; Du et al., 2018). Indeed, consider sequence of neural networks (fN (z; ()) NEN with the widths of the layers going to infinity as + cc. Assuming proper parametrization and initialization, for large the SGD dynamics on fN is known to be well approximated by the corresponding dynamics the first-order Taylor expansion of fN around its initialization 0
fN (2;
fx 8º) + (of ) 8º)
Thus, in the large width limit it suffices to study the dynamics on the lincarization fN. When using the squared loss, these dynamics correspond to optimizing kernel least-squares objective with the neural tangent kemne Ky (z. x') = (Vofx (z; 60). (ofx('';
Their paper uses "Ideal World" for "Oracle World" and "Real World" for "Empirical World".

---

Under review as a conference paper at ICLR 2022
Oracle World
R(
Empirical World R(F)
Empirical World Train R,
Error
Approximation Error
Stage
Stage 2
Stage
Time t
Figure 1: conceptual drawing of empirical and oracle world learning curves. Stage 1: all curves are together. Stage 2: training error goes to zero while test and oracle error stay together. Stage 3: test eιror remains constant while oracle error decays to the RKHS approximation error. See Section 1.1 for more detailed discussion. (Dotted lines in stage indicate compressed time interval.)
Over the past few years, researchers have used kernel machines as tractable model investigate many neural network phenomena including benign overfitting, i.c., generalization despite the inter- polation of noisy data (Bartlett et al., 2020; Liang Rakhlin, 2020) and double-descent, i.e, risk curves that not classically U-shaped (Belkin et al., 2020; Liu et al., 2021). Kernels have also been studied to better understand certain aspects of neural network architectures such as invariance and stability (Bietti & Mairal, 2017; Mei et al., 2021b). Although kernel methods cannot be used to explain some phenomena such as feature learning, they can still be conceptually useful for under- standing other neural networks properties.
1.1 THREE STAGES KERNEL DYNAMICS
Despite much classical work in the study of gradient descent training of kernel machines (e.g. Yao al. (2007); Raskutti et (2014)) there has been limited work understanding the high-dimensional setting, which is the setting of interest in this paper. Although solving the linear dynamics of gradient flow is simple, the statistical analysis of the fitted model requires involved random matrix theory arguments. In our analysis the (usually inaccessible) population risk, and the Empirical World, where training is done on the empirical risk (as is done in practice). Associated with the oracle world model for and the empirical world model fo are the following quantities of interest: the empirical training error R., (ft), the empirical test error f(), and the oracle error R(fe") defined in Eqs. (1), (2), (3) for which we derive expressions that accurate in high dimensions.
study the dynamics of the Oracle World, where training is done
Informally, our main results show that under reasonable conditions on the regression function and the kernel the training dynamics undergo the following three stages:
Stage one: the empirical training error, the empirical test error and the oracle error are all close.
Stage two: the empirical training error decays to zero, but the empirical test error and the oracle error stay close and keep approximately constant.
Stage three: the empirical training eтror is still zero, the empirical test error stays approximately constant, but the oracle test error decays to the approximation error.
We conceptually illustrate the error curves of the oracle and empirical world in Fig. 1 and provide intuition for the evolution of the learned models in Fig. 2. The existence of the first and third stages are not unexpected: at the beginning of training the model has not fit the datasct enough to distinguish the oracle and empirical world and at the end of training an expressive enough model with infinite samples will outperform one with finitely many. The most interesting stage is the second one where the empirical model begins to "overfit" the training set while still remaining close to the non-interpolating oracle model in the L sense (see Fig. 2).
In Section we discuss some related work. In Section we elaborate our description of the three stages and give mathematical characterization for two particular settings in Theorems 1 and 2.
2

---

Under review as a conference paper at ICLR 2022
Target fs Oracle Empirical
y
Stage
Stage 2 start
Stage 2 end
Stage 3
Figure 2: conceptual drawing of the evolution of the empirical and oracle models ft and fer In stage 1, fe and ft" learn the best linear approximation of fa. At the start of stage 2, fc and ft" learn the best quadratic approximation. At the end of stage 2, fr interpolates the training set but is close to fe" in the L sense. Lastly in stage 3, ft learns fa while ft stays the same as the end of stage 2.
Although the three stages arise fairly generally, we remark that certain stages will vanish if the problem parameters are chosen in special way (c.f. Remark 1). We connect our theoretical results related empirical deep learning phenomena in Remark 3 and discuss the relation to deep learning in practice in Remark 4. In Section 4 we provide numerical simulations to illustrate the theory more concretely and Section we end with summary and discussion of the results.
2 RELATED LITERATURE
The generalization error of the kernel ridge regression (KRR) solution has been well-studied in both the fixed dimension regime (Wainwright, 2019, Chap. 13), (Caponnetto & De Vito, 2007) and the high-dimensional regime (El Karoui, 2010; Liang & Rakhlin, 2020; Liu et al., 2021; Ghorbani al., 2020; 2021; Mei et al., 2021a;b), Most closely related to results is the setting of (Ghorbani et al., 2021; Mei et al., 202 aab), Analysis the entire KRR training trajectory has also been done (Yao et al., 2007; Raskutti al., 2014; Cao et al., 2019) but only for the fixed dimensional setting. Classical non- con-paramttric rates are often obtained by specifying a strong regularity assumption on the target function (e.g. the source condition in Fischer & Steinwart (2020)), whereas in our work the assumption on the target function is mild.
Another line of work directly studies the dynamics of learning in linear neural networks (Saxe al., 2013; Li et al., 2018; Arora et al., 2019; Vaskevicius et al., 2019). Similar to us, these works show that some notion of complexity (typically effective rank sparsity) increases in the linear network over the course of optimization.
The relationship between the speed of iterative optimization and gap between population and empir- ical quantities has been studied before in the context of algorithmic stability (Bousquet & Elisseeff, 2002: Hardt et al., 2016; Chen al., 2018). These analyses certify good empirical generalization by using stability in the first few iterations to upper bound the gap between train and test error. In contrast, our analysis directly computes the errors an arbitrary time t (c.f. Remark 2). The rela- tionship between oracle and empirical training dynamics has been considered before in Bottou & LeCun (2004) and Pillaud- Vivien al. (2018).
3 RESULTS
In this section we introduce the problem and present a specialization of our results two concrete settings: dot product and group invariant kernels on the sphere (Theorems I and 2 respectively). The more general version of our results is described Appendix A.3.
3.1 PROBLEM SETUP
We consider the supervised learning problem where we are given i.i.d. data (æ;, Wi)nn The covari- ate vectors (æ;)isn cii Unif(gd-1(vG)) and the real-valued noisy responses y = fa(æ:) + for some unknown target function E ( (Vd)) and (Ei)ign Gia N(O,o?). Given a function
3

---

Under review as a conference paper at ICLR 2022
E (P(d)-((V))) define its test error R(f) and its training error (f)
(1) where (Fnow Unew) is i.i.d. with (2t, vilisn- The test error R(f) measures the fit of I on the population distribution and the training error R2 (f) measures the fit of f to the training set.
R(J) = (a Maaww) { (Yneew - [
Rn,(J) = ((=-)(a;))
For kernel function Ha (Vd) (v-) R, analyse the dynamics of the following two fitted models indexed by time the oracle model ftr and the empirieal model fü. which are given by the gradient flow on It and Rn over the associated RKHS Ha respectively
d
dt 1f
(((( x) -2)"
(2)
f((z) = - (i 1 Σ (() - ft(x))) di
d
with zero initialization fo" fo =====
These dynamics are motivated from the neural tangent kernel perspective of perepaarameteizeed neural networks (Jacot et al., 2018; Du et al., 2018). A precise mathematical definition and derivation of these two dynamics are provided in Appendix E.
For our results make some assumptions the spectral properties of the kernels Ha similar to those in Mei et al. (2021a) that are discussed in detail Section A.2. At a high-level we require that the diagonal elements of the kernel concentrate, that the kernel eigenvalues obey certain spectral gap conditions, and that the top eigenfunctions obey hyperconctracctviity condition which says they are "delocalized". For the specific settings of Theorems and 2 we give more specific conditions on the kernels that are more easily verified and imply the required spectral properties.
3.2
DOT PRODUCT KERNELS
In our first example, we consider dot product kernels Ha of the form
(4) for some function has [-1,1] + IR. Our results apply to general dot product kernels under weak conditions on ha given in Appendix C.2. In particular they apply to the random feature and neural tangent kernels associated to certain fully connected neural networks (Jacot al., 2018).
Ha(mi x22) = ( wd) Vo,, D2 E (Vd),
Before presenting our results for this setting we introduce some notation. Denote by Pire the orthog- onal projection onto the subspace of L (V())))(V spanned by polynomials of degree less than or equal to f. The projectors P. and P> are defined analogously (see Appendix G for details). We use oa(-) for standard little-o relations, where the subscript d emphasizes the asymptotic variable. The statement fdd) = wa(g va(g(d) (d)) is equivalent to g(d) = (d)f.)).. We use (-,z(-) in probability relations. Namely for two sequences of random variables Zı (d) and Zz(d). (d) oa, (Z,r(Zz(d) if
for any e, Ce > 0 there exists de E Zoo. such that [P (d) (d) < C.) S 8 for all d 2 de- The asymptotic notations Oa, OI,= etc. are defined analogously.
Theorem (Dot Product Kernels). Let {fa E (2( H2) be a sequence of functions such that for some > O, Ilfally=- = Oa(1), and let {Halaz1 be a sequence of dot product kernels satisfying Assumption Assume that for some fixed integers s, 2 and some 8 > 0 that
ditó <ts @+11-6
g=to <n +11-
Then have the following characterizations,
(a) (Oracle World) The oracle model learns every degree component of fa as time progresses
R(S |P>sfalliz of + oa(1),
||se -Psjfalli: oa(1).
(b) (Empirical World - Train) Empirical training error follows oracle error then goes to zero R.,( = - + o² + 01.(()
it/n = oa(1),
R.,(f.) (1)
it/n wa(())
4

---

Under review as a conference paper at ICLR 2022
1.0
16
Grade
1.0
Cracie
1.0
Cradle
0.8
Eng. Train
Emp. lest
Emp. Train
Lmp. lest
0.8
IP-O44
Cyclic Test
Dot Prod. Train
0.6
U.b
iP
Error
Cyclic Train
0.4
PP.
6.4
IP.Ad
0.4
IP-2t4"
0.2
0.0
0.0
2
4
2
d
log og
log hggt/logd
(a) Dot prod. kernel, n x 2
(b) Dot prod. kernel, n. x 2.99 (c) Dot prod. vs cyclic, nt x d
Figure 3: Schematic drawings of the conclusions of Theorems 1 and 2 for three different noiseless settings. Panels (3a) and (3b) illustrate the performance of dot product kernel Ha for two different scalings r((d). The full three stages appear in (3a), but the second stages disappears in (3b) since log n/ log d is nearly an integer (see Remark 1). Panel (3c) compares the performance of dot product kernel Ha (red) and corresponding cyclic kernel Ha,iuv (green) for a cyclic target function fa. The cyclic kernel in (3c) generalizes better but optimizes more slowly (see Remark 2).
(c) (Empirical World- Test) Empirical test error oracle error until the empirical model learns the degree-s component of fa
R(f+) = || (j) + o 0ap(1),
PP
= Oa,((1).
The results are conceptually illustrated in an example in Fig. 3a which shows the stair-case phe- nomenon in high-dimensions and the three learning stages. We see that in both the oracle world and the empirical world, the prediction model increases in complexity over time. More precisely, the model learns the best polynomial degree. In the empirical world the maximum complexity is determined by the sample size which contrast to the oracle world where there are effectively infinite samples.
to the target function (in an L sense) of increasingly higher
The results imply that generally (but not always c.f. Remark 1) there will be three stages of learning. In the first stage the oracle and empirical world models are close in L and fit a polynomial with degree determined by The first stage lasts from & 0 to nd < for some small >> O. As approaches n, there is a phase transition and the empirical world training error goes to zero at t = nd >> From time nd= till at least d=+1 is the second stage where the empirical and oracle models remain close in L but the gap between test and train error can be large. the sample size is not large enough for fo to learn the target function, then at some large enough t we will enter third stage where fe improves in performance, outperforming ft which remains the same. On synthetic data in finite dimensions we can see resemblance of the staircase shape which becomes sharper with increasing d (c.f. Appendix F).
Remark (Degenerate stages of Learning). For special problem parameters will not observe the second and/or third stages. The second stage will disappear if n. d9 for some q E N (see Fig. 3b), or if fa degree-s polynomial. The third stage will not occur if pafa lies in the orthogonal complement of the RKHS Ha-
3.3 GROUP INVARIANT KERNELS
We now consider our second setting which concerns the invariant function estimation problem introduced in Mei et al. (2021b). As before, ture vectors (æz)isn aiid Unif(gr-+((dd) and noisy responses y, fa(x,) + Et. We now assume that the target function fa satisfies an invariant property. We consider a general type of invariance, defined by a group Ga that is represented as subgroup of the orthogonal group in d dimensions. The group element E Ga acts on vector
given i.idd. data (æ,, Be)in where the fea-
gd via
g æ. (x) = fa(g - x) for all g E Ga- We denote the space of square integrable Ga-invariant functions by L"(Sd-1 (Vd). We focus on groups Ga that groups of degeneracy a as defined below. As example, we consider the cyclic group
We say that f. is Gr-invariant
5

---

Under review as a conference paper at ICLR 2022
Cycλ {go. 91....:9d-11 where for any (#1..... RT)T (Vd",(Vd), the group action is defined by 9: x = (#441, Fet2...., Idd 21, (2,...,;;)) The cyclic group has degeneracy 1.
Definition (Groups of degeneracy a). Let Va, the subspace of degree-k polynomials that are orthogonal to polynomials of degree at most (k: 11-1 11 in (2())-I(V))) and denote by (ax( the subspace of Va, formed by polynomials that are Ga-invariant. We say that Go has degeneracy if for any integer & 2 a we have VVax/Va,a such that c I dim(Va. (V..))/ S Ck for any 2).
x d (ie., there exists 0 < S Ck < to0
To encode invariance in our kernel consider Ga- Ga-invariant kernels Ha of the form
in (aiin ( (:2) = / h((21.9 g x2)) /2)/d))a(dg))
(5)
where Fæ is the Haar measuare on Ga. Such kernels satisfy the following invariance property: for all g.g' E 9a and for Ha( 222) = Ha(g 21,g'- 22) for every æ1 22. For the cyclic group, aa is the uniform measure. We now present our results for the group invariant setting.
Theorem 2 (Group Invariant Kernels). Let Ga be group of degeneracy a S according to Def- inition 1. Let {fa E L (3d (Vd), Ga) sequence of Ga-invariant functions such that for some rj > 0, [ = O1(1), and let (Hald21 be a sequence of Ga-invariant kernels satisfying Assumption 5. Assume that for some fixed integers 2 0, and some 5 >>> 0 that
d S st
p-atô S a+1-a-6.
Then we have the following characterizations,
(a) (Oracle World) The oracle model learns every degree component of fa as time progresses
R(F = |PPsffal + +o + oa(1), || PPiifall = oa(1).
(b) (Empirical World - Train) Empirical training error follows oracle error then goes to zero
Rn (f:) ||P>jaallix + =² 01,
ift/n = oa(ld)) ift/n (d')
RR (ff:) (1)
(c) (Empirical World Test) Empirical test error follows oracle error until the empirical model learns the degree-s component of fa
R(f.)) = || [dlli of +I)(1),
|| [ P [mm 0d.p(1).
With respect to the dot product kernel setting (c.f. Theorem 1), in this setting the behavior of the oracle world is unchanged, but the empirical world behaves as if it has d times as many samples. This is illustrated graphically in Fig. 3c. It can be shown that using an invariant kernel is equivalent to using dot product kernel and augmenting the dataset to {(g æ; ys) E Ga, E [m)] (c.f. Ap- pendix E.2). Hence for the cyclic group which has size d = d, we arrive at the following intriguing conclusion: if the target function is invariant, then using dot product kernel and augmenting i.i.d samples to nı many samples is asymptotically equivalent to using nd i..dd samples.
Remark (Optimization Speed versus Generalization). Interestingly, training with an invariant kernel is slower than with a dot product kernel and takes longer to interpolate the dataset despite eventually generalizing better on invariant function estimation tasks (c.f. Fig. 3c). This conclusion is not an artifact of the continuous time analysis (c.f. Appendix E.3) and is observed empirically in Section 4.2 for discrete-time SGD. This example highlights the limitation of stability based analyses (e.g. Hardt al. (2016)) which argue that faster SGD training leads to better generalization. While a faster rate leads to betler generalization in the first stage when stability can control the gap be- tween train and lest error, our analysis shows that the duration length of the first stage also impacts the final generalization error.
Remark (Connection with Deep Phenomena). The dynamics of high- dimensiimesi kernel regres- sion display behaviors that parallel some empirically observed phenomena in deep learning. For

---

Under review as a conference paper at ICLR 2022
kernel regression, we have shown that the complexity of the empirical model, measured as the num- ber of learned eigenfunctions, depends on the time optimized when' & n. and the sample size when t > n. At high-level. also expect a similar story for neural networks but for some other notion of complexity. is believed that neural networks first learn simple functions and then progressively more complex ones, until the complexity saturates after interpolating some time proportional (Nakkiran et al., 2019b). We have also shown that in kernel regression there is a non-trivial "deep boostrap" " phenomenon (Nakkiran et al., 2020) during the second learning stage: the gap between the oracle world and empirical world test errors is negligible whereas the train and test errors ex- hibit a substantial gap. The gradient flow results for kernel regression can also provide insight into the deep bootstrap for random feuture networks SGD as these results can approximately predict their behavior (see Section 4.2).
Remark 4 (Connection with Deep Learning Practice). Although we believe our results conceptually shed light on some of the interesting behaviors observed in the training dynamics of deep learning, due to our stylized setting we may not exactly see the predicted phenomena in practice. Accurately observing the three stages of kernel regression requires sufficiently high-dimensional data in order for the kernel eigenvalues to obey a staircase-like decay and for training to be sufficiently long as the time axis should be in tog-scale. Our results hold for regression whereas for classification the empirical model may continue improving after classifying the train set correctly. Despite these caveats, certain conclusions can be observed in some realistic settings (c.f. Appendix E.4).
4 NUMERICAL SIMULATIONS
As mentioned previously, Fig. 3 is "cartoon" of the conclusions stated in Theorems 1 and 2. In this section, we verify the qualitative predictions of our theorems using synthetic data. Concretely, throughout this section we take d = 400 and n d3. 8000, and following our theoretical setup (c.f. Section 3.1) generate covariates (æz)ign Midd (ni with (si)isn riid oO), for different choices of target function fx. All simulations in this section are for the noiseless case of but a noisy example is given in Appendix F.
and responses y4- = fx:)) +
In Section 4,1, we simulate the gradient flows of kernel least-squares with dot product kernels and cyclic kernels (Fig. 4) to reproduce the three stages as shown in Fig. 3. In Section 4.2 we show that SGD of (dot product and cyclic) rundom-feature models (Fig. 5) exhibit similar three stages phenomena, in which the second stage behaviors are consistent with the deep bootstrap phenomena observed in deep learning experiments (Nakkiran et al., 2020). Empirical quantities are averaged over 10 trials and the shaded regions indicate one standard deviation from the mean.
4.1 GRADIENT FLOW OF KERNEL LEAST-SQUARES
Under the synthetic data set-up mentioned earlier, we first simulate the oracle world and empirical world errors curves of gradient flow dynamics using dot product kernels of the form
H ( (z) = E E (o (ww 20))) ar2))]
(6)
for some activation function σ. We will examine a few different choices of f. and kernel H, which are specified in the descriptions of each figure.
The oracle world error is computed analytically but the empirical world errors require sampling train and test datasets. We compute empirical world errors by averaging over 10 trials. The results are visualized both in log-scale and linear-scale on the time axis. The log-scale plots allow for direct comparison with the cartoons in Fig. 3. The linear-scale plots are zoomed into the region < S nd since: 1) plotting the full interval squeeze all curves to the left boundary which is uninformative 2) in practice one would not optimize for very long after interpolation.
In Figs. 4a and 4b we take the target function to be a polynomial of the form
fz) au Hea (21) +... + ag (x1(, ||P = az51,
where (t, is the ith Hermite polynomial (c.f. Appendix G.4) and the approximate equality in Eq. (7) holds in high-dimensions. In panel (4a) we consider use the ReLU activation function (t) = max(t, 0), and take fa to be quadratic polynomial with (ag, 01, 02) (1/2, 1/22, 1/ 1/V8). With
7

---

Under review as a conference paper at ICLR 2022
1.0
1.0
IGP
10
0.8
G8
0.8
|Po/dl
0.6
Deatle
Imo Bed
Error
C.6
Emp 3rd
Cruc a
Errer
Emo. Tran
Eir.. Tainn
P
|P.
lng Bagtyloga
Iog Pgt//ng
Ing rylogdd
(a)
(b)
(c)
1.0
1.0
Seacle
1.0
Gracle syc
0.0
Emp. lest
finp.
0.8
Emo. Thiin
Emo Test
0.8
12t
0.6
0.2
0.0
0.0
0.0
Figure 4: Top row: Log-scale plot of errors versus training time for dot product kernel (4a, 4b) and fdot product, eyclic) kernels in (4c). In (4a) ReLU and (au, a1 02) (1/2, 1/v2, 1/V8). In (4b), ReLU +0.1 Hez and (ag, d1, a2, ag) (1/2, 1/ 22, 0, 2/). In (4c). is Eq. (8) and ReLU +0.1 1 Heg. Bottom row: Same as the top row but with linear-scale time and zoomed in.
the three stages phenomenon. In panel (4b) choose f- to be cubic polynomial with (ao, 01, 42 a3) (1/2, 1/ /21 0,1///2 and ott) max(t, 0) + 0.1 (t) (we need the third Hermite coefficient of a to be non-zero for stage to occur). This choice of coefficients for f. is such that | ff> ~ |P>ff 12,2, so that the second stage in (4b) longer compared to (4a).
such a choice of parameters,
In Fig. 4c, we take the target function to be a cubic cyclic polynomial
d
d
d Σ x. 24 1=1
fx(2) = 3 Σ 24
2,0++1 Σ
(8)
i=1
where the subindex addition in Ti+-k is understood be taken modulo d. We compare the per- formance of the dot product kernel H and its invariant version Hime (c.f. Eq. (5)) with activation function att) = max(t, 0) + 0.1 (ty( The kernel Hmy with samples performs equivalently to H with nd samples (c.f. Remark 2), but is more computationally efficient since the size of the kernel matrix is still n n. Using Hin elongates the first stage by factor d, delaying the later stages and ensuring that the empirical world model improves longer.
Although in the simulations, the dimension is not yet high enough to see a totally sharp staircase phenomenon in the illustrations of Fig. 3, even for this d we are still able to clearly see the three predicted learning stages and deep bootstrap phenomenon across range of settings. To better understand the effect of dimension show similar plots with varying d in Appendix F.
4.2 SGD FOR TWO-LAYER WANDOM-FEATURE MODELS
To more closely relate with deep learning practice and the deep bootstrap phenomenon (Nakkiran et al., 2020), we simulate the eπrо curves of SGD training random-fcature (RF) models (i.e. two- layer networks with random first-layer weights and trainable second-layer weights), in the same synthetic data setup as before. In particular, look at dot product RF models
faot a)
wi Midd Unif(Sd-1),
and cyclic invariant RF models
N
az) =
1
Σ as
a(wwi, x)))g)
wi <id Undf(Sd-1).
VN
G4
8

---

Under review as a conference paper at ICLR 2022
0.8
Oracl
Emo. Tct
0.8
Orade
Test Train
Dx hool Tea
hoo Toa
Cycl::
Cyck: Thar
Emo. Tran
E200
0.6
0.6
Emor
0.0
0.4
0.2
0.0
0.0
0.0
500
1000
1500
2000
2500
500
1030
1500
2000
2500
0
200
400
000
000
Step
Step
Step
(a)
(b)
(c)
1.0
1.0
Seacle
1.0
Cracke
Grale
0.0
Emp. lest
finp. Tran
0.8
Emo lest
Emo. Thiin
12t
sycl
0.6
0.6
0.4
0.2
0.2
0.2
0.0
0.0
0.0
6'
d""
Figure 5: Top Row: SGD dynamics of random-feature models deseribed in Section 4.2. The tar- get function and data distribution of (5a), (5b), (5c) are that of (4a), (4b), (4c) respectively. Bottom Row: The corresponding linear-scale errors of kernel least-squares gradient flow for comparison.
For all following experiments we take the activation a to be ReLU and N = x 105 x n 1.44
For given data distribution and RF model we train two fitted functions, one finite dataset (empirical world) and the other on the data distribution (oracle world). More specifically, the training of the empirical model is done using multi-pass SGD
finite training of size with learning rate v = 0.1 and batch size b- = 50. The training of the oracle model is done using one-pass SGD with the same learning rate 17 and batch size but at each iteration a fresh batch sampled from the population distribution. Both models ft, for are initialized with a; for i [N]. To speed up and stabilize optimization we use momentum 3 0.9. Note that if we took N - 1J - 0, and = we would be exactly the dot product kernel gradient flow setting.
In Fig. 5, the data generating distributions of panels (5a), (5b), (5c) are respectively the same as that of panels (4a), (4b), and (4c) from Section 4.1. The top row of Fig. 5 shows SGD for (dot product, cyclic} RF models, and the bottom row shows the corresponding gradient flow for {dot product, eyclic} kernel least-squares. We see that the corresponding curves in these two rows exhibit qualitatively the same behaviors. Additionally, the results in panel (5c) show that predicted, even for discrete SGD dynamics the dot product RF optimizes faster but fails to generalize, whereas the invariant RF optimizes slower but generalizes better.
5 SUMMARY AND DISCUSSION
In this paper, we used precise asymptotics to study the oracle world and empirical world dynamics of gradient flow on kernel least-squares objectives for high-dimensional regression problems. Under reasonable conditions on the target function and kernel, we showed that in this setting there are three learning stages based on the behaviors of the empirical and oracle models and also connected our results to some empirical deep learning phenomena.
Although our setting already captures some interesting aspects of deep learning training dynamics, there are some limitations which would be interesting to resolve in future work. We require very high-dimensional data in order for the asymptotics to be accurate, but real data distributions have low-dimensional structure. We work in limiting regime of neural network training where the is an important direction to extend this
dynamics are linear and the step-size is infinitesimal. analysis to the non-linear feature learning regime and to consider discrete step-size minibatch SGD, as these are considered important aspects of network training. Our results hold for the square-loss in regression problems, but many deep learning problems involve classification using cross-entropy loss. Lastly, our analysis holds specifically for gradient flow, so it would be also interesting to consider other iterative learning algorithms such boosting.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32:7413-7424, 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30003330077 2020.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM
Journal on Mathematics of Data Science, 1(4):1167-1180 2020.
Alberto Bietti and Julien Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. arXiv preprint arXiv:1706.03078, 2017. 2017.
Léon Bottou and Yann LeCun. Large scale online learning. Advances in neural information pro- cessing systems, 16:217-224, 2004.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 1912.01 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 1804vv180..061/1 2018
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054 2018.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38(1): 1-50, 2010.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algo- rithms. J. Mach. Learn. Res., 21:205 2020.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study loss landscape geometry and the time evolution of the neural tangent kernel. arXiv preprint arXiv:2010.15110, 2020.
Jonathan Frankle, David Schwab, and Ari S Morcos. The early phase of neural network training. arXiv preprint arXiv:2002. 20.220022.3333. /0365, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When neural networks outperform kernel methods? arXiv preprint arXhv:2006.13409 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz. and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054, 2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. arXiv preprint 1rxiv: 07552, 2018
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47. PMLR, 2018
Zhiyuan Li. Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint arXiv: 1a0e:/911.000000 2019.
10

---

Under review as a conference paper at ICLR 2022
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can gener- alize. The Annals of Statistics, (8(3):1329-1341) 2020.
Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined anal- ysis beyond double descent. In International Conference Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2021.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random fea- tures and kernel methods: hypercontractivity and kernel matrix concentration. arXiv preprint 100.:2200..1088, 2021a.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint arXiv:2 2021b.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.02299 2019a.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems, 32:3496-3500 2019b.
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint arXiv:2010.08/22) 2020.
Loucas Pillaud-Vivies Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradi- descent on hard learning problems through multiple passes. arXiv preprint arXiv:1805. 10074, 2018.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1); 335-366, 2014.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32:2972-295 2983, 2019.
Martin Wainwright. High-dimensional statistics: non-asymplotic viewpoint, volume 48. Cam-
bridge University Press, 2019.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn-
ing. Constructive Approximation, 26(2):289-315, 2007.

---

Under review as a conference paper at ICLR 2022
A GENERAL SETTING
In this section we present our theory for training dynamics of kernel regression in an abstract setting similar to that of Mei et al. (2021a). We first introduce the setting of interest, then state the relevant assumptions, and finally we provide our theoretical results. We provide proofs these results in Appendix B.
A.1 PROBLEM SETUP
Consider a sequence of Polish probability spaces (Ra, Va), where 2/ is probability measure on the configuration space Xd, indexed by integer d. We denote by [22( I,² (2a, va) the space of square integrable functions
(Ka, va). For p 2 1, we denote |I (+(aa) = E [z="")) the L' norm of f. Let Da S L (Xaa be a closed linear subspace. In some simple applications we will consider Da I (Xa), but the extra generality will be useful in certain applications.
We are concerned with a supervised learning problem where we are given i.i data (yi, x;)isn. The feature vectors at; rvsi Va are in Xa and the empirical-valued noisy responses yi are given by
= fa( + 8
for some unknown target function fa E Da and e miid o(),
We consider a general RKHS defined on (Aa, 122 via the compact self-adjoint positive definite operator HHI, Da - Da which admits the representation
Hag(æ) = / Ha(æ, x' x2)g(""))v
Xa
where Ha L2 x Ka) with the property that Sx, Ha(æ, x' la)))(g (eel))) (add))uld''' for g Dj.
By the spectral theorem of compact operators, there exists an orthonormal basis (w))221, span(e,, 2 1) Dd (Xa) and empirical eigenvalues (Na,))521 with nonincreasing ab- solute values |a,il 2 |2,22 2 and Σÿ²1 Pa.s 00 such that
Ha( x22 (Z))))))))
where convergence holds in (xa, x Xx).
For C f1. we denote Pss to be the projection operator from (2(a)) onto Da.s span(1);,) E S). We denote Ha, to be the operator
Hla.s = K2
j=1
and H,ss the corresponding kernel.
If [j N j E we will write short-hand Ha and analogously for S Ej
The trace of this operator is given by
Tr(Hla,s)
>aa Rezee (Ha,s( oc.
Define the test error L (Xa) RP and training error R, (x2(X))) +R
R(f) E (new MMeww (Unow (x
(,,(f) = >>>0 (2: - f(xx))² 3=1
(9)
where (æ1, w/).................... (æn, vn)s (Fuew: Inew) are iid. For a kernel H3 L2 we will consider the oracle model for and the empirical model ft which satisfy the following gradient flows
d
dt Jt (x) -V (z)) = Ez,r, Ha(x 2) - (x)),,
(10)
dt f((z)= - = n
Σ
Ha(x, x, x2) f((xi))
(11)
1=1
12

---

Under review as a conference paper at ICLR 2022
A.2 GENERAL ASSUMPTIONS
We now state our assumptions on the kernel and the sequence of probability spaces (Ka, va). Assumption (fn(d), m(d)) Concentration Property), We say that the sequence of op- erators (22 satisfies the Kernel Concentration Property (KCP) with respect to the sequence (n(d), m22 if there exists a sequence of integers {r(d))a2) with r(d) 2 m(d), such that the following conditions hold.
(a) (Hypercontractivity of finite eigenspaces.) For any fixed q 2 1, there exists a constant C such that for any h (a.sr(d) span(ps: r(d)), have
|| S C/
(b) (Properly decaying eigenvalues) There exists fixed 80 0, such that, for all large enough,
n(d)2+ó0 < )=r(d)+ )2,,)
j=r(d)+1 Ad.j
m(d)2+60 )= 22,5)
jj=(d)++1 Xa.j
(c) (Concentration of diagonal elements of kernel) For (2r (x)))e(n(d)) mid Va, we have:
|Eawe, [H sm(d)) (x;; .z)²] Bm -u, HH,
(ar, x )²) odr((1) En (H 2. (2,, )²)²
max (E(m(d)
max (E(n(d)
Hd.)m(d) (I); axi) - Ex H Ha (a, æ)] os.((1) Ex sm(d)) (x, x)).
Assumption ((a) can be interpreted as requiring that the top eigenfunctions of Hg are delocalized. Assumption 1(b) concerns the tail of cigenvalues of HH and is a mild assumption in high- ditdemiiensos.. Lastly, 1(c) essentially requires that "most points" in Xa behave similarly the sense of having similar values of the kernel diagonal Ha(æ, x)).
Assumption 2 (Figenvalue condition at level ((n(d), m(d)) We say that the sequence of kernel operators ( satisfies the Eigenvalue Condition at level ((n(d), m(d)))a2 the fol- lowing conditions hold for all large enough
(a) There exists a fixed 8n such that
20
n(d)== < X4
Adk
(12)
d.m(dd) k=m(d)+1
mdd)1-60
X2 d. k=m(d)+1
d.k
(13)
(b) There exists a fixed 8, such that
n(d) 1-60
X2,0.
2 d. k=m(d)+1
(c) There exists a fixed 8, > 0, such that
m(d) S ndd)2_bu
Assumptions 2(a) and 2(b) can be tion between the eigenvalues in the subspace Da,5((a) and the subspace Da, The technical requirement 2(c) is mild.
spectral gap assumption. This ensures clear separa-
In the asymptotic setting, we will be interested in understanding the model learned at a time t = t(d) which scales with the dimension. The next set of assumptions give requirements for valid scaling.
13

---

Under review as a conference paper at ICLR 2022
Assumption (Admissible Time at (t(d), u(d), m(d)) We say that the sequence (t(d), u(d), r((d), (22) is an Admissible Time for the sequence of kernel operators {Ha)a21 if the following conditions hold
(a) There exists a fixed 6n > O, such that for d large enough
1
S t(d) ((d) < t(d))+ 1+60
X3 x
(b) uf(d) m(d) for infinitely many d, then
t(d)
22 - os(l).
n(d)
kmmid)+1
(c) There exists constant C. such that
m(d)
k=m(d) +1
Assumption 3(a) is similar to the spectral gap condition Assumption 2(a), 2(b) for (t(d), u(d))az1. Assumption 3(b) relates the ordering of the indices u(d), m(d) the relative growth of t(d), n()..
Assumption 3(c) requires that the cigenvalue tail does not decay too abruptly.
A.3 MAIN RESULTS
In this section we give the main theoretical results. Recall the problem set-up and notation from Appendix A.I. We will characterize the gradient flow dynamics dynamics of the oracle model f Eq. (10) and the empirical model fa Eq. (11) for a general kernel Ha-
Theorem 3 (Oracle World). Let {Sa E Daja21 be sequence of functions and {Ha) d21 be sequence of kernel operators such that {(Hla, t(d), u(d))aa21 satisfies Assumption 3(a), then
R(f(*) = PP fall of + oa(1) Ilfall
||58 S (1) Ilfalle
where P Psu(d) and put(d) are the projection operators onto the subspace spanned by the top u(d) kernel eigenfunctions and the orthogonal complement respectively, as defined in Appendix A.I.
The error of the oracle model is determined solely by optimization time t through u(d). Due to the spectral gap assumption ((a) learning only occurs along the top u(d) eigenfunctions.
The next results describe the empirical model. First we characterize the training error.
Theorem (Empirical World Train). Let {fa E Dalaz1 be a sequence of functions, (#;)se(n(a)) Pa independently, and {Ha]a21 be sequence of kernel operators such that ([Ha, n(d), m(d), t(d), u(d)))a21 satisfies {(n(d), m(d)) -PPPP (Assumption 1), eigenvalue condition level (n(d), m(d))aaz1 (Assumption 2), and {(n(d), m(d), t(d), a(d) valid time (Assumption 3). Define KH Tr(Ha,>m()) and t(d) min(u(d), m(d).. Then for any > O we have,
R.,(f)) = ||Ps + + + oar(1) (Ifall + +o?), (,,( = 01,((1) (llfalli + oz),
ift = oa(n/kn), if wa(n/nn)
In the carly-time regime < n n/KE the training error may be non-zero and matches the oracle world error if also u(d) S m(d). In the late-time regime > n/Kн the training is negligible and the model interpolates the training set. The quantity ки arises since the empirical kernel matrix can be decomposed H H <m H and the second component is approximately multiple of the identity: Hzm ~ Tr(H I, Kи I, This term acts as a self-induced ridge-regularizer.
Our final result characterizes the test error of the empirical model.
14

---

Under review as a conference paper at ICLR 2022
Theorem 5 (Empirical World Test), Let {fa E Daldz1 be sequence of functions, (Z))ie(n(d)) ~ Va independently, and {Halaz1 be a sequence of kernel operators such that ((H,, m(d), Md), a(d) satisfies {(n(d), m2d)) (Assumption 1), eigenvalue condition at level {(n(d), m(d)))d2 (Assumption 2), and {(((d), m(d), t(d), u(d)))a21 is valid time (Assumption 3). Define ((d) = min(u(d), m(d)). Then any > we have,
R(f.) ((P=e())falliz of + oar((1) (Ilfall2a-n + o2), | Psacaa L 01, (llfallie-> + +o2)
The result shows that the empirical model is essentially the projection of the regression function onto the first {(d) eigenfunctions. The quantity f(d) controls the complexity of the model which increases with time up until u(d) 2 m(d) after which the complexity is limited by n.
15

---

Under review as a conference paper at ICLR 2022
B PROOF OF GENERAL SETTING
B. ORACLE WORLD PROOF OF THEOREM 3
The oracle model ODE Eq. (10) with initialization fo = can be solved (c.f. Appendix E.1) to yield the solution
ft fa - e-
1Ba fa.
Therefore the excess risk is given by
R(f(') = Exwns (f
fa(a)e- 21E fa( fa(æ)vu(dz)) = Σ Exxp(-2tX2.)
N2
k=0
where 22 are the kernel cigenvalues and fa = (fa. sha) are the Fourier coefficients of fa in the kernel eigenbasis (c.f. Appendix A.I). We can control this quantity as follows,
[R(F2) o² - IPPrufall fall [Ifall & max
max exp(eepppp exp((22X2.)) max 1 - exp( k
k2u+1
max 0(L221)) } k2u+1
< max
max exp (xp((e((((AA))))) kSu
< max
(exp( (((((( 0 (() oa(1)
where the last inequality follows from Assumption 3(a). This shows the first theorem statement,
|1 - P falffl = oa()) -
Now observe that
Psula 100 Σ
Σ
k2u+1
hence
[1 Psulfalli
[|fall2 <
max
(rxxexp(-225 exp(-21X2,))
max (1 -22..
ksu
k2u+1
max 1 - exxp-22/15 } oa(1) k2u+1
max
max maxexp( (P2p-2222,,)
kŠu
where the second inequality follows from the fact that (1- < 11 e- and the final equality is from the proof of the first part of the theorem. Thus,
ll
Psufalli = oa(1): -lfal)-
completing the proof.
B.2
EMPIRICAL WORLD PRELIMINARIES
We will introduce some useful notations and the objects of analysis for studying the empirical world.
B.2.1 TRAINING DYNAMICS
For the training of the empirical world c.f. Eq. (11), if u())
E RR. then from
Eq. (44) if (0)) = 0 then
u(t) y Hij (In -1H/")p
(14)
where H Ruxa with the (i,j)th element given by Hij Ha( æ5) and y + R with (fa(x))...... fa(m,)))...,,(..) TT(
E R. and e (,1,..., En) E RR.
16

---

Under review as a conference paper at ICLR 2022
For RR, define h(x) (Ha(æ1, x). ..... Ha)= RR.. The training and test errors as defined in Eq. (1) can written as
1 y 2HH/"g R2 (f:)) = - [l(((t) 2lا 71
n
R(fi) 1Ex0 (fa(x) =ut) T H h())))
Expanding R(f() yields
R(fi) = Bn Bm[[a(x)²)) - -u(()) H E H H H
(15)
where E (E)) E R", M (Mij)i.elnl Rax", and H (HH1)))eEfm) g2xx with
E2 = Em (a(, Mj ES, (Ha az (a(
Hij = Ha(w;, 2)).
B.2.2 DECOMPOSITIONS AND NOTATIONS
In this section recall some useful decompositions of empirical quantities from Mei et al. (2021a). As mentioned earlier the eigendecompositiin of Ha is given by
Ha(æ, y) Σ (
We write the orthogonal decomposition of fa in the basis { he21
Sa(x) Σ Saxv)(x))
k=1
Define
Φ (va(x1),.... v)(22))) E R"
D&m diag(Ad,1, Ad2,,.... Ad, E Rm
V <m (vi(x,) (v)( E R=
fsm (fa.1, fa................. fa.)) R.
We have the following orthogonal basis decompositions of f. H, and M
f = fsm + fom:
fsm v Sm smm
f>m
Σ fareher
kmm+1
H Hm + H Hom:
H &m
H >m
X2 1b
Zm
mm
k=m-1
(16)
Egg Eyms
sm Esm
D2
5m Sms
Exm
k=m+1
M = Mgm + Mym:
M = V sm D V
M
Σ
Sm
Sm
k=m-1
By Lemma 6 below, under Assumptions 1 and 2(a) the matrices H and M can be written
v <m
D m
Sm KH (I, + AH),
(17)
M T <m
(I + A AM).
(18)
Em
17

---

Under review as a conference paper at ICLR 2022
where
Ry Tr(Hd,
Σ
d,ks
& 12m+1
RM (r(
k2m+1
and
max A Hrll llop | (I,
We will use shorthand for the scalar valued dimension dependent quantity e ((/1n)) and take
K Kmm I, ae (t/n) D
(19)
We also introduce the shrinkage matrix defined as
Sem
Il
KH
diag(($;) E mm where 8j
X
(20)
Sm
d.j +
If unspecified we will typically use A, A' etc. to denote matrices with operator norm (1,((1). For positive integers L m. define [e, m] = {e + 1, l....,m, m}. We will use the following notation
Sem = diag((s)))steem
for 8y defined in Eq. (20)
V fm
(tbx (())(()))) E (ax(m-))
fim Σ SanarR
kE[C.m]
B.2.3 AUXILIARY LEMMAS
Here we collect some lemmas which will be of use to us.
Lemma (Matrix Exponential Perturbation Inequality). For matrix operator norm AI Rax= are symmetric then
||e
B| < A - B max |1A11111BB111
For general square matrices
A, B E R we have
|e B S A
B [
Lemma 2. Let E RUXD W E Rmxp D B T VE RPXP, Then,
E x and E R. Denote = ZT E Raxp and
Z T DD IDB
The notations in Lemmas 3-8 all follow the notations given in Section B.2.2. Lemma (Lemma 12 from Mei et al. (2021a) with 0). Let Assumptions and hold. Then,
nn MH- Vm S2 v /m//llop oa,((1).
5m
Lemma (Theorem 6(b) from Mei et (2021a)). Let Assumptions ((a), 2(c) hold. Then, V sm/nn Im llop 01,
Lemma (Lemma 13 from Mei et (2021a) with 0). Let Assumptions and hold. Then,
D Lemma 6 (Theorem from Mei et al. (2021a)). Let Assumptions and 2(a) hold. Then we can decompose the kernel matrices as follows
v -
Dz Sgm o1,((1).
V
D
Kg + AH),
m
Sm
M
T
BM + AM).
<m
mm
18

---

Under review as a conference paper at ICLR 2022
where
20 Σ
Rи (r.))
13
#2m+1
RM = (H(
Σ 12m+1
and
max A llop |1A (L.
Let Assumption I(a) hold. Let S,T disjoint subsets of N. Let D RIS|x|SI be diagonal matrix. Then we have that for any 1) >> O, there exists C(n) (independent of d), such that
Lemma 7.
5 fr//n² s C(T) [|PT fallata 12ta Tr(D)/n,
where the expectation with respect to the randomness in s, Vr.
Proof. L S ||S|] be the bijection such that v (#=100)(( then we have
ΣEΣ
M.EET SES JJEnn]
Σ ΣΣ Dew.o
M SES sE(n]
Di(ejuss Ba (PPTa)))))
m
sES
1
D P((s)((s) [|Prfal 11 11
n
I <((n) (Pr Du/n.
where the second to last inequality is by Holder's inequality and the last inequality used the hyper- contractivity assumption in Assumption ((a).
Lemma 8 (Exponential Kerne Decomposition). Assume the conditions of Lemma 6 hold and as- sume there exists 6 > O, such that (I(d), u(d)) satisfies the condition
160
(21)
X2
dd
Let j(d) satisfy min(u(d), m()) jdd & m() then
taa/ - (t/n)( D3, v
oz,,(1))
op
Proof. First consider the regime = Od(n/KH). Recall the decomposition,
v T Sm Sm + KIn + AH) H = M Mm
where A Aollop 01)) By Lemma 1 and Lemma 4,
HtHH c((n))( D3 taal)
tx taa
+ (t/n)RH Anllop
op
#21+1
op
x2 v mm V /m///l + (d.r(1) k21+1
max
Our(t max x²x) + oar(1)
k2j+1
Oar(t-ba + o1, odr((1),
19

---

Under review as a conference paper at ICLR 2022
where equality (a) holds by assumption Eq. (21). Now if = wa(n/KH). then it is easy to that
||
H /
w twml)
se we-w))()) od.F
max
op
op
and therefore
e tH/n
(t/n)(W D t
$ 2 2maxx
|1-1111m1)
(t/n)( D3 4 2 txal]
(1.=
op
op
B.3 EMPIRICAL WORLD- TRAIN
If / = wa(n/KH)) then by Eq. (17) it is easy to see that ||e ((0-2(0/)))) llop = oa.((1), hence
(n. = (1) [|fall...
From now on we focus on the case that & oz(n/KH). Let us decompose the training error as follows
Ra(fi) = R1 + Ra + Rs
where
1 8 201/))H f,
R1
n 2
R2 ET T- 22//)) f.
n 1
R3 E H(t/nnH E.
n
B.3.1
TERM Ri
Let us start by analysing Rj. We can write
R (fet + " -22//n) (f (f
1
Ti +
2T, + T3
where
7
1
f 2(//aHH fse.
N 1
T2
LLe 20//1 fee.
" 1
T3 f 2(t/n) fze n
Let us analyse the term Ti,
Ti < -sT -55ee-211011 -2t/n)) VI fet.
By Lemma 2, denoting
T St seenn
T see
Vtt/n)/=.DDs V. <t Be -2
We will show that
Be 2nD2
01.r(1).
(22)
op
20

---

Under review as a conference paper at ICLR 2022
By Lemma 4, since BBlo (1,r for d large B has desitive-deffiite square root B B1/2 w.h.p. Therefore we can write
Be 22D B
D2.B'' B1/2 B
2BB
and bound the operator norm
Be 2:D
B 2/B D /
op
opp
21mmi D (2/2))
B
op E
| lop E
2thmar (B) Amin (D2)) = 01,)
since by Assumption 3(a), tmmin (D (tttu).. Therefore 7i 01,7(1) ||PPeefall2z.
Now we analyse the term T3. Observe that by the inequality 1 - 1
1 1 - (2t/n)= FfI De Lo kL + AH))fst S T3 f n - ff
n
We have by Lemma 7.
v V >efss//n? $ [C()) D2 v
d,a
n
where the last quantity our (1) |P>efall 2 by Assumption 3(c). Thus we see that Observe that by the Cauchy-Schwarz inequality,
T3 = >P>sfflll + 01r(1) (PPesalllss
T2 S (TiTg) 12 s <A=:(\)) [| |PPsefallzai Putting everything together we see that,
R1 = -PPse + 08F((1) (I]fal + |PPsefal
B.3.2 TERM Rs
Turning to R2, we take the second-moment moment with respect to
[e
4
Ee Te 20//)) ff e 22(t//)) El/o?
o?
n²
4
4 n (15512/))
T TTe 1-00/)) f s
01, ||5al12.
By Markov's inequality R2 oar(1) [|fal 02
B.3.3 TERM Rs
Now let us analyse Rg. Recalling the definition B = TT se M se/n, we can compute the expectation
1
E. Ra))
Tr
I, 2((4//n)
n
(a)
1
wwt/n Tr - - (22t///(veeD o1.
71
(8)
1
Tr(2(t/n) D2 M [1) + 0s.((1)
71
(c)
1
Tr(1/ + (1,
2t
-ant/n
|B] Tr Tr(D2g) + 01 oar(1).
21

---

Under review as a conference paper at ICLR 2022
Equality (a) follows from Lemma 8. For (b) used the inequality 1 1--- ~ I and that trace is the sum of eigenvalues. Equality (c) uses the cyclic property of trace. In the last equality we used that by Lemma 4, BBll.p (1, and Assumption 3(c) implies that (t/n) Tr (r( = Oa((t/n)mn) =
(1( since by assumption we consider = oa(n/Kн)) Turning to the variance
Var. = Eg [Rg E5 [Raa]
1
n² Eel(e _e 2(/n)) E)² [Rs]
1
Be [e =) -o (d.:(11)
n²
( 0(1/n) 0ge + to= - 0º + 0.. (1))
oar(11) - oe
where the first inequality uses that ||c 2(t/n) op S and (a) uses that for & o(),
3o Therefore by Chebyshev's inequality, R3 of( (1))
Putting everything together yields
(fi) = R1 + R2 + Rs = ||P>el + oar(1)) (llfal + +z))
B.4 EMPIRICAL WORLD TEST
Recalling utt) from Eq. (14), let
u(1) v(t) + e(t)
where
v(t) = (I, c -(H/
(23)
e() (I, c (H/
(24)
Recall the expansion of the test enror from Eq. (15),
R(f.) Ex(fa(x))]] 2u(() - E ( H
= [|falli;- 27; + + - 21' + 2Tb,
where
Ti H E,
Т2 vtt) T H HH
Т3 E(t) H
Т. E(t) H
Т3 Et)) -
The proof for the test error is the most involved, but will follow similar strategy of analysing each term in the expansion. We first begin by analysing T₃ in Section B.4.1, then T1 in Section B.4.2, and finally terms T3, T4, Tr. which are all simpler than the first two, in Section B.4.3. At the end of this Appendix section we present the proof of Theorem
B.4.1
TERM T2
As before, we will analyze each term separately. We begin with term T2. Proposition (Term T2).
T = H
S ||
od.(1)) II
where recall the shrinkage matrix Ssm defined in Eq. (20) and vt)) in Eq. (23).
22

---

Under review as a conference paper at ICLR 2022
Proof of Proposition 1. To analyze T2 further decompose it into the following terms
T₂ = (fgt + f>e) (In H (In - (HH/"(fst + fse)
T21 T22 + T23.
where
T21 f [L H -
(25)
T22 = 25 - e H H (I. E -1H/m) fftt
(26)
T23 (I M (
(27)
Using Lemma 9 and 10 proven below, by the Cauchy-Schwarz Schwarz inequality,
T22 S (2T21722)" = 01,p(1) SP I[alllrtn
and hence
T2 = T21 + T22 + +T2 SeIfet 2 + 0sp(1) Ialall
Lemma 9 (Term T21 Eq. (25)).
Tzn = S | - + oar(1)) [
Proof of Lemma 9, Recall the notation a and se from Eq. (19). Define A such that
A = (In /H/ Kgt
which by Lemma satisfies A o1, Then we can split T2i into
T21 = T211 + T212 + T213 + T214
where
T211 Kee goS2, T <t K stfst/n²
T212 Ke km S v I K s
T213 K
se (H MH
sm
S2 Sm sm/m /n K sefse
T214 AL MH Kgefst + f2,K
MH + AHAH-M MMH'AAf
We will show that the dominant term is T21 and the others are of lower order. By Lemma 3,
n hH MH
S2 L T sm Sm sm/mm Em///lp o2r(11,
and since K 3 I,, T213 01r((1) |Peeffali. 1. By Lemma 3, Lemma 4 and since Sgm = Im
llap < 1 = $2 Sm
v _ /m///llnn + o1. < + oop(1)
hence it is easy to see that T211 = (1,r(1) || 1l... Turning to T212 we have
n LT (In ae (t/n) I 1 TT im (I, or (1/n) Di ffse
T212 S
(a)
de (1/n) v im T i se ae -1t--ae---l--)1-a (1/n)DD 8
fet
v se mm / o..((1) |PPeeaalEe..
where the first inequality used S < Im- we used Lemma 2 in (a), and the last equality used Lemma 4 (note that v V. all zeroes submatrix of Im). Finally we look at the main term T2n. Defining the matrices
Vim n is an off-diagonal block of TT W wm// which corresponds to an <m
A
TT
(t/n)/ge So 56
n
B
V
V
gB.
23

---

Under review as a conference paper at ICLR 2022
write
T211 f2 v
n St (I, ae WWW)) ge v Sr ae Wew sefse
(BS A0 B + a AS AA)ss
Now observe that by Lemma
sec (1/n) D'y Be-
A
and by the same argument used to show Eq. (22), ||Allop 0d,z(1). Since B In A' and Sge 3 Ie, we have
Ten1 = ||scffee| + 0ar ( ||Psefallia>
hence combining terms
T21 = T211 + T212 + T213 + T214 = S 1 + 01, (P)sl||Psffal
Lemma 10 (Term T23 Eq. (27)).
T23 = fI - "H/")HH"H" MH (I, - - Illaalll i
Proof of Lemma 10. Let define the matrix
G - e-t -
H MH
(I, M
6 -HH//)).
Using similar reasoning from Lemma we can write
1
G
K
Sm
S2 TT
Sm
K Sm A
n12
1
K
K
S2
V
Ket + A
n
<m
mm
5m
for matrices A, A' sstisfying max
{ A
A 'llop) = (1)) We can split T23 into
up
T23
J. Gfzt
n
(fom + fem) T G + fem)
2 f Gf + f Gf
1
f Gf +
-T21 + T232 + Te33 + T234
where
T231
I sm Sm 52 T K Kmmfmm
n
Sm Sm
2
T232
fI Gfzm:
n²
1
T233
fm Ket
1 S2 cm Sm
v
Keefem:
K
n²
T231 = (1))(1) |PP>efflll..
Let us first start with analysing T2a1, defining
T Sm smm/ e//n/n we have
T231 f v SI ae (t/n)D2 D3 B s2 2 (Im ae BD/ Sm v 5m fm
1
n² sm
(0)
S (1+ (o..((())) v sm v Sm fmmn
=or((1)
f Lat
24

---

Under review as a conference paper at ICLR 2022
where the first equality is by Lemma 2 and the last line follows from Lemma 7, Markov's inequality, and by the fact that m/n n = oa(1) by Assumption 2(c). To see that inequality (a) holds note that
Im ae (t B
B B-1/2
1/2
(Im
ae
D D B B
op
op
B B- 1/2
B1/2
Since S2 1 Im
(Im - ac (t/n)) B 2 ae (t/n))
B
Bllop
B
ogr((1),
where the last equality is by Lemma 4. Now let us turn to T233, which we can further split into
T233 T2331 T2332
(28)
where
T2331
f K S122 Ketfem
n22
T2332
n2 S S Se w im K <essim
T v se/n and using a similar argument for T231, the first term can be seen as Redefining B
T2331
n23 fim 1 T
1 ce(( - ae (t/m) 5 (I- ae (t/n)DD 3 w & Pim
2m
$ (1 + (aF(1)) Fm 11 V se/n|lop = =od,(1) PmPemaallie
(29)
Turning to the second term T2332, let
A
= 1 bm
In -
(V D2 " L
n
then we can write this term as
T2332 f AS im Afim im
f A fe S f Afe + 01, (1).((11||Peemllll (|
(30)
where the last inequality holds since
Ā < T L im Im- A by Lemma 4 and
7² = A 1/2 AA 1/2
3 A 1/2 (I +I+ A A 1/2
= A A 1/2
AA 1/2
A A'
By the inequality = x < x. in the PSD order we see that
Kit
(
1 T Vemm cm
n 2m
D2
Fm
+
n n
Therefore from Eq. (30) we have
tm fem + fT Kgt (1 Vem Pi + oar((1) falmffll
fT v T T2a32 I n fm
D
T
n
For the second term on the right, by Assumption 3(b) and by Lemma 4,
kut fi
TT im Vem Fimm -0p((1) || 12
25

---

Under review as a conference paper at ICLR 2022
For the first term by Lemma and Assumptions 3(b), 3(c),
Fl v im V
D
V V Se
Vim [mm] S (1/n)C(()) [PP Ipmmmalliize (r(
n
= pm (0ap(t)-lPPmm/aliizee) falliizzs
therefore by Markov's inequality
T2332 = (eP(()))|PPmmaallee ||Pemfalliatm.
Hence combining terms
T233- T2331 + T2332 01p(1)
||Pemfalliee fallali
By the Cauchy-Schwand inequality
T232 = n Jim Gfzm
1/2
< 2 Ji Gfem 1f S Gf>m
1/2
(T2as + 01,(11) ||P>| [IP>>Jdlliz) 1/2
2 + oar(1) || |P>eSallee
S o1.F(1) (o.F(l)-|PPsefall) ||P>efall ||
Putting everything together we see that
T23 = T231 + T232 + T233 + T231 = o1p(1) I1 [[
B.4.2
TERM Ti
Now we will analyse term Ti. Proposition 2 (Term Ti).
T (I, -e-h//1 H E = | fse || 0g,5 [|.fll
f
2
Proof of Proposition 2. We break Tj into the following terms
T = Ti + Ti2 Ti3
where
Tn = f - - (H/1 H Esm-
(31)
Tia = e 11H H Esm=
(32)
Ti = f (I- e--e-tHe HH/n H E>m-
(33)
Using Lemma 11 and recalling Lemma 10.
Tia S (T23)
fssm || og ||P fallzzz Ilfallza=n
where T23 is as given in Eq. (27). From the analysis of Ti in Lemma 12 and Ti3 in Lemma 13 we combine everything to get Proposition 2
s fee + os.p(1) II T
Lemma 11. For vector v E R"
J Esm S (v 1 M 12)2/22 Fz
=
1 T
1/2
n
<m
52 D
mm
Zm
v +
(1p((1
n
[101l/2
26

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 11. Recall that Esm v <m D
fmf By the Cauchy- Seiihy-Schwarz inequality,
v H Esm v H
<m D2
sm Sms
- (v (U'H" H
D v
H
0)
1/2
fsmm]
Sm
Sm
s (0
MH 0021/31 Fsmm
= -( 1
1/2
S Sm
Sm + od. |
|
n2
5m
where the last equality follows from Lemma 3. Lemma 12 (Term Tn Eq. (31)).
Tu s fst [ + os,p(1) (a.e(1))PPssffalll 1IPsmfulli-
Proof of Lemma 12. First note that by Lemma for some A such that a 0dp(1),
Tn = Tin + Ti12
where
Thi = f (V/m)( v tetnn H H
T11 f4 AH Esm-
By Lemma 11,
1/2 [s 01.F(1)-111 -
Tii (lelle) [1f<ell//n) |nH MH
lop)
We now consider
= - TT112
where
Tim H. Esm
Ti11 T ((tn)) H- Egm.
Note that by Lemma 5,
v D2
D2 5m - [S 01l orr(1),
where 0 is x (m - E) matrix of zeros. Hence for the first term Th11I
Tim - 1v <m D2 Smm = || fcr 2 + 0ap((1) |PPmmallia.
Define Hee D2 v se. For the second term Ti by Lemma 11
Tin2 & (S+ (1P=(()))PPPsaal1 1/2
Fsm
(34)
where
S
n L (1/n)
S2
52 T Sm Sme (L/n) fst.
Define A = TT
T
See
(t/n) H
ct. We have
5 n2 S (M/)Hs
sm V sme (t/n)
Te f (1/1) v e (1/)) fee no f fse (1/n) im w TIme ((//))ttrr fse
1
< 1 n/ f/ (1/n) V L - fze ||
<e | -1
1 eee/nall
A + (PPsslll
-ar((1) ( |Pgefflli:.
27

---

Under review as a conference paper at ICLR 2022
since noted before in Eq. (22), | od,e(1). Therefore
/ S 2 + oap(1) || smmmialii.
Tn = 7um + Tun + T112
Lemma 13 (Term T13 Eq. (33)).
Ti3 = (1) -
||PsmSallez Iallle.
Proof of Lemma 13. We have
Tist = If C--1/1ii H Exml
- 11
H
H 'lop |Eymll2
Note that we have Elll [ = n llfal 2.. Further by Eq. (17), we have
H H Ilop S
Rn with high
probability. Finally, recalling the definition of E>m from Eq. (16), we have
E 1 n
Na S
max Nák PPsmfalliz. 622-1
k=m+1
As result, have
Ti3 S Oar(1)) - ||P>mfallze ll In? max Xa
1/ 12/HH
#2m+1
= OI.((L) |PPsmflllza a In max
/2,0//
Σ Na.
k2m+1
k2m+1
odr ||P>mfallzz |/lll
where the last equality used Eq. (13) in Assumption 2(a).
B.4.3 TERMS T3. T4, Ts
To analyse the terms T3. T4, T3 adapt the corresponding steps for the proof of Theorem 4 in Mei et al. (2021a). For the following analysis we recall the definition of e(I) from Eq. (24).
Lemma 14 (Term Ta).
T3
MH 20.0 -
Proof of Lemma 14.
E [T3]
Tr (
Tr Tr MH-1
Tr 11 Sm S2 /mmnn² + (1,
18 W3
Tr V Sm v m 0s,((1)
mm + o. (1)) 0a.((1) = 0s,p(1),
where (a) used Lemma 3, (b) used Ssm x Im. and (c) used Lemma and Assumption 2(c). The lemma then follows from Markov's inequality.
Lemma 15 (Term TT).
Ta = = - T
oa.((1) (0 + l[
28

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 15.
[T(
Egle
11 H -tH/"))
0,
02
E H
1 E
< E H Z
Notice that M v cT
D "
V Σ
for any L E N, by the decomposition of Eq. (16).
Therefore
sup
D
L T
11
H
V D Dalllop
sup
L
V
T
ST.
H
op
(35)
H
MH 1lop = oa,,(1),
where the last inequality follows from Lemma 3. Hence,
E
2
lim E
ES
L+00
(a) lim
v
H 2 LI D2
SL
100
lim sup Lox
D 1
H 2 v
2t.
D
S
lim
fsu
10000
(1) ||fall 1.2
where (a) follows from the definition of Egi, (6) follows from the definition of operator norm, and (c) follows from Eq. (35). Therefore we get
T4 01, oz [|fall
01,x(1) (o2 + l..
Lemma 16 (Term TT).
T;
oap(1) (020)))000 + [[aall
Proof of Lemma 16. We can write term T; as
T3 Tsi + T62
where
Ts1 =(t) MH (I, c -tH
T32 e(1) H MH (I, -tH/u)fZZ
Note as in Eq. (35), that by Lemma and Lemma 4,
| M 1/2
= =|| MH llop = odP((1),
op and taking the second moment of Tsi yields
Ee [Ta
Fele H MH
(I, - (H/ S
11/1 H -
d²
(In - é -H
H 1MH-1111 - -
1/2 2
|
M (In - -(H/") f(s( |
-1.r(1): T21
-a. ff
where T2i is given in Eq. (25). Similarly we get that
E_ [ o1, Te3 = (1r((1) Ilfallz
0
where T23 as given in Eq. (27). By Markov's inequality we deduce that
T3 = (1) a. - <I|Peefallz= + [1fall = ol. (o + ll
29

---

Under review as a conference paper at ICLR 2022
Finally putting Propositions 1, 2 and Lemmas 14, 15, 16 together for terms T2, T1, Ta, Ta and T3 respectively leads to the proof of Theorem
Proof of T'hoormm 5.
R(fa)) [|fall2= 27, T2 T3 2T, + 2Tg
| 2 - 2 SccPso| + +1|scffss) 2
= =|Psefalli> +
+ oar(1)) -I1Sa 12 [|fall + +z2)
(I- 1 +|| -IP>effll2z odr(11) (l.fall2= -1ffal22t + o?)-
By Assumption 2(b), K5t oa(1) maxjge 23. hence
[I (I- Sce) feel ou.(() Ilfalllz=
and as a result we obtain the first part of the theorem
R(fe) = ||P>efallza + odr(11) (Ilfalli + |lfall + o²)
(36)
Now observe that similar to Eq. (15) we have the following decomposition
2
- Perfa
||P salaalll: 2u(I) H-'HH Ege + (-U)THHE'eS
H- u(()
L7
where ut) is given in Eq. (14). Therefore
write
f P
| 12
2 = R(fa)) - ||Psefaliez 21(1) H-1 H-
(37)
We now focus on the term
H-1 Exzt -EEt (1) H Eyt = 0 Ese e(L) H
By choosing L = f in the proof of Lemma 15, it follows that
e(t) H Est = o1.((1) (o? + >/ (2))
hence combining with the bound for T4 in Lemma 15 yields
e(l) H E T4 e(t) - Ege
o1) (o + [1fall(22) - 01. (02 + ||Psefalli.))
(..p(1))((0)) + [|
We will now show that
= (rr((1) ||P>effllzz= Ii If ((d) m(d), then Eq. (38) follows from Lemma 13. Otherwise, consider the case ((d) u(d).
(38)
Following similar logic the proof of Lemma 13, because B[]] n falll and
E = n Σ
Nush I ndg |PPuufall2.,
k=t+1
we also get Eq. (38) since
(u(t) T E fT c -
(t/n)]lfll2 (I-1 eI- (tH (n) lp
|E>ullz
Oap(1): |PPuufallz> flfalle t2g
(ar(1)) . -IIP fallz,
where (a) used the inequality (1 - /// < 1 and (b) used Assumption 3(a). Therefore
(tt) H-LEze oar(1) (o? + []]al]?:)) hence by Eq. (36) and Eq. (37) we obtain the final part of the theorem
- = o1x(1) (llfall Loth + to?).
(39)
30

---

Under review as a conference paper at ICLR 2022
C DOT PRODUCT KERNELS ON Sd (V-((Vd)
C.I SETTING
We now apply our general theorems to the setting of dot product kernels on the sphere. Concretely we take A' = ( and Va = Unir(g<-I(Val and consider dot product kernels Ha which take the form of Eq. (4). Note that by Eq. (61) any dot product kernel hg can be decomposed as
ha((#1, 222
Bw--nnit( 1) (o x1) (())))))aaaa ( xz2))]
for some activation function dg. We state mild assumptions and show that under these condi- tions we can apply the results Section A.3.
C.2 ASSUMPTIONS
We state assumptions da after some definitions. See Appendix G for additional background. Denote by Pge the orthogonal projection the subspace of T.2 (.2 spanned by polyno- mials of degree less than or equal to The projectors P. and P> defined analogously. Let us emphasize that the projectors P are related but distinct from the Psmm while P&te projects onto the eigenspace polynomials of degree at most f, Pmm projects onto the top m-eigenfunctions.
The assumptions given the activations the same Assumption 3 of Mei et al. (2021a).
Assumption 4 (Assumptions for Dot Product Kernels at level N). Ler (Ha)az be a sequence of dot product kernels with associated activation functions {oa)a21 as Eq. (61). We assume the following hold
(a) There exists an integer l and constants 61 < 1 and co > 0, such that [oa(x)] S Co explcix²/((N)
(b) We have
min d'
Pkoa((ee Mll Pa(11,
kSS
PP22t1al((e, M)E sd(11;
where E gd-1 is a fixed vector (it is easy to see that these quantities do not depend on e).
Consider (()), such that
8 < dit1-A,
t < 1-
for some j,s E and & > O. We now verify that if {aa]a21 satisfies Assumption 4 at level s, then for appropriate choice of (u(d), m(d)) the conditions in Appendix A.2 satisfied and lead to Theorem 1. We set u(d) and m(d) to be the number of eigenvalues associated to spherical harmonics of degree less than equal and respectively
=(dkk)+O(cc)) m Σ =ld,k)=O((c
The verification Assumption (Kernel Concentration Property) and Assumption 2 (Bigenvalue Condition) at level [(n(d), m(d) is the same as the treatment in Theorem 2 of Mei et al. (2021a). We only need to verify Assumption 3. To see part 3(a), note that 1/22,((d) = Oa(d)) and 1/A3 =
Ox(di-1). For part 3(b), the condition holds because u(d) m(d) for large d if and only if j < Assumption 3(c) is easily seen to hold since the trace of the kernel operator Tr(Hl.) = O₂(1).
31

---

Under review as a conference paper at ICLR 2022
D GROUP INVARIANT KERNELS ON Sd (Vd-)
D.1 SETTING
We now apply our general theorems to the setting group invariant kernels on the sphere. Con- cretely we take Xa = st-1s-(vv (Vd) and Va = Unif($" (Vd) and consider kernels Ha which take the form of Eq. (5) for some function h. By Eq. (61), for some activation function 0a
/ Uni 1)( (æ11 w) ())(2(2222))) ()))))
Ha(æ1,
(40)
We state mild assumptions on de and show that under these conditions can apply the results in Appendix A.3. For additional technical background refer to Appendix G.
D.2 ASSUMPTIONS
We will assume that a = a for all d and make the following assumptions on a which are the same as Assumption I in Mei et al. (2021b).
Assumption 5 (Assumption on Group Invariant Kernel at level s). Let {Ha]az1 be a sequence of invariant kernels with associated activation functions da as in Eq. (40). We assume the following conditions hold
(a) For Ga Cyc., assume a to be (s 1) V 3 differentiable and there exists constants cy > 0 and 0 1 such that |a(*| cge 12 for any 2 S $ 1) V3.
For general Ga. we assume that is a (finite degree) polynomial function.
(b) The Hermite coefficients (a(a) (c.f. Appendix) verify Pie + 0 for any 0 S k <
(c) We assume that is not polynomial with degrees less than or equal to s.
Consider t(d), n(d) such that
d+ Sts d
a-atto In S d=-a+t-6.
for some j.s E N and & O. We now verify that if a satisfies Assumption 5 at level s, then the conditions given Appendix A.2 are satisfied for an appropriate choice of (u(d), m(d)) which leads to Theorem 2. We set and m to be the number of eigenvalues invariant polynomials of degree less than or equal to and s respectively
D(d, k) Oa(diaa) m Σ =(d,k)= Oa(d
where D(d, k) is the dimension of the subspace of invariant polynomials of degree k. c.f. Appendix G.6. The verification of Assumption (Kernel Concentration Property) and Assumption 2 (Eigen- value Condition) at level ((n(d), m(d) is exactly the same as in Theorem Mei et al. (2021b).
We must verify Assumption 3. To part 3(a), note that 1/X Oa(d)) and 1/A2 (dddi-). For part 3(b), the condition holds because u(d) < m(d) for large if and only if < s in which case
t(d)
d+ B-att0 = 280 = oa(1).
Tr (H(a,,m())) n(d)
<
Assumption 3(c) can be seen to hold from the fact that Tr (THH))))(d))) = a)d and
D(d, O(sd (dd
k=
from which it follows that for some constant C'
Σ
X2 < C
Σ Na.
1=
j>m
32

---

Under review as a conference paper at ICLR 2022
E
AUXILIARY RESULTS
E SOLUTION TO KERNEL DYNAMICS
Recall that we are interested in the following dynamics given in Eqs. (2), (3),
for (a) = E[ 2) (fa(z) - (z)),
dt
f((x)) - Σ n
Halæ, x)) fe(a:))
with zero initialization f0" = fo= = O. In this section we clarify the derivation, validity, and solution of these dynamics. Let us consider the maps R: Ha - R and P., Ha defined in Eq. (1).
=
R()) - / (f(x) - fa(x))) dua (x) + +o2
R (f) 1 n n (f(a;)) - -
First, recall the definition of the Fréchet derivative of functional V Ha - R ft The Fréchet derivative (f) is the linear functional such that for E Nd.
V(f + V(f) DV
lim | +0
|1
The gradient VV)) E Ha is defined such that
(VV().g)ma DV
exists uniquely by the Riesz representation theorem. The gradients of the risk functionals are VR()) Half -fa,
v (2) = - (J(z;) H:)
where Hæ, (x) == Ha( x) and HH, is the kernel operator as in Section A.1. A proof of this fact
given in Proposition 2.1 of Yao et al. (2007). Taking for (x) as shorthand for (tr(t, where (L, E Ha is the oracle model at time and similarly for fc(x), the following gradient flows with zero initialization well-defined for t 2 0,
d
dt /t
V R(S(") -HalS fa) EZ [=( [2) -
(41)
di ft -RR(())) = - (f(())) wi Hz.
d
Σ Ha(s, - f(x)))
(42)
The oracle model ODE Eq. (41) is simply linear differential equation which has the following solution involving the operator exponential exp( () Σ A*/k!
k=0
ftr fa + exp(-tHa)(oo - fa) = fa exp(-tH..)
(43)
For the empirical model ODE Eq. (42) we first consider the system of scalar differential equations induced at the points (( M)]ee(n]- Letting u(t) = (f) TI y (V1,..., Bn)
and H (x,, 2,)),, have
d dt
u(t)
H((((tt) y). n
with initial condition u(0) 0. As this a linear ODE, the solution is given by
u y (H/n (u( y) (I, c- -1H//n)
(44)
33

---

Under review as a conference paper at ICLR 2022
For IR, define h(x)) = (Ha(æ, æ1)..... ...., Ha( xn,)" Te R". Let a(t) H u(t) E ER" We
will show that the function (-) == (b()),(tt) Ha. which satisfies (fc(x)),...... f((nn))
(t), satisfies the following equation
n f((=)) = (h(x), u(t)) -(((x)) -1H/1 -(HIny) dt
which is Eq. (42) at point æ. Indeed, by the chain rule
d (h(x)) a()))
dt h((x) = dt -h(x)) d
a(t))
(h(x)) H He (e-tH/ng) n
= (h(z), e- -(Hi"g)
which is what we wanted to show.
E.2 EQUIVALENCE BETWEEN INVARIANT KERNELS AND DATA AUGMENTATION
In this section we will show an equivalence between the (time rescaled) gradient flows for training invariant kernels and using an augmented dataset. Specifically consider group and kernel H that is G-equivariant, that is
Hig z1.9 x2) = H x²2 Vg E G, Vz 22 E X.
Given a G-cquivariant kernel H, we define a G-invariant kernel Hinv as the group averaged kernel
Hine [ H@ x2)
for the Haar measure G (c.f. Eq. (5)). Note that any dot product kernel is G-equivariant for 9 subgroup the orthogonal group e.g. the cyclic group Cyc (c.f. Section 3.3).
Given dataset (X,9) y) {(r,, U1) [n]] consider the augmented dataset
X Vg) {g z;. v)) 9 G, E [n]]-
We consider the (rescaled e.f. Remark 5) empirical dynamics Eq. (3) of the gradient flow on (X y) using Hinv which we denote fr.n
d fu (x) -m V Rr (fr.tv))
(f Hinv (x,, x)
dt
and the empirical dynamics of the gradient flow on (X yo) using H which we denote fr.nug
dt frauu (x) =
Σ ff x)) - yb) (g x4, x).
gEG t=1
Proposition 3. Let G be a finite group with m elements. Given G-equivariant kernel H, if is the uniform measure on G then
fr.m = fraug
VI 2.
Proof. Let G = {9i,....
3ml 9m where is the identity. Define the output vectors
Uinv (1) = (f (#I)....
(x.)) E R."
(t) = (frane( ar).... fe (g TT)))T E R",
Uang (t) (Rky (t),..., Ugm (t)) Rm
34

---

Under review as a conference paper at ICLR 2022
Furthermore, define the kernel matrices
H n. [H(g 0i. (o/d:aj))aaa #z)lesEM ERux for E G Haug Hy l. g.
R
Hin- = iHi (0i, T; je.j)
Note that by definition Hinv 1
Σ H gi.g. We will show that
U aug (t) (unv (t), Uinv (t), ...,, Unn (f)) for all 2
(45)
From this the result follows by Theorem 4.1 in Li et al. (2019) since ft.ine ft, are given by kemnll regressions with targets Uinv (4), Mang (1) and kernels Hine, H respectively.
By Eq. (42), we write
/n)yy, Uaug (t) = (I - exp(-tH /
Winv (t) (I
where ys = (y...., y) suffices to show that
IRm By expanding the matrix exponential series and using linearity,
H ang Ug = (m* H m H B.......... m y y) for all & E N. in order to show Eq. (45) holds. We prove the above by induction on k. For k = 1, observe that
HaugUg
H
gi
m
H a y
i=1
(m inv mr
where the second equality follows from G-equivariance of H. Assume the inductive hypothesis holds for k. Then
H aug
yg
Houg H
aug
Ug
m
H
lav
j=1
i=1
H gi .3
H 91
gr
y
iml
1++1
m
H mu 3B
(m
k+1
luv y ye
where the second equality applies the induction hypothesis and the third equality uses equivariance. Thus the inductive claim is proved and the proof is complete.
Remark 5. The scaling factor in the gradient flow for ft.wo. leads to a natural comparison with ft.sgg as elaborated in Appendix E.3. As argued that section, in the gradient descent discretiza- tion. it is natural to take a step-size inversely proportional to the maximum kernel eigenvalue. In the case of dime-diiml invariant kernels, note that
Amax sug) mXmax (H) md (H (Hav)
hence the step-size for the invariant kernel flow should be times larger.
35

---

Under review as a conference paper at ICLR 2022
E.3 DISCRETIZING TIME
Comparing different "speeds" of optimization algorithms only makes sense for discrete-time algo- rithms. Consider the following gradient descent dynamies with step-size 7/ obtained as the dis- cretization of the empirical gradient flow Eq. (42)
f -
y:) xi), (
k 0,0,,,...
(46)
We will argue that it natural take 77 n/ max (H) where H the kernel matrix.
Define the sampling operator S Ha + R by S(f) = (f(x))) E R" and let S R" + Ha
be its adjoint, defined by S (y) Σ y He: (see Yao al. (2007) Appendix B for more details).
Then we can rewrite the gradient descent equation Eq. (46) as
fxt1 fr (S S S y), k= 0,.......
(47)
Let S and define H SS
1 H to be the normalized kernel matrix. Let
n
6 S H y Ha and note that since Tb S* y. we can rewrite Eq. (47) as
fk+1 = fk - nTf b),
3 =,0,
(48)
Denote the eigenvalues of H as λ 2 A2 2 2 An O. By the spectral theorem, there exists
set of orthornomal eigenvectors $1.... On Ha such that T Σ Aoooo Define a;,kk)
(fx - b, o.) R. By taking Eq. (48) then subtracting b and taking the inner product with Φ on both sides, get the coordinate evolution equations for i 1, :..... 70
ar(k 1) ((id xTT) b), tha ((fx b), (id - ()))
(1-1)A, (1,
where the second equality holds since T is self-adjoint and the last equality is since di is an eigen- vector of T. It is easy to see that (k))k) = (1 - " (0). Therefore we see that gradient descent Eq. (46) is guaranteed to converge 7 1/(2X)) and may not otherwise. Therefore is natural to choose the step-size 1) scale asymptotically as 17 1/\max H
For a dot product kernel and its corresponding invariant kernel Hinv the kernel matrices have operator norms of the same order
Amax
X max Hinv)
hence no time rescaling is need to compare the corresponding optimization speeds asymptotically.
E.4 SIMILARITIES WITH EMPIRICAL PHENOMENA
In this section elaborate upon Remark 4 and mention tions in Nakkiran et al. (2020). Although the metric in our setting is the squared loss, we can still observe three stages in classification problems when measuring the soft error. In Fig. 6a taken from Nakkiran et al. (2020) we can observe stage I and stage 2. Either training has not continued long enough to observe stage 3 or large enough so that the models have converged to the approxima- tion error of the neural network class (c.f. Remark 1). In Fig. 6b taken from Nakkiran et al. (2020), although the train errors are not plotted, by extrapolating from Fig. 6a, presumably for each n stage I and stage 2 occur. From the dimmer curves in Fig. 6b we can see that for 50000 stage 3 occurs as well.
connections with empirical observa-
In Fig. 7a, we see parallel between the use of cyclic versus dot product kernels and the use data augmentation versus not for a Resnet-18 trained on CIFAR-5m (note that using a cyclic kernel is equivalent to using dot product kernel with data-augmentattin c.f. Appendix E.2). In both our theoretical results and the empirical results of Nakkiran et al. (2020) we observe that the ideal world optimization speed of augmented and non-augmented training are the same. but for augmented training the real world training speed is slowed down, eventually leading to better generalization for long enough training.
36

---

Under review as a conference paper at ICLR 2022
Varying
0.9
Real vs. Ideal: SoftError
0.6
Reo Test
Ree Thain
ideal Tist
Test Sefte Safe--rrr
0.4
0.5
0.3
(e+2500) Ferloe13303
0.1
10000
20000
30000
40000
5000
10000
15000
20000 25000 50000 35000 40000 SGD lterations
SGD Iterations
(a)
(b)
Figure 6: Soft-error curves for Resnet-18 trained on CIFAR-5m taken from ref. Nakkiran et al. (2020). Panel (6a): 5 10a (Fig. 6 in ref). Panel (6b) Varying (Fig. 4a in ref).
Real Ideal: Effect of Data Aug
0.9
0.8
No Data Aug
1.0
Oracle
Oracle
Aug
0.7
Ideal Worlds
Dot Prod, Test
Cyclic Test
0.8
Dot Prod. Train
Cyclic Train
Test Saft: Error
0.6
Train
0.5
Error
0.6
0.4
0.4
0.3
0.2
0.2
0.1
0.0
5000
10000
15000
20000
d1
d1.9
SGD Iterations
(a)
(b)
Figure Panel (7a): aata-augmennation for Resnet-18 on CIFAR-5m. (Fig. Sa from Nakkiran al.
(2020)). Panel (7b): Cyclic versus dot product kernel (Fig. 5c from this work)
37

---

Under review as a conference paper at ICLR 2022
F ADDITIONAL FIGURES
To see the effects of varying the dimension d, in Fig. 8 we replicate the log-scale plots of kernel gra- dient flow with dot product kernels from Fig. 4. We take n d and vary d (50, 100, 200, 400). Each plot is averaged over 10 runs with the shaded region representing one standard deviation around the mean. We can see that as increasing the standard deviation decreases and the curves approach the theoretical high- sigh-dimensional prediction.
RdP
1.0
1.0
0.8
Goadl
2
C.6
0.0
GP
210 rial ToX
Grade
|P,50
0.2
iP..fd
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3,0
0.0
0.5
1.0
1.5
2.0
2.5
3,0
0.C 3.5 1.0 1.5 2.0 2.5
3.0 3.5 40
d
d
log logg/logd
(a) 50
(b) d 50
(c) d = 50
1.0
0.8
Exparcal Tnd
c.
Rik
PP
drae
Crp rod Tea
mprricl imhh
|P,2PP 1
real
1.74
0.2
IP.47
1.0
1.5
2.0
1.0
2.0 logty togtylogd
log tolotooooo
log logid
(d) d 100
(e) d = 100
(0) d = 100
1.0
1.2
1.0
0.8
0.8
0.8
IP-6'
0.6
Gradl
Grade
ri kcll Tot
210 ricll Tot
Fma recl Tran
PP
To riall Tran
0.2
lag agtt/logd
log logg/
log sggt/logd
(g) d = 200
(h) d = 200
(i) d 200
1.0
1.0
Cracie
C.8
Dmp. Teat
Dradis
IP,.G
Dradio
Em.. Train
0.0
0.2
iP.
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5 1.0 1.5
2.0
3.0 3.5
logt/logd
logg/logd
log logtylogd
(i) d 400
(k) d 400
(I) d 400
Figure 8: Each column replicates kernel gradient flow experiment from Fig. 4 over d E (50, 100, 200, 400). Column 1: Replicates Fig. 4a Column 2: Replicates Fig. 4a but with o² 0.2.
Column 3: Replicates Fig. 4b. Averaged over 10 trials.
38

---

Under review as a conference paper at ICLR 2022
G TECHNICAL BACKGROUND
G. NOTATIONS
For positive integer, we denote by [n]] the set (1,2....,,)) For vectors u, v R we denote (u, 2) U1 .... uaydd their scalar product, and || 12 (u, u/ the lz norm. Given
matrix A E RR we denote loop = max |w]la=1 || Au its operator norm and by || =
(Ei, A 1/2 its Frobenius norm. If A E R is a square matrix, the trace of A is denoted by (r = LiEin] An.
We use Oa(-) (resp. oa(.) }) for the standard big-O (resp. little-o) relations, where the subscript d emphasizes the asymptotic variable. Furthermore, we write f = Pu((g) if g(d) = Oz(f(d),, and wa(g) if g(d) = od(J(d).. Finally, f = Oa(g) if we have both f= O2(g) and Pa(g))
We use Oar( ) (resp. og.(( )) the big-O (resp. little-o) in probability relations. Namely, for h (d) and h2 (d) two sequences of random variables, h1 (d) Oar(hy(d)) if for any > there exists C. > 0 and de E Ezoo such that
(()//2)))22 > C.)
AA 2 de,
and respectively: (d( = oa.((hyd)), if h1 h1(d//22(d converges to 0 in probability, Similarly, we will denote h1 (d) = (2 if h2(d) Oa.(hh(d)), and h1 (d) (hyp(h)(d)) if h2(d) (d)())) Finally, h1 (d) (hr()) if we have both hy (d) (ar(ha(d)) and h (d) = (h2())
G.2 FUNCTIONAL SPACES OVER THE SPHERE
For d 2 3, we let (r) = (ær TRd ||a||2 = r) denote the sphere with radius r in Rd. We will mostly work with the sphere of radius vd, sd-1(vd) and will denote by the uniform probability measure (Vd). All functions in this section assumed to be elements of L2((d-1 (Vd), ra), with scalar product and norm denoted as (-, )) and ||
(f = (ga))(va)
f(x) g(x) Ta(dx).
(49)
For l E Z20. let Va. be the space of homogeneous harmonic polynomials of degree & on Rdd (i.e. homogeneous polynomials q(x) satisfying Aq(x) 0), and denote by Va,e the linear space of functions obtained by restricting the polynomials in Va gd-1(v7). With these definitions, have the following orthogonal decomposition
( ra) + Vae.
(50)
t=
The dimension of each subspace is given by
28 2
(
dim(Va. = B(d, e)
(51)
d-2
l
For each é Zzo the spherical harmonies (Y:50) Jis)5B(d.) form an orthonormal basis of Va,e:
(Y=(d)) y((d) 12 = 8.j
Note that our convention is different from the more standard one, that defines the spherical harmonics as functions on (1)) is immediate to pass from one convention to the other by a simple scaling.
We will drop the superscript d and write Yr, YId whenever clear from the context.
We denote by P4 the orthogonal projections to Va, in (18g--((vd)... TT). This can be written in terms of spherical harmonies as
B(d.k)
Pa/(#) Σ
(S, (,NYL:
(52)
1=1
We also define Pste Et=
Ek=0 Pt. P I-
St
Eiseta Pk, and P = P Pzr P
39

---

Under review as a conference paper at ICLR 2022
G.3 GEGENBAUER POLYNOMIALS
The E-th Gegenbauer polynomial Q, is polynomial of degree t. Consistently with our convention
for spherical harmonics, we view Q! function Q( | d] + R. The set (Qe 1e20 forms
an orthogonal basis on ([[[d, d], i2), where if is the distribution of vd ei) when a ~ Td.
satisfying the normalization condition:
1), (/l = B(d, k)
65k
(53)
In particular, these polynomials are normalized that (,) 1. As above, will omit the (d) when clear from the context.
superscript (d) in Q((a)
Gegenbauer polynomials and consider the subspace of V formed by all functions that are invariant under rotations in Rd that keep unchanged. It is not hard to see that this subspace has dimension one, and coincides with the span the function Q,[1 ((v, ))-
directly related to spherical harmonics as follows. Fix St
We will use the following properties of Gegenbauer polynomials
1. For æ. y S (Vd)
(2 ((x 1),)), Qn ((y, 1)
S5 ((x, ((x,))).
(54)
B(d,k)
2. For x, ayr std1(Vd)
1 B(d,))
Q ((r,)))
Σ
(x)) (g).
(55)
B(d,k)
These properties imply that, up to a constant, 06a² ((x, is representation of the projector onto
subspace of degree-k spherical harmonics
(Pxf)(x)) = B(d,k) / (ga-)(va)
2.th ((x, f(v) rayd))
(56)
For a function E L3(l-vd, Vdl, r2)) (where T is the distribution of (ei, x) when Uni(()(-1(Vi)), denoting its spherical harmonics coefficients Sax(ot to be
(a) = 1 J-vava (x) (Vdz)r
(57)
then we have the following equation holds in 1.2(1- vdl + sense
a (xx)
B(d,o)B(d,kkc) (4) (vdz).
k=0
For any rotationally invariant kernel Ha(æ), x2)
ha ( 02) with ha(vd.)
I [[[-va,va], rJ), we can associate a self adjoint operator Ha 12 ( (Vd)) - I (2(
Has( = '(V))
ha(l f(x)) (a ra(dæ)).
(58)
By rotational invariance, the space V& of homogeneous polynomials of degree l is an eigenspace of Ha, and we will denote the corresponding eigenvalue by (h,a) In other words Haf = En Pha The eigenvalues can be computed via
(a.e(ba)) = =/== ha(x/va) (dd))
(59)
40

---

Under review as a conference paper at ICLR 2022
For dot product kernel Ha(æ, y) ha((x, v)/d) consider the Gegenbauer expansion of ha in 1, ([-vv, vdl,
ha(( w\/d) Σ ((d, (a..y))
(60)
Using Eq. (54) we can equivalently write the kernel as an expectation over random features for some activation dd
ha( u)/d) = B 10 ( (w, y))l
(61)
by taking
0a(z) = Ed
(Vdx).
(62)
Note that da (3([-v,, vdl, T/)) as long h(1) < co.
G.4 HERMITE POLYNOMIALS
The Hermite polynomials {Ho form an orthogonal basis of I.2 (TR, where 7(x)
=="2/2dx/ 2 is the standard Gaussian measure, and Heş has degree k. We will follow the classi- cal normalization (here and below, expectation is with respect to G (N( 1)):
(GH))(G) (G) k! 6,²
(63)
As consequence, for any function g (RR have the decomposition
(x(g) A!
g(x)
Hzx()),
pa(g) (g( He,(G))
(64)
The Hermite polynomials be obtained high-dimensional limits of the Gegenbauer polyno- mials introduced in the previous section. Indeed, the Gegenbauer polynomials (up vd scaling in domain) are constructed by Gram-Schmidt orthogonalization of the monomials {x Ja20 with respect the measure 72 while Hermite polynomial are obtained by Gram-Schmidt orthogonaliza- tion with respect to Since Ft + (here = denotes weak convergence), it is immediate to show that, for any fixed integer k.
lim Cocff(Qx (f (Vdx) B(d, Coeff {
(ax))//2 Hc)(2))
(65)
d-+00
Here and below, for P polynomial, Coeff ( (P(x) is the vector of the coefficients of P. As consequence, for any fixed integer k. have
mm(a) = lim
(Bd,,)))))
(66)
do
where pa (0) and (o) are given in Eq. (64) and Eq. (57).
G.5 THE INVARIANT FUNCTION CLASS AND THE SYMMETRIZATION OPERATOR
Let GJ be group that is isomorphic to a subgroup of (d), the orthogonal group in dimension. That means, each element of Ga can be identified with matrix in O(d) dddd and the group addition operation in Ga can be regarded as matrix multiplications and y Ga. we define group action g to be the multiplication of matrix representation of with the vector æ. We equip Ga with probability measure na. which is the uniform probability measure on Ga. More specifically, the Borel sigma algebra on Ga is defined as the Borel sigma algebra of (d) restricted on Gg. The uniform probability measure ny satisfies the property that, for any measuralse set B C Ga and any g Ga. have
Odd. For any x E (V
na B) Ra(gB).
41

---

Under review as a conference paper at ICLR 2022
Let P(S*-((V)) be the class of L functions on (V='(vd) equipped with uniform probability measure Unif(S"-I(va)) (Vd)). We define the invariant function class he
L3(8 9.) { LL f(x) f(g- x), vo E Vg E Gu).
We define the symmetrization operator S: (7((5- - 17() 9a) to be
(8f) = / Su
())-)))a(dg).
G.6 ORTHOGONAL POLYNOMIALS ON INVARIANT FUNCTION CLASS
We define Va,s& S (V(8*-I(Vd)) to be the subspace spanned by all the degree é polynomials, Va,s = Vd.st (V()) to be the orthogonal complement of Va.g,, and V2,+ Va,a& n V d. In words, Va, contains all degree k polynomials that orthogonal to all polynomials of degree at most k- 1. We further define Vd,< Va,gk-1 and Va.z Va
Let P St be the projection operator on L2(S--1 (vdd), Unif) that project a function onto Va,s the space spanned by all the degree polynomials. Then easy to see that Psee and operator commute. This means, for any S E (2(SS-1(VV))) we have
Pcr[S(()] = (())
Similarly, we can define Pe. Pec. Psc, P2e, which commute with S. We denote Va.( = Pv(S)-I(Vd) Ga) to be the space of polynomials in the images of P.S. Then we have
Pe(Aa, Gu)
((P("
We denote D(d;k) k) (Va- ga: dim (P 9a)) to be the dimension of
(d) (V 9a). We denote ( he(Di (Vū) to set of orthonormal polynomial basis
in (x Ga). That means
E Unit((
(d) ki (x) y (d)
k2l2 (x)] 1sk1 12, 12),
and
((1) kl
(z) = Y(6 (g x), Vo = Vg E Ga.
42


Reviews:
[{"review_id": "ur1_7zlMZho", "reviewer": "Reviewer_qXRH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths: Nice empirical results studying several cases around the three phases in the MSE curves. \n\nWeaknesses: Although the connection to deep learning is very weak, the paper mentions deep bootstrap and some other connections with deep learning. \n\nIn my opinion, the paper would benefit from more motivation for comparing the oracle risk together with the usual train and test errors. As it stands, the paper's attraction is rather limited.\n\nSome issues:\n- Is \\beta_t on page 1 a scalar or a vector? Either way, there seems to be a problem with the linear dynamics on the eq. at the bottom of the page. \n- In theorem 1, I could not find where w_d(1) is introduced. \n\nTypos:\n- In Figure 1, the oracle world legend should write R(f_t^{or})\n- At the top of page 2, f is not defined in the definition of K_N, I guess it is f_N. Normalization with N here does not make sense to me as N was only introduced as an index of growing width networks on page 1 (instead of precisely the width of the network)\n\n\n", "summary_of_the_paper": "The authors discuss three phases of the MSE loss curve: in the first phase the training, test, and the oracle errors remain close together; in the second phase, the training error goes to zero; and in the third case, the oracle loss converges at the approximation level whereas the test loss is higher. There are two theorems on dot product kernels (including some NTKs) and invariant kernels where the functions through linear dynamics with two kernels exhibit three phases. ", "summary_of_the_review": "It is not clear why the main message of the paper around the three stages of learning is interesting for the community. The paper does study several cases including random features. Nice experiments are included supporting the main message of the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h7BlvfchLq7", "reviewer": "Reviewer_WyHh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is a timely paper: the deep bootstrap paper (Nakkiran et al. 2020) reported\nan interesting observation, which the authors investigate here in a more\ncontrolled setting. While the authors don't seem to go significantly beyond the\ntechnical tools developed by Mei et al. and Ghorbani et al., which the present\nauthors acknowledge, they use them to provide theoretical insight on a question\nnot directly investigated by Mei and Ghorbani. \n\nThis paper is also well-written: the structure is clear, previous work is\nacknowledged, the schematic plots in Fig. 1+2 are helpful. I was only unsure\nabout how to interpret Fig. 3: is it a purely schematic plot, i.e. a drawing? Is\nit obtained from simulations, or from theory? Also, the target function is\nnoisy, so how can even the oracle world reach zero test error in Fig. 3? Or is\nthe test error simply very small?\n\nMy only qualm with the presentation regards Fig. 5 and the section on SGD. If I\nunderstand correctly, this plot only shows that the difference between gradient\nflow and the discrete updates of SGD are very small, is that correct? If so, I\ndon't find the agreement between gradient flow predictions and discrete SGD\nupdates so surprising - or are there specific reasons why it would be? Instead,\nit might be worth relegating these plots to the appendix and showing what\nhappens if you know train two-layer ReLU networks end-to-end on the same\ndataset. While I understand that you focus on kernel ridge regression here,\nbridging the gap to a setup with feature learning, if only numerically, would be\nanother interesting contribution imho. I would understand if the authors prefer\nto keep the paper in the RF setting though.\n", "summary_of_the_paper": "This paper studies the learning dynamics of gradient flow for kernel ridge\nregression. The authors contrast to different setups: the \"empirical world\",\nwhere the model is trained on a finite data set, and the \"oracle world\", where\nthe model is instead trained directly on the population loss, or in other words,\nby minimising the test error. Nakkiran et al. (2020) recently reported that the\nerrors in both setups stay close to each throughout training for a range of deep\nneural networks. By studying the relation between empirical and oracle world in\nthe setup of kernel ridge regression, the authors investigate this phenomenon in\na setup under precise theoretical control.\n\nThe authors perform such a study by leveraging the analysis of Ghorbani et\nal. (2021) and Mei et al. (2021), who gave a detailed and precise analysis of\nthe implicit bias of learning in random feature models, and in particular the\nlearning of approximations of increasing complexity. \n\nContrasting the learning in the two worlds, the authors find that learning\ngenerally, but not always, proceeds in three stages. In the case of polynomial\nkernels, models in both the empirical and the oracle learn first the leading\n$\\ell$-components of the target function, defined as those projections of the\ntarget function along the polynomials of small degree. After the training error\nof the empirical model reaches zero, a second phase ensues where the test errors\nof both models remain close, but the gap between training and test error in the\nempirical world can be large. Finally, either there is enough training data to\nlearn the target function perfectly, or learning enters a third stage where the\noracle model learns the target function perfectly, which the empirical model\nwon't achieve.\n\nThe authors confirm this picture also for invariant kernels, say\ntranslation-invariant ones, using technical tools from Mei et\nal. (2021). Quantitatively, the presence of an invariance shows up in the\ntraining speed, which is slower than for the product kernel (Remark\n2). Numerical experiments for kernel least-square confirm the theory, while the\nauthors also report experiments for SGD for random feature regression.", "summary_of_the_review": "I see the contribution of this paper in providing a theoretically sound\ntreatment of the observations presented by Nakkiran et al. (2020) in a\ncontrolled setting. I think this paper would be a valuable contribution to ICLR,\nand recommend acceptance.\n\n*Edit 14.11.* After the first round of responses, and after reading the other reviews, I have increased my confidence score from 4 to 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "d_bm4x8y-P1", "reviewer": "Reviewer_Ud7D", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In my opinion this is an interesting paper. \nPrior works have already shown that under appropriate conditions, kernel models can learn at most an $\\alpha$-degree polynomial, where $\\alpha$ depends on the relation between the sample size and input dimensionality, as well as certain invariance structure. \nWhile it is not very surprising that the training time of kernel gradient flow (up to the sample size bottleneck) plays a similar role as the sample size in kernel regression, to my knowledge this is the first work that analyzes this correspondence in the high-dimensional asymptotic limit. Such result may be interpreted as a \"scaling law\" for optimization, i.e., a certain sample size and training time is required to learn a target function with certain complexity. I believe the ICLR community will find this message relevant. \n\nA few comments and questions.\n\n1. My impression is that the theoretical analysis does not consider SGD. If this is the case, then mentioning SGD multiple times in the abstract and introduction can be misleading. \n\n2. Related to the previous point, the population dynamics (2) requires an integration over the input distribution, which is not very realistic. If we optimize the model using one-pass SGD instead, would the number of training steps be analogous to the training time in gradient flow?\n\n3. If we consider gradient descent on random features models (as in Section 4.2), then following the results in [Mei et al. 2021], do we expect the model width to play a similar role (in terms of limiting the complexity of the learned function) as the training set size or training time? \n\n4. It might be a good idea to elaborate on how results in this submission differ from the classical nonparametric rates for kernel regression, in which the generalization error rate is typically specified by the source and capacity condition. What are the benefits of working with the asymptotic setting? For example, the depicted three-stage phenomenon is not really that surprising, and I don't think it is only present in high dimensions. \n\n5. The listed assumptions in Appendix A.2 are rather opaque. Can the authors comment on whether it is straightforward to verify these conditions for more general input distributions (beyond unit sphere or hypercube), such as a Gaussian mixture?", "summary_of_the_paper": "Studied the evolution of generalization error of the kernel gradient flow trajectory with respect to the training (empirical world) and population (ideal world) MSE loss.\nThe analysis builds upon [Mei et al. 2021], which relates kernel ridge regression to projection onto low-degree polynomials. The authors showed that the estimator optimizing the empirical risk achieves vanishing training error, but the test error plateaus at certain value depending on the training set size, whereas the online (population) estimator can learn increasingly complex components of the target function as training proceeds.", "summary_of_the_review": "I believe the contributions in this paper are solid, and the take-home message is of interest to the ICLR community. I will consider adjusting my score if the authors can address some of the aforementioned concerns.  \n\n----------------------Post-rebuttal update----------------------  \nThank you for the detailed reply, which addressed some of my concerns. In my opinion this submission is above the acceptance bar (I think 7 would be more appropriate for my evaluation, but that is not an option...)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "G46EF-oCf49", "reviewer": "Reviewer_5uQz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is a good paper that applies the machinery developed in [1] to solve / explain certain DL phenomena. In what follows, I briefly summarize the strategies / contributions. \n\nIn the kernel gradient descent setting, the dynamics can be characterized by the gradient flow (solution) operator $G_{t, X}$, where $t$ and $X$ are the time and training dataset, resp. The $t=\\infty$ (i.e. kernel regression) is solved in [1, 2]. The current paper analyzes the setting of $t<< |X|$ (stage 1), $t\\sim |X|$ (stage 2) and $t>> |X|$ stage 3. The paper shows that, in the high dimensional setting, $G_{t, X}\\approx P_{\\min (t, |X|)}$, where $P_r$ denotes the projection operator onto certain low-frequency eigenspace (depends on $r$). The main technical difference between the current paper and [1] seems to be: in [1] $G_{t=\\infty, |X|}$ is essentially a matrix inversion and in here $t<\\infty$, $G_{t, |X|}$ is a matrix exponentially. This difference requires certain technical treatment and other than this, the overall strategies seem quite similar. \n\nIn sum, the strength and weakness of the paper are \n\n(Strength) Explaining/ solving certain phenomena that were previous observed in DL setting using \"Kernels\".\n\n(Weakness) Technical innovation is not very high and largely depends on the framework of [1]. As mentioned in (Strength) above, the proposed problem itself is mainly about \"Kernels\" rather than something unique in DL. \n\n\nMinor Comments: \n(1). The gradient flow dynamics in the current paper seems to be the limit of GD dynamics rather than SGD. \n\n\n[1] Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration. \n\n[2] Learning with invariances in random features and kernel models ", "summary_of_the_paper": "The paper studies the training/learning dynamics of (inner product) kernel gradient descent in the high-dimensional setting. The main contribution is proving a three-stage learning dynamics which were observed in neural networks in existing work. \n(1) Stage 1: train loss ~ test loss ~ oracle test loss (training set == whole (input, label) distribution) \n(2) Stage 2: test loss ~ oracle loss; train loss ->0; \n(3) Stage 3: test loss unchanged; oracle loss decays; \n\nI think this is a nice application of the results developed in [1], showing that many seemingly surprising deep learning (DL) phenomena are indeed not unique in DL -- most of them are provable / observable in the kernel setting. \n\n[1]Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration. ", "summary_of_the_review": "Although this is not a breakthrough paper and the technical contributions is not very high, I believe this is another nice paper showing that a lot of DL phenomena are can be explained by Kernels. The analysis also offers some basic intuition of neural networks' learning/training dynamics. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* Study gradient flow dynamics of empirical and population square risk in kernel learning. 

*Strengths:* 
- Empirical results studying several cases in MSE curves.
- Explaining / solving certain phenomena in DL using kernels. 

*Weaknesses:* 
- More motivations would be appreciated. 
- Technical innovation not so high. 

*Discussion:* 

Ud7D found that the main strength of this paper is the take-home message rather than innovations. They concluded 7 might be appropriate for the evaluation. This opinion was seconded by WyHh who considered 7 the most appropriate rating. 5uQz also found that 7 would be the most appropriate rating. qXRH maintained concerns about the novelty of the work and rating 5. Nonetheless, they agreed the study is valuable and would not oppose acceptance. 

*Conclusion:* 

Three reviewers found this paper is definitely above the acceptance threshold (suggesting rating 7) and one more reviewer found it marginally below the acceptance threshold however not opposing acceptance. I found the general impressions from the discussion well described in a comment from Ud7D, who indicates that although this is not a breakthrough paper, it is a nice paper showing that a lot of DL phenomena are can be explained by Kernels. I conclude that the paper makes a sufficiently valuable contribution and hence I am recommending accept. I suggest the authors take the reviewers’ comments carefully into account when preparing the final version of the manuscript.
Decision: Accept (Poster)