Precise Learning Curves and Higher-Order Scalings for Dot-product Kernel Regression  
Authors: Lechao Xiao
Hong Hu
Theodor Misiakiewicz
Yue Lu
Jeffrey Pennington
Venue: NeurIPS 2022 Accept (2022)
Keywords: Dot product kernel
NTK
NNGP
Marchenko-Pastur distribution
Learning Curves

Abstract: As modern machine learning models continue to advance the computational frontier, it has become increasingly important to develop precise estimates for expected performance improvements under different model and data scaling regimes. Currently, theoretical understanding of the learning curves that characterize how the prediction error depends on the number of samples is restricted to either large-sample asymptotics ($m\to\infty$) or, for certain simple data distributions, to the high-dimensional asymptotics in which the number of samples scales linearly with the dimension ($m\propto d$). There is a wide gulf between these two regimes, including all higher-order scaling relations $m\propto d^r$, which are the subject of the present paper. We focus on the problem of kernel ridge regression for dot-product kernels and present precise formulas for the mean of the test error, bias, and variance, for data drawn uniformly from the sphere with isotropic random labels in the $r$th-order asymptotic scaling regime $m\to\infty$ with $m/d^r$ held constant. We observe a peak in the learning curve whenever $m \approx d^r/r!$ for any integer $r$, leading to multiple sample-wise descent and nontrivial behavior at multiple scales. We include a colab notebook that reproduces the essential results of the paper.

Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression
Lechao Xiao* Google Research, Brain Team xlc@google. com
Hong Hu" University of Pennsylvania huhongowharton. upenn. edu
Theodor Misiakiewicz" Stanford University misiakie@stanforr edu
Yue M. Lu
Jeffrey Pennington Google Research, Brain Team jpennin@google.c com
Harvard University yueluEseas harvard. edu
Abstract
As modern machine learning models continue advance the computational fron- tier, it has become increasingly important to develop precise estimates for expected performance improvements under different model and data scaling regimes. Cur- rently, theoretical understanding of the learning curves that characterize how the prediction error depends on the number of samples is restricted to either large- sample asymptotics (m -> oc) for certain simple data distributions, the high-dimensional asymptotics in which the number of samples scales linearly with the dimension (m d). There wide gulf between these two regimes, including all higher-order scaling relations m xx d", which are the subject of the present paper. We focus the problem of kernel ridge regression for dot-product kernels and present precise formulas for the mean of the test error, bias, and variance, for data drawn uniformly from the sphere with isotropic random labels the rth-order asymptotic scaling regime m + co with m/ /d" held constant. We observe a peak in the learning curve whenever m d" d'/r! for any integer r, leading multiple sample- wise descent and nontrivial behavior at multiple scales. We include colab? notebook that reproduces the essential results of the paper.
Introduction
Modern machine learning has entered an era in which scaling is arguably the most critical ingredient improve performance. Recent breakthroughs such as GPT-3 [24] and PaLM [11] have demonstrated that performance of various learning algorithms improves in predlctaable manner as the amount of data and computational resources used in training increases. The functional relationships between performance and resources are loosely referred to as learning curves. While extrapolation of empirical learning curves widely used make predictions about how model might perform when extra resources become available, a rigorous theoretical understanding is lacking. A fundamental obstacle in developing a detailed thcoretical model of such learning curves is that they depend on many moving parts, e.g. the data distribution, the network architecture, the training algorithm, among others. In addition, even in the simplest possible settings, the learning curves can exhibit non-trivial structure that naive scaling laws fail to model, e.g. the well-known double-descent phenomenon [7, 3].
In the past couple years, large amount of effort from the community has improved our theoretical understanding of such phenomena and in some cases precise characterizations of learning curves
*LX, HH and TM contributed equally. HH's work was done while at Harvard University.
Available at: htpp://tinyurl.com/2nyyym
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Prediction: Gap=128
2.00
Prediction: Gap-32
1.75
Prediction: Gap=8
Prediction: Gap=2
Simulation
Test MSE
1.00
0.75
0.50
0.25
0.00
10"
101
102
10a
10f
m: # Training Samples
Figure 1: Precise Sample-wise Learning Curves for One-hidden Layer CNN kernels. The theoretical predictions (Eq. (18), solid lines) agree with finite-size simulations (markers) across several orders of magnitude and captures cases in which the curves are relatively simple (monotonically decreasing, small spectral gap) and complex (multiple-descent, large spectral gap). Simulations are obtained from kernel regression with one-layer CNN kernels averaged over 50 runs. The input is of shape do x with size dg = 14 and number of patches p = We vary the kernels by varying the ratio (aka spectral gap) between consecutive eigenspaces, where the ratio Gap [2, 8, 32, 128].
have been obtained (see e.g., [21, 1, 31, 34, 28)). These results have helped clarify several puzzling empirical observations, such as the origin of the double-descent peak [2. 27, 13] and linear trends between in- and out-of-distribution generalization performance [38, 39, 30], among many others. However, the precise predictions from many of these analyses have been possible only in the linear high-dimensional scaling regime in which the number of training samples m scales linearly with the dimension d, i.c. m & d. In these asymptotics, the model's effective capacity is limited to linear functions of the features. In contrast, many state-of-the-arr models operate in a regime where the amount of data is much larger than the data dimensionality; for example, large text corpora can contain trillions of tokens, whereas the effective input dimensionality of language models is at most millions.. Therefore, going beyond the linear scaling regime (m x d) to higher-order scaling regimes (m d') essential in improving our understanding of modern machine learning systems, and is the focus of the current paper.
Several works have investigated the behavior of the learning curves for nonlinear scalings in the dot-product kernel or random features setting, but they have done so only in the noncritical regime where ø d" [17, 32, 26]. [8, 10] also derive the closed-form predictions of the learning curves for both the critical and the noncritical scalings, but they have done so via nonrigorous statistical physics methods and "Gaussian equivalence conjecture" [12, 22, 16. 18, 19, 20]. Rigorously extending these results to include the critical regime x d" is nontrivial, both from the technical perspective, namely, proving "Gaussian equivalence conjecture", and also from the phenomenological perspective, we shall see the critical behavior induces nonmonotonicity and multiple sample-wi winple-wise descents.
In this work, obtain precise formulas for the sample-wise learning curves in the kernel ridge regression setting for a family of dot-product kernels for spherical input data in the polynomial scaling regimes d' for all N This family of kernels includes the neural network Gaussian Process (NNGP) kernels and Neural Tangent Kernels (NTK) associated with multi-layer fully-connected networks or convolutional networks. Both kernels serve as important starting points towards deeper understanding of neural networks as they often capture the first order learning dynamics of neural networks in certain scaling limits [23, 25, 4].
1.1 Contributions
Our primary contributions are to establish the following, for data drawn uniformly from the sphere:

---

1. The empirical spectral density of the Gram matrix induced by degree-r spherical harmonics converges Marchenko-Pasee Pastur distribution when (d" (d" /r!)//m converges to positive constant as d -> oo (Theorem 1);
2. A precise closed-form formula for the sample-wise learning curves for dot-product kernel regression when m x d" for all r E N" as d + oo (Theorem 2);
3. Empirically, the theoretical predictions agree with finite-size simulations surprisingly well even in the strong finite-size correction regime (Fig. 1);
4. An extension of the above results to convolutional kernels (Section 5).
Finally, we note that our results also assume the high-degree coefficients of the label function to be random and isotropic; see Eq. (11). It remains an open question to prove similar results when the label function is deterministic.
2 Notation and Setup
Let X' = - denote the input space, where S is the unit sphere in R2 and X is equipped with the normalized uniform measure a. We use Aa to represent any quantity (a scalar, vector or a matrix) with ||Ai||| - 0 as d - (in probability if Aa is stochastic), where III ||| can be the absolute value of a scalar, the norm a vector or the operator norm of a matrix.
Let X Rmxd be the training inputs where the i-th row of X is x.. We assume {m:)ee/m) is sampled uniformly, iid from X. The label function f S - will be defined in Section 4. Let K K(d) be dot-product kernel defined on S x S i.e., K( x') = h(x x²) for some function h E [-1, R. We assume h has the following decomposition
A(t) Σ h.P.(t), with
00,
where Pk is the k-th order Legendre polynomials in d dimensions. For simplicity, we assume = (hx) a sequence that is independent and he * for all l: < kn where kn sufficiently large. As such, decompose the kernel function using sperical harmonics,
K(
Σ
Yv,(())Yu
())
(d(N))))
where Yk, is the (-th spherical harmonic of degree k. _d, k) = d O is the total number of degree k spherical harmonics in d dimensions, o / (d, k) is the eigenvalue of Ysi. and (ar) is the column vector (=,((())))((N(()))) We also denote by (X) the N(d, k) matrix whose i-th row is T.
Structure of the Empirical Kernel and Marchenko-Pastur Distribution
The structure of the empirical kernel matrix K (X, X) plays a critical role characterizing the sample-wise test eиror for the kernel ridge regressor associated to K. We assume the training set size scales polynomially, i.e. m d" for some positive integer r E N Decompose this kernel into low-, critical- and high-freet high-frequency modes as follows,
K(X, X)
Σ (X)((X) (X)Y((X) + Σ (X)((()) ber
(3)
kDr
The low- and high-frequency parts have simple structures since ((d, k)/m either diverges to in- finity or converges to zero with rate least d=1,, yielding concentration that results significant simplification. To be precise, for high-frequency modes k > r, (x(X) is "fat" matrix and
"eee Sec. 6 for empirical evidences in favor of these results.

---

(M2, 0e6200 77m17611
d=3,d=80, 1598
1e4, dm24, mm2/0
08
Empricaal Spactrur
2
Ernp rical Spactruu
Emarical Spactruu
0.2
0.0
0.0
2.5
d=24, mm-20000
rw3, p=10. d=24, m=00000
rw3, p=20. d=24, 12000
1.6
Imprical Spedirum
P 0.76
0 0.10
Enp ricel Spedtrum
38
0g.0 0.23
Emeribe/SSactrun Soadtum
2.00
0.4
92
12
3.0
the empirical distribution of product kernels (X, ( r) vs theory prediction from Ha, for various degrees r, imput dimensions dl and number of samples m as indicated in the titles. Bottom: the empirical distribution of the CNN kernel (F(X))((X))) (X) (d, r) vs theoretical prediction. We fix r, d and m but varying the number of patches p E [6, 10, 20).
Figure 2: Marchenko- Pastur Distribution of Spherical Harmonics. Top:
(d,
k) = I + As where Aa vanishes d - oo [32]. Thus, the high- frequeryy parts behave like a regularizer in the following sense,
Σ (X)((X) Σ (o)((,))) CAAIm+AA +
Σi h I Ad-
(4)
On the other hand, when k < r, (X) a x (d) "tall" matrix with Ndd k)/m
Odd /m) ((d-(r-k) + O. Similarly, Mei et al. [32] show that (x() (x))/m
IN(d,)) + Aa. implying that when restricted to the subspace spanned by low-frequency functions (Yatberr the regressor associated to the empirical kernel ((X,X, X) acts like a pure multiplicative scaling.
remains to understand the critical-frequency mode (X)). It turns out that if (d,,k) k)/m + a E (0) then the empirical spectral measure of the random matrix (X)) (x(X/mm converges to the Marchenko- distribution Ha, whose density is given by
(o(()= = (1 (1- (1) + Via t)(t - a-)
la (1),, where as = (1 + va). (5)
2mat
where (t) 0 if t + 0 else 1. See Fig. 2 for visualizations of pa- The r case is obvious
as Yı (X) X for some normalizing constant ca and it is clear m (X) TY = S x x converges to the result show that this result continues to hold for all degrees.
m Prachenko-Pasttur distribution Pa if d/m + a E (0, as + oo [37]. Our first
Theorem 1. For fixed r E N and a E 00), if (dd + a E (0, 00) as - oc, then the T (X) converges in distribution to the Marchenko- empirical spectral distribution of (Y) Pastur distribution (MP(())
In the top panel of Fig. of r, d, and a. The Marchenko-Pastuu distribution Ha, perfectly captures the empirical measures of the random matrices TM (x) TY, (X) for all considered. We sketch the main steps of the proof of the theorem below; see Appendix B for the whole proof.
generate the empirical spectra* of J EY,,XX)T,xXXX for various values
'In the plot, we generate the spectra of the kernel matrix Y, (X) instead of the covariate matrix Y.(X) T (X). Although both of them have the same set of non-zero eigenvalues. the former can easily implemented via Legendre polynomials P. (x x').

---

Sketch of Proof. From Bai and Zhou 15, Theorem 1.1], it suffices to prove concentration of the following quadratic forms: for every sequence of (dd k) N(,, k) matrices {A,} with operator norm Aallop I 1, the variance
((((()) AaY,(x) - Tr(A.) - 0 d +
(6)
For the purpose of illustration, we assume A As is a diagonal matrix. Then we only need to show
k)
E (Ex
1) + 0.
(7)
By hypercontractivity of spherical harmonics [6],
EgY ((
- (E (x)) 1/2
Ck:
(8)
where Cs is some absolute constant. Since |Aul - || 1, we can drop any (d, ()²) pairs of (1) ) in Eq. (7). We show that for the remaining pairs (1, 1,, the eigenfunctions are asymptotically uncorrelated the sense
Eg E = E. (x) = 0
(9)
which implies Eq. (7).
4 Generalization Error of Dot-Product Kernel Regression
In this section, we establish the average generalization error for the kernel regression in the asymptotic regime (d, r)/m - a, for some (0, oo) and r 1 fixed. We assume the label function
f (Sa-1) is given by
f(x) = Σ Σ fa)a((z) Σ Yz(x),
(10)
1 (2
A21
where fa are the "Fourier" coefficients and fx [JulTeN(aa) We need to make a technical assumption that for k', Zr
FR
Ef. = O, Efaft
IN(AR) and Efef = ON(aA)x (d,
(1I)
Le. fxr is centered with isotropic covariance and (fu are mutually uncorrelated. Note that we allow fur to be deterministic for k < r. We F = (Fx)21 be fixed sequence with Σx21 F2 < oc, where F ElE(((,,A) f&r for l < r. For convenience, set F3, Ex>s F2 (similarly for f2.. 2. etc.) and use f to denote the random vector [su) Given training inputs and observed labels Y = f(X) + e, where ~ (O (m) is the noise, the prediction using kernel function K given by
y(अ) = K(x, (K(((XX))))) X) + Amm) (f(X) + +
(12)
Here is the regularization. As such, the mean test error over the random labels is given by
Err( X; A, h)
(, h) where Err(X; ; A, f, h) Ee (b())) - f())) (13)
To state our results, we need to introduce two functions XB and xv which are related to the bias and variance in the generalization error,
(a, / + 3 and xv(a, as² ʃ
f [11 ((1+Et) (1)+
(14)
Both XB and Xv have closed-form representations; see Appendix C.5. Define the effective regular- ization associated to the r-th order scaling to be
R2
a, a(A + ig.,)
(15)
Finally, define the bias and variance associated the r-th order scaling to be
By(a) (a; F ExB(a, a)) f2, V,(a) (a F. =x (a. (a. X, a))
(16)
(Fg +0?)
(17)
The following is our main result, which characterizes the test error in the asymptotic regime
d'.
5

---

Theorem 2. Let a E (0, 20) and r 2 1 be fixed. Assume N(d, rm + as d + oc. Then the average test error given by
Err( X, F. h) V.
(18)
where A. + 0 in probability.
4.1 Interpretations
We provide some high-level interpretations of the bias term B, and variance term Vz.
The Bias. From Eq. (16), the regressor learns all low www-freuencyy modes (k < r) but none of the high-frequency modes (k > r) the bias B, contains no low-frequency modes (i.e. k < r) but all high-frequency modes F3,. Importantly, the regressor is progressively learning the critical- frequency mode Y, the training size m N r) increases, i.e. from since (a (,, + a - oc and xa(a, &r (h, a)) + Of a + 0+. See 3 for the illustration.
a 0f
The Variance. From Eq. (17), the variance term Xv treats all high-frequency modes F3, the same as the noise term e. Moreover, Xv + 0 as - 0 or oc and is peaked at a = 1. The height of the peak depends on the effective regularization
Variance Decomposition
and
Teat MSE spror scare.
it diverges to infinity with rate 6,7 as & + co. In- deed, when 1 and E 5-1---1/// 122 - we have t(1+Et) -2 (t) x --22 f + (-) (f sarrse-idt-ii dtt E!/2.
1/2 which implies Xv (L.
Finally, Eq. (18) not only gives precise generaliza- tion formula (up vamishing term Ad) when m (d, ~ d" but also when d--1+6 $ m S d=-6 (i.e. when "a = oc") and when d
Training Sampler ocale)
Figure 3: Multi-scale Bias- Variance Decom- position. Theoretical predictions of the bias and variance from Eq. 16 and Eq. For each r. the variance is non-monotonic and has peak at (d,, r) r)= Ex (dd,k).
m m--1-6 (i.e. when "a = 0+") for any 8 E (0,
Indeed, in the non-critical scaling regime d=-146 x
148
m S d a = N(d, /m/m + oo as d + oo and
(a oo) + V,(a= = 00) - F2 + 2r2-
(19)
As such, the regressor learns all low-frequency modes but none of the critical- and high-frequenny modes (k 2 r), which is consistent with the result in [17, 32]. A similar argument also shows (a 0+)++ V2 0+) = F3,, namely, the regressor also learns the r-fereuency mode. This observation implies that we can glue together Eq. (18) for r 2 and remove all duplicate terms to generate sample-wit wise learning curve (LC):
LC(m; S, = Σ
Br
N (d,r)
... -rr -(r-
V, (Nid.
((d,sr) X,
A
m
m
r21
(20)
where N(d, = Σ ((d, k). The (-(r- 1?? term in the above equation is due to the fact that F over-counted (r- p--1 1) many times (one in each Bg for ls 1,..., (r 1).) It is worth mentioning that using a = (d,, < r)/m rather than = (d,, r)/m in the variance V, captures the finite-size correction more accurately. See Eq. (206) Appendix.
Corollary 1. If. for 1 < r E N. (1) N r)/m + a for some a E (0, 0o), or (2) d' 1+1 2 m S d=-6 for some E (0, 1/2), then
Err( X; f, h A) LC(m; X, S, Aa
(21)
where Aa + 0 in probability as - co.
Recall that for each r, the variance term V, could diverge to infinity as &, + at 1. Thus we might expect peak in the learning curve for each r. yielding the multiple-descent phenomenon, as shown in Fig. However, such phenomena can disappear by making the heights of the peaks small via choosing & small. We will discuss this point in the experimental section.

---

Our analysis can be extended analyzing NNGP kernel and NT kernel for one-layer convolution [35, 36, 43]. In this case, we assume the input space is X' = 8h do where do is the dimension a patch, p is the number of patches, and d = pdo is the total dimensions the inputs. The measure associated to X is the product of the uniform measure Sd.-1. We assume that both the filter size and stride the convolution are equal to dg. As such, after the first convolutional layer, the input reduced to vector of dimension p. We then apply non-linearit and dense layer to map this 4.2 Proof Sketch
The proof of this theorem is quite involved; see Appendix C. For simplicity, we assume the observed labels are noiseless, i.e. o² = 0. An ingredient is to understand the structure of the operator
fx) ((x, (K(X,
f(X).
(22)
The high-level strategy is as follows. We decompose the function into low-, critical- and high- frequency parts f = for + fr + for As such, the test error is roughly
Exr(X)= Errer (X) (x), (x))r(X)) where Err, EyKeTTRK(( fx(2))?
and similarly for Errer (X) and Erryr (X). The next step is to estimate each part separately.
Using the fact that the low-frequency parts of the kernel function K is almost an isometric operator on the column space (X), one can show that Eg ( Ag + 0 in probability, pointwisely.
Low-frequencies.
Critical-frequency. Up to vanishing term, one can remove all non-critical frequencies in the kernel function K in Tk in the sense of making the following substitutions
Kxx, x) + ( ( (X) and -
(23)
Thus, with y (A + TKJr {aa M, Ad. where
M,(X) = - (,,,, + + -Y,()))
(24)
Taking expectation with respect to (using orthogonality of Y, (z)) and then with respect to fr.
Ey.Ea (. (X), E,, (X) = FF (M)
(25)
Applying the Sherman-Mooriion--oodddu formula and then Theorem
/N(d,)) - +?? /
Hall)
Tr (V+ /o /N((r)))))))((()))))))
(t + E, dt.
High-frequencies. The cross term R. / (1) (x) Aa and thus
Ey - fxr (z) = Es (x) - Ef + Ad.
(26)
The second term equal to F3. The calculation of the first term is similar that of the critical frequency above (namely, we remove all high-/low-frequency components in K.)
5
Convolutional Kernels
5.1 One hidden layer
p-dimensional vector to a scalar. The NNGP and NT kernel have the following general form. Let (ax))E|p) E X, where 2;; Sdo-1 is the i-th patch
K K(x, x²) 1 Σ
h(
P2 (a. 20)
Σ (x(())) (d.,))
p [E(2
EE 821
SE(P]
Denote ( = (x;) and (z) = ( (x: TIE (d Then Y is the degree spherical harmonics associated to this kernel, which span space of dimension pN (do, k).
7

---

Theorem 3. Let N' and a E (0, be fixed. If pN rm/m + a (0, as do + oc and the rows of X are sampled uniformly, iid from 8 - then the empirical spectral distribution of m (X) (, tends to the Marchenko-Passee distribution
as do + co.
The assumptions the label function are similar to that of dot dot-product kernel, e.g."
F f(x) Σ Ya()), with fk Ja~NN Ar (. k) (NN(do.t) 121
if
(27)
p.V(do.))
otherwise fk is deterministic with f 2 = F2.
Theorem 4. Let a E (0, x)) and r 2 be fixed. Assume PN (do; r)/m + a as do + co. Then the average test error is given by
E X, F2h) = (a; 5,)) Va Ad.
(28)
where Ado + O in probability as dg + cc.
Corollary 2. If. for I E.N, N. (1) (d r)/m - for some a E (0), or (2) pdp-1+ 1+8 x
S pdl for some 8 E 10), then
Err X; h. LC(m; f.) Ado
(29)
where Ad. + 0 in probability as do + co.
5.2 Deep Convolutional Kernels
The eigenstructure of general CNN kernels are much more complicated as they depend on both the frequencies (i.e. the order of the polynomials) and the topologies of the networks [42]. To rigorously describe the eigenstructure, a heavy dose of notation must be introduced, which is beyond the scope of the paper. Nevertheless, the approach developed here is readily extended to cover general CNN kernels. We briefly describe the main ideas.
Following [42], we assume the input space is still X = - where p is the number of patches. For simplicity, we assume the network has L convolutional layers and each layer, the filter size and the stride are all equal to do. Thus the spatial dimension of the input is reduced to 1 after 7, convolutional layers. We then add non-linearality and a dense layer generate the logits. The kernel has the following form
K (x, x')
Σ
Σ
(.. where
(x,( = II Yo. (æ.). (30) <E(p]
KENY [NIlicis][N (do,
Unlike dot-product kernels in which &s is a scalar and the eigenvalues depend only on [k] (i.e. the frequencies), oh depends on both |k] and the spatial structure of the vector k: in rather complicated manner. Nevertheless, as dg + oo, ofe ~ d 50 = d'ja/t. for some L S j& E N. We can then categorize the eigenvectors according to the decay order of oh.-- Unlike the case of dot-product kernels or the one-hidden layer CNN kernels, in which eigenvectors with same-order eigenvalues are in the same eigenspace (i.e. the eigenvalues are the same), multiple-layer CNN kernels can have multiple eigenspaces with the same-order eigenvalues. Although this results in extra challenges (see below), our overall approach carries over. Consider the critical scaling regime m d", for r rorr=jjl j/L for some I, < N. Likewise, we can decompose the kernel into low-, critical- and high-frequency parts according to jk < r. jkk = and ju > r, resp. Following similar assumptions on the labels and eigenvalues, the bias and the variance can be essentially reduced to computing
1
Tr RR, + +X(X) (x)))/m)- XB N
(31)
Ner 1 XV m No.
Tr(RR, + +X,,()) Yx, 2Y (
(32)
'The Gaussian assumption is unessential. We use it here for convenience.

---

Theaey Presiction Simulation
Theory Prediction Simuittion
Test MOE
Pia
::0 11
Nid 5.2) Tharning Samplas
No5. 3.
Nin 444
ghid +533 phin, s21
5331
mi Training Samples
Dot Product Kemel
(b) One-layer CNN Kernel
Figure 4: Simulation vs Prediction. We generate the learning curves obtain from kernel regression by densely varying m from to 24000. For each m, we average the MSE over 20 runs. The closed- form prediction from Eq. (18) captures the simulations surprising well even for small d. Left: dot product kernel with d 24. Right: one-hidden layer CNN kernel with do = 20 and p = The spectral gap is Gap 32 in both plots.
where R, and Rgr are diagonal matrices whose entries are determined by the eigenvalues of the critical-frequency modes. In the dot-product kernels or one-hidden layer CNN kernels sctting, R,, is scaled identity matrix and simple, closed-form expressions for the above traces straight- distribution. However, for general diagonal matrix R. with bounded limiting spectra, R. does not commute with Y,T ( and more detailed random matrix analysis is needed. See the supplementary material for more details.
forwardly follow from the Marcenko-Pastee
6 Experiments
We provide experiments to show that our learning curves (Eq, (21)) accurately capture empirical sample-wise learning curve even when the ambient dimensions remains small. Even though our theoretical results require averaging the test error over random labels (aka, mean test error), our experimental results suggest this is unnecessary, i.e. the learning curve Eq. (21) can capture the test error accurately for any given draw of label function.
Experimental setup. We generate a polynomial kernel function I:(1) -x(1=>>> -E PR where Pa is the degree-k: Legendre polynomial in d dimensions. The kernel function can be efficiently computed via K K(x, x²) h(x x'). We choose the label function be f(x) Σ Σm. Fx))(z), where ya (x) [jE(d Why
II + x4. and the coefficients Wky are randomly sampled from a Gaussian for each k. Therefore TF (2=) = Σi= P2. For simplicity, we also set o² =0 (i.e. noiseless) and À = 0 (i.e. ridgeless). Note that when m dd" the regressor still contains "effective noise" 1²3, from un-learnable high-frequency modes and "effective regularization" i.3,- Finally, in our experiments, we will vary the value of the spectral gap: Gap = h Under this setup, the predicted learning curve LC(m) LC(m; Gap) depends only on the spectral gap of the kernel.
and then normalized so that (y
choose F = k and h Gap ((--), where
To simulate higher-order scaling (r > 3), the dimension d has to be very small as we need to invert a sequence of matrices of size ranging from m
m d" /rl. Due to the constraints in compute and memory, the largest m we can have is typically m maxx 2 25, 000 for one single GPU and in our experiments typically around 24. As such we are a regime with strong finite-size corrections. Finally, all experiments are run in single A-100 using Google Cloud Colab Notebooks.
Learning Curves Accurately Capture Simulations. In Fig. 4, we generate the empirical sample- wise learning curve by applying kernel regression Eq. (13) with training set X. We vary the training set size m densely in [1, mmax] and for each m we sample plot for the test error. The closed-form learning curve is obtained from Eq. (21) and the calculation done Sec.C. C.5. Even the low-dimensional regime with d = 24 for dot-product kernel (do = 20 and p = 6 for one-hide me-hidden layer CNN kernel), the predicted learning curve captures the empirical
independent
to get the errorbar

---

Moin of Sinuration
- Ste Simulation
1.3
Mean end Smuration Presiction
0.25
0.2
Standand dedditto
0:15
0.1
2.9
6.05
10
18
31
54
95
157
10
Irpult dimunsian:
Irpur More
(a) Mean of Simulations.
(b) Standard Deviation of Simulations.
Figure 5: Simulations approach predictions as d + oo. The mean and the standard deviation are computed over runs. The predictions and simulations are obtained via the second peak = namely, N (dd, 2).
learning curve surprisingly well, which has highly non-trivial multiple-descent behavior. It worth mentioning that, from the simulation, the deviation of the test error from its mean is relatively large when small but vanishes quickly as becomes larger. This suggests Theorem 2 and Corollary 1 should hold a pointwise fashion, i.c. without averaging the test error over random labels.
Finite-size correction vanishes as d oo. Our theoretical results assume that the input dimension is sufficiently large and these results are exact when d xo. To visualize the finite-size correction, we plot the dependence of the correction (between simulations and predictions) on the the input dimension Fig. 5 (a) shows that the means of simulations are converging to the theoretical prediction. Fig. 5 (b) shows that the standard deviations are converging zero.
Small Spectral Gap Eliminates Multiple-descent. In Fig. I, we plot both the predicted learning curves and simulations when Gap ranging in [2, 8, 32, 128). For S r S 6, we have & -r-11r-1) Eier Gap-(k-1) and & R Gap when Gap large. Recall that the variance term V, peaks at a and the peak scales like / x Gap When Gap is large, e.g. Gap 32, 128. the variance is also large near = 1, the multiple-deseent phenomena are more prominent. On the other hand, when Gap is small, e.g. Gap 8, 2, such phenomena disappear and learning curves become monotonic.
7 Conclusion
In this work, we establish precise asymptotic formulas for the sample-wise learning curves in the kernel ridge regression setting for a family of dot-product kernels in the polynomial scaling regimes m x d" for all r E N We demonstrate that these formulas can capture empirical learning curves surprisingly well even in the regime where strong finite-size corrections would be expected. We rigorously prove that the learning curves can be non-monotonic near m x d' /r! for each e N There are a couple limitations of our approach which could improved in future work. The first one is the strong assumption on the distribution of the input data, namely, the uniform distribution on the spherical type of data. In addition, the learning curves are obtained only the kernel regression setting and extending the results to the random feature setting (see, e.g., [29]) and the feature learning setting [44] would be meaningful future directions.
Acknowledgement
We thank Ben Adlam for providing valuable feedback on draft. T.M. was supported by NSF through award DMS-20318 and the Simons Foundation through Award 814639 for the Collaboration on the Theoretical Foundations of Deep Learning. T.M. also acknowledge the NSF grant 206-2006489 and the ONR grant competitive fund award for promising scholarship, and by the US National Science Foundation under grant CCF-1910410
The work of Yue M. Lu is supported by a Harvard FAS Dean's "
10

---

References
[1] Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In International Conference Machine Learning, pages 74-84, PMLR, 2020.
[2] Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine- Line-grained bias- variance decomposition. Advances in neural information processing systems, 1321-02111 2020.
[3] Madhu Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensiona dynamics of generalization error in neural networks. Neural Networks, 132:428-444 446,,4466660 2020.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
[5] Zhidong Bai and Wang Zhou. Large sample covariance matrices without independence structures in columns. Statistica Sinica, pages 425 442, 2008.
[6] William Beckner. Sobolev inequalities, the poisson semigroup, and analysis on the sphere sn. Proceedings of the National Academy of Sciences, (9(1 ((11):48164881) 1992.
[7] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32)15844-15588 2019.
[8] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020.
[9] Jennifer Bryson, Roman Vershynin, and Hongkai Zhao. independence conditions. Random Matrices: Theory and Applications, page 2150040, 2021.
Marchenko-pasturr law with relaxed
[10] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model aligmment explain generalization kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12. 2021.
[11] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.03311, 2022.
[12] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical review letters, 82(14))2975, 1999.
[13] Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning, pages 2280-2290 PMLR, 2020.
[14] Reza Rashidi Far, Tamer Oraby, Wlodzimierz Bryc, and Roland Speicher. Spectra of large block matrices. arXiv preprint cs/06 2006.
[15] Christopher Frye and Costas J Efthimiou. Spherical harmonics in dimensions. arXiv preprint arXiv:1205.3548. 2012.
[16] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation eπror in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pages 3452-3462. PMLR, 2020.
[17] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 1922):1029-1054 2021.
[18] Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning neural networks: The hidden manifold model. Physical Review X, 10(4):041044, 2020.

---

[19] Sebastian Goldt, Galen Reeves, Mare Mézard. Florent Krzakala, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with two-layer neural networks. 2020.
[20] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pages 426-471. PMLR, 2022.
[21] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986, 2022.
[22] Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. arXiv preprint arXiv:2009.0766 2020.
[23] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[24] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08366 2020.
[25] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
[26] Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent minimum-norm interpolants and restricted lower isometry of kemelss. In Conference on Learning Theory, pages PMLR, 2020.
[27] Licong Lin and Edgar Dobriban. What causes the test error? going beyond bias blas-nariance via anova. Journal of Machine Learning Research, 22(155):1-82, 2021.
[28) Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021.
[29] Yue M Lu and Horng-Tzer Yau. An equivalence principle for the spectrum of random inner- product kernel matrices. arXiv preprint 2xXii:2205506300 2022.
[30] Horia Mania and Suvrit Sra. Why do classifier accuracies show linear trends under distribution shift? arXiv preprint arXiv:2012. 2020.
[31] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematies, 75(4))667-766, 2022.
[32] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization eπror of random feature and kernel methods: hypereontractivity and kemeel matrix concentration. Applied and Computational Harmonic Analysis, 2021.
[33] James A Mingo and Roland Speicher. Free probability and random matrices, volume 35. Springer, 2017.
[34] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arXiv: 1911.0144, 2019.
[35] Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolañia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks 2018.
with many channels are gaussian processes. arXiv preprint
12

---

[36] Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A Alemi, Jascha Dicksticktt and Samuel S Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. arXiv preprini arXiv: 191200203,, 2019.
[37] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[38] Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Covariate shift in high-dimensional random feature regression. arXiv preprint arXiv:2/11.082.4 2021.
[39] Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparamettriization improves robustness to covariate shift in high dimensions. Advances in Neural Information Processing Systems, 34, 2021.
[40] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 101 1.302,, 2010.
[41] Denny Wu and Ji Xu, On the optimal weighted &2 regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33:10112-100 10123,, 2020.
[42] Lechao Xiao. Eigenspace restructuring: principle of space and frequency in neural networks. arXiv preprint arXiv:21 2021.
[43] Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006. 14548, 2020.
[44] Greg Yang and Edward Hu. Feature learning in infinite-widhh neural networks. arXiv preprint arXiv:20/ /. /4522, 2020.
13


Reviews:
[{"review_id": "k40j6A2wuig", "reviewer": "Reviewer_Yvrw", "summary": "Derive the precise generalization error of kernel ridge regression in the polynomial regime $n=\\Theta(d^r)$ for dot-product kernels on unit sphere. The analysis generalizes [Mei et al. 2021] to the case where $r$ takes integer value. The key observation is that the degree-$r$ decomposition of the kernel matrix has a Marchenko-Pastur spectrum, which, together with a random label function assumption, gives a simple description of the generalization error similar to the case of linear regression. Theoretical predictions align with empirical findings.", "questions": "1. In the experiments, are the coefficients of the label function randomly sampled at each run? Do the theory still provide a good match if the coefficients are fixed? \n\n2. Can the authors comment on the possibility of extending this analysis to other data distributions such as Gaussian?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The generalization error of kernel methods in high dimensions is an important research problem. This submission considers the challenging polynomial scaling setting and completes the picture in [Mei et al. 2021] by covering the $r\\in\\mathbb{N}$ case. The asymptotic formulae provide a precise description of the multiple descent risk curve (without manipulating the spectrum of the input matrix). I feel that this is an interesting submission that is relevant to the NeurIPS community. \n\nOn the other hand, the current results are also a bit limited for the following reasons: \n1. The analysis is based on the decomposition of kernel matrix into convenient orthogonal bases, which seems to work only for restricted input data (e.g. sphere or hypercube). It is not clear if the similar results can be shown for general settings. \n2. To reduce the bias term to the Stieltjes transform of the decomposed kernel, the high-degree components of the label function is assumed to be random and isotropic. The authors should highlight this limitation in the abstract / introduction. \n\n[Minor] the reference list for precise learning curves / Gaussian equivalence principle is incomplete. Please update the citations and include more relevant papers (e.g. see related work section of [Loureiro et al. 2021]).  \nLoureiro et al. 2021. Learning curves of generic features maps for realistic datasets with a teacher-student model. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cOOOnCFZLH0", "reviewer": "Reviewer_sFMD", "summary": "This paper characterizes the prediction error for kernel ridge regression with dot-product kernels. Different from the previous work that focus on the linear scaling regime (sample size $m$ $\\propto$ data dimension $d$), this work focuses on the higher-order scaling regimes ($m\\propto d^r$). To establish this theoretical result, the author first study the limiting distribution (MP distribution) of the spectral density of the gram matrix under this scaling regime [Theorem 1]. With the help of this theorem, the author can express the testing error in terms of the MP distribution [Theorem 2]. Experimental results match their theoretical result. Extensions to convolutional kernels are also included. ", "questions": "- The uniform distribution on the spherical type of data seems restrictive and existing literature also made similar assumptions. Could the author provide the literature review to compare assumptions on the data distributions for this problem? ", "limitations": "See weakness part in previous section. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**: Main theoretical result [Theorem 2] itself gives us an understanding of the learning curve of kernel regression for higher-order scaling regimes, extending previous analysis in literature. The intermediate theoretical result [Theorem 1] and supporting proof are also interesting. From my perspective, the key step is to view kernel function as harmonic series and then study the empirical spectral distribution of the non-trivial term from this series. Previous literature [Tao, 2012] only gives similar result for the case $r=1$, but the auhor shows that it holds for all degrees.\n\n**Quality/Clarity**: Presentations of notations, theorem statements, and proofs are crystally clear. Theoretical results are highly non-trivial. Experimental results match their theory surprisingly well. \n\n**Significance**: Their theory on learning curves applies for dot-product kernel and NNGP/NT kernel with one-layer convolution, which covers many scenarios in machine learning literature.\n\n**Weakness**: \n1. The author commented that it is promising to extend the theory for deep convolutional kernels, but due to the complicated structure of this type of kernel, it is left for future work. I agree on this point but I am looking forward to seeing some updates on deep convolutional kernels in the future.\n2. As the author have commented in Section 7, the strong assumption on distributions of input data and the focus on kernel regression setting makes this work less popular. However, I believe similar technique can be used to handle more general settings, which can be finished in the future.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TDSQZeEZcLE", "reviewer": "Reviewer_HvxY", "summary": "The authors aim to theoretically analyze the relationship between number of samples ($m$) and test error (learning curve) in the case of Kernel regression for dot product kernels when the $m \\sim d^r$ where $d$ is the dimensionality of data and $r$ is a natural number. Their analysis shows that when the input distribution and labeling function follow some regulatory conditions, under some asymptotics, a closed form formula precisely characterizes the learning curve for the mentioned set of kernels, and their experiments support this claim. Moreover, they asymptotically derive a closed-form distribution for the gram matrix of some dot product kernels, which seems valuable for future works.\nAlthough the work indeed does have some limitations (mentioned in greater detail in the limitations section), both on the theoretical and experimental aspects, I find the contribution to be impactful in the direction of understanding/characterizing generalization error in modern machine learning.", "questions": "My questions have been mentioned in the weaknesses section.", "limitations": "I have mentioned unaddressed limitations as part of the weaknesses. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n* The theoretical results of the work are sound and fills a gap in the study of learning curves for the case of non-linear relationship between the number of samples and dimensionality of the data.\n\n* The predicted distribution for the spectral distribution of the mentioned dot product kernels seems very accurate and can potentially benefit future work. \n\n* The conducted experiments, although with some limitations, strongly support the theoretical results.\n\n**Weaknesses:**\n\n* Some parts of the text are hard to follow. For instance, the notation section brings up the whole decomposition of the function of the dot product kernel without motivating it. This kind of introduction to some topic without motivating it beforehands happens a lot in the paper, and for me was generally confusing. Moreover, sometimes some equations or results are being referred to before being obtained or described. For instance, in line 171 there's a reference to Eq 29, which is undefined at this point for the reader. Likewise, $\\chi_B$ and $\\chi_V$ are introduced without much motivation. \n\n\n* Various assumptions are not justified nor analyzed, and their importance could be better explained. As an example, the assumption of having according decomposable labeling function could be better explained in a sense that how close is it to the practical datasets that one might expect, at least for some toy examples. \n\n* I believe the writing could enjoy more description about motivations, intuitions, the why of different assumptions and the relativity of them (how often do they hold in practical settings? why do we need them and what goes wrong if we don't have them?) instead of some extra formulas in the main text, such that the main text would give an overall intuition about the problem and the approach to solve it along with the derived theorems, and the proof sketchs could be delayed to the appendix instead. However, this is just my opinion. \n\n* Although the experiments strongly support the theoretical results, the range of values used for $m, r, d$ seem a bit limited to me. In particular, there are some asymptotics in the theoretical results (high frequency and low frequency decompositions of the kernel value that converge or diverge asymptotically as $d \\to \\infty$) that I expected to result in very noisy experimental results, specially for the range of tested values, but surprisingly this doesn't happen in the provided experiments. I would be curious to know why this is the case. Moreover, experiments involving noise and ridge regularization could also benefit the paper.\n\n* I believe more insights could be provided based on the solid theoretical results that are achieved. Having a closed formula for determining the precise learning curve in the mentioned context unlocks a lot of analyses. For instance, how does $r$ in $m \\sim d^r$ affect the number of descents in the curve or the slope of the curve? How does the labeling function or the data affect the slope and/or the number of descents? The dependence on the spectral gap is mentioned, but when does one expect large or small spectral gap? \n\n* Some more detailed concerns and questions:\n  * What is the definition of a \"fat\" or \"tall\" matrix? \n  * Why would one expect the coefficients of the legendre polynomials to be non-zero up to a large index in the decomposition of $h$, and why does it have to be independent of $d$?\n  *  Could you please shed more light on the decomposition of the labeling function and the specific assumptions like the fact that $\\hat f_k$ should be isotropic? How likely is it that practical datasets follow such decompositions?\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8RrwheWhfDM", "reviewer": "Reviewer_1Wx8", "summary": "Summary.\n\nThe paper studies the kernel ridge regression and provides close form characterization on the loss curve in the finite sample regime of $m \\propto d^{r}$, where $m$ is the sample size, d is the input dimension and $r \\geq 1$ is arbitrary integer. The paper also proves the results hold broadly to the neural tangent kernel (NTK) of one-layer convolutional net.\n\nModel. \nThe paper studies the classical kernel ridge regression under the assumption that input data draws from d-dimensional sphere and certain isotropic/independence assumption of higher order Fourier coefficients. While previous work of [Mei and Montanari 2021] considers mostly of linear regime, i.e., $m \\propto d$, the paper extends the result to $m \\propto d^{r}$ to arbitrary integer $r$.\n\n\nResult.\nThe paper provides a close form characterization of the population loss. It is hard to describe in non-mathematical way, the close form characterization consists of Bias and Variance terms, where both terms are certain integral of Marchenko-Pastur distribution (limiting spectral distribution for random matrix) and exhibits the double descent phenomenon (bias always decay, but variance first goes up and then down)\n\n\nMethod \n\nThe method extends from the previous work of [Mei and Montanari 2021]. They use Legendre polynomial decomposition to the kernel and by standard concentration, argue one only needs to look at the $r$-th order decomposition. Then perform standard bias-variance decomposition and use random matrix theory to argue about the spectral. Some technical complications come out along the proof.\n", "questions": "1. Why the kernel result only apply to convolutional kernel but not other neural tangent kernel (say one-layer ReLU)?\n2. I have difficulty understanding the setup. Line 76, why is $P_k$ a k-th order Legendre polynomial in 'd dimensions'? Isn't $P_k$ from $[-1,1]\\to \\mathbb R$? The equivalence between the Legendre polynomial and spherical harmonic representation looks non-travail to me, can you provide a reference for this?\n\n\n", "limitations": ".", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength. The paper provides close form characterization of loss curve for kernel regression and offers some insight on the double descent phenomenon. The technique follows largely from [Mei and Montanari 2021] but also turns out to be very interesting and non-trivial to me.\n\nWeakness. There are no significant weaknesses but the writing could be significantly improved.  (See below)\n\n1. Line 72. It is better to use $x^{\\top}$ instead of $x^{T}$ for transpose. This applies to other matrix/vector transpose.\n2. Line 46. “Extending these result “ - - > “Extending these results “\n3. Line 40. “Large text corpora can contain trillions of tokens, wheares” I don't quite get it, the input dimension of language model might not be that large, but the entire models could still be quite large.\n4. Eq. (5) what is $\\delta_{0}(t)$.\n5. Eq. (11) typo: need to add transpose for the variance and covariance.\n6. Figure 3. Might be good to make bias and variance more clear.\n7. Line 190. Would be good to make a separate paragraph for low frequencies and critical frequencies\n8. The experiments are all simulations that should be emphasized somewhere.\n9. The reference format seems wrong.\n10. typo: Line 258 $y_k(\\mathbf x)$ should be the summation over $j\\in[d]$\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "69as4uBeuL6", "reviewer": "Reviewer_jzgb", "summary": "The authors explicitly characterize the learning curve for kernel ridge regression under poly scaling regimes $m \\sim d^r$, both theoretically and empirically. Despite the strict restrictions on the distribution and the setting, this interesting multiple-descent behavior in the sample-wise learning curve could help the understanding of neural networks.", "questions": "See above in weakness. \n\nUpdate: the authors reasonably address my concerns and I have changed the scores.", "limitations": "Yes. As the authors pointed out in section 7, this works only focus on kernel ridge regression with uniformly distributed data, the generalization of the results is a very important topic. The impact of this work, beyond the interesting phenomena, should be more carefully explored.  \n\nI do not see what is the potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nTheoretical results seem to be solid (did not check step by step though). \nExperiments serve as good illustration of the key ideas.\n\nWeakness: \n1. (minor) readability could be improved by adding more details (could be placed at the beginning of the appendix in a separate (sub-)section):\n(1) explicit definitions of asymptotic notations, e.g., $\\sim$, $O(\\cdot)$.\n(2) background on decomposition via spherical harmonics \n\nMoreover, are there (commonly seen) examples for the kernel function that eq. (1) is satisfied?\n\n2. (major)The contribution/impact of the current finding should be more carefully articulated, instead of several lines in the intro (lines 54-56). Also a better summary of the existing works on both linear/non-linear scaling regimes would be better. \n\nWhat is the connection (in terms of the empirical/theoretical behavior, technique in obtaining the theoretical results, etc.)?\n\n3. (major)More experiments would be better: I would not say d=60 is very large (though I am not expert in this field). Since the goal is to demonstrate the (asymptotic) theoretical findings using numerical evidence, I would expect more extensive results (in terms of settings, such as dimensionality, distribution parameters, etc.). \n\nFor example, with larger dimension, would you observe better empirical scaling? To be precise, the authors state peak appears at $m \\approx d^r/r!$, then I would expect experiments indicating as $d \\rightarrow \\infty$, the different between $m_{peak}$ and $d^r/r!$ shrinks to zero.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept