Generalization error of spectral algorithms
Authors: Maksim Velikanov
Maxim Panov
Dmitry Yarotsky
Venue: ICLR 2024 spotlight (2024)
Keywords: gradient descent
kernel ridge regression
optimal algorithm
generalization
asymptotic error rates
power-laws
Primary area: learning theory

Abstract: The asymptotically precise estimation of the generalization of kernel methods has recently received attention due to the parallels between neural networks and their associated kernels. However, prior works derive such estimates for training by kernel ridge regression (KRR), whereas neural networks are typically trained with gradient descent (GD). In the present work, we consider the training of kernels with a family of \emph{spectral algorithms} specified by profile $h(\lambda)$, and including KRR and GD as special cases. Then, we derive the generalization error as a functional of learning profile $h(\lambda)$ for two data models: high-dimensional Gaussian and low-dimensional translation-invariant model. 
Under power-law assumptions on the spectrum of the kernel and target, we use our framework to (i) give full loss asymptotics for both noisy and noiseless observations (ii) show that the loss localizes on certain spectral scales, giving a new perspective on the KRR saturation phenomenon (iii) conjecture, and demonstrate for the considered data models, the universality of the loss w.r.t. non-spectral details of the problem, but only in case of noisy observation.

Published as a conference paper at ICLR 2024
GENERALIZATION ERROR OF SPECTRAL ALGORITHMS
Maksim Velikanov Maxim Panov Dmitry Yarotsky
Teccnnoooyy Innovation Institute, EEcole Polytechnique, MMBZUAI *Skoltech
maksim. vel velikanov@tii.aa maxim. paappaannnnaaaaaae ac, d. d.yarettsky&koltecch.. ru
ABSTRACT
The asymptotically precise estimation of the generalization of kernel methods has recently received attention due to the parallels between neural networks and their associated kemnlls. However, prior works derive such estimates for training by kernel ridge regression (KRR), whereas neural networks are typically trained with gradient descent (GD). In the present work, consider the training of kernels with a family of spectral algorithums specified by profile h(A), and including KRR and GD as special cases. Then, we derive the generalization error a fune- tional of learning profile (A) for two data models: high-dimensional Gaussian model. Under power-law assumptions
and low-dimensional cousslationinvaattti on the spectrum of the kernel and target, we use our framework to (i) give full loss asymptoties for both noisy and noiseless observations (ii) show that the loss lo- calizes on certain spectral scales, giving a new perspective on the KRR saturation phenomenon (iii) conjecture, and demonstrate for the considered data models, the universality of the loss w.r.t. non-spectral details of the problem, but only in case noisy observation.
INTRODUCTION
Quantitative description of various aspects of neural networks, most notably, generalization perfor- mance after training, an important but challenging question of deep learning theory. One of the central approaches to this question is built the connection between neural networks and its neural tangent kernel, first established for infinitely wide networks (Jacot et al.] 2018 Lee et al., 2020 Chizat et al. 2019). and then further taken the rich realm of finite practical networks (Fort al. 2020 Maddox et al. 2021 Long 2021 Kopitkov & Indelman 2020 Vyas et al. 2023).
Consider task of learning target function f*(x) from training dataset DN fxx 12 and (possibly)
noisy observation y/ = [(((,) aēs, E; ~ (O, 1), using given kernel K(x, x
Then, many
authors (Bordelon al. 2020 Jacot et al. 2020a Wei et al. 2022) derive asymptotic N - co
generalization error for kernel ridge regression (KRR) algorithm with regularization r7:
LKRR (n) = 2 On
Jfffff
Σ
(noHee)² A x2
7 Tef
(I)
(Nea + A1)
N
A TTef
where x are population eigenvalues of K(x, x') and c are respective eigencoefficients of f*( (see definition in (4)). The main motivation of our work is what happens with (I) when, required by association with neural networks, KRR is replaced with GD or an even more general learning algorithm.
Importantly, a result of the type I may give precise insights for the family of power-law spectral distributions, closely related to capacity and source assumptions non-parann non-parametric statistics:
A 1- (with > 1), of ~- (with
0).
Power-lav conditions exhibit a rich picture of convergence rates. For the case of noisy observa- tions 2 > 0, (Caponnetto & De Vito 2007) gives minimax rate O ( For noiseless obser- vations ²² = 0, the optimal estimation rate significantly improves (Bordelon et al. 2020 Cui al. 2021 becoming ONN-*), However, the optimal rates are not always achievable for some classical algorithms. For example, in the case when > in the noisy case the rate of the KRR becomes

---

Published as a conference paper at ICLR 2024
Noisy observations o² > 0
Noiscless observations
KRR
GF & Optimal
KRR & GF & Optimal
Exponent in L O(N #)
2v 2x+1
2v
x+1
Spectral localization scale s
x+1
M {0,
2v+1
V/
Universality
yes
yes
no
Our results for power-law spectral distributions 2 and three algorithms: optimally regu- larized KRR, optimally stopped Gradient Flow (GF), and the optimal algorithm (see Section For quantities exhibiting saturation 5 2, the vertical line -|- separates saturated and non-saturated y values. The spectral localization at scale s means that the error is accumulated at eigenvalues À of the order N (see Section 5.1). the last line, by universality, we mean the asymptotic equality of the errors for different problems with the same population spectrum Aτ Ct While we show the universality only for our two data models, we would expect it to hold for a broader class of data models.
Table I:
O(N INNT) ) i.e. KRR doesn't attain the minimax lower bound (Li et al. 2023). Such effect is usually called saturation and is well-known in various non-parametric problems (Mathé 2004] Bauer et al., 2007). However, the saturation effect can be removed with algorithms other than KRR, for example spectral cut-off (Bauer et al. 2007) or gradient descent (Pillaud- Vivien et al. 2018). In
noiseless case, (Bordelon et al.) 2020; Cui et al. 202I) show saturation at the same point " 2, with the rate changing to O(N 2r). Whether noiseless saturation can removed by algorithms
other than KRR, to the best of our knowledge, was not studied in the literature.
Our contribution. In this work, we augment the above picture in several directions, as summarized in and the following three blocks
Loss functional. In Section 3 we introduce new kernel learning framework by specifying the learning algorithm with spectral profile l(A) and expressing the generalization error as a quadratic functional of this profile. While specific choices of h(A) can give KRR, Gradient Flow (GF), or any iterative first-order algorithm, we go beyond these classical examples and consider the optimal learning algorithm as the minimizer of the loss functional for given problem.
The models. As the loss functional is problem-specifee Wishart-type model with Gaussian features and a translationallinvariia model on a circle. In Sec- tion 4 we derive loss functionals for these models. In addition, introduce simple Naive Model for Noisy Observations (NMNO). In the presence of observations noise, for reasonable learning al- gorithms, and at least for power-law spectrum, NMNO model gives asymptotically exact loss values for both Wishart and Circle models despite their differences. This suggests a possible universality property for larger family of problems, including our Wishart and Circle models as special cases.
consider two different models:
Results for plwer-law spectrum. In Section S we reach specific conclusions by restricting both kernel eigenvalues and the target function eigencoefficients be described by power-laws
For both noisy and noiseless observations, we derive full loss asymptotics. While the re- sulting rates are indeed consistent with the prior works, precise characterization of leading order asymptotic term gives access to finer details, such as the shape h² (A) of the optimal learning algorithm.
We introduce the notion of spectral localization - the scale of kernel cigenvalues over which the loss is accumulated and quantify it for algorithms under consideration. In particular, this perspective provides a simple explanation of KRR saturation phenomenon as the in- ability sufficiently fit the main features of the target function.
By characterizing the shape of the optimal algorithm, we point to the cases where it optimal to overlearn the training data, akin to KRR with negative regularization. Moreover, we specify the values of power-law exponents at which overlearning is beneficial.
2

---

Published as a conference paper at ICLR 2024
2 SETTING
Generalization error. We evaluate the estimator f(x) with its squared prediction error [fxx
f [x)),, averaged over inputs drawn from population density p(x), and then all the randomness in training dataset Dx:
レ 2 EDN 1 1-1111==
2 EDN.e [f(xx) (xx) p(x)x
(3)
where e (f.g) = (x)xxxx)
NOO, D), ||/| = (J, and angle brackets denote the scalar product
Population spectrum. Central to our approach is the connection between generalization error L and spectral distributions À Ct of the problem, defined by Mercer theorem as
x(x,''= Σ (x)
fx) Σ cioi (Ó1, uw
(4)
Here, A are the kernel eigenvalues, c are the target function coefficients, and (x(x) are the eigen- features of the kernel. In the most interesting scenarios, the number P of features øi is infinite, and the respective eigenvalues X ++ as I oc.
In this work, we aim at two levels of results w.r.t. the population spectrum Az q, First, we want to obtain a characterization of 7 for a general Aς, ct similar what is done in the classic result (I] Second, we will assume the power-laws ( to obtain more detailed description of the generaliza- tion error Lp.
An important object is the empirical kernel matrix K E RNNN composed of evaluation of the kernel on training points (K)i xy), Let additionally denote by y f + E RV the observation vector with components (y); = (x;) + e;; by A E RPx' the diagonal matrix with (A)u = A and by & E R-xx the matrix of kernel features evaluated at training points, i = (x,). Then, spectral decomposition (4) allows to write empirical kernel matrix as
K "
(5)
Data models. A standard approach to analyzing the generalization error consists in considering general families of kernels K X(x,x' x') and targets f (xx). typically defined by regularity assumptions, and deriving upper and lower generalization bounds (c.g., see (Caponnetto & De Vito 2007)). We adopt a different approach that allows us to go beyond just the bounds and describe generalization error I.5 with more quantitative detail. To this end, we consider two particular models, Circle and Wishari, that represent extreme low- and high-dimensional cases of the kernel learning setting.
Wishart model. This model a common choice for our setting: it was explicitly assumed (Cui et al. 2021 Jacot et al.) 2020b Simon et al. 2023) and is closely related to settings of (Jacot al. 2020a; Bordelon et al. 2020 Canatar et al., 2021; Wei et al. 2022). Specifically, assume that the kernel features (x) and data distribution p x are such that feature matrix & has i.i.d. Gaussian entries: (x;) ~ (0, 1). Then, the resulting empirical kernel matrix in (5) is called Wishart matrix in Random Matrix Theory (RMT) context. Intuitively,
think about Wishart model as a model of some high-dimensional data with all the structural information about data distribution and kernel being wiped out by high-dimensional fluctuations.
Circle model. To describe the generalization of a kernel estimator trained by completely fitting (i.e. interpolating) training data, SSpigler et al. (2020) and [Beaglehole et al. (2023) used model with translations-invarian kernel and training inputs forming a regular lattice in a hypercube. In this work, we consider, for transparency, a one-dimensional version of this model. Yet, the one- dimensional version will display all the important phenomena we plan to discuss. Specifically, let
inputs come from the circle x E S R mod 2x, and the training set DN = {u + 2mi N Here, an overall shift of the training data lattice, which we sample uniformly u 10, 2x)) to introduce some randomness in otherwise deterministic training set Dy. Then, the kernel and the target are defined in the basis of Fourier harmonies as
N Ji=0
0c
K K(I, x') = Σ
Xre ill-ax''
f*(x) = Σ
qe
(6)
10-00
We assume \ X-1 E R and C-1 = q ensure that both the kernel and the target real-valued.
3

---

Published as a conference paper at ICLR 2024
3 SPECTRAL ALGORITHMS AND THEIR GENERALIZATION ERROR
Several authors, e-g. Bauer et al. (007)) : Rastogi Sampath (207) Lin et al. (020), considered
Spectral Algorithms to generalize and extend the type of regularization performed by classical meth- ods such as KRR and GD. Indeed, both KRR and GD fit observation vector y to a different extent in different spectral subspaces of the empirical kernel matrix K. For spectral algorithms, this fitting degree is specified by a profile ((A) so that the estimator is given by
f(x) = 1(x)xxxx 10( K)y.
Here k(x) E R. has components (k(x)); = K ((x,x.) Function h(A) is applied to the kernel matrix $ K in the operator sense: h(-) acts element-wise on diagonal matrices, and for an arbitrary positive semi-definite matrix with eigendecomposition A DUDU we have h(A) UTh(D)U
Let us show how classical algorithms can be written in the form with a specific choice of h(A):
1. Kernel Ridge Regression with regularization vj is obtained with (2) X Then, 7
transforms into the classical formula for KRR predictor: f(x) = ((x))((K + Not) N 'y
- (For this and the next example, 2. Gradient Flow by time f is obtained with (A) = 1 1- E 1A,
we provide the respective derivations in Section B.1
3. For an arbitrary general first-order iterative algorithm at iteration 1, h₂(A) is given by the associated degree-l polynomial with he 0) (see Section B.T. For example, GD with a learning rate a is given by (A) = - (1 ax)*.
Now, we make a simple observation that is crucial to the current work. Note that generalization error is quadratic in the estimator f. while f is linear in h according to 7 Thus, for any problem, the generalization error is quadratic in the profile h. This observation is formalized (see the proof in Section A in
Proposition 1. There exist signed measures p dd2), (d2) and (d)) (given in equa-
tions 37 - (39 such that the map h + f + Li given by is expressed the quadratic
functional
- |/ M(NI) d22) 2 h(N) + 11
L(h]
(8)
+ 2 N / (2(
1
We will refer to the measures (()) 22)) and (()) as the learning measures. Proposition shows that the loss functional is completely specified by these measures. 'he first line in (8) describes the estimation of the target function from the signal part f' of the observation vector y. which
hindered by insufficiency of N observations to capture fine details of (x)). Similarly, the second line in (8) describes the effect of (unwanted) learning of the noise part E of observations y.
The functional (8) makes the relation between the learning algorithm ((A) and the generalization eтror maximally explicit. However, properties of the underlying kernel and data are reflected in the learning measures pl2 dd2),, ( (dX) and (dX) in fairly complicated way. In Section A show some general connections between the kernel cigenvalues A, the features Φy (x(x), and the learning measures. Yet, the explicit characterization of learning measures is challenging even for our two data models, and constitutes the main technical step of our work.
Optimal algorithm. Consider a regression problem and associated loss functional 8 Since the loss functional is positive semi-definite, under suitable regularity assumptions it has a (possibly non-unique) minimizer
h" (*(A)= arg min [A]
(9)
that achieves the minimal possible generalization error in a given problem. We refer to the spectral algorithm with profile h²* (A) as optimal. In the context of models with llw spectra, we will also speak of optimal algorithms in broader sense, those providing the optimal error scaling with N. We will analyze the conditions of optimality in the Circle and Wishart models and show that in the noisy setting they have the same structure, easily understood using simplified loss model.
4

---

Published as a conference paper at ICLR 2024
4 EXPLICIT FORMS OF THE LOSS FUNCTIONAL
Circle model. The main advantage of this model is that it admits an exact and explicit solution. Below, we describe its main properties, with derivations and proofs given in Section D
Due to the fact that training inputs x; form regular lattice, the eigenvalues X of empirical kernel matrix K become deterministic: A -----o -00 Nn Behind this relation is the learning picture based on aliasing. For a given k E 0, N - 1, the information about the target function contained in all Fourier harmonics with frequencies 1 = k + Nn, E Z is compressed into the single k-th harmonic, and then projected back the original 1 k + Nn harmonics of the estimator f. This leads to a transformation of population quantities X/1 [| 2 that we call N Nedeformation:
00
20
Σ
12t Ni+Nnlc++Nal
(10)
It is periodic: [X] (//l// =
NNi Also, d = [
Then, we have
Theorem 1. Loss functional of the Circle model is given by
N-
[AE] [Au]
Dulce 21 [
Lih] = Σ
( [eal
(2x)
((xa)) + [[cx| [ccxl2]
(II)
The special feature of the loss functional (IT) compared to the general form (8) in that there are no off-diagonal λ # X2 contributions to the loss. Then, the optimal algorithm is found by a simple point-wise minimization:
he" (Ax) [Aalek/P]NG NN IN + [ PAR
(12)
Wishart model. This model, although more common in the literature, does not enjoy an exact solution like the Circle model. However, using two approximations, in Section explicit form of the measures p!2), (()), p(s) describing the loss by equation 8 We give
E
we derive an
outline of our derivation.
First, we point out that the learning measures from (8) can be reduced to the first and second moment of the imaginary part of the resolvent R(2) = (K =I)- computed at the points x = > i0 near the real line. Then, we make standard RMT assumptions to describe the resolvent in terms of the Stieltjes transform r(z) of spectral measure K, which satisfies the fixed-point equation
Σ r(2)AL N
1 = 22(2) +
(13)
r(2)A++
The first resolvent moment is computed straightforwardly and the second moment at the same point 22 can be computed with differentiation trick (Simon et al. 2023), but for the second moment at 21 * 22 a new tool is required. For that, we employ Wick's theorem of computing averages over Gaussian fields, where we take into account leading order pairings and neglect subleading O(N
terms. The above procedure expresses the moments of R(z) in terms of three auxiliary functions
Xie
X?
m(z)) -x+r((
u(=) = -x+r((3
w=(2) Σ
x
(14)
Finally, we obtain loss functional (8) by specifying each of the learning measures. Using the notation 3(=) for imaginary part of we find first moment of signal measure and the noise measure to be
(ds) Su(A)
(de
3w(A)
(15)
dA
πÀ
dA
πス
The second moment of signal measure has diagonal X X2 and off-diagonal \ * Xa parts (12) (dX1, r (A1)12
3(v(A)))8(A) A22)
ddid/2
(16)
1 3fu(de) 3f(r)(a))) 3(
x 222112
A d2
5

---

Published as a conference paper at ICLR 2024
== 0.5
==
KRR p -itc
with t= Na
KRR with n- N (saturation)
with = N
-.- CV
CV
10'
10'
CN-slen
10:3
10-1
10:11
10
10-4
10-4
Gustar N-teGee
10'4
10a4
Czada N N-1dtt
10*4
101
10
10
10
10'
107
101
101
10a
101
10
10'
Wishart
Cosine Wishart
NMNO (Wishart Cosina Wishart)
Circle
NMNO (Circle)
Figure 1: Generalization error of different data models in presence of observation noise converges to our NMNO model (solid) as N + which in turn converges to its O(N=#) asymptotic (dashed). plots have = 1.5. Cosine Wishart an additional data model not covered by our theory yet converging to NMNO. The difference between Circle and Wishart asymptotic the plot 3 is duc to localization the error on scale 0 at saturation. For details and extended discussion see Sec.
Non conn-sauuaate KRR: 7:20
Non-saturated KRR; n=1
Saturated KRR: n-0
Scales
Noise
learnnng
Error scales
Signal
learning
3113
Noise
after leamning
Signal
after leaming
Total
localization
eigenvvalue
eigenvalie
Scale diagrams of different KRR regimes for noisy observations. All plots have v 1.2, while x = 1.0 in the non-saturated case (left and center) and = 5.0 in the saturated case (right). The dotted lines represent the noise 1 and signal K terms in equation (18). The solid lines show the same terms with added components (h) and (5(1~A), Left: the sub-optimal (8h > 8.) non- saturated case. Center: the optimal (8%, s.) non-saturated case. Right: the saturated (n 2v) case with the choice 8n 2041 optimal for KRR, but sub-optimal among general algorithms h.
Figure 2:
Naive Model of Noisy Observations. As we can see from results for Circle and Wishart model above, the loss functional of given model can be quite complicated. We will see, however, that in the presence of observation noise x² 0 the asymptotic (N - co) generalization properties of both these models are well described by a simple artificial model (NMNO), introduced below. We conjecture this match to be universal phenomenon, valid for wide range of models.
For a large dataset sizes N, we expect all the complex details of the problem to be concentrated eigendirections I with small A₁ whose features (x) can not be well captured by the empirical kernel matrix K of size N. On the contrary, K should succeed in capturing (x(x) with moderate A and empirical and population cigendecompositions should be close each other.
Let us therefore assume that we can ignore the small eigenvalues and determine the generalization error only using components with moderate A (later, we will explain this by loss localization at moderate spectral scales). Then, the contribution of the 1-th component to the generalization can be approximated by (1 o for signal fitting part, and o² observation noise. This completely determines the associated loss functional. Let us describe the ps
x h²2()) for the learned
population spectral data λι, ar by the spectral eigenvalue measure px (dX) = Σr dx, (dA) and the
coefficient measure (ddd) Ex, (dA). Then, define the NMNO model by the functional
a² 2N
1 j (1- (c(A))
L [nmno)
(2(W))) +
(17)
Aniia
Auiin
Here, Amin is reference minimal population eigenvalue defined by the condition /l ([Amin (i.e., such that the segment [Amin; contains exactly N population eigenvalues).

---

Published as a conference paper at ICLR 2024
5 RESULTS UNDER POWER-LAW SPECTRAL DISTRIBUTIONS
In this section we perform a deeper study of the Circle, Wishart and NMNO models of Section 4 in the setting of power-law distributions 2 Prioritizing transparency over generality, we assume Ar Ct to be exact power-laws in the form convenient for a given model. Specifically, for Circle model we take X (14) 1)-" and le. (14) 1) -x-1, while for Wishart model we assume continuous
analogs of these spectral distributions, namely assume them to have smooth densities supported on
[0, 1]: (x(d))= = _ - dY and po(dX) = _ dd.
5.1 SCALING ANALYSIS AND ITS APPLICATION TO THE NMNO MODEL
Under power-law spectral assumptions, it is key observe that various important quantities scale as suitable powers of the training set size N. In general, given sequence aN, we will say that it has scale s if for any e > 0 we have |ay] o(N str) and aN w(N "-9). If only the first or the second condition holds, we say that the scale of aN is not less or not greater than s (respectively).
Suppose that gNv (A) is sequence of functions on the spectral interval (0, 1]. We say that this sequence has sealing profile S(9) (s), 2 0, if for any sequence AN E (0, 1] that has scale the sequence 1gN (Ax) has scale St() (s). It is easy to check that the scaling profile, if exists, is continuous function of s (see Lemma 1p. The basic example of a sequence of functions having
scaling profile is the sequence gN (A) = Na with constant a, b; in this case S(9) (8) = bs a.
Integrals of functions with a scaling profile also have specific scaling:
Proposition 2 (see proof in Section C.. Let (N be a sequence of functions with a scaling pro- file (s)),,, and let aN > be a sequence of scale a > Then, the sequence of integrals Saw 1gN (A)ldd has scale minos.sa a)) (s)+
When prop. 2 can be applied to the functional 8 we call the set Stor = arg ming (S())) +s) of scales which dominate the loss integral as spectral localization scales of the generalization error. In the rest the paper, we reserve the letter to denote the scale of eigenvalues A.
Application to NMNO. Now apply the scaling arguments to the NMNO model 17 for which will be easy to find explicit optimality conditions. Suppose that the problem has either discrete or continuous power-law spectrum with exponents
as described above for the Circle and Wishart model. Then, Amin in equation (17 has finite scale v. Suppose that the functions h and 1 - have scaling profiles ((h) and 5(1 Then, applying Proposition in the continuous case or analogous Proposition 5 in the discrete case, we obtain
Proposition 3. The NMNO loss [mmmo)))h] [h] has scaling
Sumno
min USa5v
(1 (1- + 25th A (5x 25( (5))-
(18)
Here, min; the first and second arguments in A come from the noise and signal terms in (77 respectively. In the continuous case use the fact that -
has scaling profile
s(1 + () 25th) while x-/v-1(1 (el1-h(Mg) (a)))² has scaling profile s 1) + 25(1-N)
Clearly, for any particular s only one of the values ((h)(s) and ((1-h( can be strictly positive. This implies a bound on feasible loss scalings:
gummo [M] < min
((1 - V 1
(19)
ose5v
x+I
The minimum here is attained the scale 8, -ー Moreover, an algorithm h attains the optimal
scale x+T exactly when for each E [0, we have -1- 2 ^ ( s 25((1 (s)) 2 ल
Proposition 4. Sumno ~ and the equality occurs when 1) ( (s) [ + for
8 2 ~ and 2) s(1-h)
( 5s) for $ S..
These results provide simple picture of spectral algorithms close optimality for the NMNO
model: one should choose the spectral function h that [л())] $ NI for X S N .+

---

Published as a conference paper at ICLR 2024
R and so that |1- h(A) S N X 20 for X 2 N2NN*+ as the loss localization scale for the optimal algorithm.
V x+1, The value can be referred to
Let us apply the obtained conditions to KRR and GF. KRR with regularization v has (2, = X+1 Suppose that ry has scale S1y then h, has the scaling profile (s) (s -s,) V 0, while 1 h 1, we see that condition 1) in Proposition 4 is satisfied iff $, S 8. *+11" Condition 2) more subtle: if & &.
A
=h_ and has the scaling profile ((>-)(s)) (s) = (s,, - 5) V O. Recalling that equals X4-7
2" I 1, then it is satisfied iff Sn 2 Su, but in the case 2 1 is rather satisfied iff Sn - 1[x++)- We see, in particular, that in the case 2v while in the case 2 > they cannot be simultaneously satisfied (and so KRR cannot achieve the optimal scaling x+I/ an effect called saturation (Mathé) 2004 Bauer et al.) 2007). See Figure 2
x < 1 conditions 1) and 2) are simultaneously satisfied iff sn = 8,,
for illustration. In contrast, GF (A)
-A has saturation: choosing to be of scale -s, satisfies both conditions of Proposition for all v > and k > O.
5.2 NOISY OBSERVATIONS AND MODEL EQUIVALENCE
For our two data models, Circle and Wishart, the intuition behind the NMNO ansatz can be rigor- ously justified by showing that this ansatz represents the leading contribution to the true loss. For instance, consider the circle model with loss functional[ specified by (TO). The empirical eigen-
values Å = [> = A + O(N for |k] < .N22, so the scale v of the correction [Λx - Au is higher than the scale s of the eigenvalues A except for the eigenvalues of the highest scale v. This shows that the empirical and population quantities are significantly different only on the highest spectral scale = Continuing this line of arguments, we get
Theorem 2. Assume that the learning algorithm (A)) is such that h(X) and 1 - h(A) have scaling profiles 5(h and (s). Assume that the maps log X + log [h(A] and log À + log | are globally Lipschitz, uniformly in N. Then, if = s is not localization point of NMNO functional
I, [mmnn)) [h, Circle model specified by 11) and Wishart model specified by (6) 15
are equivalent
to the NMNO model in the limit
OC:
T, [(mmno) [h] = I. (circle) [1] + (1)) = T, (wishart)) [b] + o()).
(20)
We prove the theorem separately for Circle and Wishart models in Sections D.2 and E.3.3 Note
that the condition of equivalence is specified using only NMNO model. Thus, if satisfied, it allows analyzing the simple functional (17) instead of the more complicated ones (I6). (15) and (TT). The requirement that s is not a localization point is reasonable as the heuristic derivation of the NMNO model in Section 4 included an assumption that the loss localized at moderate scales.
5.3 NOISELESS OBSERVATIONS
We focus on Circle model to describe main observations, with derivation deferred to Section D and Wishart model results deferred to Section Let us write the loss functional perturbatively
Ick 2 (1 ((7)) ( + N x (00))
L[h]
Σ
+N
(21)
2
k==1
small parameter. From this, make several observations. First, take h = h" Then, i < 2v, the loss localizes on s = y (i.c. the sum is accumulated at [k] ~ NN and has the rate O(N-*). This rate is natural and reflects that we are able to learn target function everywhere except at inaccessible scales À < ~ Moreover, by examining the first term in (2T). we see that this rate is not destroyed by learning algorithms sufficiently close to the optimal: Ih(As) - ht- (A+) o(r*).
with 7 = [k|+1
N
The situation changes dramatically for к > 2v: the optimal loss L[h"] becomes dominated by 0(r"-=x11) term in (21) and localizes at = 0 (i.e. the sum is accumulated at [k| ~ 1), changing the rate to ONN 22).. We call this behavior saturation since it has features similar to KRR saturation effect for noisy observations: transition at However, noisy KRR saturation is algorithm- driven and can be removed by replacing KRR with GF, while saturation in 21 persists even for optimal algorithm h² h*(A). Interestingly, the optimal
2v; change of error rate; localization
O.
8

---

Published as a conference paper at ICLR 2024
2.0
200
233
120
125
123
101
036
6:72
Ooe DaeeBee c-3-)
125
025
60
A.
11"
Optimally stogped
Optmally reguirriedd KRR
The optimal algoritim
Intorpolaion
Figure 3: Generalization error (left) and profiles I(A) (right) of various algorithms applied to the Circle model with = 1.5 and noiseless observations with different s. Before overlearning transi- tion & = V/ - optimal algorithms underlearn observations (h(A) < 1) while starting to overlearn them (A( > 1) after the transition. For details and extended discussion see Section
loss in the saturated phase can be achieved (asymptoticalll) by KRR with negative regularization: L[h*] - + o(1)), 1f" Denoting Riemann zeta function as {(a), we have
1 L. T 2 (n 2(()))²+2((2)))
cc
2
N- 0-22(1 + (1))))))
(22)
with minimum at 17" -2( The benefit of negative regularization was empirically ob- served in (Kobak et al. 2020) and theoretically approached in (Tsigler & Bartlett 2023). Within our framework, KRR with negative regularization be thought of as special case of overlearning the observations.
In fact, overleaming also occurs in the 2v phase. In Section D.3 we show that the loss functional
can be asymptotically written (see (38) using
[k|+1 for (continuous) eigenspace indexing, for
N''
example X, <- Xx. Then, denoting Hurwitz zeta function as 2(), the optimal algorithm becomes
1e* (Rx) c (1)
c(a) = [(or + ((ar, 1x)).
(23)
The optimal algorithm 23 has an intriguing property (see also Figure 3): it interpolates the data h" (A) = when ς V K. In other words, for hard targets with the observation is required for optimal performance. But, for easier targets with becomes optimal to overlearn the training data contrast to conventional wisdom. The same holds for Wishart model (see Sec. E.3.4). Thus, we identify the point 1 overlearning transition.
1, and, otherwise, the sign of 1 h- coincides with the sign of
1, classical regularization by underfitting
it
6 DISCUSSION
We have extended results of type 1 to general spectral algorithms, as given by our loss functional for Circle model and (5)) 16b for Wishart model. It allows address questions that require going beyond specific (KRR.GF) algorithms. For example, we show that the nature of saturation at 2v different for noisy and noiseless observations, with the latter being an intrinsic property of the given kernel and data model, and can not be removed by any choice of the learning algorithm.
Our formalism of spectral localization and scaling, while being compact, provides a simple and transparent picture of the variety of convergence rates under power-law spectra distributions. Also, the equivalence result between our two data models and naive model of noisy observations (17) relies on the straightforward estimation of the scale of perturbation of population quantities by finite size N of the training dataset. Thus, an interesting direction for future research would be to check whether the equivalence holds for other data and kernel models.
CN-##1 #1 + o(1)) compared to the rates L = O(N-#) In this work, we used the full asymptotic obtain the shape of optimal algorithm h² (A). In the noiseless case, the knowledge of h (A) allowed us to characterize the overlearning transition at
Finally, let us mention the advantage of full loss asymptotic
1. which otherwise would be invisible on the level of the rate ONN~*). Investigating whether x = v 1 remains the point of overlearning phase transition for more general data models is an interesting direction for future research.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Eric Moulines for insightful discussions during the initial stage of the work.
REFERENCES
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory, Journal of complexity, 23(1)52--7,, 2007.
Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. On the inconsistency of kernel ridgeless regression in fixed dimensions. SIAM Journal on Mathematics of Data Science, 5(4):854 872, 2023. doi: 10. 10.1137/22M14999819
Blake Bordelon, Abdulkadir Canatar, and Cengiz. Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization kernel regression and infinitely wide neural networks. Na- ture Communications, 12(1). may 2021. doi: 10. 10000///4447--01-2330005
https:
//doi. org/10 1 03882FFFFF 414444446666200 457-222344
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm.
Foundations of Computational Mathematics, 7:331-368, 2007.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143, 2021.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: empirical study of loss landscape geometry and the time evolution the neural tangent kernel. In Advances in Neural Information Processing Systems, volume 33, pp. 5850-5861, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL htt.tpsss/pprrcceeeeeeeeeee ngs. neur ps. cc/aaper
www.eerwr........oo..oeeeee pdf
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Ker- nel alignment risk estimator: Risk prediction from training data. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33. pp. 15568-15578, Curran Associates, Inc., 2020a. URL httttss:/pprcceeeeee
neurips ct cc/ppper.pp.p...c.e serrrrfllessee ftl.es//ppper//20/// htt.
File
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit regularization of random feature models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4631 46400 PMLR, 13-18 Jul 2020b. URL https: http://///pccceeensns... v stress/v119/aacot200. html
mlr. www.ppeessvvvl
Hui Jin, Pradeep Kr. Banerjee, and Guido Montufar. Learning curves for gaussian process regression with pawer-law priors and targets. In International Conference on Learning Representations, 2022. URL httpttt::/::/errretete
net./ forum? d=Ke -
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21 (1)663633 -6778 2020.
10

---

Published as a conference paper at ICLR 2024
Dmitry Kopitkov and Vadim Indelman. Neural spectrum alignment: Empirical study. In Artificial Neural Networks and Machine Learning- 2020: 29th International Conference on Artifi- cial Neural Networks, Bratislava, Slovakia, September 15-18, 2020, Proceedings, Part II 29, pp- 168-179. Springer, 2020.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): 124002, dee 2020. doi: (0.1088/172-54466aaaa 2F1 1F1772--2 54688 F2a58882abb6222
URL https: /tttps://ee... htt.eei..rggg/// 1088
Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations, 2023. URL https://
openreview net. www.oooooonuurrrroorrroro
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Har- monic Analysis, 48(3):868 890, 2020. ISSN 1063-5203. doi: https://do..or//00.011/// acha.
2018.09.009. URL https: /ww. sci encedi rect com ccnm/science/artticlee//
510655203 83001
Philip M. Long. Properties of the after kernel. ArXiv, abs/2105. 2021.
Wesley Maddox, Shuai Tang, Pablo Moreno, Andrew Gordon Wilson, and Andreas Damianou. Fast adaptation with linearized neural networks. In International Conference Artificial Intelligence and Statistics, pp. 2737-2745. PMLR, 2021.
Peter Mathé. Saturation of regularization methods for linear ill-posed problems in hilbert spaces. SIAM journal on numerical analysis, 42(3):968 1118899733110 2004.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Loucas Pillaud- Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gra- dient descent on hard learning problems through multiple passes. Advances Neural Information Processing Systems, 31, 2018.
Abhishake Rastogi and Sivananthan Sampath. Optimal rates for the regularized learning algorithms under general source condition. Frontiers in Applied Mathematics and Statistics, 3:3, 2017.
James B Simon, Madeline Dickens, Dhruva Karkada, and Michael Deweese. The eigenlearning framework: A conservation law perspective on kernel ridge regression and wide neural networks. Transactions Machine Learning Research, 2023.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment. 2020(12):22401,, dec 2020. doi: 10. 1..108//72--445//accllll URL https:///
5468/abc61d.
dx.doi wtt.i...rg/lli 100.:..1111111111 5468/ abc6ld
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24:123,,, 2023.
Nikhil Vyas, Yamini Bansal, and Preetum Nakkiran. Empirical limitations of the ntk for understand- ing scaling laws in deep learning. Transactions Machine Learning Research, 2023.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning, pp. 23549-23588. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
2
Setting
3
Spectral algorithms and their generalization error
Explicit forms of the loss functional
5
Results under power-law spectral distributions
5.1
Scaling analysis and its application to the NMNO model
5.2
Noisy observations and model equivalence
Noiseless observations
8
6
Discussion
References
10
Spectral perspectives
13
Population perspective: transfer matrix
13
A.2
Empirical perspective: learning measure
14
Joint population population-empirrcal perspective: transfer measure
15
Gradient-based algorithms
16
B.1 Kernel form of predictors
16
B.2 Implementing spectral algorithms with a pair of Gradient Flows
...........
Scaling statements
18
D Circle model
20
D.1 Loss functional
20
D.2
Power-law ansatz: noisy observations
................................
23
D33
Power-law ansatz: noiseless observations
25
D.3.1
Perturbative expansion of the loss functional
................................
25
D.3.2
Optimally scaled learning algorithms
26
D.3.3
Saturated phase x > 2
................................
28
D.3.4
Non-saturated phase x 2v
30
D.3.5
The overlearning transition point
30
E
Wishart model
31
Resolvent
32
E.1.1
Computing the resolvent moments
33
12

---

Published as a conference paper at ICLR 2024
Loss functional
37
Power-law ansatz
39
E.3.1
Solving fixed point equation
40
E.3.2
Learning measures
42
E E.3.3
Noisy observations
44
Noiseless observations
46
Experiments
47
Figure
details and discussion.
47
F2
Figure
3
details and discussion,
49
Cosine Wishart model
50
A SPECTRAL PERSPECTIVES
In this section, we show general relations between generalization error 3 population spectra Àτ, et and learning algorithms h()). Recall that profile h(A) is applied the eigenvalues of the kernel matrix K (i.c. values of the kernel function evaluated on the training dataset Dv). Therefore, relating generalization error and ((A) involves the properties of the empirical spectrum: eigenvalues of K and the related eigendecomposition of the observation vector y.
With these remarks in mind, we may say that we are dealing with population and empirical per- spectives on generalization eтror (3). We start with population perspective in Section A. which
behind the classical result ( Then, we proceed with the empirical perspective in Section A.2
which basically amounts to proving Proposition I introducing learning measures p(2) (10) ple)
Finally, In Section A.3 we combine population and empirical perspectives. While probably less conceptual than the first two perspectives, the joint population-empinee perspective an essential
step in our derivation of the loss functional for the Wishart model.
A.1 POPULATION PERSPECTIVE: TRANSFER MATRIX
A central object for the population perspective is the transfer matrix Tiv introduced explicitly, for example, in (Simon et al. 2023) in the context of KRR. Specifically, let decompose the predic- tion (7) over kernel eigenfunctions (i(()) as f(x) Σ, (xo(()). Then, the prediction coefficients can be written as
=
Σ Twer + oe,,
Pur > (
a = (
(24)
where di is the vector of eigenfunctions computed at the dataset inputs ( = = (r(x;,, and (s); = is the vector of observation noise. Note that the transfer matrix Tw has clear interpretation of the rate at which the information cv contained spectral component l' transferred to spectral component l. The population noise component ě describes how much of the of the observation noise e was learned in the /-th population spectral component.
The population loss 3 (sometimes we use this term synonym to generalization error) is straight- forwardly expressed through the first and second moments of the transfer matrix, and the variance of population noise components
L== ED.. Σ
C a) 2=)=
1
Σ ci 4
Σ
(2)
2T 51,1)) 2N Livi,
o² Σ
0
(25)
13

---

Published as a conference paper at ICLR 2024
where
T EDN Tiv
(26)
(2) EDN
TTge T15l2
(27)
6
(2) NED. (()))=((())]]))) -DN
1 Xi N o7 ((* h K)
)²
(28)
The representation (25) makes the most explicit dependence of the loss on population coefficients a, while the dependence on the learning algorithm h(A) and population eigenvalues A hidden
inside moments TPr 2r(3) 15,2 of the transfer matrix and noise variance e/²) Yet, for the case of
KRR the results ①I shows that the dependence A can be made fairly explicit.
A.2 EMPIRICAL PERSPECTIVE: LEARNING MEASURE
As this perspective focuses empirical spectrum of kernel matrix and observation vector, start with writing eigendecomposition of K, f" y de and as
N
K N
up uf
uf ug
duks
(29)
k=1
N
1
CK
Uk
(30)
k=1
Uku
(31)
where in the last line EN are i.i.d. normal Gaussian because orthogonal transformation to empirical eigenbasis {ux leaves the distribution isotropic Gaussian vectors E (N 1) unchanged.
Then, inserting spectral decomposition 29 of the empirical kemell matrix into the prediction gives
fx(x) (k(x))
2'
1
m(dx)) Nn
h h(Ax)
(k(x))
u
u
m1
N
N
k=1
(32)
-f ((2))t
dd) + VN
(11)) (x, (x,d)), dA),
where x (x, dA) and g (x, dA) are target and noise learning measures:
N n
(x, dA) (k(x))* T
f
(33)
1 VN
(k())
(x, dA)
8%
(34)
The target learning measure defines what pattern is learned from the target function at the neigh- borhood dA of the empirical spectral position X. Similarly, the noise learning measure defines the patterns of the noise learned in the neighborhood of X.
14

---

Published as a conference paper at ICLR 2024
As for the population perspective, substitute the expression of prediction in terms of learning measures 32 into the population loss (
f EDN.. oF /// MANDDL VN 2
(AA)D (x))), ((x)
-1 1
/ h(AI)M(A)) (x, d( pin)
-2 2
- -2 / (f (I ax)) + (x),,
(35)
EDN ( ( h(A)) /
(x, ds))
VN
o²
/ J MAn)) (p (x, dAn), To d2z))
N
Now, observe that the term in the second-to-late line in (35) is linear in noise learning measure averaged over e which is zero: Eeple) dA) = VN Ex= (k(x)) un 8x Ege2 = 0 since E& = 0.
Similarly, taking the expectation over observation noise helps to simplify the last term
(u k(x), uf k(x)) E, Ekp
(p(e)) ddi), (x, (x,2)
Σ
8znn (d (dd2)
Nd1d2
11
(36)
uu k())ll
= -x (d)2)
5x (d12)
N
X2
where we have used E5,, kky k2. Now, one can recognize the loss functional stated in Propo- sition[] [ the first 3 terms and the last term of (35) correspond to the respective terms of In other words, the learning measures announced in Proposition are given by
(dA) = EDx
('(x),700xx, da))]= (xx0 dAI), (1))ppp000 1x, d(x)))
(37)
(dA ddz) = EDN
(38)
2
(d2) EDN
8%
(39)
X2
Again, the loss functional 8 represents the empirical perspective on the generalization error, mak- ing the dependence on the learning algorithm ((A)) very explicit. But, the dependence on the prob- lem's kernel structure and target function is hidden inside measures (d)) and (d)), dd2).
A.3 JOINT POPULATION-EMPIRICAL PERSPECTIVE: TRANSFER MEASURE
To combine to perspective described above, consider a 1-th spectral component of learning measure (ds) = (x), p()) (x, d')). Then, inserting decomposition 4 of the target function into target leamingg measure (33) allows to write
(dD) = (x)( pi) dx)) = Σ CuPir (d)):
(40)
where
A N
P (ax)
Σ
( un
(u Φr )
(41)
can be naturally called a transfer measure. Now, we insert decomposition 40 into 37 and
38 as well as population eigendecomposition (4) into 33 The scalar products in 37 and 38 become
(x), d2)) = M
( (dx) Σ
apll
accuply (dA),
I.
(42)
(x, (x,
Edt (axi))) (dDz))
Σ a C19PH ( (l1
15

---

Published as a conference paper at ICLR 2024
As for the norm ||u k(x)]| in (39) we can (((x), (k(x))²)
Σ Xi Di
(43)
Combining the expressions above and noting that (x))2 = Σ, of gives yet another represen- tation of the population loss in terms of the first and second moment of the transfer measure and population decomposition of noise variance measure.
Lbk]
1 2 11.22
Σ au
(f h(AA))(A2)
(12) - 2 ahs)
h(A)p)) (1) (dx) (d))) 61.12) a2 (44)
0²
(45)
2N
where
(1) (dA) EDN
Pir
(0 (dN)
(46)
Phrg (dd1, d22) = LED
(2)
Pith (d)) (dAa))
(47)
X 1
( (dx) EDN p
O uu 85
(48)
X
If the moments of transfer measure Pie (dA), Ph (dA1, d.2) and noise variance measure
(e) (dX) are known, the representation (44) connects spectral distribution λ1 ct of the problem and Pi learning algorithm ((A) with the population loss, thus justifying the name joint population-empirct spectral perspective.
B GRADIENT-BASED ALGORITHMS
The purpose of this section is two-fold. First, in Section B.1 we support our examples of h(X) provided in Section 3 with the respective derivations. This amounts to show that for linear models trained with gradient-basee based algorithm, the predictor during optimization form 7 with specific choice of h(A). Second, in Section B.2 try to connect general spectral algorithms specified by some profile (A)) with gradient- optimization, which not included in the main paper due to the space constraints. For that, we provide a simple construction based on a pair of GF processes.
be written in the
B. KERNEL FORM OF PREDICTORS
To consider gradient-based optimization for the kernel method setting discussed in the main paper, we need to introduce linear parametric model f(w,x) whose parameters will be updated during the optimization process. Starting with a kernel (xxxx') with population dccomposition (4), let us
define the model features (x(x) = (x). Then, combining the features in a vector (b(x) E RF, (vb(x), (x), the linear model is defined as
f(w, x) = (w, (x)), W W R.P.P.
(49)
For positive definite kernels P = 0o, and both model's features and parameters belong to RKHS HK of the kernel K: w, xx(x)= Hk.
The (neural) tangent kernel (Jacot et al. 2018) of the model 49 is given by NTK,(x,55 = (x),,), <b(x')) = E (xx' started with. Note that one can go in the opposite direction: start from the linear (49) and then define a kernel method specified by the tangent kernel (NTK) of the linear model. An especially interesting example of the latter direction is a (non-linear) neural network f( x) linearized at d resulting in fua ( x) f(Or. + (0 O.. Vef x)). If constant prediction f(0,, x) is ig- nored, the linearized neural network also described by (49) with gradients as the model features (x) Vof (0o, x) and the displacement from Og model parameters 0 Og.
K(x,'',, x'), thus reproducing our original kernel we have
16

---

Published as a conference paper at ICLR 2024
To finalize the connection between the parameter-based setting and Bernel-based setting from the needs to be trained by minimizing quadratic loss on train dataset Dy
main paper, linear model (49)
N
LDD (w)= 2N
Σ
(f(w, x.) -vi)
i=1
(50)
N
Σ
((w, xx(x)) - (w", (xxx)))== = 2 2 w*)"H( w*),
2N
where H = + N (x,, (xx) is the Hessian of the train loss. In the following, it will be convenient denote v the matrix of features calculated on the training dataset (4) 2by (x,(,,),, ). and use finite-dimensions notation for inner and outer product in the parameter space: i.e. the Hessian
H = N' T and empirical kernel matrix K & T. In (50), we have assumed that there exists a
w" parameter value w so that the model (49) completely fits the observations TTw" = y. Considering
the typical case P > N, this amounts to feature matrix having full rank rank V = N
Now, let us proceed with showing how gradient- based optimization fits into the family of spectral algorithms given by 77. We start with the basic example of vanilla Gradient Descent with learning rate o, having parameter update rule W = W, - a V. (w.). For the quadratic loss (50). this reduces W
W, - aHH w. w") = w" -I- (I-aH)(W:
w"). or, equivalently,
(51) Here we introduced the polynomial (A) (1 aA) that will prove useful notation in the following and is related to the profile (A) as (x() = 1 (A). To obtain the representation 7 for the learned prediction
W++1 - w (I aH) - w = (:H) - w")
(x) = (we, (x)) we additionally need to set wo
0. Then,
f((x) (w" " + Pa (wo w"), (x)) ( (H))) xbxx) (he (H)w", xb(x) (52)
Next, note that polynomial Pa(A) is often called residual polynomial due to its normalization at as (0) 1. or equivalently (0) The latter implies that we can write he Xg
with some polynomial (A) of degree t- 1. Using an algebraic identity J JJJ"JJ J "JJJ")
for arbitrary matrix J and polynomial allows us to finally obtain 7
f((x) = (Hq. (H)w", xx(x) = N
1
I T T qe( " TT )w" (x))
1 q 1 T 1 v w (xx)
(53)
N
1 k(x)
N qe Jy = k(x) ( K Kg (o K)y = (K he Kyy, K
1
where in (I) we have used that T w = and v (xx) k(x)" Thus, we have shown that for GD with learning rate representation 7 holds with h(A) = 1 11-(1- -11-aA)
The argument above can be easily extended to the case of Gradient Flow (GF). First note that un- (Woo
(Wo- w"), thus der GF dynamics d at We = -LDDx (w.) the parameters are W,- w' = c Hi
implying (A) = e At and (A) = - e A Then, for (A) = (a( = 1-e-Ar we also have J J² = J (JJJT) which can be seen, for example, by from the Taylor expansion 4e (A) = En (-12)" The rest of the argument is unchanged. (n+1))
X
Gradient descent is also easily extended to arbitrary first-order iterative optimization algorithms. For all such algorithms, the parameter change W. Wo on iteration ł belongs to an order t Krylov subspace: Wt- Wo E span span(H H(w, w" w"), H2 H2 (Wo- w') ) H' Ww w )} (see, e.g. (Nesterov) 2003), page 42). This is equivalent to saying that Wi+1 w" (H) w" with Pt (X) being an arbitrary residual polynomial (i.e. normalized as (0) 1). Since in our GD argument we did not use any property of its (X) except for residual normalization, the argument continues to hold, making the representation for all first-order iterative optimization algorithms.
A similar assumption was implicitly made in the main paper in the definition of the spectral algorithm Indeed, the existence of inverse - also requires rank( (V) = N. This is natural assumption for positive detinite kernels K: empirical kernel matrix has full rank if evaluated on a set of distinct inputs x,, which in turn happens almost surely for typical generation processes of Dx such as i...d. drawn x,. In principle, one can also consider the case of non-full rank of K, or alternatively non-existence of w completely fitting the observations, and replace K in with pseudoinverse. For simplicity, we leave such cases future work.
17

---

Published as a conference paper at ICLR 2024
B.2 IMPLEMENTING SPECTRAL ALGORIHHMS WITH PAIR OF GRADIENT FLOWS
Recall that in the section above we get GD residual Pr (A) = - (A) = e An alternative way get this would be declare Wt w" Pt (H) (w w*) and then rewrite original Gradient Flow ODE at W LD (w;) in terms of the residual (A(A) as
Oepr(A) AAp((A), Po(A)= =1.
(54)
with an immediate solution (A( = AA.
Now, suppose we are given some target profile ((A) with respective residual () = 1 T((A) + 0
that needs to be implemented. Our strategy is to design such GF process with residual ge ge( that converge to the desired profile at long training times qoo (A) = lime-+oo 9r (A) (()). The basic GF
process given by (54) always converges full interpolation of the training data: lim, Pr(A)
lim;-oc e Ar = O. We propose to overcome this interpolation property by using two optimization processes the first process standard GF (54) converging 0, and the second GF process will use
gradients of the first GF to converge to p()) + O. These two process are defined by a pair of ODEs
de W: - WW (wi). d = =-(1+ g(t)) V W (w:),
(55)
U
where w, and u, the parameters of the first and the second process respectively, and the initial conditions are assumed to be identical wo = un- Associating residuals Pe()), (A)) to parameters w, u, ODE system (55) is rewritten
(O.p(()) = -A), (2.((A) = =-(1 + +((())
Po (A =.
(56)
Here (() is a function controlling the final solution (A), and therefore needs to be chosen based on the desired solution P(A). At given control function g(t) the final solution 9oo can be easily found by integrating the second equation J0x 0:q: = 9-0 (A) - 2o (o(() and substituting the solution of the basic GF Pe (A) e- into (A). Then, setting the final solution to the desired value yoo (A) = ((A) leads to an integral equation on the control g())
I (1 ((+)(t) de A dt = P(A).
(57)
Since 000 AM 1, we cancel from both sides, arriving at Laplace transform of g(l) on the left-hand side
((t)e-xi dt P(A)
(58)
Thus, choosing (t) as an inverse Laplace transform P(A) implements the desired spectral algo- rithm ((A).
C SCALING STATEMENTS
In the section, we give rigorous versions of the scaling statements outlined in Section 5.1 In the end of the section also provide Proposition 5l as discrete analog of Proposition which will be required for the Circle model.
Intuitive derivation. Before proceeding with rigorous proofs, let us give a simple intuition behind the scale of sums and integrals stated in Propositions Iaaatiions[andl [5
We start with the integral case, following notations and assumptions from Proposition 2 To find the scale of the integral f (A)]dd, let us divide the range of scales E [0, a] into many small segments and look at the contribution from a single segment (So, sel, corresponding to the interval of cigenvalues Agp = -N- >p), A = N- 40 Due to the continuity of scaling profile S9 (see Lemma [ below), we can neglect the change of the (A) Asg- Approximating the length of
18

---

Published as a conference paper at ICLR 2024
eigenvalues interval as |Azol = Ao we estimate the contribution to the integral from (So, Su + e] as
9N (A)l X | [Nn( x A N S
(59)
which is exactly the expression under the minimum in Proposition 2 To see that only the scales which minimize ((s) (s) +
give non-vanishing contribution the final result, take two scales S2 such that ((s2) - G(s1) = 8 > 0. Then, according to (59), the contribution from scale segment (82, 82 + will be N times smaller than from the scale segment (81, 81 + e]. and therefore will vanish in the limit N - oc.
$2
We can summarize the above with the following simple heuristie: replace dA with X under the integral and maximize the resulting expression get an estimation of the integral scale. The case of a discrete sum goes along the same lines, leading to the heuristic of replacing the sum Σx with current index k: Σx 19N (Ax (X)) k 19 (A )), and then maximizing the resulting expression.
Continuity of scaling profiles. Lemma 1. The scaling profile (*), if exists, is a continuous function of
Proof. Suppose that 59 exists but is not continuous. Then there exists 8, 0 and sequence 8m + S. such that (sm(s (s.) > for all m and some positive constant c. Suppose w.l.o.g. that (sm) 59 (s.) for all Consider some fixed m and choose some sequence (m) of
scale Sm- In particular, we then have
(m)
<N=*tt1/mm and A (m) > Nm 5mmmm
N
(60)
for > Nm with some Nm. By definition of the scaling profile, we also have
(A
(mm) | (mm) > (s.)ttt))
(61)
for large enough; say for N Nm with the same N,, as before. We can assume w.l.o.g. that Nm is monotone increasing. Now define the sequence AN by
AN AN (m) Nn < S Nm+1
(62)
This sequence has scale s., but 1 (Aw)l > (c.)to)) for all sufficiently large N, contradict- ing the fact that that 9N (Aw) must have scale (s.).
Proof Proposition Part 1. Let us first show the part the statement that says that for any
<> 0
[
IN (A)ldA o(N
(63)
ox
Suppose that this not the case, and there is e > 0 and a subsequence Nm, such that
19N N=a.te
(64)
ax
Divide the interval [0, into finitely many subintervals I, [by, b141 of length less than c/2. For each subinterval I,, define
Am,r arg max X:- log AET,
[A),
(65)
Note that for each the sequence has a limit point s E T,. By going to a subsequence, we can assume w.l.o.g. that the limit point is unique, i.c. is the limit. Then can define for each the sequence X by setting X Am, if
loog.... Am, takes values in the compact interval 4,, so
N = Nm and somehow complementing it for N + Nm so that the sequence X has scale s7. By scaling assumption, we then have
(N = oONN-(N- s(o) -ONN-sl0llan (s.)++/22)
(66)
and in particular
(m ((0) (x))==/22
9N (Am,r) of
(67)
19

---

Published as a conference paper at ICLR 2024
By definition of Am,r.
19N (A)lda = 1 log No
dN
I9N,
(Nm
dq 1 Σ
INm r N.v.....
(68)
dg
follows that
S( IgN... (2)led =
Σ
N (s.)+
2
(69)
o
Σ
Nm (st2))
(+))++++
(70)
omNm
(71)
contradicting assumption 664
Part 2. Now prove the opposite incquality:
9N (A)ld) = w(N
(72)
Jay
Let q. arg min (S(s) + +). By continuity of 5(0), there exists an interval /
lg.
6, + 5] where 5(9) (s) < (( + e/2. Arguing as in Part 1, we then deduce from the scaling assumption on ((9) that
min A lOg AEl
(9N w(N (1))))))
(73)
follows that
S [9N(A)|da2 (N- 2. 1016--N-9 2N-
min A:- log Aer
1g (A)l
(74)
(
(75)
=W(N (c.
(76)
(77)
as desired, This completes the proof of Proposition 2
Discrete spectrum. Suppose that (Xg (N) E (0, 1] is a N N-dependent, size-N multiset (with possibly repeated elements) such that the sequence of the respective distribution functions FA(A) Hkk E N À < A < |}| has scaling profile (x)) Observe, particular, that the Circle model with the population eigenvalues \ ([1]+1)- the distribution of the empirical eigenvalues d (as well as of the population eigenvalues A for & restricted the interval (-N/2, has the scaling profile ((F) (s) 5.
Proposition 5. Assuming that min((> (N) M w(N a9) with some and ((F) strictly monotone decreasing, the sequence of sums Rx=l I9N (A has scale s, minosesa (s)
(s))
The proof of this proposition is analogous the proof of Proposition 2
D CIRCLE MODEL
Here, we give all our derivations related to Circle model.
D.1 Loss FUNCTIONAL.
In this section provide the proof of Theorem 1
20

---

Published as a conference paper at ICLR 2024
The main technical motivation behind our Circle model is to simplify the empirical kernel matrix K. Indeed, K becomes a symmetric circulant matrix
20
2ml(i-j)
K) = Σ
Are
(78)
To establish the relationship between the (complex) eigendecomposition of empirical kernel ma- trix (29) and observation vector (y); = yo one side, and the population spectra X,, C4,1i C- on the other side, we write
N-1
30
2nk(i-1)
K
Σ
Σ
N
N
Age
(79)
This leads to empirical eigenvalues
2nks
Ax
Ac+Nn (ux), =
(80)
VN
00
Note that empirical eigenvalues Ås turned out to be non-random, which is a consequence of the regularity of training dataset DN Observe that each empirical eigenvalue except d is twice degen-
erate: A ÄN k for k N/2. This the consequence of the fact that we took the kernel function K (ar - ) to be even.
Turning the target function, we have
Σ qee ul+
2ri N
Y/ oE; +
(81)
The respective empirical coefficients in the decomposition
V Ex Th Un are
Uk
N
y.c
2
TSK
Σ
2
cikkNNa
(82)
N
Here EK = 1 Eee 1 VN
kmki
E C are complex Gaussian random variables. They are i..d. up to few dependencies, for example, E EN (overline denotes complex conjugation here). Therefore, later we will use the definition of & in terms E; to avoid accurate formulation of its statisties.
e
Finally, let us use the obtained eigendecompossition of the empirical kernel and target to write an expression for the prediction components
ल = 2T 10
2T f(x)e it do = A
N
N
Σ
ik Dut
ii(+ 285)
Uk
A
N
k=0
1=0
(83)
A (ex Hu BuDDer DKr
A
where k; mod N. Note that representations 83 and 822 define transfer measure Pi (dx) introduced in Section A.3 Due to the regular structure of the training dataset in our setting, the transfer measure also has specific regular structure.
1. In the basis of Fourier harmonics {eitr _ the information is transferred from (' to ( only if / - l' is divisible by N (we can say that such I, l' are compatible).
2. If 1, are compatible, the information transferred only through a single empirical eigen- value AN.K.
Now, we start to derive the specific form of (44) for our translation translation-invarian invariant setting. It will be convenient divide the contribution the final loss Lx [h] into bias term and variance terms responsible for randomness w.r.t. to u and ex:
[A]- J, BiBis [M] Var, [h] + T. Var.e
(84)
21

---

Published as a conference paper at ICLR 2024
Bias term.
This term is the loss of the mean prediction with population coefficients
Bu, [c:]
À M((rnn)
2x
Ru
Nnj N
Ct No
du
A
1h h(dx
(85)
Ak.
Aki
whose substitution into I Eu.=f((x)]] gives
)² lap22
N [h]
1
Σ
1
d h(dmn)
(86)
Ak:
Here see that how well the component can be learned depends on the closeness between and A for < N we have k = and typically A A (assuming that X decay fast with l). Thus, the target function can be learned well by setting h())= 1.
Noise variance term. Since the prediction linear the noise Es, its contribution to the loss comes only from the terms which are quadratic in Eş. Then, define the noise variance by the contribution such terms to the loss. Denoting the contribution of the noise to the prediction as f(t), we calculate its second moment
Eu,
ihi
20(64 12)
Be Bil
Arch(der))
o²
(87)
Ake
N2
Ake
N
11
where we used that f(e) is independent of u making expectation E,, trivial. The respective contri- bution to the loss
0²
L
Var &
[h]
Σ
(88)
N
Dataset variance term. This part is simply the contribution of the rest of the variance prediction. The respective second moment is
Bu, [a: d( - = >xh((rm)))
(N -ng)u du
CtNNn, CtNNn,
ARa
2T
11-
(89)
10
n=-00
Subtracting the mean (55 from the second moment, we get the dataset variance loss term
Ach(Smn)
Var, 1 [1]
= Σ
Σ
10tNal2
(90)
Ak:
J 00
Final expression.
Let us First combine bias and dataset variance terms.
I Var,u
[h] + I. Bius
/h]
1
Σ
|cr1 2/a/1 h((re))
x + (Mr h(dm))
144N2l
2
A
t=
(91)
1
(lci) - 2/c11 h(Nan) 2
(
(h(da))
d +lx/1
12
N1+Nn
2
Ake
where we have rearranged the sum over I with fixed h; in the quadratic term.
Adding the noise variance term, we are now able write the final expression for the generalization emoor
la|2 1 h(dd)))
h(Are))
+ o² (2i(((te))
) (92)
Lhh] 2 L0
1 Σ
M +
[ANNN
Ake
N
22

---

Published as a conference paper at ICLR 2024
where have used N-deformations (T0) notation for the sum Σ i [X N: As last step, we observe that the sum over indices the same fixed ky = k mod again leads to N-deformations (TO), allowing to rewrite the full sum over 1 Z into the over kn 0, ,....,,. N- 1. Then, denoting by simply as k; we have
N-11 [mh] = Σ
(
[AR] (rt))) [Ac]
[elcel ((Ax)) [Icx|[ ]
I + ||ce (Io)llN)
(93)
which proves Theorem
Let us now describe the optimal learning algorithm P and therefore the optimal algorithm is well defined and is given by pointwise minimization each Ak. The resulting optimal algorithm h (Ax) is
Note that the functional (93 fully local,
he (Ax) [AACCl MAICC/?INNNNN PAeN
(94)
N [a I P
It may also be convenient to give a "completed square" form of the loss functional L|4] 8L [h h-] + L|h*), 8L(h"] 2 that separates the minimal possible error Lihh]] with an excess positive error if the algorithm is non-optimal h h +
N-1
[AR] [Ax N
[ih] = 2
Σ
o² + [|cmP]NN)
-Ro)))) (ha)))
(95)
D&x la 121
+
6 N
[|ca [2] N DANNN
Finally, we note that one can use translation symmetry ls k + N of N-deformations 10 order to shift the summation in (93) to values - S k
< N for example, k E { N
2
Like in 21 denote such summation range simply as
Σ -
The purpose of this shift is to
put all high empirical spectral quantities [Ag|e 2b] in the region |k| < N. allowing to write, for example, Xx ((Ik) ")
D.2 POWER-LAW ANSATZ: NOISY OBSERVATIONS
Now, we turn to a more detailed analysis of the Circle model. As in the main paper, we separately consider the noisy x² > 0 case in this section and the noiseless 6² case in the next Section D.3
Recall that we adapt basic power-law spectrum X = 1", of = --1 2 since for the circle model the population naturally indexed by the whole integer set Z., leading to
(96) The purpose of the current section is show the equivalence of circle model and NMNO models,
\ (1 oi = 11
l Z.
thus proving the respective part of Theorem [ The intuition behind NMNO relies on the close- ness of population and empirical spectral distributions in the eigenspaces distant from the spectrum edge ||| < N. Thus, we need to compare N-deformations [Xg /g/c 22 IN with their population coun-
terparts A cg. (2b, considering the values |k| <
N relevant for the loss functional (IT) From the
definition (TO) we get
[Xg ck] IN = Ailcx
Σ aa N. 2b nz
N M(-w))(++1)
N vy-av-baas b(x+1)
=Aile 2h
(97)
m== [1 + 1+h b(x+))+1) +tb)ao+b(ett)
m==1 (nz + 1-k (akkammnn b(x+1)
N
N
Aglc 2b O(N av- avr-b(++1))
X2 Ag/ce/ 2b
((7
where, in the last line, we have assumed that av + 6(k + 1) > 1 so that both n and n2 series are converging. Also, we have recalled the notation 1 N
introduced in Section 5.3
23

---

Published as a conference paper at ICLR 2024
It turns out that the relation equivalence to NMNO model. For that, write the Circle model loss functional [I as NMNO
[Ag|e 2h
N X cx| + D(N-avvM<+)) is sufficient to establish
functional (nmoo) [t), defined in 17 plus two corrections terms
Lih = [nmmo][h] [h] + [L + 6 [h]]
(98)
where the correction due to the displacements between the population and empirical eigenvalues in the argument of the learning algorithm is
نL [h] = Σ
%/
+ ((1-)(w))) (R(())) (( ((=a)))))))
(99)
k=
and the correction due to difference between population >glcx 22h and empirical [2g |cc p01 cients in the loss functional
coeffi-
NV
[ N Nx(h)) + (1cca1), 1
[ N
8 Leontt [k]]
Σ
lexe
lcal3)
N
|
1
k=
N
(100)
Melckl P N |
1cu| lca13)
[|cx|*]
10xl
From this point, our strategy is to specify the scales of all the terms of NMNO functional (nmmo) [h], and of the two corrections (L Loooet [b]. Then, we can invoke the scaling argument of Propo-
sition _ negligible contribution to the loss.
(actually its discrete version in Proposition 5) to show that all the correction terms give
First, recall from Section 5.1 that the scaling of NMNO terms is given by
S $ 1 + 25 (s), 8 (1<(1-((A))) MAa))) 27 =
(101)
~+] v 8 + 25(1
(102)
Next, we proceed to the 8Late hh] correction. To bound its terms one needs a certain smoothness
assumption on h()). Currently, in Theorem [ we require that the maps log À + log [A)
and log À + log [I - h(A)] are globally Lipschitz, but maybe a weaker smoothness condition is possible. To understand the application of this condition, take some function g(z) such that
a mapping log x + log gxz is Lipschitz with constant C, i.e. log
g(x+Ar)
g(x) S Cl log star|
Then, taking any constant C" C, there is 8 > such that for all |
8 we have
x
u(x+Ax)-gg(a) -x(x < C''(x)) Az Coming back to the difference between empirical and population
eigenvalues and using (97) gives - O(r"), and therefore 11(((x))N?(Aa))) = 0 (A<))²) A
(and similar estimate for (1 - h()))²). Recalling the scale S(7] = 5
5. we get a h12 (((As)-?(AA))) 21+リ ー s - (s). | ((1 (1- h(x)))
|
N 1
bound on the scale of the respective correction terms
2
S
(103)
N
(1- 2 (1-)()e)))) } A = + (5
(104)
Finally, repetitive application of (97) to all the terms of & [h] gives the remaining scales
1 N
|e
2
s
122 (xx)
2 1+ (v - 8) + (s).
(105)
N
] N
2
[ΛR]
S
[1cx| PI]
N - 1cxl (12(3)))(((m))
2 (k+1)) ^ (v+ kt/-us) + (2)h))ss,
(106)
[>e] 2
Ae lcul?? [2]
s
- -Icx 12) P)((Tw)
4 EtI- + ((h)
(107)
[Ax]] N
s $[[caa]] IN - -cal
1
(108)
24

---

Published as a conference paper at ICLR 2024
Here, all the estimations relatively straightforward. except for, possibly, the bound (06) that involves two values depending on whether A + V or the opposite (a reminiscent of overlearning transition of Section 5.3 here!). We demonstrate the bounding of this term in detail
2 (1 0(721))
||cu|?
lcx| ( O(+)t)))
N
AE
2
Ax (1 (L(+0(77)))
=lxx/(11 +(+*tt) + 0(+")) lcA P 0 1 (x((t))))))
(109)
-|cll" + +0 (lk) + -1)ON(-K--1)
N(++1jAr
This immediately implies the bound on the scale of [|cx| 9NN
Agly [Aa]y
lexl used in (06
Now, having specified the scale of all the corrections, our task to show that they contribute neg- ligibly to the loss. In other words, the scale of the total contribution of all the corrections has to be strictly lower than that of NMNO loss. Using Proposition [
this is written
(1- (1-3 +555h( A s 25(1-1)
min 0SeSv
(110)
min 0Sa5p
(1 (v + (2(())(s)
(111)
((1 + 1) ^ (u+ xt1-r 5) (2)
(112)
A (v sti + (s))
(113)
A ( st1-" (s(h) (8))
(114)
(1s +
(115)
easy to see that this strict inequality can only be violated (by becoming equality) when the mins are attained at = v so that the r.h.s. of (TOS) is equal to the r.h.s. of (1OI). However, this possibility is excluded by hypothesis of the theorem. This completes the proof of Theorem 2 Circle model.
for the
We remark that the Lipschitz condition in Theorem used compare algorithm h(A) evaluated at the population and empirical eigenvalues, is required only for the discrete (Circle) problem. is easy to check that this condition holds for the KRR algorithm with H, (A) = X+o
A_ However, is violated
for GF with (A) not Lipschitz on the scales < st. Fortunately, (1 - h2)) on such scales is exponentially small, and the contribution the loss from corresponding terms, both NMNO and its corrections, can be ignored. Thus, the equivalence between Circle and NMNO models still holds for GF algorithm. We expect that the Lipschitz condition Theorem Can be weakened to take into account GF algorithm but leave it for future work.
e-x, -M;; for time t N the mapping log À log(1 (A)) -At is
D.3 POWER-LAW ANSATZ: NOISELESS OBSERVATIONS
In this section, we derive the results presented in Section 5.3 while also giving full versions of the results that were discussed only partially in the main paper. For the convenience of exposition, the order in this section repeats that of Section 5.3
D.3.1 PERTURBATIVE EXPANSION OF THE LOSS FUNCTIONAL
In the main paper, relied equation 21 as starting point quite easily conclude that the loss localizes on the smallest spectral scale s = 0 in the saturated phase k > 2v while localizing on the highest scale
2v. Essentially, equation 21 ignores the details of the problem at subspaces corresponding to small eigenvalues X XN/2 (and [k| ~ N), while providing simple estimation of different loss functional terms for large eigenvalue subspaces with d > Xx/2 (and kk| < N). Alternatively, if one starts from exact loss functional (IT). there seems to be no clear path to deducing the existence of saturated and non non-saturated phases, and obtaining their convergence rates.
in the non- saturated phase
25

---

This term is estimated follows Published as a conference paper at ICLR 2024
The above discussion illuminates the importance of perturbative expansion of the loss functional in |k|+1 the small parameter т N or, in other words, perturbative corrections λ Ax and c₁ - ck of population spectral distributions in the presence of finite dataset size N. For the circle model, the effect of finite dataset size N is captured by deviation of N-deformations [Agloe 2 from their population counterparts Xg 1x|28. The simplest form of this deviation was already obtained in equation (77). which we will use below to derive equation 21
Let us start by writing down the loss functional in "completed square" from 95 and the absence of observation noise
Y Σ 2 k=
[osP N [2NN (M(A))-1'(( ([a+)
(De xIx)²
L
-1 - +[lcx|2
(116)
[cx [2] N (
Note that the first term here, i.c. the factor in front (h(Ax) - h (Ax)) 2 was already estimated in the second line of (109): it agrees with the factor Lapl2 2 (1+)(T)) appearing in (2I) up to replacement ((7(**11))) (()) valid due to (K + 1) Ar> 1. We use this simplification in (21) because we do need a more accurate estimation of the correction term this moment.
The second term of 21 corresponds to the generalization error of the optimal algorithm, which allows to denote it as La [h*] since L[k*] = ΣN'2 N/2 Lx(h*].
Dk=-Ny2
(1x1)=131N)) ||cx|]] I
L [h-) = [|c
1cx ( ((Fatt+y)
1cx (1x - |cx1 22 0(FrtT) + 0(F2n))
(117)
-Iaa((((tatt)) +0(7 +((72))
(TN) - - (o(tatl) 0(72M)
= =N-~-1000 0())))((2))-))))
D.3.2 OPTIMALLY SCALED LEARNING ALGORITHMS
In Section 5.3 we mentioned that the rate ONN of the optimal algorithm h" (*(A) in the non- saturated phase also holds for learning algorithms h(A) within suitable neighbourhood of h" (A), characterized by a condition (h(As) - h² h²(Ax))) )2 = o(r*). In this section, we derive this result while also providing more systematic discussion of learning algorithms that do not destroy the rate of the optimal algorithm.
Let us call an algorithm l(A) optimally scaled if the scale S[[[A]] of associated generalization error [h]] is the same that of the optimal algorithm h- (A)
S[L[N]] = S[L[h]]]
(118)
While one might try to find all algorithms satisfying (188). here we take a less ambitious approach by considering simple family of conditions on ()( 11* (A)l and then choosing the weakest condition within the family. Specifically, for any two constants a, b, consider the following bound
on the scale of deviation of an algorithm (((A) from the optimal one:
S(In(A) - h (X)[ 2 bb
E (0,u.
(119)
which is a slightly weaker (e.g. up to log N factors) version of (a(A) h- 22) = o
Here limited the scale of X to [0. 2/ because this is precisely the interval of scales occupied
by the set of empirical eigenvalues {Ax
1 passed as an input to algorithms h, h".
N-
k=0
It is easy to check whether all algorithms satisfying condition
(199 are optimally scaled. First, can equivalently rewrite (118) as S [[[[h] - L[h"]] 2 S[L(h*]] Then, applying Proposition to (2T) yields
26

---

Published as a conference paper at ICLR 2024
S S[L[h] - L[k*]]
0Sa5v ($[[ex|²) +((((())) - (1()))
min
(120)
bb. ( aas +b -a++ :) - 1b+n+av av,
a 2
min u
According the above calculation, the of all pairs a, b that guarantee algorithms under condi- tion (119) to be optimally scaled is given by A = {(a, b) E IR2 b + 0 (N + av) 2 [[[[h"]] Now, if we wish to pick pair (a, b) E A such that condition (119) is the weakest at spectral scale have to minimize + b. Fortunately, there is unique pair (a", b*) that provides the weakest condition across all relevant spectral scales
(a'.b") -- arg min as b Vs E [0,v]. (a.))A
(121)
Applying this result to saturated and non-saturated phases, with respective convergence rates O(N and O(N="), gives the desired conditions for optimally scaled algorithms
(A(M(A) h" (T))]] 2 -8 8 + K in the non-saturated phase < 2v, S((n(A) - 1- (*))]] 2
K
(122)
K + 2 in the saturated phase K > 2v.
(123)
stronger version of optimally scaled algorithm condition. Recall that the loss of the opti- mal algorithm h" in saturated and non-saturated phases localize at 8 0 and = respectively. However, conditions
122 (13) do not provide the same localization property for the excess error L - L[h]. To see this, take (h()) - h" (A) O N=A2v, which corresponds to values ba",b") given in (12T). Substituting these values in excess error scale calculation (120) makes the function under the minimum s-independent, implying that the excess loss localizes all spectral scales E [0, v). Such spread of localization scales introduces a logarithmic factor in the error rate.
Taking, for simplicity, (^(2s) he (hw) ((k) + 1>-*N- RADe and using (1 gives
[[M] L[hi] =
Σ
o(T))( ((++oT)][A(A)) 2-- (Ax))
(124)
1 O(T) -(NN-A22
AA2
AA2n log N).
+1
To avoid these issues, let introduce slightly stronger version of conditions 122 by picking a small parameter > 0::
123
specified
(M(A)) A O(A)N) (I(A)) - (2)) = 101-0(--N))
in the non-saturated phase < 2v,
(125)
in the saturated phase 2v.
(126)
For any 8 > O, the above conditions guarantee localization of the excess error either at 8 (saturated phase) or conditions in computation like (124) produces the rate of the optimal algorithm without log N factor [.[M] [[hh]= = O(N - -A2r))
// (non-saturated phase), as can be seen from (20). Also, using these
Finally, let us comment on (b( h-- (2x)) = o(7*) condition for non-saturated phase, mentioned
in the main paper. Since 5 = (2 . in many cases one can replace o(r") with O(7*+5) with 0 can provide such replacement, it is possible to show that the rate the excess error remains [h] [ = O(N-*), although with a more
some and thus satisfy condition 125 When
technically involved version of computation 124
27

---

Published as a conference paper at ICLR 2024
D.3.3 SATURATED PHASE 2n
When discussing the saturated phase in Section 5.3 we first deduced from O(7#) terms in equa- tion (2T) that the loss will localize on the scale s = (corresponding to [k] ~ 1), and then stated that the loss of the optimal algorithm can be achieved by optimally regularized KRR. In this section, we derive an asymptotic expression of the loss functional in the saturated phase, which both explains the statements made the main paper and gives a more systematic picture the loss-algorithm relations in the saturated phase.
Generalization error of optimal algorithm L|A-]. The asymptotic of L[h"] originates from 0(72-=K-)) term in equation (2T), which dominates the whole loss functional for > 2v. To verify that this is indeed the case, we need a more accurate characterization of N-deformation cor- rection terms than in (97). For that, we recognize that the sums over n1, n2 in the second line of (97)
are Hurwitz zeta functions <(a,x) = In=o(n + x)= evaluated at a av + b(K + 1) and two specific values of x::
[xgloR 2 a=ar+b(x1) >g|c 26 + - (sa,,1 1+k) c(a,1 1 w+) (0),1++*))
(127)
Substituting Taylor expansion ((a, 1 1+ c) = {(a) - aç(a + 1)c + 0(2)) of Hurwitz zeta function at 1 into (17) we get more detailed version of 97
Aglcs 26 NN \ 20(a)
+
(128)
Equipped with (128) turn to derivation of the leading asymptotic of 0(r2v-k-) term dominat- ing the loss. By looking at (117). we can see that the term of interest comes from finite N corrections of [AE] x- Then, mimicking the derivation (17) and using 128 for [Xæ] N we have
cc 2 (1
L 1c& (1 (1++0(7+) 0(T
X2 + 2C(222) (1+0 0
(129)
|c 2 N 20 O(N O1+ +
= =2((2v)
Substituting the above in the loss functional sum results gives
y
L(h2]
1
2C(2v)
Ck
2 20
N
+0 --]
2
1af
2 2(22)) 20 (1+
Σ
(130)
X
A
= 2 20 + o(1)
Σ
x
lea 2
X
Here in the last equality we extended the summation to all population eigenspaces due conver- lay at > 2v, which reflects localization of the error on scale = 0. X
gence of the series Li=-o0 corresponding to ||| ~ 1.
Note that in 130 we could have evaluated the sum over the population spectra
= Σ o
Σ
11
2Ç(K + - 2v) - 1.
(131)
However, we view the version with the sum as being more general. Intuitively, it stays valid in the case of population spectra having power-law form only asymptotically: X (14) + +1)-"(1 + o(1)) and la/2 = (M +1)-= (1++(1)) o(1)). In that case, the value of the sum is not fixed by the asymptotics of \₁ |cj 2 and may vary substantially. In contrast,
from computation (19)
and corrections to N-deformations (97) and (128) that the factor 2((2v) is determined by population spectrum X with indices / near the values 1 N, -N, NN2N, 2N ... Therefore, the factor 2 2((2v)
......
28

---

Published as a conference paper at ICLR 2024
in the loss is determined purely by asymptotic behavior of A Overall, this creates interesting situation where the loss (130) is localized on the smallest scale s = O, but the asymptotic shape of the population spectrum almost fully specifies the generalization error asymptotic [[h-] CN 2v (1 + (()), with only the constant factor Σ 0.
lei determined by the details living on the localization scale X
Full generalization error [h] The full generalization error is obtained by combining [h( with the part of (116) associated with deviation from the optimal algorithm {(() - At (A). We will con- sider only the algorithms (A) with mild deviation from the optimal, given by condition (125 As
demonstrated in Section D.3.2 this condition guarantees the rate not worse than the rate O(N 22)
of the optimal algorithm, and also localization of the excess error on the same scale
Having ensured localization of the excess error on the scale 0, let us first look at the perturbative expression of the optimal algorithm h² (A) at this scale. Substituting (128) into 12). we get
h" (Ax) = 1+ 2(()) N ([+O(N-))+01))
(132)
A
Using the above expression of the optimal algorithm, we compute the full loss functional as follows
1
(1 + (()) (M(Aa) -1 - -2((e) N (1 (
N + 0(-)))
2
k=
1
Ica 12
+
Σ
2 (2 (2 (1))
(133)
2
X
k=
1 2
leEl
(MCA) 1) - + 2((2V)
N
(1 + o(1))
2
X
While the above expression for [[h] is already a valid asymptotic for the loss in the saturated phase, make few further refinements.
First, note that (33) relies on condition (25) for the algorithm h(A). This condition might be quite
difficult to verify in practice, as it requires the knowledge of the optimal algorithm h(A). However, perturbative expansion (122) shows that optimal algorithm satisfies |At (A) - 1|2 = O(A -2N 222). 22).
Since in saturated phase > 2, we can always make > N-2 smaller than x - by choosing e < x 2. Thus, employing triangular inequality shows that the original condition (25 equivalent to
(n(A) - 11= 0
0<E< V
(134)
The main advantage of condition 134 compared to (26) is that is easily verifiable. For instance,
KRR has 1 (A) 2 which satisfies (144 for m ON- Similarly, for gradient flow we
have 1 - (A) e tA which satisfies 34 with t = 2(N 2 on
E') and some E' > 0 depending
Note that KRR and GF examples of ((A) considered above satisfy 13 not only on the scales s E [0, but for all s 2 O. or equivalently À S 1. Based on this observation, let us impose condition [34) on all À < 1. Then, the summation indices in (133) to all population values I E Z, similarly to how it was done for optimal algorithm loss in (30).
To summarize, through the derivations and discussions above we have proved
Theorem 3. Consider the Circle model in saturated phuse > 2v. Then, if an algorithm h(())
satisfies (34) for all X < 1, the loss functional is given by
[4 1 N-2 2v (1 (11)
Σ
20
1a12 X?
(MAN) -1) -1)-w(())) +2((20)
(135)
29

---

Published as a conference paper at ICLR 2024
Finally, let comment on the KRR result
(22 presented in the main paper. Observe that the combination X(h(A) - 1) entering the loss functional (335 is given, in case KRR. by
X(h, (A) - 1) 1+
+ (1+
(136)
Substitution of the above into loss functional (135) leads the KRR expression According to condition (134), this expression is applicable only for small enough regularization strengths |n) = O(N
D.3.4 NON-SATURATER PHASE K < 2v
In this section, obtain a limiting form of loss functional in the non-saturated phase. While this form was not discussed explicitly in the main text, was used to produce the first two plots in Figure
An important feature of the non-saturated phase is the localization of the loss on the highest spectral scale v, which is ensured for algorithms h(A) satisfying (125). Such localization corresponds to values 7 ~ 1, so we can not rely on perturbative expansion in small parameter T -> 0, as we did in the sections above. Instead, for all terms of the loss functional (116) we need take into account their limiting N + oo form at fixed 7. For N-deformations, such limit leads to symmetrized Hurwitz zeta function <!a) C(a, 7) {(a, 1 7) introduced in equation
23
of the main text. Indeed,
slightly rearranging
127 we get
[A] cx 23)] N N N (C + S(a, - )
N-000 constt
N (())
(137)
Next, observe that on the scale v the density of eigenvalues d is very high, in sense that N0000
AA241-Aal O(T-1N-1) Tmconst
0. Thus, the limit N L Do the summation over spectral
A
index A in the loss functional 116 translates into an integral:
N
dk + 22 S0² dr,
where for the last transition recall that r |k|+1 and N-deformations [Xg c& (2b N are even functions
N'
of k. This leads to the following continuous form of the loss functional (116)
(x+1) (220) CT
(clutntt)) 27
L (cont) [h] = N
(c 2 ((())))((()))) + ((x+1))
dr
s(ut1)) ((av)
(138)
(x+1) (20)
-2 slutxtt)
= N
h22 (2((x))
h(2r) + (lict)) dr,
(
clo)
where 2, - ) and the optimal algorithm h² (7r) is given by 23
(1)
D.3.5 THE OVERLEARNING TRANSITION POINT
Observe that if K = w- 1, then in the case of zero noise o² = 0 the optimal algorithm (22 becomes hr (Ae))) = 1, and the same holds for the limiting (N - oo) version 23 We prove now that for larger (smaller) x the optimal algorithm becomes overlearning (underlearning). We give the proof for the limiting (N oo) version, but it is easy to see that the proof extends without change to the original discrete version as well.
Lemma 2. Consider the N limit of the optimal algorithm given by
23
slu slutat!) clu)
ht (xx)
(a) = ((,, x)) + ((0, 1-r) x).
(139)
(let1) (20)
(20)
Then for any 10)
1. R K < v,
h² (a,))
x+1= v,
(140)
k+1>b.
30

---

Published as a conference paper at ICLR 2024
Proof. We have
In Inr)"Ar) = (In c clutxt)) ((n(tt) (In cf ((t) = fmae da faae d3
(xtt)
pate
d²
(()).
(141)
To prove the lemma, it suffices to show that the function f(a) (la) is strictly log-convex for a > i.e. ff" > (f')². Note that
20
da f()) = Σ (- In(n+ +)) (n+ + 7) Σ (nn( + +1 ())
(142)
Then, the inequality ff" > (fr)² is just the Cauchy inequality for the vectors
(..., (n + a/2 (n -a/2 ....)
(143)
and
(..., In(n + +T) a/2 .... In(n + - r) + -7)- )...).
(144)
The inequality is strict because the vectors are not collinear.
The over/under-learning property (A²) x is clearly visible in the right two subfigures of Figure 3 At k > // 1, the optimal regularized KRR is also overlcarning (with a nega- tive regularization). The optimally stopped GF in this regime is GF continued to infinity, icc h(A) lim (1 -
E
WISHART MODEL
As for the circle model, in this section we collect all our derivations for the Wishart model.
Our strategy in computing loss functional relics on the resolvent R(z) of empirical kernel matrix K T AΦ:
R(2) (N 6 A 21
21 )
( E AoDIoo 21
-1
EEC, C,
(145)
where Φ, are the columns of feature matrix T
We note that the projections on empirical eigenvalues and eigenvectors, appearing in empirical trans- fer measure 41 are related to the resolvent via the limit in the complex plane
N
5% (d))
lim y-0
Σ Aunnaa - (A + in)1
dA
(146)
lim &R(A ig)dA, y y-0
where 3z denotes the imaginary part of E C.
Now, denote the resolvent projected on features Φ as
1 Rav (z) N Φ R(())))
(147)
and the first two moments of the latter
Ru-(2) = Ex
Ry (z)
(148)
11,41115511 (21, (21, = Ex
Ru,g (z) (egl
(149)
Then, substituting [46] into the transfer measure resolvent
immediately connects to the projected
31

---

Published as a conference paper at ICLR 2024
A lim 3 Bir iy) Jdd.
(150)
Carrying the relation (550) over the first and second moments of the transfer measure gives
A lim R(im) (A + iyjdx,
Pi (dx) (dx)
(151)
オ\xー0
dR Ni
Phigg (dA1, d2))
lim (mm))
Rigg (A1 + iyy. 22 + (22)d\id\2,
(152)
22\112
--
12-0+
A lim Rfi (A + iy)
p p (dX)
(153)
where (((m)) and R 4,22 are the moments of the imaginary part of the resolvent projections
R(im) (z) = EDN
3 ({)r
(154)
14 (21, 22, = EDN
( Runy ( (22)
(155)
Then, the learning measures defining the loss functional lation indices as in (44)
(8) are obtained by summation over popu-
E.1 RESOLVENT
Given the connection between resolvent and learning measures , p()), ( p(+) described above, we that the resolvent moments (148) and (149) are fundamental building blocks for the loss func-
tional (8. In this section, we try to calculate these moments and simplify the result as much as possible.
To start, recall that the Tr[R(=)] gives the Stieltjes transform of the empirical spectral measure k== 8% A central quantity in our calculations will be Stieltjes transform of the average spectral measure μ [
=
r(z) = /
u(dt)
1 [T]](())]]
(156)
Next, denote resolvents of kernel matrices with one or two spectral components removed as
R_((z)= = f2 (z) N AAsoboo)
Σ m3l1
Am Dm -
(157)
N
R R R (2) N
1
1
Σ
Am Am Dm 21
(158)
N
mifh
and the respective Stieltjes transforms r=)(s), (=)- In our calculations, we will use two assumptions Assumption 1. (Setf-averaging property). For a random Gaussian vector & (O, indepen- dent from &
N N O 1 (2)((2)) ["R(220]=r(6 r(2).
Assumption 2. (Stability under eigenvalue removal)
(2-r(z)==-116) r(z).
In classical RMT settings, e.g. that of Marchenko-Pasun law, both of these assumptions can be rigorously shown. Specifically, both the statistical fluctuations of x o R(2) and the change of
32

---

Published as a conference paper at ICLR 2024
r(2) after eigenvalue removal give contribution the limiting spectral measure as N co. We leave for the future work the validity of these assumptions in our settings.
As final preparation step, let write down quick way of deriving the self-consistent (fixed-point) equation for r(z) using the above assumptions. Starting with the trivial relation = N Tr[I] we get
=
1 N
Tt
R(=) NV Σ A
-
=
Σ A N
1
2 N
(2))0) - =r(2)) (159)
Next, we relate $ ) Φf (=)) via Sherman-Morrison formula in order to break the dependence between Φi and the matrix inside.
X N R (2))0)) 2
o R (2)
N Φ R(=)(i H R (2) (
1+ A o R (z)
1+ \ 2 (2)
(160)
11) (2)
(2)
r(z)
+ 11
+ Xer(z)
where in (1) and (2) used the assumptions I and respectively. Substituting this into (159 gives the self-consistent equation
r(=) 1+r(2)Ai
1 1= -2-2)
(161)
which is often written in fixed-point form
r(2) (1)==1/ /
A
_ N
(162)
For -1 < O, we have r(z) N for effective regularization BeH,NN defined in 11
E.1.1 COMPUTING THE RESOLVENT MOMENTS
Reflection symmetry. Here, we mainly repeat Simon et al. (2023) to establish useful exact rela-
tions for resolvent expectations. Recall that distribution of Gaussian random vector ~ ~N
remains invariant under orthogonal transformations: Uz ~ _/(0, I). where U is an arbitrary orthog- onal matrix. Now, we notice that our averages of interest [154) and (155) have form E& [f(K Φ)
for some function f(---) of empirical kernel matrix K = 4 and "features" 4. Applying
transformation U perturbed kernel matrix 4 U U + gives
E [[f( LAAD"UAA'G Φ. Φ) E [
T A U$)]
(163)
we take to be a reflection along one of the basis axes, e.g. (U(m)) = 8w - 28mm) for reflection along axis m, then ( A(U(m))r = A. This implies
E [f D) =E [(0" A U(m))
(164)
Applying (164) to 154 and 155) gives their non-zero elements are only those with paired indices: (z) for the first moment and Ruer 22), Rar (21, Ra Æ2) for the second moment. Moreover, note that we interested only in those components of the resolvent second moment that contribute to the loss This leaves R2vv(21 22) to be the only relevant components.
First moment. Here, all the necessary computations were already done in 160). leading to
r(2)
Ru(x)= = 1 Avr(z)
(165)
33

---

Published as a conference paper at ICLR 2024
Second moment at 21 22. In this case, the second moment is connected to the derivative of the first moment, which was utilized by Simon et al. (2023) and Bordelon et al. (2020) to obtain the generalization error of KRR. Indeed,
2 R(2)Ø1
Revilz, 2) E
Φ ((2)
T Am
d
Em
Am
21
(166)
-
Φi
Φ
-xy Ru(z).
N
As prerequisite for computing the derivative 0x (2), we compute similar derivative of inverse Stieltjes transform (2). Differentiating the fixed point equation (161) in the form r-1 Art w.r.t to either 2 or Xp gives
El
N
Actr
0r
N
I
Apr
=-1,
(167)
8z
N
(Ar
0r-1
X
1
Apr-1
1
x-2
(168)
Qλv
N
+
+
N
(1r +
N
(Au + 1-1
leading to
dr
dr
--2
(169)
dz N (Au + 1r=
dr-1
(170)
Oz
1 Ei
Apr-2
14++-117
Using this, we second moment becomes
-0g Revi(2, 2) = - Ru(z) = 11 N 12 +r
dR
(171)
Second moment at 21 * with formula, including two subsequent applications to break dependence with Φi, Φr. Denoting Ry (z) the resolvent with, possibly, removed eigenvalue, removing an extra eigen- value can be written in simplified form under assumptions [and]]
Here and the next case / * l' we will again ap-
ply Sherman-Morrise
R (2) R$ (2) + Aer(z)
A
R (2) 2 R # (() a ((),, di0"" (x)))())))) (172)
where ((X, Y, X aXYX is polynomial in two matrices X, Y and scalar variable a, and (z(2) is shorthand notation for /1 + Apr(z)).
Using representation
[12 we can write our second moment element
Ruu (21, 22)
E [rr (X, Y, Y, Y2)])
(173)
where we have denoted
X, (221) R
Y
di0T N an a(()),, 02 a((2)
(174)
Now we exploit the independence between X1, X2 and Y by first taking the expectations w.r.t. Y. Since Y is product of two Gaussian random variables and (T73) is polynomial in Y containing monomials of degree from to 4, need to compute Gaussian moments of the order from 4 to 8. This can be conveniently done using Wick's theorem for computing moments of Gaussian random variables, which equates 2m-th moment to the sum all pairings of 2m variables of the products of m intra-pair covariances. Specifically, for normal vector x ~ \/0 I), it reduces to the products of Dirac deltas
E [i Fig ... Fiam-1 Fizm
1
Σ
II
E
Σ
II
2m
2m
aESam
j=1
(175)
34

---

Published as a conference paper at ICLR 2024
where S2m denotes the group of permutations of the index set (1, 2m- 2m). Now apply Wick's s theorem separately to each monomial from (73). For the simplest order-two monomial, we have
By [THYX, YX,]] N
Σ (o) [ox, de (Xi)s in 05 (X2)s 44--
- (Tr[X,) Tr + X2))
=N-2 Tr|X]] TF [x + Tr [2[
(176)
21 22
- r( r172 + O(N
=r(2))((22) +
21
22
where r2 is a shorthand for r(21), r(z)) Here we first applied Wick's s theorem, then transformed
the product X2 -x (21- Then, we wrote the resolvent traces in terms of Stieltjes transform 1r[X1,2] = (2122) using assumption (T). thus removing the need to take expectation with respect X1, X2 the remaining calculation of the second moment Ruu 21, 22). An important ob- servation is that when computing the moment of order the leading term in N has to be the product of traces Tr Tx[X,], while the other terms (containing at least one trace of a product) will give ONN contribution. Using the above observation, can easily compute leading terms for all the other averages:
Ey [T YX YX, N N -(N-)) +
Ey YX;
= N Tr + 0(N~)) = - =
(177)
Ey [Tr YX YX, YX2]] = "TX,, O(N-)) rir2 O(N-)).
Combining all the monomials, we can summarize the whole computation as follows
(21 22) = q(r,, (,.r,,,,r)))ee 1,a1))(12,,)) 1,02) + O(N-))
(Ar 1 [(x + + +O(N-), (178)
where in the last equality used q(r(=), 1())))) (=) Note that in the limit 21 22, the expressions above coincide with previously derived (17I) up subleading O(N-1) terms.
Second moment at 21 * 22 with I + V. Here we need to remove two eigenvalues A and Av. The respective resolvent expression is
R(()) =q (
ar(=)) = (R (-)()),
o.ΦT , (2)),,
d N ,=ra))))))
N
(179)
ai (2),
210
an (z), ar (2)),
N
N
where
TX, Y, Y', d') l(o( Y d)), a.
(180)
= XXX d'XY'X + ad'
Substituting 179 into 149
will produce expression of the form
Revi(E1, 22)
E [Tr Y, Y', ai, a'), Y, Y', ag اb)]]
(181)
Φu N of az (21), and al ar (22).
where in addition to (74) we have denoted Y
Now, 1et us again calculate the expectations over Y, Y' using Wick's 's theorem. The difference with the case that the pairings between & and Φi produce zeros due their independence. For example, the expectation for the simplest monomial is
Ey,y (X,
E ~V Σ
10h, o'_ (X1); 6s Φ, (Xe)s (1
N
441
(182)
1 r(=)) r
-N
Tr
N
21
22
35

---

Published as a conference paper at ICLR 2024
Observe that the monomial above has N magnitude. This is the consequence that N terms from the / = case arose from pairings between Y' and Y. which are zero in the + case. Taking into account the symmetry (2 22) Ryr (22, 21), we proceed similarly and calculate the leading terms for all the other independent monomials.
Terms with X2:
By,y Y [TrYY'X, -N +0N 3)
By,y XX, || O(N-))
(183)
By,y,
B YX, |,"
- -
New terms with X₂ 2
Ey.y X
YX,, YX, /XX (184)
Ey XXX,
3N -NN TrX Tx +X O(N-2)
New terms with X₂ Y'
Ex,y
YX, ,X, Y 7X1
E [Tr Y'X, Y'X YX YX, = N N " -
(185)
E E [Tr Y YX Y'X, YX,Y X'X
3N Tr X I Tr +ONN 3) 3)
New terms with X₂ XX, Y
Ex.Y (TXX, Y X,
YX2 Xxll
N Tr X2] Tr Txx +O
(186)
Ey,y [T,Y'' YX, X YX, YX, Y'x2|l
3N X X2] Ir 2 22) + +ONN 90 O(N
A new term with X2 Y'X, YX,:
EY [Tr YX, Y' YX
(187)
= = X2 + 9TH TX +N -
To summarize, observe two types of monomials. The first type has the order O(N-2) and composed of those monomials which take X,' from qX1, Y, a',,",",,a ,a,dd)) and/or
X2 Y'X, YX, from 7(2,, Y, Y', a22 a²). The rest of the monomials g(>)")))), contain exactly one factor T+(X,X,) = N have the order O(N-1), and satisfy
1 - r2 g (2,,,2,,11 1,1) +O(N-2)
Ey,y' [9(X1, X. X,Y)))
N 21 22
T172
(188)
1 r2
g (11,
+(N (0
N 21 22
Thus, the leading 1(N-1) term for the second moment with l + l' is given by
R 22) =
ri - -
II
[r. - (a, + a,) +a, +
N
21 - 22
1,2
(189)
1 ri T2
ri T22
(\v + 1z + O(N
N 21 - 22 (N+r - -
Again, in the limit
21 + 22, the result above coincides with previously derived [7] up to sublead- ing (N) terms.
36

---

Published as a conference paper at ICLR 2024
Summations over 1' and I in (44). For the loss functional will need not the bare second mo-
ment Rurr((21, 22) but the sum Vv X (2r 22). First, let us start with the case 21 = 2/ where
X
the second moment is given by (71). The essential sum to compute is Ev (Ap -y Using the fixed-poing equation [61 gives
O2r 0-r-1 XE.
1
a r Ax (r = +2) 0,r Av +r- Oz
(190)
N
(Av 12
N
O2
We can substitute this result into the second moment to get the desired second moment sum.
Σ Rurile2) = X (1r 0.r 'r=
(191)
(Ar 1r+2-1122
Now, we proceed to the case 21 * 22. Similarly, from (199 we see that the essential sum to compute
22 1 1 - -r2 Σ (Av + tri [A + +ri N
Avri
Aurz"
Σ
N 21
22
Av
+r
d +
1
(192)
1 -1
12
1
21 22
which is basically a finite difference version of the sum for 21 = 22. Again, we substitute this result into second moment sum to get
X7 - [ -
Σ XB 22)
22)
21-22
+ O(N
(193)
(Ar t 1(x+r2))
Now let consider the sum over l in in the form
First, observe that the first-moment term from enters
LdAA)(=))= = Σ -
A u(=).
Ex+r (2)
(194)
Here encountered the first auxiliary function u(2) introduced (4) However, directly performing the respective sum for the second-moment term does not automatically reduce it to an expression with "decoupled" factors (depending only z1 or z2 but not jointly on 21, 22). Yet, can perform an additional transformation to express the result in terms of decoupled factors. Representation of fractions product difference, similar (922. gives for two parts of Σ1, of Ruvr 22)
c rr 1
Xre
27
01
U2
Σ
(195)
(Ar + +1 r5
A +
- Gri +
Σ1
of
El
(M++1 ((
21
Actri
22
Autra
r1
12
11
0/2
22
(196)
where we have encountered second auxiliary function u22) defined in putation of the second moment, we have obtained
14
Summarizing our com-
v=21) v(22)
Σ Rurr = u(21) u(22) + +r (22) R
Σ o
(197)
21 22
Thus, we fully expressed the population sums of resolvent moments in terms of two auxiliary func- tions v(2) and u(=), which would later define our final result for the loss functional.
E.2 LOSS FUNCTIONAL.
In this section, we using the resolvent moments derived in Section E.I.I to compute the loss func- tional (44)
37

---

Published as a conference paper at ICLR 2024
KRR case. As sanity check, let's first compute the loss for the case of KRR learning algorithm (2) = ___
z-11 with the expectation to recover the original expression In the absence of target
noise 0² 0, we have
Li(by]
0²=0 0
Σ
Xi Rurr(- -1) - R2( +1
r
(198)
XP Nen(1 Tmt
d
Oe (A: + nen)
- 2
+1
(Ar + nen)²
A 7ef
For the contribution of noise term we have
c/
X2 Φ (-n))1 -2
1 N
E
Φf R(-n
(199)
X2
0 Ra(--1) = (Ae + mott)
Combining noiseless and noise contributions, we obtain
()RR(1) = n1. Oe
0² X70
(200)
(A1 + net)
2N (Ar 7eft 7
which is the same
General case. Now we turn to our main goal of describing learning measures pl2),p(), (0,,p( De- note, u(\)= limy-so, u(> iy) and u(A) limy--o, v(> +iy. Then, for the first moment of the learning measure, we have
(dx)= =E
Parpi (1) (d))= = TAy-+0
1 lim E idda= TT
3u(()
dd.
(201)
I.
For noise measure p1 (dA) we similarly obtain
+A Sw(A) x²²
0 (d)) πス 9-0
lim
di,
(202)
where ((A = limy-so w(A + iy) for the last auxiliary function w(z) defined in
14
Now we proceed to the computation for the second moment of the learning measure p (dA1. d22))
using the relation (152). We have
(dd(,, d22)=
lim Σ Ed
R(im) 18g4, (A1 + iy1, X2 iy2)dA1d22.
(203)
T2A
91 00
00
Note that while for the first moment we simply have Rij (2) (2), the relation between Re R(fm) 1522 (21, 22), and previously computed Re (21, 22) less straightforward since the product of two imaginary parts has to be taken out of expectation. This can be done with the following trick: for two random variables Wi, W2 we have
WiW2
wi W2
E [w
E [w] W2]
E [Swn Swa]
E
R
R
(204)
2
Taking W1 (i (21), w2 Rri(22), and noting that R(2) R(Z), get the desired second moment of imaginary parts
Rurri m Rurr(Zz,22) 22)
(im) (lfin (z1, 22) = E RRr (z) ) (3 = .
(205)
Observe that the part u(z1) + u(22) Σ, o7 Eiv of Remillz 22) gives no contribution when substituted into (055
R (u(21) + =((2))
2) - (u(21) + u((2) - Σ of) = R Rl((2)) u(>2) = 0. (206) Σge
38

---

Published as a conference paper at ICLR 2024
Indeed, the remaining part has non-trivial contribution that will compute below in the limit 21 - A1 + i0, 22
+ A2 + i0.
lim Σ AZ 11192222 (A1 + iy 22 + iyz) y1 +0 y2+ 1.1"
r(\1 + iny) - v(A2 + iy2)
R lim
r (A1 +
+ 18/2
2 in +++
t A2 + i(y/1 - -922
(207)
2/ +0+
(A) + ig))r ir - -1y2) u(A1 + inn) - v(22 iy2)
+ R lim r
2 +
X1 X2 + i(yi + y22
02 +
The first limit here be easily taken in joint way 1/1 1/2 y 0+. leading to
lim r (01 iy1)r- (22 iy2) eA11 iy1) v(A2 + iyz)
v( v(>2) r(A1)r(12)(A) - A2)
(208)
yi +0+ +
A1 X2 + i y2)
Note that this expression is regular at \ X2 since we assume v() to be differentiable.
The second limit might have a non-vanishing singularity at λ = X2, for which we will need to use SakhooskiiPlemee) formula lim,-v0+ I
1 = ird(2)) + P(E), where P denotes the Cauchy principal
value.
u(11 iyz) v(A2 iy2)
lim 1 (A1 + iy1rr (A2 in/2
Mi +0+
A1 - X2 + i(311 + 1/2)
+0
lim -- + inn (A2) v(\1 + iuy) v(12)
81 ツーー
d1 A2 + in
v(A1) uA22)
=/r (A))
- X2) +r +r (2))
ty A2
(209)
Note that the singularity at A X2 under the Cauchy principal value is purely imaginary and, therefore, will disappear after taking the real part (07). Next, us combine (208) with the second term from 209)
(A2) v(12)) (A1) (A)) - -o(Aa))
R 2
do A2
3(r (A22 ( - (r)))
(210)
A2
{ (A1) 3( ((((21)33(11111)))
\y A2
where in the last line have used the relation r- r E, of -u. into the learning measure second moment
uu. Finally, we combine all the terms
(d) d22)
(AD)(
3(b(A1)]8(A)
- -22)
dA1d12
TPZ
(211)
3((AA)))((-
22222
A1 A
Thus, we have derived the expressions and (16) of the main paper.
E.3 POWER-LAW ANSATZ
The analysis of the loss functional given by 15 and (16 is much more tractable for continuous approximation of our basic power distributions
Σ (ax) +
1 - =x(d)),
Σ (d2) + 1 Hc(d)). (212)
39

---

Published as a conference paper at ICLR 2024
In partieular, the fixed-point point equation (161) for Stieltjes transform r(2)
becomes
== = (z) + N /
1 r (=) ddA
(213)
x+)
We will encounter many integrals similar to the one above, with the general form
(x ( xadX
A x+ a>-1, x [-1,0.
(214)
Such integral can be expressed in terms of Hypergeometric function 2 2F1. This can be immediately used to get asymptotic z + 0 expansion, which will be very useful later
Fa(x) 2/i (1, a, a. a
O
(215)
(1 + aax
sin
(Ta)
For this asymptotic expansion, we assume that x has a cut along R_ and $ Z.
Below describe the essential steps in computing the loss functional for the Wishart model.
E.3.1 SOLVING FIXED POINT EQUATION
In this section, will analyze asymptotic N solutions of fixed-point equation (13). Note that we are interested in the solution of this equation when approaches the real line from above:
r(A) = lim r(A + ie).
(216)
c00
First, let us find values of when Sr(A) = TT((A) > 0, which corresponds to support of the empirical spectral density ((A) of K. For this, let write (-) iv. and rewrite (213) in the limit s + 0 as a pair of real equations
X( + -
x N -X- v2 mx(d))
N /
(X)2g
0
7) 2² Mx(d))
(217)
(X'
N 7)2 m2
1
(X)²
Now, let fix value of corresponding the point outside of the support of μ4, where O. and therefore t & supp(μx) = [0, to ensure convergence of the integral. Since the solution of the fixed point equation for z C4 is unique, there should be no value of and e satisfying equations 217). But since À can be defined for any value of u, the second equation should have no solutions with v F Due to the monotonicity of the expression the brackets, this gives necessary condition for 7 corresponding to the point outside the support:
(N)² N (X' (N)-)))M(dd)) <
1
/
(218)
Additionally, it is easy to that for the values of 7 not satisfying the inequality above, there is solution of the second equation in (277) with v < 0, which induces the solution of the first equation with some X, meaning that the triple (X, (A,T,8) v) corresponds the point inside of the support of μ.
The argument above fully characterizes the support of μ: there two support edges X_, } with the respective values 7- < T+ > given by the equality version of 218). The right edge T4 should be at a distance ~ N-1 from = 1, where we have
1
(X' W (x (xx)) = 1 +(1
(X)²
o(1)
(1(1) dx'
N
N
Jo
(X T+)²
(219)
(1)
1
(1 +o()) = =
N
T4
T4
40

---

Published as a conference paper at ICLR 2024
From the calculation above and the first equation in (17). the right edge is given by
(1(1)
= 1+
(1 + o(1)
N
(220)
4 (1
log N N o(1))
log (T+ - 1) + (()) = (x(1)
N
Turning to the left edge of the support, we note that it has the order N Thus, we can use asymptotic expansion of Hypergeometrie function (15) with a leading to asymptotic form of fixed point equation
T/V C (2). C. = N
2 = (2) +
(221)
sin(T//)²
where we, for simplicity, do not write (1 + o()) correction factors in the asymptotic.
Then, for the left edge of the support we have
= 1 1 110F_ (-T- - iv)
C. 100-T--io----
C C. v
(---)- (222)
(222)
Nv
i0u
N
i0v
N
v=
which gives the respective left edge values
T- --- ( C2) N
1w-1)-- N
(223)
A_
Now, let give more explicit solutions of sxed-pointt equation in different scenarios.
To the left of the support (A < A_). In this region the solution of fixed point equation is real, and will in fact has lot of parallels with KRR applied to the Wishart model. Thus, we translate A and r(X) to their KRR notations: 7 -À is the KRR regularization and Jjoff r- is the effective implicit regularization, appearing in ( In these notations, the asymptotic form of fixed point equation becomes
7
Cy -1
+
N Netf
(224)
Boff
When Nef has the scaling 2 V, we can write nett N- and 1) ijN-", which satisfies N-independent equation
7
Collat
(225)
7ett
The equation above gives a nontrivial relations between îj and Tefr. However, when N- < fett < 1, or in other words it has the scaling ( < v, the relation simplify to an explicit one:
neff = 17 + N "
(226)
Inside the support (A_ < < A+). In this region it is convenient to write r()) (d(e)
with the phase taking values in the upper half-circle: 0 < & < æ. Substituting ro (o(A)e into the limit form (22T) of fixed point equation we get a pair of real equations
X ro- (- (-cos cos à +
C₁ (ro) 1 cos ((1 1
(227)
N
-1 sin ((1 )
0 to sin Φ
N No
(228)
Let us rewrite the second equation here using the left edge value r_ (-T-)-1
- ( sin
sin Φ
To = --
N-
(229)
sin ((1 20)
sn ((1 4))
41

---

Published as a conference paper at ICLR 2024
Thus, see that the solution of fixed point inside the support is mostly conveniently described by using the phase & as a free variable, and then specify the rest of the variables by the mappings + to and (To. d) + À given by equations (229) and (227) respectively. In this representation, < = corresponds to the left edge A_ of the support, while Φ > corresponds to the right edge of the support.
As for outside of the support case, we see that on the scale N the fixed-point equation admits N- independent form. Specifically, set À = \N- and ro = No Then, the triplet To. o, satisfies
- (To) cos Φ + (To)) -1+ cos ((1 - 2))
(230)
sin Φ Cv sin ((1 }m)
To
Finally, we turn to the values N < X < 1, corresponding to the scaling In this case, the pair of equations (227)
(229 becomes
C 1+ A 0
N(TT Φ) )(
T/V
) (1+ (TT cot
cos(
N
0
(231)
π
To
N(T
Noting that in the leading asymptotic order rn --1 1, the second equation be rewritten as
(232)
N
We can summarize the above equations in a single complex equation
--1-1 r(A) (A)=->-1 (1- /o)( -=
(233)
N
In particular, taking the imaginary part of Stieltjes transform above gives Br(X) 1
N mux (A). This
implies that for N- < X < 1 the (normalized) empirical eigenvalue density N Nu(A) coincides with population density (A) as expected.
E.3.2 LEARNING MEASURES
In this section, we specify the form of empirical learning measures (d)), d)2), (dX) and (dA), derived in (00) 202) and (16) respectively, for the case of power-law distributions (112) Note that all three learning measures are expressed in terms of r(A) and imaginary parts of 3 aux- iliary functions v(A), u(A), w(A), whose asymptotic form will now analyze. In the continuous
approximation 212 these functions are given by
o(A) = / (
f ON) X +
w(A) = L' (X)=-+dX
w(A) = -//
X -+r-((A) (234)
X +AA)
Since all of these functions have the same functional form expansion of the imaginary part this integral, using (15) as basis. First, we consider <
X+r x+--1(X let write an asymptotic
(X
and use the leading term of asymptotic expansion (215) together with asymptotic formulas 227
and 229p.
S.
dX + r(1+ (l-+a)r(-aa3 a((-))((8 -ims)
(235)
π sin( sin(am)
N sin
C, sin ((1 106)
42

---

Published as a conference paper at ICLR 2024
Importantly, away from left edge X > X_, or equivalently significantly simplifies
< 1, the above expression
[ (p 0 X +
) (1+ (+) -1)
3
(236)
= (1+ (1+0(
The the leading term above is expected: since 3r (2) < À for >> X_, the fraction can be approximated with Sokhotski formula 3 -44- (X) 2 (X'). However, our approach with asymp- totic expansion of Hypergeometric function in (215) also provides estimation of correction term to the Sokhotski formula, which would be difficult to obtain directly.
Let now take into account the omitted subleading terms in the asymptotic expansion 213 These terms make regular power series in x, and therefore their imaginary part can be estimated =
(A)) = ( A'
Thus, we can summarize our computation for A_ < X << as
s L.
(X + = = + + + +
(237)
Note that while the asymptotic form above is mostly meaningful for À > A_ when the corrections as small, we can formally use at for ~ X_ but the corrections become of the same order as the leading terms.
The values functions Bv(A), (n()), Sw(A), can be obtained by using either 235 or 237
depending the scale of X. In particular, when x_ < X < we have
3e(A) (M) + 1
N
1
BA(A) = AA) +
(238)
N
Sw(A) = (A) 0
N
As an important application of the expressions above, let estimate the scale of the off-diagonal (2)
part Poti (A1, A2) of the learning measure (12) (A1, A2) given in (16). Using (238) and (33 we get
2 -- x (1 (1+0 N π T21122N(Ar A2)
o - (1+0
0 N-)
Poft (A1, A2)
(239)
Now will estimate the scale S of Poff (A1, assuming that A and d2 have the scales 31 and respectively. First, assume that A1 X2 has the same scale as their maximum ê1 V Ag. Then, the corrections to the leading terms in the numerator can be neglected, and the scales of both denominator and numerator are given by minimal scale of two subtracted terms. Specifically,
ST I s2) (1 s1 #52) (5s1 + -- "=1 (s1 s2 1+ $1 A2)
(240)
2
82
Yet, the scale derived above may not be valid when A1 and A2 are to close to each other. This does not happen, which can be seen, for example, by writing the difference in the enumerator of Poff (A1, Aa)
(2)
and observing that the whole expression behaves regularly as x + X2. Then, similar argumentation together with (235) shows that the scale derived in (201) holds when both s $2 v. Thus, for all X1 A2 inside the support of we have S(p (>1, 82) 2
$2.
Finally, estimate the contribution of off-diagonal part of the second moment the loss Tu [h] ((()))(A2))))) (dd,, dd2). For that, we can use a two-dimensional analog of proposition which can be proven similarly.
43

---

Published as a conference paper at ICLR 2024
Proposition 6. Let gN (A1, X2) be sequence of functions with scaling profile Sta) (2), and let AN > be a sequence of scale O. Then, the sequence of integrals Sax Sax gN (A1, d2) has the scale
$ loN(d1, 22) dA1d22
min 05e1.825a
(810)
81 + 82).
(241)
AN JAN
Applying this statement to Loff ((ii (d)1,
(f)))))))) dd22), we get
[Lott] 2 min 0Se5i
8-81 1-81 - (()) + 5 (82) + + 82 21.
(242)
In other words, we have shown that
J (ONN dA2) O(N-))
(243)
Actually, the estimation above is tight, which can be shown, for example, by taking h(A) = computing the leading order term above, which will be exactly N-1, Note the presence of N-1 term in the loss, regardless of the value of 6, v is unnatural for our problem because we expect be N which can be smaller than N-1, The reason for
the rate of the optimal algorithm this unnatural term can be traced back to our calculation of the resolvent second moment in (189) and (178, where in the application of the Wick theorem we took into account only the pairings producing leading order terms in N. Thus, we might expect that taking into account subleading order pairings Wick theorem would lift the (243) from ONN O(N-2). What would be the
(2) role of the off-diagonal Pott if we took into account all pairings (i.e. performed non pontuutuureetie computation) clear the moment and is interesting direction for future work.
E.3.3 NOISY OBSERVATIONS
For noisy observations, our goal to show the equivalence between full loss functional and the NMNO functional (Theorem 2}. In terms of the population densities yx (A) and Mc(A), the NMNO written as
/
0² [ N
L nmmo)) [h]
(A))a)))) + (1- (A()) dd
(244)
N-v
Let us decompose the difference between two functionals
2 (w(A)
[[h] - (umuo) [h]
()(A)) (2(2))
N
T²²
|r- (A)ISS0(A)) mo(A) (2(())
+
x²²
(245)
Bu(A)
-Ha(A) M(2)) da
Td
N-
1
/
h2 (2) (1 (1--(())) ( da axls)))
2
Now, similarly the translation invariaan model on a circle, we write down the scales of all terms in the difference between two functionals, assuming that À has the scale s. For that, we use asymptotic expressions (238) for functions v, u, w, and also expression 233 for (X).
44

---

Published as a conference paper at ICLR 2024
s
0²
Sw(()
-a(A) ( (2)
21 21-8- (1 - + (s),
(246)
N
x²²
(A)))
Mc(A)) 12(2))
5 48 (1 ") + )))
v 5) + (s)h
(247)
T22
3u(2)
mc(a)) )((2)
2 3 (1 + (5 + (s),
(248)
Td
0²
(()))
+ (s),
(249)
N
s (1 h(2)) Mc(A)
- + (s)
(250)
For the last two terms, we do on the level of the whole integral, which is taken over a single scale
= V.
S
N h
(A))AANA) = -2)
(251)
N- /
(1-h(A))
= = 25(2
(252)
Using the scales derived above, need to obtain the conditions on the learning algorithm scales 5(2-h), ((h) for which the scale of all corrections to the loss is greater than the scale of NMNO loss given, as usual, by
s (mmmo) [
min o5s5u
[(5 ())))))) (1 -1-3 ( 22)
(253)
K ++
Again, this means that we can neglect all corrections whose scale (after integration with dA) is greater than 6 x+1- In particular, we can neglect O(V-1) correction coming from off-diagonal part of the second moment 243
First, note that the terms 251 and (52 exactly equal the contribution of noise (449 and sig- nal (250) parts at scale
V. Thus, if these terms are to be neglected,
should not be
localization scale of L (nmno) [h].
Second, observe that the right parts of 0A ( s) and (A("=*s) s) in 247 and 248 when activated,
give at most O contribution to the total loss, and therefore can also be neglected. Then, after choosing the left option, we see that (248) is never less than (47p. Thus, the total contribution of these two terms can be effectively described by the scale 5s
(1 +) (s))
Lastly, we can see that (246) is always larger than corresponding NMNO noise scale (49 except for where they are equal. But since already require not being localization scale of (nmmo) [h], the term (24 can be neglected.
Thus, all requirements in addition to s = not being a localization scale of (nmno) [h] can be summarized as
min 5o + (1- 0505u
(1-1) 3) 5()
>
min ose5v
(5* 25(1 ^ 25(1 (s)()
(254)
However, we have
K 5s + (1 - -)= + 5(h) 2 1 1 K 05e5y
min
(255)
K+1'
therefore, the requirement (55 satisfied automatically. Summarizing, the corrections to the
NMNO functional asymptotically vanishing when is not a localization scale of 7, [_(mmoo][]]]
45

---

Published as a conference paper at ICLR 2024
E.3.4 NOISELESS OBSERVATIONS
Now, we take x² 0 and analyze the respective loss functional. Recall that our current calculations are accurate up to (,, as we discussed before. Therefore, we will neglect all the terms that give contributions of the order O(N- since they are beyond our current level of accuracy. This means several things:
1. We ignore the contribution to the loss of the off-diagonal part f'h(Ai)((22)) (dA1, d22) of the functional.
2. We ignore the O correction to 3r(A) and Su(A) in (38): in the previous section we have shown that they have most O(N-1) contribution the loss.
3. We restrict ourselves with the values of signal exponent 1. Since the optimal scaling of the loss in the noiseless case is expected to be N" we will not be able to capture it for
K 2
4. The previous point also implies that we cannot access values 2v > 2 corresponding to the noiseless saturation phase since eigenvalue exponent values are confined to the physical region v >
With the above remarks taken into account, we start deriving the loss functional and, for compact- ness, ignore all the " terms. First, due to the diagonality of the remaining part of the learning measure 2 (dA1, dd22), we can immediately specify the optimal algorithm and the respective de- composition of the functional
I (A))S(())
(Su(A)) + (Ha(A)- T/ (A))S(A))S
) ) dA, (256)
[MM] 2 X
x²2
AA (*) (A) =1 11+0 0
(257)
where we have used asymptotics (338) to estimate the deviation of the optimal algorithm from k-1 h(A) = 1. Again using 238 we see that the free term in (256) has the order 0 A "
) which,
N
given < 1, always localizes on the maximal scale v. If we additionally assume that the
learning algorithms fits higher eigenvalues well enough: |1 (AA) = O(V in (266) will also always localize on the maximal scale v.
the first term
Now, relying on the fact that the loss localizes on s = v, we can use expressions of all the terms in the functional through the phase é. Eigenvalue is defined by an explicit form of (227
sin Φ sin(á 2)
A= N-
sin o( cot( x) cot Φ).
(258)
Using 235 and 229
the terms of the functional become
(A)
sin Φ
sin( x)))
(259)
T²²
C sin $)
sin t π sin? a( cot( 1-1 1p cot
sin Φ
-atv
sin ( cot col( - cot x)) =-
Mc(A)=
(260)
C. sin - -)
(3u(A))²
sin ②
sin 2 の)
(261)
(1/-1((A) (A)
Cv sin ()
si )) sin mt)
The optimal algorithm is
cot(2-1 )) cot
I*(A)=
(262)
cot / () - cot
46

---

Published as a conference paper at ICLR 2024
Substituting everything in the loss functional gives
x
sin Φ
sin (Ø (h(() h
2
Cv sin +
psin T sin 25 cot( -ー 1) - cot o)²
(263)
1 ( sin Oi cotl(= - cot ()) -1
sin sin (5
d(NvA)
+
de,
vsin のの) sin
dep
Finally, we note that the Φ + π asymptotic the expressions under the integral above can be inferred from the respective
x N + 0 asymptotic of the original functional, since
N (1 + o(T 6)). Thus, we can write
PN
L(h|
N
[0((T (m- ()) -((o))
Φ)) ()-mtttt) (1( (0(()=+))(0pppp))))))
1((A)))
dis (264)
From the above expression we see that, if = expression under the integral is integrable at Φ æ Therefore, the upper integration limit can be shifted without changing leading order asymptotic of the loss.
11) = O(V= Φ), the
Overlearning transition. As we discussed above, our analysis of Wishart model in the noiseless case is restricted the values of target exponent к: due O(N-1) accuracy of calculations. Thus, if < 2, we can access overlearning transition point K. = - 1 < 1 and verify whether the transition holds for the Wishart model. Proceeding similarly to respective Lemma for the circle model, we have
Lemma 3. Consider the optimal algorithm
266
cot 1- 1)) cot
h (*)))
(265)
col cot
with eigenvalue X (( E (0, T) parameterized according any Φ E (0, x)
258
Then, assuming < for
< 1, k ++1u h (A)
1, K 1 = v,
(266)
1,
x+1> n.
Proof. Observe that both the nominator and denominator of 265 have the form g(a, o)
cat(aş) co)(Φ) with E 10, & E x). Since (ot is strictly decreasing on (0, r), the function g(a, Φ) is 1) positive at fixed ø is strictly decreasing in Thus, for the ratio of such functions, we have
g(a. Φ) < 1, a > b g(b 0)
1, a b.
(267)
1, b. The above is equivalent to the statement of the lemma
b x
The above result shows that the behavior of the sign of h(A) 1, which indicates overlearn- ing/underlearming, exactly the same in the Wishart and Circle models. This makes believe that overlearning transition can be a quite general phenomenon going beyond two data models con- sidered in the current work.
F EXPERIMENTS
F.1
FIGURE I DETAILS AND DISCUSSION.
Let us start by describing the experiment setting and details. Both KRR and GF plots use optimally scaled regularization y and time 1, derived in Section C For all three data models, consider
47

---

Published as a conference paper at ICLR 2024
ideal power-law population spectrum: X = - of 1---1 (truncated at P 4 x 10 due to computational limitations), and an adapted version X = (2(14+1)) |q|2 = (2) --_
Z for Circle model. The extra factor of here is needed to asymptotically align population spectrum small A: for all three models we have (c( Al) A and μx (IA oo)) - - x 0.
The figure contains 3 types of data that are computed in different ways. The first type is scatter plot markers and corresponds to the estimation of generalization loss via direct simulation. For Wishart and Cosine Wishart (see Section F33 models, this amounts to sampling empirical kernel matrix K and observation vector y, calculating the generalization error for the resulting sampled realization, and finally averaging the result over n = 100 repetitions of the above procedure to estimate the expectation over training dataset DN in (3). Due to computational limitations, we were able to execute this procedure for sizes of empirical kernel matrix only up to N = 4 x 103, For Circle model, Theorem | gives an exact value of the expected loss (3) (i.e. no approximations are made during the derivation). Since for the considered type of population spectra the N-perturbations (TO) can be expressed in terms of Hurwitz zeta function (see (127), ) we compute analytically all the terms in This way, we are able to reach much larger values of N for the circle model.
Let us also comment on the estimation of the generalization error (3) of a given realization of Wishart or Cosine Wishart models. The expectation over requires scalar products
(K (x,,
Σ (x)
(xx,))
(268)
for points X, from sampled dataset DN- The expressions above can be used to calculate these scalar products experimentally since we have access to X Cr and already sampled feature values (x;).
The second type of data is depicted with solid lines and corresponds to the direct calculation of NMNO loss (17). which becomes a sum for discrete population spectrum. Assuming A are sorted descending order, NMNO loss becomes
- M(D)) o² N MAN
T. (nmmo) [h]
Σ
(269)
which we can easily compute for quite large values of N.
Finally, the third type of data is N oo loss asymptotic L = CN o()) depicted with dashed lines. The constant C we compute analytically, similarly to limiting expressions (38). (35) for noiseless Circle model and (263) for Wishart model. For that, we 1) recall (see Section the
v loss localization scale Sloc for the considered algorithms: $loc x+1 for GD and non-saturated
KRR, and $loc E {0, 2 P } for saturated KRR 2) and then get the limiting expressions of NMNO loss functional
For GF, we have algorithm profile (A(A) = =1 tt and loss localization scale is Sloc x Thus, we make change of variables x = XN x and i'N=iz leading to the following limiting loss
I (nmmo) [bo]
5 N 2
1 1 /
1 (X)3 +
x' (x) $ dx' X
(270)
Note that the integral above converges both at X' + 0 and X' + co, which reflects that our change of variables has used the correct loss localization scale. The integral in (270) can be computed either numerically or analytically by reducing it to Gamma functions.
For KRR algorithm profile is h, (A) X and loss localization changes between saturated and non-saturated phases. In the non-saturated phase, we make change of variables À X x.r and 7 N/NN rमI, leading to
N नम. 1 / (N)) + 22 dx' X' 2v.
I (umuo) [h,,]
(271)
2
Jo
(x+1)
In the saturated phase, the noise part localize at 9loc
v 2 which coincides with the scale of
regularization 7) 1/ N मम.. The signal part localizes at $oo 0 where the loss functional
48

---

Published as a conference paper at ICLR 2024
remains discrete, and we can perturbative expression for the learning algorithm 1,(2) 17* This leads
1. V.u o²
1 00 (2)2 ax m)++)) x + (4))
lej 1 X > 2v.
I (mmno) [hr)]
N
(272)
2
As for the GF, the integrals in (271) and (272) can be computed either numerically or analytically by reducing them to Beta function integrals with a change of integration variable 2 = X44"'
Discussion. The main conclusion of the figure is. indeed, the match between the actual values of the loss for a given model (scatter markers) and NMNO values (solid lines) for large enough N. This validates experimentally the statement of Theorem 2 Importantly, the Cosine Wishart model is not covered by our theory but still demonstrates the equivalence. We interpret it an indication that the equivalence holds for a broader class of models. At the moment, we are not ready to give any potential candidates for such class of models since it requires different set of tools than the one used in this work.
Observe that the match between the actual loss of data model and its NMNO analog happens
quite small N for big value of target exponent x = 5 (two right subfigures) whereas much larger N are required for small к 0.5. This is general manifestation of the fact that slower power- laws require much larger sizes N for asymptotic N - oo behavior to start working. For instance, NMNO loss [7 ignores the error associated with unlearned signal at eigenvalues À Amin. The contribution of this part can be roughly estimated as He([0, Aw))/Mo((0 1]) & N-* = e log Nx. which becomes negligible at exponentially large values of dataset size N > e=.
Finally, we note that only the third subplot of the figure (corresponding to saturated KRR) has different loss asymptotics for the Circle model one side and Wishart and Cosine Wishart on the other side. This difference is due to the respective population spectra which, although matching asymptotically À -> O, different at the head of the spectrum À 1. Then, since the loss for saturated KRR localizes at the scale s = 0 (i.e. X ~ 1) as demonstrated in Figure 2 the difference between population spectra À start affect the loss values. On the contrary, when there is no saturation (the rest of the plots on the figure), the loss localizes on some scale > 0 where the two population spectra become (asymptotically) the same. This is the reason why 1,2,4 subplots have single common loss asymptotic colored in grey.
F.2 FIGURE 3 DETAILS AND DISCUSSION.
This figure's primary focus is the comparison of different algorithms. Profiles of each of 4 consid- ered algorithms were obtained as follows: interpolation is simply ls(A) 1, the optimal algorithm was calculated from (23), optimally stopped GF was obtained by first evaluating the asymptotic loss (138) on a wide and dense grid of t values subsequently picking t" as the optimal among those values, and for optimally regularized KRR the same procedure (including both negative and positive regularization values) was used.
On the first plot, we validate the asymptotic loss value L (asym) = CN (dashed lines) computed from (38 with exact loss value at finite N given by (IT) (scatter markers) computed similar the respective values from Figure I On the remaining 3 plots we already exclusively use asymptotic expression (38).
Discussion. The first plot indeed confirms that asymptotic expression (asym) CN-* given by (138) can accurately describe the loss values with the correct constant C.
The second plot examines the behavior of the constant C' across the range of target exponent values K E (0, 2v), while saturated values k > 2v have different rate N 2 and thus not considered on the figure. In particular, in the vicinity of the saturation transition the constant starts to blow up C - do as K + 2v - O. The overlearning transition at K = // is also quite visible: for x < v all the considered algorithms have very close loss values, while for > 1 significant gap appears between optimal KRR and the optimal algorithm on one side and interpolation and optimal GF on the other side. This demonstrates that significant overlearning h()) > 1 is required for strong
49

---

Published as a conference paper at ICLR 2024
performance. Note that GF profile h₂(A) = = 1 < which forces t' do for K > 1, thus explaining exact match between green and grey lines for K <
Actually, it is quite difficult to distinguish loss curves of different algorithms (except for the over- learning gap discussed above) on the two left plots. However, there a well-defined (i.c. not due to numerical errors) difference between the algorithms (high zoom is required to it!). Such small difference seems to be an intrinsic property of the Circle model: we have tried wide ranges of x and and observed that in all of them, the relative difference between different algorithms of the order of 1% or smaller.
F.3 COSINE WISHART MODEL
The model is constructed as follows. Given a population spectrum A o E R, = 1,,,,,3, the features (2)) with x E S are defined as
0, 1 12 1,
Φ1(x)) = (V2 cos(tz),
(273)
and the training dataset inputs 2, E DN are sampled i.i.d from a uniform distribution on the circle S. In partieular, (233 ensures that E, (z))r ow.
The Cosine Wishart model can be thought as something intermediate between our main Wishart and Circle models. On the side, the population quantities of Cosine Wishart models the same those for the Circle given in (6). except for the presence of il(x+(')) terms in the kernel (<x,z") making it non-tran translation invariant. This last aspect does not move Cosine Wishart model too much from Circle, the respective empirical kernel matrix K would still be almost diagonalized
by discrete Fourier harmonics 2xk if the inputs were forming regular lattice. The more impor- tant difference is that inputs of the Cosine Wishart model are sampled i..d., which completely eliminates the possibility to analytically diagonalize K, which is a core step of the Circle model solution.
On the other side, for a given population spectrum A ct the structure of Cosine Wishart model and Wishart model similar in the sense that in both cases, random realizations of empirical kernel matrix K are obtained by sampling components of the feature matrix O with first to moments being Edi; and EDI 1, except for iE:o: spike in K. However, the most important difference is that for Wishart model, all entries of & are independent, while for Cosine Wishart there is a very strong correlation of entries 4n = v2 cos(lr;) with different / but the same i. This correlation turns out to be crucial and makes the Stieltjes transform r(z) Tr (K =1) no longer deterministic, which was the core assumption for our analysis of Wishart model based on the fixed-point equation
for Cosine Wishart which only amounts to a single
50


Reviews:
[{"review_id": "nxSJSwCT3C", "reviewer": "Reviewer_v7ue", "summary": "This paper develops optimization algorithms for KRR estimators using a new meta function termed ``spectral profile'', and shows its versatility to generalize to settings beyond KRR.", "questions": "* Is Figure 2 mentioned in the context? I'm kind of missing what those curves represent here.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Equation (7) in introducing the profile $h(\\lambda)$ seems new and interesting.\n\n* The theory appears to be rich, reasonable and self-contained.", "weaknesses": "* The paper may seem a bit hard to follow at the beginning due to certain missing definitions (say, $\\nu$ in equation (2)), which need further context derived from reading Section 2.", "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": "", "extra_scores": {}}, {"review_id": "sDUcWIyXdc", "reviewer": "Reviewer_jkPS", "summary": "This paper defines the spectral algorithms for regression task with Kernel Ridge Regression (KRR) and Gradient Descent (GD) as its special case. Then they derive and compute the generalisation error as a functional of the learning profile $h(\\lambda)$ where $\\lambda>0$ is the ridge and $h$ a function acting point-wisely on diagonal matrices. \n\nThen the paper assumes the two data models: high-dimensional Gaussian and low-dimensional translation-invariant model to further derive and interpret the generalisation error, recovering the result from previous study, as well as explaining some phenomenons in a new perspective, for example the saturation effect of KRR.", "questions": "I really like the idea of the generalisation error of spectral algorithm. What are the biggest obstacle to generalise the argument of this paper to more kernels?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality: The idea of spectral algorithm is novel and can be seen as unifying different common machine learning methods like KRR and GD. \n\nQuality: The paper contains both theoretical deductions and experimental validations. The citation is also very up-to-date. \n\nClarity: The paper is organised in a clear manner by mentioning the motivation at first and postponing the technical details in the appendix.\n\nSignificance: Although the computation limit on the two simple models, this paper is a first step into understanding the generalisation error of spectral algorithm in a unifying way.", "weaknesses": "There is almost no weakness except a few typos, for example, on section 4 EXPLICIT FORMS OF THE LOSS FUNCTIONAL (Circle model), on the fourth line it should \n$$\n\\hat{\\lambda}\\_k = \\sum\\_{n=-\\infty}^\\infty \\lambda\\_{k+Nn}.\n$$\n\nAlso, due to the complex form of the generalisation error, only two simple data models are considered.", "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": "", "extra_scores": {}}, {"review_id": "INZjLVEmoG", "reviewer": "Reviewer_wTWc", "summary": "This paper considers a general framework that expresses the generalization error in spectral algorithms. A generic formula is derived for an arbitrary choice of kernel and profile. Then, the analysis is specialized to account for the circle model and the Wishart model. The theory can explain the KRR saturation phenomenon. Finally, a simplified naive model for noisy observations (NMNO) was proposed, for which the generalization error can be neatly expressed, and it is shown that under certain conditions, the circle model and the Wishart model collapse into NMNO.", "questions": "* On page 3, when you define $\\boldsymbol{\\Lambda}$, what is the number $P$? Is it the exact rank of $\\mathbf{K}$ or its numerical rank, or it does not matter too much?\n* In the statement of Proposition 1, I do not think $\\rho$ has been defined before and I do not think it is a standard notation outside this community. What is the precise definition of it?\n* Can you make your conjecture on page 6 slightly more formal?\n* It's not a question, but I think your discussion of the circle model in the GF case might be related to this line of work below. Did you happen to come across these works and see some potentially interesting connections to your paper?\n    * Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang, Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks, International Conference on Machine Learning, pp. 322-332, PMLR, 2019.\n    * Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman, The convergence rate of neural networks for learned functions of different frequencies, Neural Information Processing Systems 32, 2019\n    * Annan Yu, Yunan Yang, and Alex Townsend, Tuning frequency bias in neural network training with nonuniform data, International Conference on Learning Representations, 2023", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper takes a generic point of view. It seems that the result can be applied to many different situations, which improves the power of the result.\n* The theory is nicely applied to provide a new perspective to already observed phenomena.\n* Overall, the paper is clearly written and most results are motivated.", "weaknesses": "* The analysis in the paper does not account for the errors induced by discretization. For instance, although it is claimed at the beginning of the paper that the theory covers gradient descent, what is really done is for gradient flow. Also, when the kernel $K$ is discretized using the samples, the following assumptions are all made about this discrete kernel, and it is not obvious how it can be connected to the continuous kernel.\n* Certain parts of the analysis do not obtain nice closed formulas. For example, those in `section 4` for the Wishart model and those in `section 5` for the noise-free case.\n* Although this is a theoretical paper, it would be helpful to include some experiments, even if they are on synthetic datasets. This helps explain (and justify) the theory.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)