Learning Curves for Deep Neural Networks: A field theory perspective
Authors: Omry Cohen
Or Malka
Zohar Ringel
Venue:  (2020)
Keywords: Gaussian Processes
Neural Tangent Kernel
Learning Curves
Field Theory
Statistical Mechanics
Generalization
Deep neural networks

Abstract: A series of recent works established a rigorous correspondence between very wide deep neural networks (DNNs), trained in a particular manner, and noiseless Bayesian Inference with a certain Gaussian Process (GP) known as the Neural Tangent Kernel (NTK). Here we extend a known field-theory formalism for GP inference to get a detailed understanding of learning-curves in DNNs trained in the regime of this correspondence (NTK regime). In particular, a renormalization-group approach is used to show that noiseless GP inference using NTK, which lacks a good analytical handle, can be well approximated by noisy GP inference on a related kernel we call the renormalized NTK. Following this, a perturbation-theory analysis is carried in one over the dataset-size yielding analytical expressions for the (fixed-teacher/fixed-target) leading and sub-leading asymptotics of the learning curves. At least for uniform datasets, a coherent picture emerges wherein fully-connected DNNs have a strong implicit bias towards functions which are low order polynomials of the input.    

Under review as a conference paper at ICLR 2020
LEARNING CURVES FOR DEEP NEURAL NETWORKS: A FIELD THEORY PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
A series of recent works established a rigorous correspondence between very wide deep neural networks (DNNs), trained in particular manner, and noiseless Bayesian Inference with a certain Gaussian Process (GP) known the Neural Tangent Kernel (NTK). Here we leverage this correspondence to provide explicit analytical predictions for the learning curves of DNNs any fixed target fune- tion. Focusing on datasets whose input measure is uniform on a hypersphere, our predictions match experimental curves very well and reveal strong implicit bias towards functions which are low order polynomials of the input. Two novel analytical tools underlay our approach. First renormalization group approach is used to show that noiseless GP inference using NTK, which lacks a good analytical handle, can be well approximated by noisy GP inference on related kernel we call the renormalized NTK. Second field theory reformulation of the problem allows a controlled perturbative expansion of the test error the inverse dataset size. We believe our approach lays the foundations for a more precise quantitative understanding of DNNs.
INTRODUCTION
Several pleasant features underlay the success of deep learning: The scarcity of bad minima encoun- tered in their optimization (Draxler et al. 20188 Choromanska et al., 2014), their ability to generalize well despite being heavily over-parameterized (Neyshabur et al. 2018 2014) and expressive (Zhang eet al. 2016), and their ability to generate internal representations which generalize across different domains and tasks (Yosinski et al., 2014 Sermanet et al. 2013).
Due to the complexity of DNNs our current understanding of these features is still largely empirical. Notwithstanding, progress has been made recently in the highly over-paramen pee-paaraetrrized regime (Daniely al. 2016 Jacot et al., 2018) due to the fact that the networks' parameters. in all non-linear layers, change in a minor yet important manner during training. This facilitated the derivation of various bounds (Allen-Zhu work, the following correspondence with GPs: Considering finite-depth DNNs which are much wider than the dataset-size, trained with MSE loss, weight decay, and at vanishing learning rate (the NTK-rreime) one finds that the imitialization-averaeed predictions are the same as those of Gaussian Processes Regression (GPR) with a kernel known the NTK. Several subsequent works corroborated these results empirically (Lee et al. 2018 Lee et al., 2019 Arora et al. 2019) and extended them (Arora et al. 2019). For fully-connected DNNs, the NTK-regime (and GPs associated with DNNs in general (Lee et al. 2018 Novak et al.) 2018) ) seems to faithfully capture the generalization power of DNNs trained with MSE loss (Lee et al. 2019).
al. 2018 Cao & Gu 2019b a) on generalization and, more relevant for this
One of the most detailed objects quantifying generalization are learning-curve graphs of how the test error diminishes with the number of datapoints (N). There are currently no analytical predictions or bounds we are aware of for DNN learning-curves which are tight even just in terms of their scaling with N, let alone tight in an absolute sense. In contrast, the theory of GPR is rich with analytical tools which have yielded in the past high accuracy predictions for learning curves, One of the most transparent ones is the equivalence kernel (EK) (Rasmussen & Williams 2005) which will be introduced in section 3 In short, EK gives intuitive functional prediction of the expected GPR predictor of a fixed target function when averaged over datasets of size N, and consequently of the learning curves.

---

Under review as a conference paper at ICLR 2020
Clearly such detailed understanding of generalization in DNNs is desirable. However, several technical issues prohibit the application of the EK and related results (Rasmussen & Williams 2005 Malzahn & Opper 2001) to DNNs trained in the NTK-regime. First, the NTK-regime corresponds to noiseless GPR where the DNN and corresponding GP both fit the training dataset exactly, whereas EK assumes Gaussian measurement noise the training labels. In the case of noiseless GPR, EK and related approximations break down and predict perfect generalization with very small datasets. Second, the eigenfunctions (features) and eigenvalues of the NTK are needed so that the EK can be interpreted. Third, as EK results can be misleading, it is important to estimate the validity range of these approaches and, in related manner, derive sub-leading corrections.
In this work we make the following contributions:
I We establish that noiseless GP inference using NTK can be well approximated by noisy GP inference on a related set of kernels we dub the renormalized NTKs.
II We obtain closed expression for the leading and sub-leading asymptotics of learning curves for any fixed target function (fixed-teacher learning curves) using extension of the field-theory formalism of Malzahn & Opper (2001) for GPR.
III For uniform datasets, where the input is distributed uniformly on hypersphere, these expression simplify considerably and, together with the features and eigenvalues we obtain for the renor- malized NTKs, lead to clear relations between deep folle-connected networks and polynomial regression.
IV Again for uniform datasets, we provide analytical predictions for learning curves along with estimates for their range of validity. We believe our learning curves estimates stand-out in terms of accuracy they get to within 3% of experimental generalization values. We emphasize that our predictions can be applied to fully-connected DNNs of any depth, trained the NTK regime, and that our approach provides a systematic way of making further accuracy improvements.
2
PRIOR WORKS
Learning curves for GPs have been analyzed using a variety of techniques (see Rasmussen & Williams (2055) for a review) most of which focus on a GP-teacher averaged case where the target/teacher is drawn from the same GP used for inference (matched priors) and is furthermore averaged over. Fixed- teacher or fixed-target learning curves have been analyzed using a similar rrand-canonical/Poisooo averaged approach (Malzahn & Opper 2001) as our, however, the treatment of the resulting partition function was variational whereas we take a perturbation-theory approach. In addition previous cited results for MSE-loss breakdown in the noiseless limit (Malzahn & Opper 2001). To the best of our knowledge, noiseless GPs learning-curve have been analyzed analytically only in the teacher- averaged case and in the following settings: For matched priors, exact results are known for one dimensional data (Williams& & Vivarelli 20000] Rasmussen & Williams 2005) and two dimensional data with some limitations of how one samples the inputs (in the context of optimal design) (Ritter) 2007: 1996). In addition Micchelli & Wahba (1979) derived a lower bound on generalization. For noiseless inference with partially mismatched dismaachhedprrors (matching features, mismatching eigenvalues) and at large input dimension the teacher and dataset averaging involved in obtained learning curves has been performed analytically and the resulting matrix traces analyzed numerically [Solichh (200T). Notably none of these cited results apply in any straightforward manner in the NTK-reeime.
Considering kernel eigenvalues, explicit expression for the features and eigenvalues of dot-product kernels (K = K(x-zz 2')) were given in Azevedo & Menegatto (2015). The fact that the 1-th eigenvalue of such kernels scales as d' (d being the input dimension), which we used in our derivation of the bound, has been noticed in Sollich (2001). Kernels with trimmed spectrum where the spectrum is trimmed after the first r's leading cigenvalues, has previously been suggested as a way of reducing the computational cost of GP inference (Ferrari-Trees Trecate et al. 1998). In contrast trim the Taylor expansion of the kernel function rather than the spectrum (which has a very different effect) and show that effective observation noise compensates for our trimming/renrmmaizzatio procedure.
Several interesting recent works give bounds on generalization (Allen-Zhu et al. 2018 Cao & Gu 2019b a) which show (1///N asymptotic decay of the learning-curve (at best). In contrast our predictions typically well below this bound.
2

---

Under review as a conference paper at ICLR 2020
3 FIELD THEORY FORMULATION OF GP LEARNING-CURVES
3.1 GPR DEFINITION AND PROBLEM STATEMENT
We begin with standard definitions of GPs and Bayesian Inference GPs. A GP is defined as a stochastic process of which any finite subset of random variables follow a multivariate normal distribution. In similar fashion multivariate normal variables, GPs also determined by their first and second moments. The first is typically taken to be zero, and second is known as the covariance function or the kernel K Kaz the GP distribution. The main appeal of GPs is that Bayesian Inference with GP priors is tractable. In GPR we use the posterior mean as the predictor g", and it given by:
[f)(()(())) where E|:] here denotes expectation under
gx(x.)
E 7,
K (K() o² 1
(I)
where v, is new datapoint, Im are the training targets, In are the training data-points, (K)] = K Kr,..m the covariance-mattr (the covariance-function projected on the training dataset D), and g² is the variance of the assumed Gaussian noise of the labels, which also acts as a regulator of the prediction. Some intuition for this formula can be gained by verifying that in the noiseless case (a² the prediction some training point æ. Ig coincides with that point's label g* = 9q.
The quantity of interest in this paper will be the dataset averaged generalization error which we define now. Throughout this paper will assume that both train and test points are i.i.d. random variables drawn from probability measure μ(r). With this in mind we define the generalization error of prediction g" or MSE loss as
(lg(x.)) - g" (x=)]1 - f (g(x.) - g" (xx)))
Note that g" is itself a function of N draws from js which make up the training set D The dataset averaged generalization error is (2) averaged over the ensemble of all possible N sized training sets. We denote this average as (-) D. so for instance the dataset averaged generalization error would be <llg* - -91=)) Dy We see that in order to calculate learning-curves, one needs to average quantities like 9" and 9ºh These averages turn out to be difficullt to handle analytically, to facilitate their computation we adopt the approach of Malzahn & Opper (200I) and instead consider a related quantity given by the Poisson averaging of the former
(...))
-
D.
12
where can be any quantity, in particular g" and g²2 Borrowing jargon from physics we refer to the original data ensemble as the canonical ensemble and to the above as the grand-canonical ensemble. Taking 7 = N, means we are essentially averaging over values of N in an VN vicinity of N. This means that as far as the leading asymptotic behavior is concerned, one can safely exchange N and as the differences would be sub-leading. In App. we compare learning curves as a function of N and 1) and show that they match very well.
Equation T determines the predictions, and therefore the learning-curr -urvees, but it not very convenient for analytic exploration of the expected predictions. This fact is due to the (potentially very) large matrix inversion involved, and the additional averaging over Dx required. Nonetheless there are some results for the expected prediction g², the most famous of which is the equivalence kernel (EK) result for the prediction fixed target function as a function of the training set size N (Rasmussen & Williams 2005):
gkk,N(x)=
Σ
An An + 0² / (n)
(4)
3

---

Under review as a conference paper at ICLR 2020
Where A and (x) here the eigenvalues and eigenfunctions of the kernel w.r. the input probability measure (1) and g(x) = Ln, (n) is the target. One notices immediately that the prediction breaks down completely in the noiseless case where (4) implies perfect estimation of the target with just one datapoint. To gain some intuition as to why having x² = 0 hinders predictions of (g") Dy one view it hard constraint (f(x,) g(nn) )) and hard constraints
typically less tractable than soft ones. Indeed this can also be seen as a motivation for considering the above Grand-canonical dataset ensemble. In related view, finite o² can be seen as form of averaging which smooths and regulates analytical expressions making them more tractable. Another limitation of the EK result is that (to the best of our knowledge) there no systematic way extend orders of I/N and get more detailed picture of GPR generalization.
3.2 FIELD THEORY FORMULATION
To facilitate the analysis of Eq. (T) we formulate the problem from a statistical-fiele www.dd-theorr/pallttte integral viewpoint (Schulman) 1996). These are well-studied, powerful approaches for performing integrations over space functions (the jargon "paths" when one dimensional and "fields" when is higher dimensional). This section is somewhat technical and the reader who is not interested in derivations is invited to skip to section 3.3 To get some familiarity with this formalism, consider first averages the (centered) GP itself with dataset. Using the path-integral formalism define the probability density functional of a GP with kernel K:
Polft = exp (- dede' [
(5)
JDD exp dddd' (()d="((
where I' Df denotes integration over the space of (well behaved) functions, for concreteness we x²) is the inverse covariance function (f dx' K [xx, x²) K (x', x²)) = 5(x x²)). Po is analogous to PDF with the sample space being the set of real functions. To define the
limit dx' some compact domain such as the hyper-sphere, K-1 (xx,
one first chooses an orthonormal basis dx) arranged in order of likeliness Pole Polo,] 2 Poløy] for i
of functions (x) (with respect
(note that this comparison doesn't require calculating the path integral in (5). Second, one expands
Σ; (x), and defines the path-integral as a series of simple integrals
F J [DFFIA= {
[[
(6)
where F is some functional of f (like Po in (5) Finally, one makes this last expression well-defined by taking a limit procedure where the number of integrals gradually taken infinity (Schulman 1996).
Performing the above procedure we show App. that a stochastic process with functional probability density Po is equivalent to the original GP. Following similar procedure, and denoting can show alternative representation of
|| dxdx' fxx) x')
N
g' g'(x,) = z-1 / Df f(x.) exp
(
lllll
[(f(z)) - -gn)²
20 n=1
N
Z = Df Dfexp exp
1f
> (f(an)) - )2
202 n=l
where Z is known as the partition function (see Rasmussen Williams (2005) for equivalence of and 7).. is useful to define the partition function with a " "source term":
[[a(z)] / Dfexp (-2
11f1 dza(x))(x)) 1 N
-(( gn)²)
(8)
202
==1
4

---

Under review as a conference paper at ICLR 2020
Then the GPR prediction is simply
('xx-)- ① logg ((((x)))))) da( (2.)
(a.))==
Dr(aa) where [a(x.) = 5(x - v.). -..) This form makes it clear that we can get quantities like dataset averaged predictions by finding the average of log Z. By using the grand canonical ensemble, averaging over be carried using the "replica trick" (see for instance (Gardner & Derrida 1988)). which aids in averaging over expressions like log(2) 2) and their derivatives via the equality Specifically:
draws from the dataset
log( () M0
z
a
ZM -
(x.)))
=
lim M-
da(x.)
M
(((
(10)
M / II m=1
M
(Z 1n
fm exp
fl li +
duze at Em -(()))²
where, as standard in the replica formalism, the computation should be carried positive integer M and the analytical result extrapolated to zero at the end. Neatly, Taylor expansion in r of the above r.h.s. yields the (...),, averaging appearing the hh.s.
The main benefit of (TO) over ( is that it allows for a controlled expansion in 1/1. At large (or similarly large N) we expect the fluctuations in (m)) to be small and centered around g(x). Indeed such a behavior is encouraged by the term multiplied by in the exponent. We can therefore systematically Taylor expand the inner exponent
20mm (fm (z)()))))
Σ M m=
(fm(z) -xx)))
- ΣM ( g()))2
+... (11)
20
20
and each term will yield higher order of (g" (x.)), in 1/n.. The first order of the systematic expansion we defined can be dealt with in exact manner, in which case we recovers the aforementioned EK
result 4 with the slight difference that N gets replaced with 7/ (see App. F for the computation). The second order term and further terms render the theory non-Gaussian and cannot be dealt with exactly but rather through the use of certurrbtiio-thhorrFeeeeeee wwwtrr/-eenaaaannnaanaaaaa
3.3 FIELD THEORY FORMULATION PREDICTIONS
Performing the calculation described in the previous section obtain the following closed expression for large N behavior of noisy GPR using any kernel, in particular kernels associated with deep fully-connected networks and convolutional networks.
(x*(),)) = PEK, ISL., (LL/r²)
(12)
7 k
7
9:03 (Ix) / du (x) (x) (x)
gss.,
A
The first term the familiar EK results but with N replaced by n,. The second term (gST..)) is sub-leading correction which captures the behavior at lower N's.
As shown App. F similar expressions for ),, are obtained using two replica indices. Interestingly we find that (g 7 = ) + ( Hence the averaged MSE error is simply (*9(())))) gxx.))² integrated over v.. Since the variance of g" came out to be O(1/7²) one finds that g" which is (1/n), is asymptotically much larger than its standard deviation. This implies self averaging at large v,, or equivalently that our dataset- dataset-averaged results capture the behavior single fixed dataset.
(x+)),
5

---

Under review as a conference paper at ICLR 2020
Equation 122 and the average MSE error are of our key results. They provides us with closed expressions for the dataset-averaged MSE loss as a function of 7) namely, the fixed-teacher learning curve. They hold without any limitations the dataset or the kernel and yield variant of the EK result along with its sub-leading correction. From an analytic perspective, once A, and Φ;(x) are known, the above expressions provide clear insights to how well the GP learns each feature and what unwanted cross-talk is generated between features due to the second sub-leading term. Notably for the renormalized NTK introduced below, the number of non-zero A finite, and so the above infinite summations reduce to finite ones. This makes these expressions computationally superior to directly performing the matrix-inversio in ① along with an --dimensional integral involved in dataset-averaging. In addition having the sub-leading correction allows us to estimate the range of validity of our approximation by comparing the sub-leading and leading contributions, as we shall do for the uniform case below.
4 UNIFORM DATASETS
To make the result [12) interpretable, (2) and X are required. This can be done most readily for the case of datasets normalized to the hypersphere ([|=,,ll = 1) with uniform probability measure and rotation-syni symmmetrc kemel functions. By the latter we mean Kr,s' = KOr,Oz' for any O, where O is an orthogonal matrix over the space of inputs. Although beyond the scope of the current work obvious extensions to consider are datasets which are uniform only a sub-space of x and/or small perturbations to uniformity.
Importantly, the NTK associated with any DNN with a fully connected first layer and weights initialized from normal distribution, has the above symmetry under rotations. This follows from the recursion relations defining the NTK (Jacot et al., 2018) along with fact that the kernel of the first conleece layer is only function of x x². It follows that the NTK can be expanded as Kz.z' = Σn, bn (x x')". An additional corollary (Azevedo & Menegatto 2015) is that its features are hyperspherical harmonics (x)) as these the features of all dot product kernels. Hyperspherical harmonics are a complete (and orthonormal w.r.t a uniform measure) basis for functions on the hypersphere. For each / these can be written as a sum of polynomials in the input coordinates of degree I. The extra index m enumerates an orthogonal set of such polynomials (of size deg(1) ()). For kernel of the above form the eigenvalues are independent of m and given by (Azevedo & Menegatto| 2015))
(
b2st! (2s +11 T [(s 5) (2s) (s+1+
A = VT T 2
(13)
==0
For ReLU and erf activations, the 6n 's can be obtained analytically up to any desirable order. Thus one can semi-analytically obtain the NTK eigenvalues up to any desired accuracy. For the particular case of depth 2 ReLU networks, we report in the App. H closed expression where the above summation can be carried out analytically. However as we shall argue soon, it is in fact desirable to trim the NTK in the sense of cutting-off its Taylor expansion some order m, resulting in what we call the renormalized NTK. For such kernels, which would be our main focus next, the above result can be seen as closed analytical expression for the eigenvalues.
Interestingly, for any connecco network and uniform datasets of dimension d on the hypersphere, there is universal bound given by X S K/ deg(() s O(d"),, where K is Kz.z which is constant in x. Indeed note that Kz is finite and therefore its integral over the hypersphere is also finite and given by J Kz, = Kr Σm \ Σ, dog(l) The degeneracy (dog(l) is fixed from properties of hyper spherical harmonics, and equals deg(!) = 2+ (l+d-2) (Frye & Efthimiou 2012) which goes as (ad)) for l < d. This combined with the positivity of the x 's implies the above bound.
T+d-2
Note that usually the hyperspherical harmonics are normalized w.r.t Lebesgue measure on the hypersphere, but in this context the normalization is w.r.t a probability measure the hypersphere.

---

Under review as a conference paper at ICLR 2020
Expressing our target in this feature basis g(x) Eim m pim Vi (I) 12) simplifies
a CK,0// d d t A + d2/n
g" 9EK,1
Σ
Dim Vim (x.)
(14)
where Ck = Em (2 -nnn///0--11 and notably cross-talk between features has been eliminated at this order since En Dim (2)(2)² is constant yielding En,. J duazsrm (1) de (x) bn. (+)
xx 6 By splitting the sum, Ck,02/1 cases in which A < <o² /n and their complement one has the bound CK < # #F FFFoo//+++ -n Lim|) A where # F is the number of non-zero kernel eigenvalues. Thus for kernels with finite number of non-zero A is, as the renormalized NTK introduced below, /n has a 17 asymptotic. This illustrates the fact the above terms are arranged by their orders in 7).
Taking the leading order term one obtains the aforementioned EK result with N replaced by Equating the two contributions provides an estimate of when perturbation theory breaks down. Focusing on A > a²/ /1), the perturbation theory appears valid when Ck,02/n < o². In the limit o² + O, and for trimmed kernels, this yield # < 7). Notably it means that the original non-trimmed NTK cannot be analyzed perturbatively the noiseless limit. In the next section we tackle this issue.
5 GENERALIZATION IN THE NOISELESS CASE AND THE RENORMALIZED NTK
The correspondence between DNNs trained in the NTK regime and GPR using NTK implies noiseless GPR (o² = 0) for which the perturbative analysis carried in previous sections fails. Here we show that the fluctuations of (x) associated with low X's can be traded for noise the fluctuations of fm()) associated with high X's thereby making our perturbative analysis applicable. As shown in the previous section, the lower X's correspond to higher spherical harmonics and hence have higher Fourier components. We argue that these higher Fourier modes can be marginalized over in a controlled manner generate both noise and corrections the high X's. This is very much in spirit of the renormalization group technique common in physics wherein high Fourier modes are integrated over to generate changes (renormalization) of some parameters in the probability distribution of the low Fourier modes.
We begin by defining a set of renormalized NTKs. As argued, an NTK of any fully-connected DNN can be expanded as Kr,,² Σy= by(x= z')". The renormalized NTK at scale r is then simply "...' - -o (x x²)5, Harmoniously with this notation we denote the prediction of GPR with the original kernel as g Our claim that GPR with K and a noise of o² can be well approximated by GPR with (rr) and noise o² + of (where of - by), for sufficiently large r. Specifically that the discrepancy between GPR predictions scales as D(VNd-(r+1)/ /Kz, where d is the effective data-input dimension. As can be inferred from (13), the renormalized NTK at scale r has zero cigenvalues for all spherical Harmonies with I modes have been removed from the problem. In a related manner trimming the Taylor expansion after (x z²)" effectively reduces angular resolution and coarse grains the fine angular features captured by these spherical Harmonics with 7 > r.
Thus, as advertised, these high Fourier
To justify this approximation we consider the difference matrix K(r) - Km first for + m and n,,' 's drawn for uniform distribution of a hypersphere of dimension The terms 6y Imm" scale roughly as do/2 (see App. H for a more accurate expression) due to the tendency of random vectors in high dimensions to be orthogonal. Consequently the above difference diminishes very quickly with r. Notably this also applies for K!..... Kr..,, provided x= is a test point and not train point. In contrast the diagonal part of the different matrix is simply 02..n,m and may Kr. æ, and the off-diagonal elements of the difference matrix, one finds that (I) with these two GPRs yields identical predictions. As shown in App. H these neglected off-diagonal elements yield a discrepancy which scales as / -d (r+1)/2 (since they sum incoherently). Consequently the MSE error between the two GPRs should scale as N. This scaling with N should saturate when the accuracy is nearly perfect since then the predictions remain largely constant as N is increased.
diminish more slowly depending on the coefficients byz-r. Upon neglecting K(Tr)
7

---

Under review as a conference paper at ICLR 2020
Focusing back on the question of how to tackle noiseless GPR, we thus find that long the by decays slowly enough with q, then at any finite N we can choose a large enough r such that two desirable properties are maintained: A. The discrepancy between the GPRs is small and B. of is large enough to ensure convergence to our perturbative analysis. The required slow decay of by is harmonious with the intuition that DNNS should be initialized the edge of chaos (Schoenholz et al. 2016) where the output of the network has a fine and multi-scale sensitivity to small changes in the input. As K the correlation of two outputs with inputs I and x', having a power law decaying by implies such fine and multi-scale sensitivity. Establishing relations between good initialization and effectiveness of our renormalized NTK is left for future work.
We have tested the accuracy of approximating noiseless NTK GPR with renormalized NTK GPR with the appropriate of. both on artificial datasets (see next section) and on real world dataset such as CIFAR10 (see App B.). In both cases we found an excellent agreement between the two GPRs for r's as small as 3 and 4.
6 GENERALIZATION IN THE NTK REGIME
Collecting the results of all the preceding sections, we can obtain a detailed and clear picture of generalization in fully connected DNNs trained in the NTK-regime on datasets with a uniform distribution normalized to some hypersphere in input space. We begin with a qualitative discussion and consider some renormalized NTK scale From Sec. 4 we have that the features of this kernel are hyperspherical harmonics and that X scales as d We also recall that / is the maximal degree of the polynomial appearing in the Harmonic and all Harmonics up to the degree / span all polynomial on the hypersphere with degree up to I. Examining (14) we find that features with X >> a² /n are learnable and via the above scaling we find that learn polynomials of degree O (log(n/o* // //lg///))))))) log(d)) or less. In particular function like parity, which is a polynomial of degree d very hard to learn whereas linear function is the casiest learn. Thus despite having infinitely more parameters than data-points (due to infinite width) and despite being able to span almost any function (due to the richness of the kernel's features), deep neural networks avoid over fitting by having strong bias towards low degree polynomials.
To make more quantitative statements we now focus on a specific setting. We consider input data in dimension d = 50 and scalar target function g(ar) E1=1, fim Yom (I)) such that
Ei=i. P. Σi=zm Iim = 1/2, but otherwise iid glm 's. We generate several toy datasets DN consisting of N data points (Ix) uniformly distributed on the hypersphere 5d-1 and their corresponding targets (g(x))). We consider training a fully-connected DNN consisting of 4 layer with ReLU activations and width W which we initialize with variance (o² of = 1/d) for the input layer and " = of = 1/W) for the hidden layers (see for instance Lee et al. (2019) App. C and App. E for how compute the kernel). To be in the NTK correspondence regime we consider training such a network at vanishing learning-rate, MSE loss, and with W >> N. One then has that the predictions of the DNN are given by GPR with x² 0 and the K given by the NTK kernel (Jacot ct al. 2018
For each such DNN we obtained the expected MSE loss 119te - g|l² of GPR with the NTK kernel by numerical integration over x, Repeating this process multiple times we obtained the dataset averaged loss < ) for N = 2. NMax with relative standard error of less then 5% (this typically required averaging over 10 datasets). For direct comparison with our prediction of the learning curve, we computed the Poisson averaged learning curve (Il. - -gll">, in accordance
with (3), neglecting the terms n > Nmax- We restricted ourselves to 7/max S *Nmax 5 Max to make tail effects negligible. Notably the Poisson averaging makes the final statistical error negligible relative to the discrepancies coming from our large approximations (see A).
Since the target function involves To have some headroom we start from = 3 which implies reasonable discrepancies of the MSE between the two GPRs of the order of N/ 5.6e 4, for the maximal N we have (N 3500). Our
0, 1, 2 the minimal scale for the renormalized NTK is 2.
"To be more precise. Jacot et al, (0188) predict correspondence with GPR up to a random initialization factor. so to get exact match with GPR one would also need to average over initialization seeds. Recent research (Lee 2019) suggests this caveat he avoided under some conditions.
8

---

Lastly we argue that the asymptotic behavior of learning-curve we predict is more accurate than the recent PAC based bounds (Allen-Zhu et al. 2018 Cao & Gu 2019b a). In App. C we show a log-log plot of the gearning-curves contrasted with 1/ 1 which is the most rapidly decaying Under review as a conference paper at ICLR 2020
analytical expressions following (3) combined with known results (Jacot et al. 2018 Cho & Saul 2009) about the Taylor coefficients (b,)) yield Ao. .o.. A3 = 13.19,7.27e - 3, 5.98e
6, 1.62c 7
and of = 0.018. Since Ao A > o² /n > A2, for 50 17 < 3500, Ck, 0² /110
[deg( (0)
(eg(1))o² (ddeg(2)10 thus /7,0 be valid for r) > 50. n 100 the and the = 2 features neglected, at 17 1000 they are learned but suppressed by factor of about features, they would have been entirely neglected at these v) scale.
51/n. Thus we expect perturbation theory to features are learned well since o² /n 1.8c
Had the target contained Experimental learning curves along with our leading and sub-leading estimates are shown in Fig. 1. left panel showing an excellent agreement between theory and experiment.
While no actual DNNs were trained in the above experiments, the NTK correspondence means that this would be the exact behavior a DNN trained the NTK regime (Jacot et al. 2018 [ee et al. 2019 Arora et al. 2019). Furthermore since our aim was to estimate what the DNNs would predict rather than reach SOTA predictions, we focus on reasonable hyper-paramette parameters but did not perform any hyper- parameter optimization.
ReLU
Averaged MSE With r=3 Prediction (o" =0.019
Renormalized NTK Prediction Devistion
Expedtennca IK Prediction SL Prediction
r= -60019
0.8
-8.015
r -0.015
0.6
(1g: -9:1P)ou
0.4
101*
0.
10
300
1000
1500
2000
3000
2500
0
N
Figure 1: Left panel: The experimental learning curve (solid line) for a depth 4 ReLU network trained in the NTK regime on quadratic target function on d = 50 hypersphere is shown along with our analytical predictions for the leading (dotted line) and leading plus sub-leading behavior (dashed line). Right panel: For the same dataset, we plot the dataset-averaged difference between predictions based on NTK (gtx) and the renormalized NTK at scale (g+)) showing excellent agreement increases.
bound appearing in those works. It can be seen that such an asymptotic cannot be made to fit the experimental learning-curve with any precision close to ours.
DISCUSSION AND OUTLOOK
In this work we laid out formalism based on field theory tools for predicting learning-curves in the NTK regime. Well within the validly regime of our perturbative analysis we find excellent agreement within 3% relative mismatch between our best estimate and the experimental curves. Central to our analysis was the renormalization-pe groop transformation on the NTK leading to effective observation noise on the target. Our analysis could be readily extend in several ways: Going beyond the uniform dataset case should be possible for multi-variate Gaussian input distribution with set of similar finite variances and set of nearly zero variances. Adding weak randomness to K Kz,z' to study the difference between empirical and averaged NTKs. It would also be interesting to extend our analysis to simple CNNs. The renormalized kernel can also be used for spectral analysis of the NTK and other kernels associated with DNNs.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. arXiv e-prints, art. arXiv:1811.049) Nov 2018.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. arXiv e-prints, art. arXiv:1904. Apr 2019.
Douglas Azevedo and Valdir A. Menegatto. Eigenvalues dot-product kermels on the sphere. ArXiv e-prints, 2015.
Yuan Cao and Quanquan Gu. Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks. arXiv e-prints, art. arXiv:1905.13210 May 2019a.
Yuan Cao and Quanquan Gu. Generalization Error Bounds of Gradient Descent for Learning Over-parameterizeed Deep ReLU Networks. arXiv e-prints, art. arXiv:1902.0133 Feb 2019b.
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Proceedings of the 22Nd International Conference on Neural Information Processing Systems, NIPS '09 pp. 342-350, USA, 2009. Curran Associates Inc. ISBN 978-1-61567-911-9, URL http:/ /tt::/dlllcco acm. org/
citat ion. fottiion.mmm?mm
cfm? 2=92222222999922222 2984132
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. arXiv e-prints, art. arXiv:1412.0233: Nov 2014.
A. Daniely, R. Frostig, and Singer. Toward Deeper Understanding Neural Networks: The Power of Initialization and Dual View on Expressivity. ArXiv e-prints, February 2016.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A. Hamprecht. Essentially No Barriers in Neural Network Energy Landscape. arXiv e-prints, art. arXiv: 1803::8803.0088,, March 2018.
Giancarlo Ferrari-Trecate Christopher K. I. Williams, and Manfred Opper. Finite-dimensional approximation of gaussian processes. In NIPS, 1998.
Christopher Frye and Costas J. Efthimiou. Spherical Harmonics in Dimensions. ArXiv e-prints, May 2012.
E. Gardner and B. Derrida. Optimal storage properties of neural network models. Journal of Physics A Mathematical General, 21:271-284, January 1988. doi: 10.1088//305-470021110033
A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks, ArXiv e-prints, June 2018
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. In International Conference on Learn- ing Representations, 2018. URL htLL/ttts////eeeeee///
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve Linear Models Under Gradient Descent. arXiv e-prints, art. arXiv:1902.06720. Feb 2019.
Dörthe Malzahn and Manfred Opper. variational approach learning curves. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Symthttic, NIPS'01, pp. 463-469 Cambridge, MA, USA, 2001. MIT Press. URL/http: //d] acm. www.oo/g/ttoooooooooo http/iitate on 2tdmmidd=29553333 2...29986600
Charles Micchelli and Grace Wahba. Design problems for optimal surface interpolation. 1979.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning. arXiv e-prints, art, urXiv:1412.660 December 2014.
10

---

Under review as a conference paper at ICLR 2020
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards Understanding the Role of Parrmerramttinnti in Generalization of Neural Networks. arXiv e-prints, art, 1IXiv:1805.1200 12076, May 2018.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang. Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian Deep Convolutional Networks with Many Channels Gaussian Processes. arXiv e-prinis, art. arXiv:1810005148, October 2018.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. ISBN 026218253X
K. Ritter. Average-Cass Analysis of Numerical Problems. Lecture Notes in Mathematics, Springer Berlin Heidelberg, 2007. ISBN 9783540455929, URL https:: i1/
books?id=x 16CWAAQBAJ
Klaus Ritter. Asymptotic optimality of regular sequence designs. Ann. Statist., 24(5):2081
2096. 10 1996. doi: 22114//s//0093362/ URL 1069362311
1214//00/
Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep Information Propagation. arXiv e-prints, art. 1oXiv:661.0012333 Nov 2016.
L.S. Schulman. Techniques and applications of path integration. 1996. URL httts:://bob/
co. co..co..iioo google.cc..1/oooksscccoo
Pierre Sermanet, David Eigen, Xiang Zhang, Michael Mathieu, Rob Fergus, and Yann LeCun. OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks. arXiv e-prints, art. 13Iiv:1312.6222 December 2013.
Peter Sollich. Gaussian Process Regression with Mismatched Models. arXiv e-prints, art. cond- mat/0106475,, Jun 2001.
Christopher K. Williams and Francesco Vivarelli. Upper and lower bounds on the learning curve for gaussian processes. Mach. Learn., 40(1):77-102, July 2000. ISSN 0885-6125, doi: 10.1023/A:10076616001777 DBL.:tppp./.aa...c/.....00000111
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Proceedings the 27th International Conference Neural Information Processing Systems- Volume 2, NIPS' 14, pp. 3320-3328, Cambridge, MA, USA, 2014. MIT Press. URL http: /dl. wal.aac..om wrw. cil cetatiiiinoo.m wttp::cccmcicmmocm htt.e/ac...ccc2m2222299933333300
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv e-prints, art. 10Xiv:6611.03500 November 2016.
A POISSON AVERAGING DEMONSTRATION
Here we demonstrate that Poisson averaging has no substantial effect on the learning curve. To this end show the experimental learning curve from the main text pre- and post-averaging. It evident that other than the unintended consequence of eliminating the experimental noise, the averaged learning curve is equivalent to the original for all practical intents.

---

Under review as a conference paper at ICLR 2020
Poission Averaging Effect Demonstration
0.7
0.315
0.310
0.5
MSE Loss
0.305
1480
1490
1500
1520
2330
0.1
0.3
0.2
(192 -9
(l02
2000 -0
B COMPARISON OF NTK AND RENORMALIZED NTK PREDICTIONS ON DATASET
While lack of knowledge of the NTK eigenvalues and eigenfunctions with respect a non-uniform measure prevents us from predicting learning curves, we would like to show that the renormalized NTK is still a valid approximation this setting. To this end we compare the prediction of the NTK and renormalized NTK on the one-hot encoding of the cifar- 10 dataset.
Renormalized NTK Prediction Deviation CIFAR-10
10"
r0.00|00.000 0.0038
1=200-000022
[=3,0] 0.0024
4.0,0
r=5,0 0.0039
-9:1"
(lle:
10
10a0
500
1000
1500
2000
3000 3200
C COMPARISON WITH RECENT BOUNDS
As mentioned in the main text, various recent bounds, relevant the NTK regime, have been derived recently. Notwithstanding importance and rigor of these works, their bounds have at best 1/ /N asymptotic scaling. Here we show that given a functional behavior of the experimental learning curves such bound cannot be nearly tight as predictions.
12

---

Under review as a conference paper at ICLR 2020
ReLU NTK Dataset Averaged MSE Loss With r=3 Prediction (o²=0.019)
Experimentaa
x
SL Prediction
4x10
gll
1x
(19
2x
6 10'
10a
2x
3x
4x10' 10
D NOTATIONS FOR THE FIELD THEORY DERIVATION.
For completeness, here we re-state the notations used in the main-text.
Ω - Space pace of inputs.
r, x,, x² Inputs (in Ω2).
Nr Measure on Ω.
K (ar, x²) Kernel function (covariance) of Gaussian process. Assumed to be symmetric and positive-semi-defiiic.
6i (x) i'th eigenfunction of K (2r, By the spectral theorem, the set ) can be assumed to be orthonormal:
/ ducdd (x) By (x) 8ig
A; i'th eigenvalue of K xx,)").
dp K (xx (x))) didi (x)
s'ER
I| || RKHS norm. If f (x) E, Side (x) then Il ||l E. L
(where di an orthonormal
set). Note that this norm is independent of pz-
(x) The target function.
2 Noise variance. The noise is assumed to be Gaussian.
N Number of inputs in the data-set.
D Data-set of size N, Dx {#1, .... IN.
fi (x) The prediction function.
E EXPLICIT PATH INTEGRAL COMPUTATIONS
Here we wish to prove the probability function defined in of the main text yields the GP defined by given kernel using explicit computation of the path integral. Denoting du (()) K-1 (x,x²) (x') || 12x and noting that || Σ, x
12
13

---

Under review as a conference paper at ICLR 2020
Notably, all other higher correlation functions split into products of the above correlation function due to standard properties of Gaussian integrals (Wick s/Isserlls'' theorem).
J Df f(x) (())) exp
(-2 2 l
JЛL df. E.di (x) E, 100 (1)
exp
( Σ1
[ [Dfexp exp (-111
III. dfi exp
(-2E, At
df fa. exp
(-2xi
2xi
di (I)
01 (v)
Σ
s df feep
(-hx)
2hi
l2
d f exp
(-
2A5
J df 2h:
exp
f2
#
S df exp
12
2x:
df
exp
2hg
82
Ai
0
Σ (z) K (2,
F GAUSSIAN PROCESS PREDICTION AS A FIELD THEORY
Let us assume a Gaussian process (GP) with mean and co-variance function K 2'),2). For data-set D of size N and noisy targets (o² * 0) {g (z,))== it is known that the posterior mean obtained by Bayesian inference is
- 9 (xx))²
SD 0² = arg min
Σ
/
20
E.DDN
For data-set D size N and noisy targets {g (m=) we present the GP canonical partition function:
ox a la (x)] def [ DDfess (-bur1i + (L) E (f g g (2;))²
20
FEDN
Where the Df notation stands for path integral. log pZ [a (x))) w.r. (x*) at a (x) 0 yields:
Notice that the functional derivative of
0
a Da (x*) a(z)=0
log (Z (2))
(ZDN la (x)))
Da (x*)
ZDN (x) =
(a(a)=0
DD f exp
-111111244
Σ
(g()))((2))) 2
x:EDy
arg min
2 |
(f (x.) g (zx))²
[D exp
expexp
11
Σ
(f(m:) g(a;)))
f
20
202
ZIEDN
where the last equality is due to the fact that for Gaussian distributions, the expected value coincides with the most probable value. Therefore, the exact baysian inference mean:
2 So o2 (x*) Dce (x+) cx(===
log (ZDv la (z)))
F.1 CANONICAL ENSEMBLE FORMALISM
for evaluating the quality of certain GP, we're we're interested in the average prediction for the data-sets of size N, meaning:
14

---

Under review as a conference paper at ICLR 2020
N. (x") def (f (x")) D f ddes / diisa... f dyaxx InN (a (x*).
Using the replica trick obtain:
7 DN [a (xi)) Dempp
lim θ M- dar (x**)
S (x*)
M
aaf)==
Now, let us calculate (zbm.o la (z)))
for an integer M:
Dumua
M
11
DDx la (x)]
Df
M
| 1
+ Σ
5 (c) Σ
(ʃs (x:)) - 9 (x:))²
exp
20
j=ImEDN
Dz la (2)]) DNruN = f dpez ... f dleeN
ZN
Z Dr 0² la (x)x)=
(fz (x) - g
II DSjexp exp
|| Hx Σ a [a))) (z) dx
exp Σ
2
8O
M Dx 2 la (x))
NN. (x*)
lim +0
Da(ar)
1a(x)=0
Dymay
M
F.2 GRAND CANONICAL ENSEMBLE FORMALISM
We now wish to allow fluctuations in the value of N, meaning averaging over fC (z*) for different values of N. The motivation is simplifyy the calculations, while averaging around relatively confined region Ns. Let us average the canonical prediction while weighting according to Poisson distribution with expected value y7.
C (x*)
def
c "n N! (N,2(x"))
==0
and defining:
20 Σ
2 M, (x)]
(ZM (a (x))) D
N!
N=
we get:
M (a (x))
FGC (x*)
lim
Da (x*)
a(x)=0
M-
15

---

Under review as a conference paper at ICLR 2020
That is, the functional derivative w.r.t (z*) at a (z) 0 yields the average prediction, averaged over different data-set sizes (the canonical averaging) and different data-sets for each size (the grand canonical averaging).
For a given 1/, the standard deviation of N is 17, so the relative error V" decreases with 7).
Substituting Zz (ax (x))) Dymuy
in the expression for M,02 fax (x)] we obtain:
(Z [a (x)])
2
11
N
M
Df, exp
- Σ
M
11
+ Σ f ax) fo (x) dr
M
N!
0
5-1
j=1
M
M
(fs (x)
9 (x))
Σ
cxp
20
j=l
Df, exp
1
Σ
fa(o))) (z)
2
1=1
N
(fs (z) 9 (x))
exp
N!
202
n
DfT...fM
M
exp
1
Σ
M
| Hx
+
Σ
M
(x) (x) dr +
exp
Σ
M
(x) (x))²
20
/=1
1=1
==1
F.3 DERIVING THE EQUIVALENCE KERNEL USING THE GRAND CANONICAL FORMALISM
We wish get rid of the exponent inside the exponent. Expending it using (first order) Taylor series:
16

---

Under review as a conference paper at ICLR 2020
M. [a (x)]]=
M
"1
Dff
M
exp
ΣニΣ 15551
+ +Σ
M
f
a (2) f3 (x) +1
exp
Σ
M
(fs (x) - 9 (x))
20
3=1
1=1
M
2 e
DJJ
2 Σ 11 + EΣ
1
(()) +17
1- Σ
M
(zz(x) 9 (x)))
exp
20
j=1
/ Df exp
[-21 + f((=)
(f(x)) (
def (2 [ax (x)))
202
k la (x)] = / Df exp
(-2111166 + +f
fa a (z) (xx du)
"
I dyi (z) - 9 (x))))
exe
20
and without any additional approximation:
ZEK [a (x)]) M
θ
M, [a -
a lim
-1
PGG (x*)
lim
da (x*)
(0(2)=0
M M-
M
da (x*)
(ar)
M-1
M
log (2 (a (I:))
n,00 [ax (z:))
da (x*)
z la (I)
da (x**
(a(x)=U
aax)==
1,02 (ar (x) = 0] / Df Df
1
exp (-2 |1STPPE
/ [())) (x) dr 20 f (f (x) و (=))²)
a(z)=0
DD S (x*) exp (- Hx S (x) (x)))) -s)
Dfexp -1 - +/2 (f -
+ n [ duz (2)x) (x))) def
arg min |1
po (x*)
fl.- 2
20
and that is exactly the result for the equivalence kerne,, where 77 is the data-set size (we regarded it as the mean of the data-set size).
Let us derive it explicitly. For f(x) E, (x) and g (x) E. (x)):
17

---

Under review as a conference paper at ICLR 2020
J (ff.f(x") exp -211fll
2 due (f
20
feek (x*)
DDpexp
- 111l Hx - 20-
[dz (5 (1) - (x)))²
III. df. Eisid (x*)
exp (-12;
[L
+ 3/ (fi - 9i) )
A.
I1I. [1.dfien exp
(-
[ A1
+ 2/ (fi (()))))²)
Ess(+t)) d fifi.f..cm fx.p
f:
y1
(fi 9i)²)
2A:
20
Σ
A
re 9:0: (x*)
S exp
12
22 (Ji - 91)²
F.4 EQUIVALENCE KERNEL AS FREE FIELD THEORY
Regarding the Equivalence Kernel as the free (quadratic) theory, we can denote 1. (x*)
A (f J~EKK (f (- = x - 9:0: 9:00 (z*).*
Let us calculate the correlations in the free theory:
( Df (z) f (1) exp (- 1111 22d ddu (f (z) - (x))) (x)))
DDeexp | I 2/2 d (s (x) - g (x))²
SII df. fef (x) Ø5 (1) exp (- [ + (f. 91)²) ))
III. df. exp (-bE, [ + 3 (fi - (fi-
(f)))
df. S7 exp
9 (f: - 9i)²
2x,
2n
Φi (z) 0: (v) + Σ
xggiA
Φ1 (I) 05 (1) =
f dfi exp
2x,
12
-
2
(f: -
#Fj
\i + e"
7
+ g2 77
(Ac+ + (2, +,))
2707
Σ )
(z)
Arg:Aygs
de (1)
Ai + o²
(2g + o²
(()))
Therefore:
1 " -1
Cov (f =
Σ
Φi (x) (g)
A
and we see that the correlations are O For rotationally invariant kernel, we get that
deg(!)
-1
Vi (z) def
Var [$ (x))
+
x²
Ckn
1=0 m=
is independent of x since
deg(t)
Y2 (x) = deg (1)
m=U
18

---

Under review as a conference paper at ICLR 2020
deg(!)
1
CK,,,z²
X + 1//2
F.5 PERTUBATIVE CORRECTION FOR THE EQUIVALENCE KERNEL
F.5.1
AVERAGING f
Going the next order in the expansion:
M (x)]
M
"
Df
M
exp
2 Σ
1
|
1 Mx
+ Σ
a (2) 13 (x) +
exp
Σ
(f, (x) - (x) 9x
20
==1
1=1
M
2 2
DJ
1 M
exp
11 11
PM
Σ
a fz)
2
Σ
M
(13 (1)
g (x)))
1
Σ J=1
M
(Jz (x) - g (x)))
exp
17
20
2
202
j=1
Df
M
+ ( "
/ dpc (fz (x) (z) - 9 (x))²² (()))
exp
2
20
due (x)) (f) (x)))
exp
8 j=1
Note that:
2n.M.o3 Ja [z)] -
GCC (x*)
lim
da (x*)
a(x)=0
M
M
My.Moo2 (x))
(zEK la (x)) = =0) w
Brx(2r*)
a(x)=0
lim
M-
ZEK ja (z) 01)
M
à oo(a
[a(2)=0 2n, (a (x)]
lim
ZZE Ja (x) 01)
lim
ZEK la (x) =0l)
M
19

---

Under review as a conference paper at ICLR 2020
Calculating the first order pertubative corrections:
a
aa()== Mo 00000 (x)]
(a((a))
CC (x*)
lim M-
M
M
1.02
far (x) = 0)
M
lim
M-
MZRK EK
[0)
n.02
M
M
/
| Hx
11
Σ
dpc (Jz (x) 2 (0))
exp
20
M
M
dic (f) (z) -x) ( -
Σ fx")=
exp
80t
lim
M
Dfy cxp
1
-
1 M
Σ
Σ
M
fdys
dype (fy (x) - (2)))
M-0 M
[0)a
2
202
j=1
3=1
M
M
M
M [1(+))+
1
Σ
du (J, - -00)))))0((()))0000))
17
80
j=1
M
1
lim
|+
duz (f, (x) - (z)))² (0))))9(00)
Ej((1) fi(tt)
-0 M
S
+0
173 =
(
M
M
M dp (fs (x) (x))) - 9 (x)))
= (f (x*))) + lim
E5. (x')
M + M
800
EK As EK
+0
= (f(x"") 11o
M M ΣΣΣ
/
1
lim
dyp
(z)()) ((()) (z))² (1)x))g<))) Sa (2*))
+0
M +0 M 80
173
Calculating the correction:
M ΣΣΣ 9())))
f. (1()))
-(
+M 1) g(x)))) (1(()) + (((()) (f (21))) 2 +M (M - 1) (U ( (s(x))
Note that we eventually divide by M and take the limit M - 0. so we only care about O (M) terms:
20

---

Under review as a conference paper at ICLR 2020
f (x*) = f (x*)
77 + 801
/ dus [(00)) -2 22 (((())-
(U(()) - -(()))
(1(")))))))))))))))))))))))))))) (1000->6))))0o)+++(((100100
1
+0
1p3
These correlations can be calculated using Feynman diagrams, since the free theory (EK) is quadratic (Gaussian):
(()))" (10)))
= =35 [f (x)) (1 (x) - 9 (x)) (z)) Var (x)) Cov (f)
+ f1.05s (x")
(1) (1) (z)
+12 (1 (z)-g(z)) (z)) Var If (zv)
Cov (f
(1)())
(fx'))
= =3f (x") Var [f (x))
(0))-9(()) +61 EKK (x") (J (1) g (x))² 2 Var [xx) + 1. (x*) (1 (x) g (xx)) 4
((F(0) (1100) ((f()))(()))
= 2ar [s Cov (x (1,05 (z)- + 1a (a") Var (x)]² +2Cov [ (FE (+) g (z))
FK (x") Var If (z)] (1i (z) - g (z))² + f (x") (feE (z) - g (z)) 4
(0)z)) (()))))))))) (1
1 (x") Var [f (x)]²
+2f (x*) Var If (x)] (F (z) (x)) 2 sor (x") (FEE (z) 9 (x))
Summing everything up:
- ((r()) ((((=)- ((0)))) (5(''))
(U(()) -2(())))0()))) - (1000)-0))))(((1000000)))) -1 I (x0)), +2 ((((x)))()))))) ((
=8 (f (x) - g (z)) Var [f (4)] Cov If (x).
and all the bubble diagrams cancel as expected.
So we get:
21

---

Under review as a conference paper at ICLR 2020
FEK GG (x*) = -na00 (x") + 03
71
/
djen (J (x) - (x) (x)) Var [ʃ (x)) Cov 1/ (x) . (x*)) +
1 173
Substituting the expressions for the variance and covariance:
f/o0 (x*)
-1
-1
+
fno (x*) - 77 Σ
+
7
g:0n (x")
+
773
A +
i.j.k
7
F.5.2
AVERAGING J
This time must use two different replica indices:
Ölog Dw (x)))
( (x0)1 DNmmp
da (x**
DNmue
<(
1 OzM Dy. la (x))
lim M-30 M
da (I*)
a(()=u))
Demua
lim lim A M0 MM / |DA... f DfM / Df.... / DDisees exp
|D....DDMM
M
M
2
Σ
1lfma
fm
2
7x
2
Mx
m=1
m==1
fm (x) (2x)
2
N
(fm (z) (x))
Σ fm (x*)
Σ
Fm (x*)
exp Σ
20²
202
m=1
m=1
m=1
m=1
Averaging w.r.t poisson distribution:
22

---

Under review as a conference paper at ICLR 2020
en (lsbxnoo (x')12
[ (2')1²) DNNuE/ NN-oo(())
=Σ
N!
N=
M M- di +0 MM / Df....
f Diss
/ D [DÅ.... / Df kt
lim lim
M
1 M
|
Σ
1mmllii
Σ
exp
-1)
2 m=1
2
Pix
m==1
M
fm (x) 9 (x))
M
(Ji (x) - 9 (20)
M
M
Σ m=1
Sm (x)) Σ
Sm (x*) ~
exp
exp
20
20²²
m=1
m=
m=1
xmppa
/ DS
/ Din / (D.... |Dfm
lim
lim
M= M +0 M
exp
1
Σ m=1
M
fl 1l
1 M
fm
+1
((-
Σ
(fm (x)) - (30))
(Jm (z) (x) - 1 (30)
(x)
2
HN
20²
20
m=m
m=1
m
2
M
(fm (x) -9 (x))
V
Fm (x)
g (x0)
M Σ m=1
M
+2
Σ
fm (x* )
Σ
fm (x*) =
2
-
20²
202
m==1
m==1
ampps
/ Df.... / Dfas / DJ fDfM
DDfm
= lim
lim
M-0 M +0
M MM
1 M
1 M
+ (
((-
(fm (z) - -9 (x)))
M (Jm (x) - g (30) 2
exp
fl Mxx
Σ
2
Hx
202
202
m=1
m==
m=1
2 2
M
(fm (x) - 9 (x:))
M
(fm (x) 9 (xx))
M
+ 7
+
Σ
Jm (x
Jm (x*) =
2
20
20²
(FEK (z²))² 2
M
(Ja (x) 9 (x)))² + M
(()))))(00) (c0)) )
M
M
+ lim lim M- M-+0 MM
80 / dip
Σ
Σ
Ee (x*)
Σ > Tuloo)
d=1
-r (a²))²
+ lim lim
M- M- MM 40t / dpps
Σ la=1
(Sa (x) -9 (x)))
Σ (x) (z)) Σ fa (x*)
Σ
fa (z5*)
b=1
d=1
M
2 M
M
(Ja (x)) - (x))
T (z) (())-9((e (x)))
(1a))<1 (xx)
Σ fal(o))
a=1
b=1
c=1
d=1
-JEK (x²))²
"1 /
dy
lim
1
M
(fa (x) - g (x)) M
(z) - (x))
Σ Se (x*))
M
1.00 (x*)
404
-0 M
(1g3) m(m)) Var (ono://tttt)a///fooooooootttto
saw in (f)
+ 11 f
M
M Σ 6=1
dup
lim
Σ
(Sa (x)
fo (z**) f1()t)
4
M M
23

---

Under review as a conference paper at ICLR 2020
and we're left with:
M
1
( - (z))) Σ (6()')
lim M-0 M
1 lim 1/ M ( + (M - (M (f -1f())-((z))) ]]=
N- M
- (f(x)))) 1) ( (f) - 9 (z)))) (F (x) - y (x)) Cov (
but this correction gives 0
( s0:
((UDn DN N.-Poi())
(F (x*))²+ +
27 GEK (x*)) f dip (Pelss (x) g (x)) Var Cov (f), (x + 0 ot
1
173
and notably
( 10
F.6 PERUBATIVE CORRECTION FOR ROTATIONALLY INVARIANT KERNEL
We now wish to evaluate this expression for rotationally invariant kernel and uniform measure on the hypersphere. This simplyfies the expression for (f) to:
fu (x*)
-g (x*) 17
g1 f dyu (JEE (w) g (x)) Var [S (x:) Cow [S (x), (x*)) + +0 +0 (1)
(1)
173
= -1 (x*) + 3. Ck.mo f /dw (Jrts (x) - y (a:) Cov (s (x). (x")] =
PEK (x')
11 Ck.
a²
1
9:03 (5*) / dpadde (x)) t5 (x) +0
(1)
Ai a²
)j
σ²
173
8y
o²
= PEK (x*)
")
Ck.y.02
Σ >j
72
A;
1
+
17 0²)
gith (xx) +0 11
173
=
= S (x*) - C..mo'
E
glm
Yim (x*) +
1
Im
0²
+
Auy
o²
o² Amn )
173
The expression for (12) is:
DNmMN Nosoa(n)
0 (1)
= =(EE (z²))² 2f (x*) C.
Σ
Yi, (x")
1.
o2 2
Am a
+ Xen
a²
773
24

---

Under review as a conference paper at ICLR 2020
G VARIOUS INSIGHTS
G.1 1 CORRECTION MEANS WORSE GENERALIZATION
The correction always means worse generalization than what the EK suggests. Indeed
f. (x*) = Sa (x*) CK,
E
ft.m
Vim (x") + +0
)1²²=
i.
o²
(2 +
Amy
o²
+
Xmn
o²
113)
Σ
91 Vim (x²) CK.m0z
g1.m
Vim (x**) + 0
1
+
oz
0² 2 +
Amn
o²
173
1m
71
1,
o²
N
C Ck.
Σ I.
mm M.m (x))
x²
0² +
Ain o²
+
a2 Amn
π
pasilive
G.2 EXACT RIGENVALUES FOR 2-LAYER RELU NTK WITH of =
For the NTK associated with a 2-layer ReLU NTK without bias we were able to fined an exact expression for the eigenvalues for all
02 ww d(1 + 2k) (1 2k)²
[ (T(k))))()) 2
Tw 0
A2k
A2k+1
Ōk
2T
8TT
r (
2T
is interesting to note that for all odd / A₁- = 0 so the expressive power of the kernel (and hence the neural network) is greatly reduced.
H ACCURACY OF THE RENORMALIZED NTK
For two normalized datapoints and x', drawn from uniform dataset on hypersphere of radius 1, and at large d the random variable (x x²) is approximately Gaussian with variance O(d-1). Since (a xx) is bounded to 1-,,1, 1], the random variable (x z²)" must have standard deviation which is decaying function of r. For r < d and large d one can estimate the magnitude this standard deviation from exact known expressions and a saddle-point approximation yielding ((d/r)-=/2) s O(d-r/2) Considering next the tail of the Taylor expansion Enor by x x²'9, projected on the dataset Egzr bz )). The resulting N by N matrix is Eg>r by on the diagonal but ((d-r++1/2) other entries. As we justified in the main text, our renormalization transformation amounts to keeping only the diagonal piece of this matrix and interpreting it noise.
Consider then I for g* in two scenarios: (I) 9t with the full NTK (x( x')) and no noise and (II) gf with the NTK trimmed after the r'th power (z, but with of = Eggr by. The first K (x. In) piece, for x. drawn from the dataset distribution, obeys K K(x,,,,, vn. - K,(I,, Fn) = Old (r+1)/2). Next compare K, (T (m of and K (Ir,,aa) On their diagonal they agree exactly but their off-diagonal terms agree only up to (dd-(++1)/2 discrepancy. Denoting by 5K the difference between these two matrices, we may expand K K-1 OKIK, + - K o2 KKK(, + 231 +
Kr + 22 + 8K]-1 = [K, + -1
AA more accurate estimate is (Fन53)
1/2
d=3
d/4
(
25

---

Under review as a conference paper at ICLR 2020
We next argue that [K + o multiplied by target vector (g(2n)) is negligible compared to the identity for large enough r thereby establishing the equivalence of the two scenarios. Indeed consider the eigenvalues of 8K(K, O(VNd (r++))2) and bounded by () The typical eigenvalues of K, + - are of the same order (x,, Fn.) = K and bounded from below by o.P Thus typical eigenvalues of 8K|K, + - are O O( K) and bounded from above by O(Nd ([Nd-(r+1//2/o) /of)) The NTK has the desirable property that o. decays very slowly. Thus certainly in the typical case but even in the worse case scenario we expect good agreement at large r. In Fig. right panel, provide supporting numerical evidence.
T As 8K is (dd((+11)2) its typical eigenvalues are
We refer K, (z, x²) as the renormalized NTKs at the scale r. As follows from (3) A with / are zero. Therefore, as advertised, the high-energy-secton has been removed and compensated by noise on the target and change of the remaining I (low-energy) eigenvalues. proper choice of r involve two considerations. Requiring perturbation theory to hold well (CK,,0?/n < of) which puts an 17-depended upper bound on r and requiring small discrepancy in predictions puts another dependent lower bound on r (typically v V (r+())1)//2 << 1).
Lastly we comment that our renormalization NTK approach is not limited to uniform datasets. The entire logic relies on having rapidly decaying ratio of off-diagonal moments ((r, Tmm) )²) and diagonal moments (z, zn)²a )r as one increases r. We expect this to hold in real-world distributions. For instance for multi-dimension Gaussian data distribution the input dimension (d) traded by an effective dimension (deff) defined by the variance of (Im ..))
26


Reviews:
[{"review_id": "r1eXnS1RKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper explores how tools from perturbative field theory can be used to shed light on properties of the generalization error of Gaussian process/kernel regression, particularly on how the error depends on the number of samples N. For uniform data on the sphere, a controlled expansion is obtained in terms of the eigendecomposition of the kernel. Although the expansion breaks when the noise term goes to zero, a renormalized kernel is introduced for which an accurate perturbative expansion is possible. A variety of empirical results confirm the theoretical analysis.\n\nThe results presented here are interesting and I particularly liked the introduction of the renormalized kernel to study the noiseless case. The agreement in Fig 1 is quite impressive, and the improvements relative to naive 1/sqrt(N) scaling as highlighted in App. C shows the power of the approach. The topic is salient and will interest most theoretically-minded researchers, and I think there is an abundance of new ideas and novel content. My only real concern is with the presentation.\n\nThis is a fairly technical paper that utilizes a substantial amount of physics jargon and many loose, hand-wavy arguments that rely on significant amount of prior field theory knowledge. I suspect that only a small fraction of the community will have the adequate background to get much out of this paper. For publication in a machine learning conference, I think more effort should be devoted to speaking to the machine learning audience. Some ways to achieve this might include reorganizing the technical points into bite-size chunks, laying out a roadmap for the main calculations and results, highlighting the important takeaways, including more figures, and concretely emphasizing the connections to practice and prior work.\n\nOverall, I am a bit on the fence, but leaning towards rejection for the above reasons. I could be convinced to increase my score if I am reassured that non-physicists are able to follow the arguments and find this paper interesting.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Ske_7mrk5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis theoretical paper exploits a recent rigorous correspondence between very wide DNNs (trained in a certain way) and Neural Tangent Kernel (a case of Gaussian Process-based noiseless Bayesian Inference).  \nA field-theory formalism was developed for Gaussian Processes (2001). Here it is thus extended to the NTK case. There are 3 important theoretical results which are both proven and backed by numerical confirmation.  These results, in particular the first, provide a very accurate prediction for the learning curve of some models.  The paper is well situated within this literature.  I am not very knowledgeable about NTK or even Gps, however I understand the challenges of understanding DNNs and I am familiar with field theory and renormalization group.\nGiven the importance and quality of the results, and the overall quality and clarity of this (dense) paper, I recommend acceptation without hestiation.\n\nThere are a couple of points however that could be improved, that would make the paper more useful for the community.\nGiven the density of results in the paper, I would relax the length constraint, allowing up to 9 or 10 pages if possible, to add more explanations (not computations).\n\n\nI would like the paper to present more explicitly how the regression target labels g(x) are generated. Maybe it is said but I couldn’t easily understand, for sure, how they are generated.\n\nAlso, please explain early enough what is meant by uniform dataset (I understood it simply means the data x is drawn uniformly at random over a manifold, here this manifold is often the d-dimensional hypersphere).\n\nClaim II states that ‘...lead to clear relations between deep fully-connected networks and polynomial\nregression’’. This is, I believe, supported by theoretical proof and numerical double-check, however it is not discussed enough for the abstract’s promise to be fulflled ‘a coherent picture emerges wherein fully-connected DNNs ...’.\nI think this point deserves a more ample discussion in section 7.\n\nMore generally, the claims in the introduction or at the end of section 3 are stated rather explicitly, but very densely, and the careful reader can get the hypothesis of each result from the text. \nHowever for the sake of ease of read of less patient readers, I think it would be appropriate to have, somewhere, a more self-contained description of the results’ list. This paper is technical and some readers will be interested of simply knowing the hypothesis made and type of results obtained.\nFor instance, the sentence ‘‘They [results] hold without any limitations on the dataset or the kernel and yield a variant of the EK result along with its sub-leading correction.’’ is misleading: as stated in the previous sentence in the text, this is for the fixed-teacher learning curve, etc.\n\nPlease try to explain a bit more the intuition behind renormalization / trimming terms q>r (r integer fixed, the higher the less approximated).  More specifically, it is not very clear to me how it can be interpreted in terms of how we look at the data. You mention (x.x’)^r being negligible or not depending on r,d etc, but I wounder if there is some kind of simple ‘geometrical’ interpretation (is it a coarse graining of the data in angular space, the ‘high energy’ eigenvalues corresponding to the high frequency, high resolution distinction between very close angles ?).  On that point I am a bit lost and it’s a pity because your results are strong and rely on few, rather simple/elegant assumptions (which call for some intuitive understanding).\n\nCould you explain intuitively, to the inexperienced reader, why the noiseless case is harder to deal with than the finite-noise one ?\n\nIn appendix D, it is mentioned that you need averaging over about 10 samples to have a decent average. For a single realization of a N-sized training set, there is additional variation (Adding or subtracting to the error epsilon).  Given actual experiments are typically performed for a single realization of the data, I think this point should be mentioned in the main text more explicitly. Ideally, you could add error bars to the data, accounting for the dispersion inherent to a single-realization case.\n\nIn early section 3, a short definition of a GP should be provided (there, or before).\n\nAround Eq. 2, you should specify the interpretation of P_0[f]\n\nAfter Eq. 3, ‘where F is some functional of f.’ I would add: ‘[where F is some functional of f,] for instance Eq. 2.’\nThe derivation of eq 6 is not obvious. You do detail it in the appendix, but forgot to cite the appendix !\n\n‘Notably none of these cited results apply in any straightforward manner in the NTK-regime.’ : could you quickly explain why (no matched priors ? Noise ?) \n\n‘‘The d^-l scaling of eigenvalues’’ : at this point, the variable ‘l’ had not been defined.\n\n‘‘notably cross-talk between features has been eliminated’’ : has it been eliminated or does it simply become constant ? \n\n‘3% accuracy’ [relating to figure 1]\nI understand the idea but accuracy seems misleading. I would replace everywhere with something like ‘relative mismatch’.  OR explain better why you call this accuracy: usually a high accuracy is preferred, and here you are proud with this very low imprecision of 3%\n\n‘’Taking the leading order term one obtains the aforementioned EK result with N’’ : maybe (just a suggestion here) you could recall it here, given it was in page 1 (and in-line).\n\n\nAppendix B:  could you explain why this difference increases with N ? I would have expected this kind of quantity to decrease with N.\n\nAppendix F: there are typos in the r.h.s. in the first line.\n\\sum_j f_j \\phi_j  (I think).\n\nAppendix G: ‘noisy targets’ : you mean fully random or Kernel + some degree of noise with variance sigma^2 ?  I think it’s the first time you use this phrasing.\n\nAppendix G: you denote \\partial / \\partial \\alpha for the functional derivative. I would replace with \\delta to stress out it is a functional and not regular derivative.\n\nBeyond\t appendix G.1 : I confess I didn’t have time to read it.\n\nDespite the overall quality of the text, there are a number of wrong singular/plural matchings, which can easily be corrected. Here are some of them, with other typos as well: \n‘Furthermore since our aim was to predict what the DNNs would predict rather [THAN?] reach SOTA predictions’\n\n‘a factor of a factor\nof about 3.’\n\nas do for – > as we do for\n\nuniformally - > uniformly", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxzbYLB5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper used the field-theory formalism to derive two approximation formulas to the expected generalization error of kernel methods with n samples. Experiments showed that the sub-leading approximation formula approximates the generalization error well when $n$ is large. \n\n\nThis paper is poorly written. Many mathematic notations and terminologies are not well-defined. The setup of the experiments are not given clearly. Here I gave some examples: \n1) The authors claimed that they derived two approximation formulas, EK and SL. I didn't find a clear statement in the main text saying which formula is the EK approximation and which formula is the SL approximation. My conjecture is that, Eq. (10) gives the EK formula, and SL formula is not given in the main text. In addition, Eq. (10) is confusing because the authors wrote that Eq. (10) is a simplification of Eq. (8). However, Eq. (8) was an approximate equality, then Eq. (10) turned into an equality. \n2) Figure 1 gives experimental results. However, the description of the experimental setup is completely vague. The authors described the kernel and the target function as \"the NTK kernel implied by a fully connected network of depth 4 with $σ_w^2 = σ_b^2 = 1$ and ReLU activations\" and \"a target function with equal spectral weights at $l = 1, 2$\", without other explanations. I don't think readers can figure out what is exactly the kernel and the target function from this description. \n3) I am concerned about the writing style of this paper. I am OK with the physics jargon the authors used in the paper, as well as the non-rigorous of the result. But I think the authors should write equations in a clear way. For example, the definition of renormalized NTK should better be defined in equations such as $K_r(x, x') = \\sum_{k = 0}^r b_k <x, x'>^k$, rather than be described in words like \"trim after the r’th power\". \n\n\nHere is a technical question: \n- It seems that the authors claimed that both EK and SL give approximation error O(1/N^3). Then why SL is the \"sub-leading asymptotics\"? \n\n\nI feel the content of the paper is somewhat interesting. However, the paper is poorly written. The authors failed to deliver effective scientific communication to the readers. The results cannot be reproduced after reading this paper. Therefore, I would give a clear reject. \n\n\n---------\nAfter reading the response and the revised paper: \n\nI found that the authors modified and improved their manuscript a lot. They made much effort to address the issues I raised. This is why I think I can potentially raise my score to a weak rejection. \n\nHowever, the modifications made by the authors are still not sufficient. For example, I asked the authors in my review to clarify what is the target function for the experiments. The authors now write in the paper \"We consider input data in dimension d = 50 and a scalar target function $g(x) = \\sum_{l=1,2;m} g_{lm}Y_{lm}(x)$ such that $\\sum_{l=1, m} g_{lm}^2 = \\sum_{l=2, m} g_{lm}^2 = 1/2$, but otherwise iid $g_{lm}$’s.\" I believe that a (random) target function that satisfies all these conditions doesn't exists. I guess what the authors want to say is something like \"taking $g(x) = \\sum_{l=1, 2} \\sum_{m = 1}^{M_l} g_{lm}Y_{lm}(x)$, $(g_{11}, ..., g_{1 M_1}) \\sim Unif(S^{M_1 - 1}(1/\\sqrt 2))$, and $(g_{21}, ..., g_{2 M_2}) \\sim Unif(S^{M_2 - 1}(1/\\sqrt 2))$\". The problem of the statement of the authors is that, if $\\sum_{m=1}^{M_1} g_{1m}^2 =\\sum_{m = 1}^{M_2} g_{2m}^2 = 1/2$, $(g_{lm})_{l = 1, 2; m \\in \\{1, \\ldots, M_l \\}}$ cannot be i.i.d. (one choice is to make $g_{11} = ... = g_{1M_1} = \\sqrt{1/(2 M_1)}$ and $g_{21} = ... = g_{2 M_2} = \\sqrt{1/(2 M_2)}$ be deterministic, but they are unequal). This is just an example of the writing problem of the paper. There are many other issues. \n\nI doubt this paper can be easily accepted at a Physics venue. I used physics tools like replica methods and I knew some Physicists published in machine learning conferences. The papers these Physicists wrote deliver clear scientific communications, though also using jargons and non-rigorous tools. There are many papers using physics tools studying machine learning problems, which published at ML conferences like ICLR, ICML, and NeurIPS. This paper is far less as accessible as those papers. \n\nFinally, I want to point out that, the generalization of kernel methods have been intensively studied in the machine learning literature, for example using the RKHS theory. It would be nice to cite related literature and compare the results. It is my fault that I didn't bring this point up in my review. \n\nI agree that there could potentially be great ideas in this paper. The conference is a venue with quality control. I encourage the authors to submit this paper again after they make more efforts to improve its accessibility. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies deep neural network (DNN) learning curves by leveraging recent connections of (wide) DNNs to kernel methods such as  Gaussian processes. 

The bulk of the arguments contained in this paper are, thus, for the "kernel regime" rather than "the problem of non-linearity in DNNs", as one reviewer puts it. 
When it comes to scoring this paper, it has been controversial. However a lot of discussion has taken place. On the positive side, it seems that there is a lot of novel perspectives included in this paper. On the other hand, even after the revision, it seems that this paper is still very difficult to follow for non-physicists. 

Overall, it would be beneficial to perform a more careful revision of the paper such that it can be better appreciated by the targeted scientific community. 

Decision: Reject