Deep Equals Shallow for ReLU Networks in Kernel Regimes
Authors: Alberto Bietti
Francis Bach
Venue: ICLR 2021 Poster (2021)
Keywords: deep learning
kernels
approximation
neural tangent kernels

Abstract: Deep networks are often considered to be more expressive than shallow ones in terms of approximation. Indeed, certain functions can be approximated by deep networks provably more efficiently than by shallow ones, however, no tractable algorithms are known for learning such deep models. Separately, a recent line of work has shown that deep networks trained with gradient descent may behave like (tractable) kernel methods in a certain over-parameterized regime, where the kernel is determined by the architecture and initialization, and this paper focuses on approximation for such kernels. We show that for ReLU activations, the kernels derived from deep fully-connected networks have essentially the same approximation properties as their shallow two-layer counterpart, namely the same eigenvalue decay for the corresponding integral operator. This highlights the limitations of the kernel framework for understanding the benefits of such deep architectures. Our main theoretical result relies on characterizing such eigenvalue decays through differentiability properties of the kernel function, which also easily applies to the study of other kernels defined on the sphere.

Published as a conference paper at ICLR 2021
DEEP EQUALS SHALLOW FOR RELU NETWORKS IN KERNEL REGIMES
Alberto Bietti NYU alberto. bietti faetti@nyu... edu
Francis Bach
Inria francis bach@inria.fr
edu
ABSTRACT
Deep networks are often considered to be more expressive than shallow ones in terms of approximation. Indeed, certain functions be approximated by deep networks provably more efficiently than by shallow ones, however, tractable algorithms are known for learning such deep models. Sepa- rately, a recent line of work has shown that deep networks trained with gradient descent may behave like (tractable) kernel methods in a certain weerppaammeterieed regime, where the kernel is determined by the architec- ture and initialization, and this paper focuses on approximation for such kernels. We show that for ReLU activations, the kernels derived from deep fully-connected networks have essentially the same approximation proper- ties their "shallow" two-layer counterpart, namely the same eigenvalue decay for the corresponding integral operator. This highlights the limita- tions of the kernel framework for understanding the benefits of such deep architectures. Our main theoretical result relics on characterizing such cigenvalue decays through differentiability properties of the kernel function, which also easily applies to the study of other kernels defined on the sphere.
INTRODUCTION
The question of which functions can be well approximated by neural networks is crucial for understanding when these models are successful, and has always been at the heart of the theoretical study of neural networks (e.g., Horník et al. 1989 Pinkus 1999). While early works have mostly focused on shallow networks with only two layers, more recent works have shown benefits of deep networks for approximating certain classes of functions (Eldan & Shamir 2016; Mhaskar & Poggio 2016 Telgarsky] 2016 Daniely) 2017] Yarotsky 2017 et al., (020).. Unfortunately, many of these approaches rely on constructions that are not currently known to be learnable using efficient algorithms.
A separate line of work has considered parraaaaatteeeed networks with random neu- rons (Neal 1996). which also display universal approxination properties while additionally providing efficient algorithms based on kernel methods or their approximations such as ran- dom features (Rahimi & Recht 2007: Bach 2017b). Many recent results on gradient-based optimization of certain over- wer-parameterize networks have been shown to be equivalent to kernel methods with an architectuure-secdfie kernel called the newral tongent kernel (NTK) and thus also fall in this category Jacot et al. 2018 Li & Liang, 2018 Allen- Zhu et al. 2019b Du et al.) 2019a b Zou et al.) 2019). This regime has been coined lazy (Chizat et al. 2019), as it does not capture the common phenomenon where weights move signilicantly away from random initialization and thus may not. provide satisfying model for learn- ing adaptive representations, in contrast to other settings such as the mean field or active regime, which captures complex training dynamics where weights may move in a non-trivial manner and adapt to the data (e.g., Chizat & Bach 2018 Mei et al. 2018). Nevertheless,
'Work done while at Inria. 'Center for Data Science, New York University. New York, USA.
Inrii Département d d'Informatique de I'École Normale Supérieure. PSL Research University. Paris, France.

---

Published as a conference paper at ICLR 2021
one benefit compared to the mean field regime is that the kernel approach easily extends to deep architectures, leading to compositional kernels similar to the ones of Cho & Saul (2009); Daniely et al. (2016). Our goal in this paper is to study the role of depth in de- termining approximation properties for such kernels, with a focus on fully-connected deep ReLU networks.
Our approximation results rely on the study of cigenvalue decays of integral operators asso- ciated to the obtained dot-product kernels on the sphere, which are diagonalized in the basis of spherical harmonics. This provides a characterization of the functions in the correspond- ing reproducing kernel Hilbert space (RKHS) in terms of their smoothness, and leads to convergence rates for non non-parametric regression when the data are uniformly distributed on the sphere. We show that for ReLU networks, the eigenvalue decays for the corresponding deep kernels remain the same regardless of the depth of the network. Our key result is that the docay for a certain class of kernels characterized by a property related to differentiabil- ity of the kernel function around the point where the two imputs are aligned. In particular, the property is preserved when adding layers with ReLU activations, showing that depth role for such networks in kernel regimes. This highlights the limitations
plays essentially of the kernel regime for understanding the power of depth in fully-comnected networks, and calls for new models of deep net beyond kernels (see, e.g., A.g.,Allenn-- (Aleen-Zhu & Li 2020 Chen eet al. 20200, for recent. works in this direction). We also provide applications of our result. to other kernels and architectures, and illustrate our results with numerical experiments on synthetic and real datasets.
Related work. Kernels for deep learning were originally derived by Neal (1996) for shal-
low networks, and later for doep networks (Cho & Saul 2009 Danicly ct al. 2016 Loc
ct al. 2018 Matthews et al.) 2018). Smola et al. (2001]: Minh et al. (0066) study regular-
ization properties of dot-product kernels on the sphere using spherical harmonics, and Bach
(2017a) derives eigenvalue decays for such dot-product kernels arising from shallow worwsrks
with positively homogeneous activations including the ReL.U. Extensions to shallow NTK
or Laplace kernels are studied by Basri et al. (2019); Bietti & Mairal (2019b); Geifman
let al. (2020h. The observation that depth does not change the decay of the NTK was pre-
viously made by Basri et al. (2020) empirically, and Geifman al. (2020) provide lower
bound on the cigenvalues for deep networks; our work makes this obsorvation rigorous by providing tight asymptotic decays. Spectral properties of wide neural networks were also considered in (Cao et al. 2019; Fan & Wang. 2020; Ghorbani et al.) [2019] Xie et al. 2017 Yang & Salman 2019). Azevedo Menegatto (2014); [Seetoon & Harchaoul (2020) also study eigenvalue decays for dot-product kernels but focus on kernels with geometric decays, while our main focus on polynomial decays. Additional works on paemtearaeteriiee
or infinitewwddth networks in lazy regimes include (Allen-Zhu et al. 2019a Arora et al.
2019a Brand et al. 2020 Lee et al., 2020 Song & Yang 2019).
Concurrently to our work, Chen & Xu (2021) also studied the RKHS of the NTK for deep ReLU net workor,s, showing that it is the same as for the Laplace kernel on the sphere. They achieve this by studying asymplotic decays of Taylor coefficients of the kernel function at zero using complex-analytaa extensions of the kernel functions, and leveraging this to ob- tain both inclusions between the two RKHSs. In contrast, obtain precise descriptions of the RKHS and regularization properties in the basis of spherical harmonics for vari- ous dot-product kernels through spectral decompositions of integral operators, using (real) asymptotic expansions of the kernel function around endpoints. The equality between the RKHS of the deep NTK and Laplace kernel then easily follows from our results by the fact that the two kernels have the same spectral decay.
2 REVIEW OF APPROXIMATION WITH DOT-PRODUCT KERNELS
In this section, we provide a brief review of the kernels that arise from neural networks and their approximation properties.
2

---

Published as a conference paper at ICLR 2021
2.1 KERNELS FOR WIDE NEURAL NETWORKS
Wide neural networks with random weights or weights close to random initialization nat- urally lead to cerlain dol-product kernels that depend on the archilecture and activation function, which we now present, with a focus on fully-connected architectures.
Random feature kernels. We first consider two-layer (shallow) network of the form f()) = 7m 2j U x), for some activation function a. When W/ ~ (O0, E E are fixed and only by E R are trained with bg regularization, this corresponds to using random feature approximation Rahimi & Recht (2007) of the kernel
k(x, x') - Eww. T (t)o(""a')
(1)
ar x' on the sphere, then by spherical symmetry of the Gaussian distribution, one may show that is invariant to unitary transformations and takes the form x()) <(x x') for a certain function K. More precisely, if au)) Eizo azh;(u) is the decomposition of in the basis of Hermite polynomials hi, which orthogonal w.r.t. the Gaussian measure, then we have (Daniely et al. 2016):
n(U)= Σdtu'. atu'. 120
(2)
Conversely, given a kernel function of the form above with <(u) = Ei bas with by 2 0, one may construct corresponding activations using Hermite polynomials by taking
ouu) = Σ (u), a a (=vo))
(3)
In the case where a is s-positively homogeneous, such the ReLU o(u) max(u, 0) (with = 1), or more generally a.(u) = max(u, 0)*, then the kernel takes the
form k(xxx')= || ||<|||||"|||<>(
TTx' for any x,2'. This leads RKHS functions of the
d with in the RKHS of the kernel restricted to the sphere (Bietti form [(x) = || ( [e
& Mairal 2019b Prop. 8). In particular, for the step and RcLU activations do and Ø1, the functions K are given by the following arc-cosine kernels (Cho & Saul 2009
1 - u (I arccos(u)) + /1 v1-=2))
(u(u) = (T ar)c
Ky (u)
(4)
Note that given a kernel function K, the corresponding activations (3) will generally not be homogeneous, thus the inputs to random network with such activations need to lie on the sphere (or be appropriately normalized) in order to yield the kernel k.
Extension to deep networks. When considering deep network with more than two layers and fixed random weights before the last layer, the connection to random features is less direct since the features are correlated through intermediate layers. Nevertheless, when the hidden layers are wide enough, one still approaches a kernel obtained by letting the widths go infinity (see, e.g.. Daniely et al. 2016 Lee et al. 2018 Matthews et al. 2018),
which takes a similar form to the multi-layer kernels of Cho & Saul 2009
(x,xx)) = n² (x = ....... 5(r x²),
for x, x' on the sphere, where is obtained as described above for a given activation a, and L is the number of layers. We still refer to this kernel as the random features (RF) kernel in this paper, noting that is sometimes known as the "conjugate kernel" or NNGP kernel (for neural network Gaussian process). It is usually good to normalize λ such that x(1) = 1, so that we also have (1) 1, avoiding exploding or vanishing behavior for deep works. In practice, this corresponds to using an activation-dependenn scaling in the random weight initialization, which commonly used by practitioners (He et al. 2015).
Here assume scaling / 2/m instead of /1/m in the definition of which yields x(1) = 1, useful normalization for deep networks, explained below.
3

---

Published as a conference paper at ICLR 2021
Neural tangent kernels. When intermediate layers trained along with the last layer using gradient methods, the resulting problem non- convex and the statistical properties of such approaches are not well understood in general, particularly for deep networks. However, in a specific over-parani wer-parameterized regime, it may be shown that gradient descent can reach a global minimum while keeping weights very close to random initialization. More precisely, for a network f(z; 0) parameterized by 0 with large width m, the model remains close to its linearization around random initialization do throughout training, that is, f(x; 0) so f(: + (6 du. V Fef(z; Bu)). This is also known as the lazy training regime (Chizat et al.) 2019 Learning is then equivalent to a kernel method with another architecture-specife kernel known as the newral langent kernel (NTK, Jacot et al. 2018), given by
kNTK (z, x²) lim (Vi 00), (z(2'())).
(5)
m=-00
For a simple two-layer network with activation 0, it is then given by a²) KNTK (x, x = (ar aa)aa)) [o (w"Tx)'' x))'(w" x²)] E. x))(w" (w(waa)o(w [x)))
(o
(6)
For a ReLU network with L lavers with imputs on the sphere, taking appropriate limits on the widths, one can show (Jacol et al. 2018): ANTK(E, x') " (x IoT x²), with "K (u) = x² (u) = and for 8= = 2,... ,,...,l,,
(u) ki (u)
(#) = N (w) (15 (w)) + (u):
(7)
where Ky and 11 are given in
2.2 APPROXIMATION AND HARMONIC ANALYSIS WITH DOT-PRODUCT KERNELS
In this section, we recall approximation propertics of dot-product kernels on the sphere, through spectral decompasitions of integral operators in the basis of spherical harmonics. Further background provided in Appendix A
Spherical harmonics and description of the RKHS. A standard approach to study the RKHS a. kernel is through the spectral decomposition of an integral operator T k(2, ())(d)(())) for some measure т, leading to Mercer's theorem (e.g., Cucker & Smale 2002). When inputs lie the sphere gd-1 in d dimensions, dot-product kernels of the form k(r,'') (==xx'=)= =<<= x²) are ootationall-iinvriiant depending only on the iunsslation-ivariinnn kernels are diagonalized in the Fourier basis, rotation-inss invirinnnnn kernels are diagonalized in the basis of spherical harmonics (Smola et al. 2001 Bach 2017a), which lead to connections between eigenvalue in the Fourier setting. In particular, if т denotes the uniform
given by Tx((x)
angle between æ and x'. Similarly to how
decays and regularity measure on gd3,, then 7 TYk,; = pa Yn.j, where YEJ the j-th spherical harmonic polynomial of degree k where & plays the role of frequency as in the Fourier case, and the number of such orthogonal polynomials of degree k is given by N(d, k) 2k+d-2 (k+d-3), which grows as kd-2 for large k. The eigenvalues μı only depend on the frequency and are given by
Wa-2 []]
k(t)) -t)1d-3)/22
Wd-1
where Pk is the Legendre polynomial of degree & in d dimensions (also known Gegenbaner polynomial when using a different scaling), and wa-1 denotes the surface of the sphere gd-1 Mercer's theorem then states that the RKHS H associated to the kernel is given by
((dk)
N(d.k)
}
a
H
Σ
Σ aRSYESS
S.L.
Σ
1
k20
In particular, if pa has fast decay, then the coefficients akj of f must also decay quickly with & order for f to be in H. which means f must have a certain level of regularity. Similarly the Fourier case, exponential decay of pa implies that the functions in H are
4

---

Published as a conference paper at ICLR 2021
infinitely differentiable, while for polynomial decay H contains all functions whose deriva- tives only up to a certain order are bounded, as in Sobolev spaces. If two kernels lead to the same asymptotic decay of Ms up to constant, then by (9 their RKHS norms are equivalent up to a constant, and thus they have the same RKHS. For the specific case of random fea- ture kernels arising from s-positively homogeneous activations, Bach (2017a) shows that μk decays as dd-22s for & of the opposite parity of s, and is zero for large enough k of opposite parity, which results in a RKHS that contains even or odd functions (depending on the parity of s) defined on the sphere with bounded derivatives up to order 3 := d/2 + (note that 8 must be greater than (d- - 1)/2 in order for the eigenvalues of T to be summable and thus lead to well-defiedd RKHS). [Bietti & Mairal (2019b) show that the same decay holds for the NTK of two-layer ReLU networks, with 8 and a change of parity. [Basri el al. 2219)) show that the parity constraints may be removed by adding a zero-initialized additive bias term when deriving the NTK. We note that one can also obtain rates ap- proximation for Lipschitz functions from such decay estimates (Bach 2017a). Our goal in this paper is to extend this to more general dot-product kernels such as those arising from multi-layer networks, by providing more general approach for obtaining decay estimates from differentiability properties of the function K.
Non- Non-parametric regression. When the data are uniformly distributed on the sphere, we may also obtain convergence rates for non- paraammeetric regression, which typically depend on the eigenvalue decay of the integral operator associated to the marginal distribution on inputs and on the decomposition of the regression function fx)x) [lyla] on the same basis (c.g., Caponnetto & De Vito 2007) Then one may achieve optimal rates that depend mainly on the regularity of J when using various algorithms with tuned hyperparameters, but the choice of kernel and its decay may have an impact on the rates in some regimes, as well as on the difficulty of the optimization problem (see, e.g.. Bach 2013
Section 4.3).
3 MAIN RESULT AND APPLICATIONS TO DEEP NETWORKS
In this section, present main results concerning approximation propertics of dot- product kernels on the sphere, and applications to the kernels arising from wide random neural networks. We begin by stating our main theorem, which provides eigenvalue decays for dot-product kernels from differentiability properties of the kernel function k at the end- points =1. We then present applications of this result to various kernels, including those coming from deep networks, showing in particular that the RKHSs associated to deep and shallow ReLU networks are the same (up to parity constraints).
3.1 STATEMENT OF OUR MAIN THEOREM
We now state our main result regarding the asymplotic eigenvalue decay of dot-product kernels. Recall that we consider kernel of the form k(x, y) = <(x y) for x, E $ and seek to obtain decay estimates on the eigenvalues i4 defined in ( We now state our main theorem, which derives the asymptotic decay of pa with & in terms of differentiability properties of x around {+1}, assuming that k. is infinitely differentiable on (-1, This latter condition is always verified when & takes the form of a power scries (2) with x(1) = 1, since the radius of convergence is at least 1. We also require a technical condition, namely the ability to "differentiate asymptotic expansions" " of at +1, which holds for the kernels considered in this work.
Theorem 1 (Decay from regularity of k at endpoints, simplified). Let K 1-1,1] + R be a function that is O on (-1, 1) and has the following asymptotic expansions around +1:
x(1 - t) = pı(t) + ctt" +o(t")
(10)
+ , +o('),
(11)
for t 2 0, where P1-P-1 are polynomials and is not an integer. Also, assume that the derivatives of k admit similar expansions obtained by differentiating the above ones. Then, there is an absolute constont C(d.v) depending on d and such that:
'Th rates easily extend to distributions with density w.r.t. the uniform distribution the sphere, although the eigenbasis on which regularity is measured then different.
5

---

Published as a conference paper at ICLR 2021
For l even, if e1 # -c-1: Mh (a dd-- - For lo odd, if 01 # c-1: ps (01 (c1-c_)) (c- d--2t+1
In the case leal=llle-- then we have μt = ol:-1-20+1) for one of the two parilães (or both if =-1 If is infinitely differenliable on [-1,]] so that no such v exists, then pa decays faster than any polynomial.
The full theorem given in Appendix Baaoong with its proof, and requires an additional mild technical condition on the expansion which is verified for all kernels considered in this paper, namely, a finite number of terms in the expansions with exponents between v and + 1. The proof relies on integration by parts using properties of Legendre polynomials, in way reminiscent of fast decays of Fourier series for differentiable functions, and on precise computation ations of the decay for simple functions of the form + (1 - (2)2. This allows us to obtain the asymptotic decay for general kernel functions k as long as the behavior around the endpoints is known, in contrast to previous approaches which rely the precise form of K, or of the corresponding activation in the case of arc-cosine kernels (Bach 7a Basri et al. 2019: Bietti & Mairal 2019b Geifman et al. 2020). This enables the study of more general and complex kernels, such as those arising from deep networks, as discussed below. When K is of the form x(t) = E.. byt", the exponent v in Theorem is also related to the decay of coefficients by- Such coefficients provide a dimension-free description of the kernel which may be useful for instance in the study of kernel methods in certain high-dimensional regimes (see, e.g., El Karoui 2010 Ghorbani et al.) 2019 Liang et al. (2220). We show in Appendix B. that the by may be recovered from the [*k by taking high-dimensional limits d + oc, and that they decay as h-=-1
3.2 CONSEQUENCES FOR RELU NETWORKS
When considering neural networks with ReLU activations, the corresponding random fea- tures and neural tangent kernels depend on the arc-cosine functions 1n and Kg defined in (4). These have the following expansions (with generalized exponents) near +1:
61 f) =1 v2 2/1122 + 0
(12)
π
2v 3/2 (tt5/2).
- =1 (11--))11tt-
(13)
3
Indeed, the first follows from integrating the expansion of the derivative using the relation d di arccos(1 (1 - t) 22 /1-1/2 and the second follows from the first using the expression of K
in 44. Near 1, have by symmetry ko(-1+ 1) 1 ko - 1)= 2/2 + O((3/2), and
35 2/2/3/2 + Ot5//3) by using k² = Ko and (-1- 0. The ability to differentiate the expansions follows from Flajoolct & Sodgewick 2009 Thcorem VI.8, p.419), logether with complex-analylis properly known A-analyticity, which was shown to hold for RF and NTK kernels by Chen & Xu (202T). By Theorem we immediately obtain decay of k-d-2 for even coeflicients for K1, and k-d for odd coefficients for Ko, recovering results of Bach (2017a). For the two-layer ReLU NTK, we have KNTK (w) = uso(u) + Kj (u), leading to similar expansion to Ko and thus decay, up to change of parity due to the factor u which changes signs in the expansion around -1; this recovers Bictti & Mairal (2019b). We note that for these specific kernels, Bach (2017a); Bictti & Mairal (2019b) show in addition that coefficients of the opposite parity are exactly zero for large enough K, which imposes parity constraints on functions in the RKHS, although such a constraint may be removed in the NTK case by adding a zero-initialized bias term (Basri et al. 2019 leading to kernel KNTK,b(u) (u 1)Ko(u) K1 (u).
we have (-(-1 +
Deep networks. Recall from Section 2.1 that the RF and NTK kernels for deep ReLU networks may be obtained through compositions and products using the functions K1 and Rp- Since asymptotic expansions can be composed and multiplied, for the deep RF and NTK kernels. The following results show that such kernels have the same eigenvalue decay the ones for the corresponding shallow (two-layer) networks.
can then obtain expansions

---

Published as a conference paper at ICLR 2021
Corollary 2 (Deep RF decay.). For the random neuron kernel khr of an L-layer ReLU network with L 2 3, we have μa C(d, L)k-d=, where C(d, is different depending on the parity of l and grows linearly with L.
Corollary 3 (Deep NTK decay.). For the neural langent kernel ENTK of an I-layer ReLU network with L 2 3, we have P4 1 C(d. L)k-d, where C(d, L) is different depending the parity of l and grows quadratically with L (it grows linearly with L when considering the normalized NTK ktyrk/ L,, which sotisfies K (xxrx(1)/==
The proofs, given in Appendix C use the fact that K оr and K have the samne non-integer exponent factors in their expansions, and similarly for Nn oi and Kg. One benefit compared to the shallow case is that the odd and even coefficients are both non-zero with the same decay, which removes the parity constraints, but as mentioned before, simple modifications of the shallow kernels can yield the same effect.
The finite neuron case. For two-layer networks with a finite number of neurons, the ob- tained models correspond to random feature approximations of the limiting kernels (Rahimi Recht 2007). Then, one may approximate RKHS functions and achieve optimal rates in non-poareen non-parameeric regression as long as the number of random features exceeds certain degrees-offfreedlom quantity (Bach 2017b; Rudi & Rosasco, 2017), which is similar to stan- dard such quantities in the analysis of ridge regression |Caponnetto & De Vitol 2007 at least when the data are uniformly distributed on the sphere (otherwise the quantity sampled non-uniformly). Such number of
involved may be larger unless features random features is optimal for a given eigenvalue decay of the integral operator (Bach) 2017b), which implies that the shallow random feature architectures provides optimal ap- proximation for the multi-layer ReLU kernels as well, since the shallow and deep kernels have the same decay, up to the parity constraint. In order for shallow kernels while preserving decay, one may consider vector-valued random fea- tures of the form (a "),(" (2 Tu)x))) z)) with w ~ (O(0, I), leading a ker- (1 ()),(u), where Ko is the random feature kernel corresponding to a. With (u) = max(0, u), No,b has the same decay as KRF: and when (u) 1(u 2 0} it has the same decay as KNTK.
overcome this constraint
nel (u,((u)
3.3 EXTENSIONS TO OTHER KERNELS
We now provide other examples of kernels for which Theorem provides approximation properties thanks to its generality.
Laplace kernel and generalizations. The Laplace kernel (x, v) --lll==-ll has been found to provide similar empirical behavior to neural networks when fitting randomly la- beled data with gradient descent (Belkin et al. 2018). Recently, [Geifman et al. (2020) have shown that when inputs are on the sphere, the Laplace kernel has the same decay as the NTK, which may suggest similar conditioning of the optimization problem as for fully-connected networks, as discussed in Section 2.2 Denoting (u(u) -evii- so that (e y) Kevz(x y), may easily recover this result using Theorem by noticing that Ne is infinitely differentiable around -1 and satisfies
Kc(1 -t) - e = 1- +0
d which yields the same decay dd as the NTK. Geifman et al. (2020) also consider heuristic generalization of the Laplace kernel with different exponents, Kon Ken(u) (u) e p=<(l-u"" The- orem allows us obtain a precise decay for this kernel as well using Ke, (1 t)
1 + O(P²), which is of the form - for non-integer y > 0, and in particu- lar approaches the limiting order of smoothness (d - 1)/2 when 7
Deep kernels with step activations. We saw in Section 3.2 that for ReLU activations, depth does not change the decay of the corresponding kernels. In contrast, when considering
'For Ke and Ke,T, the ability to differentiate expansions is straightforward since we have the exact expansion (u) Σx c²(1 uu) /kl, which may be differentiated term-by-term.
7

---

Published as a conference paper at ICLR 2021
step activations a(u) = (u 2 0}. we show in Appendix C.3 that approximation properties of the corresponding random neuron kernels (of the form Ri o... Ko) improve with depth, leading to decay k-d-20+1 with V 1/2"-1 for L layers. This also leads to an RKHS which becomes as large as allowed (order of smoothness close to (d - 1)/2) when I - xc. While this may suggest benefit. of depth, note that step activations make optimization hard for anything beyond linear regime with random weights, since the gradients with respect to inner neurons vanish. Theorem [ may also be applied to deep kernels with other positively homogencous activations a, (u) max(0, u)* with 2 2, for which endpoint expansions casily follow from those of Ku or K1 through integration.
Infinitely differentiable kernels. Finally, we note that Theorem ! shows that kernels as- sociated to infinitely differentiable activations (which are themselves infinitely differentiable, see Daniely al. 2 as well as Gaussian kernels on the sphere of the form e-<(1-= w), have faster decays than any polynomial. This results in a "small" RKHS that only contains smooth functions. See Azevedo & Menegatto (2014); Minh et al. (2006) for a more precise study of the decay for Gaussian kernels on the sphere.
4 NUMERICAL EXPERIMENTS
We now present numerical experiments on synthetic and real data to illustrate our theory. Our code is available at httpgp//ggttuub..ccmm/abbttt/// stapes/eeeeeeppplsoaeoeoaoeaoooe oereool
Synthetic experiments. We consider randomly sampled inputs on the sphere 53 in 4 di- mensions, and outputs generated according to the following target models, for an arbi- trary w E S3: fz) = 1(wTx
e- (I-wTa)a0 + e -1+1+= aa)a/2 Note that ft is discontimuous and thus not in the RKHS in general, while f2 is in the RKHS of αι (since it is even and has the same decay as σд as discussed in Section 3.3p- In Figure we compare the quality of approximation for different kernels by examining generalization performance of ridge regression with exact kernels or random features. The regularization parameter À is optimized on 10 000 test datapoints on logarithmic grid. In order to il- lustrate the difficulty of optimization due to small optimal X, which would also indicate slower convergence with gradient methods, we consider grids with À 2 Amin, for two different choices of Amin- We see that all kernels provide a similar rate of approximation for a large enough grid, but when fixing smaller optimization budget by taking larger Amin, the NTK and Laplace kernels can achieve better performance for large sample size n, thanks to slower eigenvalue decay of the covariance operator. Figure rightt shows that when using m = /n random features (which can achieve optimal rates in some settings, see Rudi & Rosasco 2017), the "shallow" ReLU network performs better than three-layer version, despite having fewer weights. This suggests that in addition to providing no improvements to approximation in the infinite-width case, the kernel regimes for deep ReLU networks may even be worse than their two-layer counterparts in the finite-width setting.
0.7) and (2)
MNIST and Fashion-MNIST.. In Table I we consider the image classification datasets MNIST and Fashion-MNIST, which both consist of 60k training and 10k test images of size 28x28 with 10 output classes. We evaluate one-versus-all all classifiers obtained by using kernel ridge regression by setting y = 0.9 for the correct label and y = -0.1 otherwise. We train on random subsets of 50k examples and use the remaining 10k examples for validation. We find that test accuracy is comparable for different numbers of layers in RF or NTK kernels, with slightly poorer performance for the two-layer case likely due to parity constraints, in agreement with our thcoretical result that the decay is the same for different L. There is a small docrease in accuracy for growing L, which may reflect changes in the decay constants or numerical errors when composing kernels. The slightly better performance of RF compared to NTK may suggest that these problems are relatively easy (e.g., the regression function is smooth), so that a faster decay is preferable due to better adaplivily to smoothness.
"Thi requires the mild additional condition that each derivative of the activation is in 1,2 w.r.t. the Gaussian measure.
8

---

Published as a conference paper at ICLR 2021
KRR, Amin 1e-9
KRR, Amin = 1e-5
ReLU random features
2-byyr
2-layer Solayer
34daye
r1 #44aayer
of ddyyye
2-inyer
4x.10
etk, 2-ayer
layee
3x 10
ntx 4-isyer
layer
lap C=1
lap c=1
m-sqrtint layer (sortin), sortintl
10
3-tyer (10. sqrtin)) 5-lyyr (wgrtin). 16)
10-4
10
10'
10
10
10 10
10
10"
10
Figure 1: (left, middle) expected squared error vs sample size n for kernel ridge regression estimators with different kernels on fi and with two different budgets on optimization difficulty Amin (the minimum regularization parameter allowed). (right) ridge regression with one or two layers of random ReLU features on fū with different scalings of the number of "neurons" at each layer in terms of n.
Table 1: Test accuracies on MNIST (left) and Pashion-MNIST (right) for RF and NTK kernels with varying numbers of layers L. We use kernel ridge regression 50k samples, with À optimized on validation set of size 10k, and report mean and standard errors across such random splits of the 60k training samples. For comparison, the Laplace kernel with = 1 yields accuracies 98.39 = 0.02 on MNIST and 90.38 + 0.06 on F-MNIST.
MNIST
F-MNIST
L.
RF
NTK
T.
RF
NTK
2
98.60 + 0.03
98.49 1 0.02
90.75 = 0.11
90.65 0.07
3
98.67 + 0.03
98.53
1 0.02
3
90.87 = 0.16
90.62 = 0.08
4
98.66
+ 0.02
98.49
: 0.01
4
90.89 = 0.13
90.55 = 0.07
98.65 5
+ 0.04
98.46
+ 0.02
5
90.88 = 0.08
90.50 = 0.05
5 DISCUSSION
In this paper, we have analyzed the approximation properties of deep networks in kernel regimes, by studying eigenvalue decays of integral operators through diffcrentiability proper- ties of the kernel function. In particular, the decay is governed by the form of the function's (generalized) power series expansion around =1, which remains the same for kernels aris- ing from fully-connected ReLU networks of varying depths. This result suggests that the kernel approach is unsatisfactory for understanding the power depth fully-connected networks. In particular, it highlights the need to incorporate other regimes in the study of deep networks, such as the mean field regime (Chizat & Bach 2018 Mei et al.] 2018). and other settings with hierarchical structure (see, e.g.. -llen-ullnnZ & Li 2020 Chen al.) 2020)- We note that our results do not rule out benefits of depth for other network architectures in kernel regimes; for instance, depth may improve stability properties of convolutional ker- nels (Bietti & Mairal 2019a b), and a precise study of approximation for such kernels and its dependence on depth would also be of interest.
ACKNOWLEDCMENTS
The authors would like to thank David Holzmüller for finding an error in an earlier version of the paper, which led us to include the assumption differentiation of asymptotic expansions in Theorem [ This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 31A Institute). We also acknowledge support of the European Research Council (grant SEQUOIA 724063).
REFERENCES
Zeyuan Allen- Zhu and Yuanzhi Li. Backward feature correction: How deep learning per- forms deep learning. Xr preprint or urXi::2001.04/ 2020.

---

Published as a conference paper at ICLR 2021
Zeyuan All, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa- rameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parramelerivalion. In Proceedings of the International Conference Machine Learning (ICML), 2019b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinor, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of opLimization and generalization for overparamelerized two-layer neural net works. In Proceedings of the International Conference on Machine Learning (ICML), 2019b.
Kendall Atkinson and Weimin Han. Spherical harmonics and approzimations on the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
Douglas Azevedo and Valdir Antonio Menegatto. Sharp estimates for cigenvalues of integral operators generated by dol product kernels on the sphere. Journal of Approzimalion Theory, 177:57 68, 2014.
Francis Bach. Sharp analysis of low-rank kernel matrix approximations. In Conference on Learning Theory (COLT), 2013.
Francis Bach. Breaking the curse of dimensionality with convex noural networks. Journal of Machine Learning Research (JMLR), 18(1):629-63)) 681, 2017a.
Francis Bach. On the equivalence between kernel quadrature rules and random feature expansions. Journal of Machine Learning Research (JMLR), 18(1):714 751, 2017b.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritch- man. Froquency bias in neural networks for input of non-uniform density. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Proceedings of the International Conference on Machine Learning (ICML), 2018.
Alberto Bictti and Julien Mairal. Group invariance, stability to deformations, and complex- ity of deep convolutional representations. Journal of Machine Learning Research (JMLR), 20(25):1 49, 2019a.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advonces in Neural Information Processing Systems (NeurIPS), 2019b.
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. arXiv preprint XxXx:2006.11646 2020.
Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards under- standing the spectral bias of deep learning. Xrxiv preprint arXiv:1912.01199, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331 368, 2007.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In Proceedings of the International Conference Learning Representations (ICLR), 2021.
10

---

Published as a conference paper at ICLR 2021
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Pro- cessing Systems (NeurIPS), 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable pro- gramminng In Advances in Neural Information Processing Systems (NewrIPS), 2019.
Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems (NIPS), 2009.
Felipe Cucker and Steve Smale. On the mathematical foundations of learming. Bulletin of the American mathematicnl society, 39(1):1-49, 2002.
Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory (COLT), 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In Advances in Neural Information Processing Systems (NIPS), 2016.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the International Conference on Machine Learning (ICML), 2019a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably opti- mizes perr-paraeteerize neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2019b.
Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annols of Statistics, 38(1):1-50, 2010.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on Learning Theory (COLT), 2016.
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural langent kernel for linear-width neural networks. In Advances in Neurul Information Processing Systems (NewrIPS), 2020.
Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University press, 2009.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kernels. In Advances in Neural Information Processing Systems (NeurIPS). 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers ncural networks in high dimonsion. arXiv preprint 1rXi::1904.1111 12191, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359 366, 1989.
Mourad Ismail. Classical and quantum orthogonal polynomials in one variable, volume 13. Cambridge university press, 2005.
11

---

Published as a conference paper at ICLR 2021
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neurol Information Processing Systems (NIPS), 2018.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeflrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, et al. Generalized leverage score sampling for neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochas- tic gradient descent on structured data. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the risk of minimum-norm in- terpolants and restricted lower isometry of kernels. In Conference on Learning Theory (COLT), 2020.
Alexander Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. air preprint arXio:1804.112. 11271, 2018.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33): E7665 E7665-EE677,, 2018.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829 848, 2016.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In Conference on Leurning Theory (COLT), 2006.
Radford M Neal. Bayesian learning for neural nelworks. Springer, 1996.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143-195, 1999.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), 2007.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random fcatures. In Advances in Neural Information Processing Systems, pp. 3215-3225, 2017.
Meyer Scetbon and Zaid Harchaoui. Risk bounds for multi-layer perceptrons through spectra of integral operators. arXiv preprint xrXi::2002.1000 12640, 2020.
Johannes Schmidt- et al. Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, 4844):1875-1897, 2020.
Alex J Smola, Zoltan I, Ovari, and Robert Williamson. Regularization with dot-product kernels. In Advances in Neurol Information Processing Systems (NIPS), 2001.
Zhao Song and Xin Yang. Quadratic suffices for parametrttiiinnnoonnn via matrix chernoff bound. Xix preprint Xrx: 1906. 03593, 2019.
Matus Telgarsky. Benefits of depth in neural networks. In Conference Learning Theory (COLT), 2016.
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
12

---

Published as a conference paper at ICLR 2021
Greg Yang and Hadi Salman. A fine-gra tne-graiied spectral perspective neural networks. arXiv preprint orXiv:1907.10599 2019.
Dmitry Yarotsky, Error bounds for approximations with deep relu networks. Neural Net- works, 94:103-114, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 2019.
A BACKGROUND ON SPHERICAL HARMONICS
In this section, we provide some background on spherical harmonics needed for our study
of approximation. See (Efthimiou & Frye 2014 Atkinson & Han 2012 Ismail 2005
for references, as well as [Bach 2017a Appendix D). We consider inputs on the sphere gd-1 {i E R2 |=]|=
We recall some properties of the spherical harmonics Yu,5 introduced in Section 2.2 For j I,.....N(( k), where ((d, k) 2k+d-2 (1dd=2(kd=2)) (k+=2"), the spherical harmonics Yk. are homogeneous harmonic polynomials of degree k that are orthonormal with respect to the uniform distribution т on the sphere. The degree k plays the role an integer fre- quency, in Fourier series, and the collection (Yk,,, k 0, I...., .dd forms orthonormal basis of (3 dr). As with Fourier series, there tween decay coefficients in this basis w.r.t. k and regularity/diffe /differentiabbiity in this case differentiabilits
ls
tight connections be- functions, the sphere. This follows from the fact that spherical harmon- Saplaco-Beltrami ics are cigenfunctions of the Laplaco- Beltrami operator on the sphere Aga-: (sco Efthimiou & Frye 2014 Proposition 4.5): Aea = - 2)
(14)
For a given frequency k have the following addition formula: (dd
Σ
(e ((d
(15)
where P& the k-th Legendre polynomial in dimension d (also known as Gegenbauer poly- nomial when using different scaling), given by the Rodrigues formula:
T( Pa(t)= r(k + 1-1 421)
(
d
k (1 (1-2))b(4-3)1)
(1 ( 03/2
(16)
dt
Note that these may also be expressed using the hypergeometric function 2 (see, e.g., Ismail 2005 Section 4.5), expression will use in proof of Thcorem 1
(sce the proof of
Lemma 6
The polynomials P& are orthogonal in [3[[-1, 1], dv) where the measure du is given by the weight function dv(t) (1 12 (2)dd33)/2 dt, and we have
[ P1(()(
12) -2)(0(1))-d--3))
Wa-1 1
(17)
Wa-2 N(d,k)
where Wp-1
2/2 F(p/2
denotes the surface of the sphere SP-1 in p dimensions. Using the and orthogonality of spherical harmonics, we can show
addition formula 15
f P2(wT x) Px(w v)dr(w) N(d, k)
85k Pa(x Tv)
(18)
We will use two other properties of Legendre polynomials, namely the following recurrence relation (Efthimiou & Fryel 2014 Eq. 4.36)
1: + d --2 2
(P&(1) 2k 2-2
(1)
2k + Pk+1 (t),
(19)
13

---

Published as a conference paper at ICLR 2021
for k 2 1, and for h 0 we simply have tPo(t) (t), well as the differential equation (see, e.g.. Efthimiou & Frye 2014 Proposition 4.20):
(1- + (1- + k(k + d ()) 0.
(20)
The Funk- formula is helpful for computing Fourier coefficients in the basis of spherical harmonics in terms of Legendre polynomials: for any j = l,...., N(d, k), we have
(o) I [(x (loTT)Yx, ())
[" 1O)P - (2)dd---)------- d1.
(21)
wa-1
For example, we may use this to obtain decompositions of dot- dot-product kernels by computing Fourier coefficients of functions n((r,,)) -)). Indeed, denoting
2 []
jkk Wd-1
((())P(()(1
3)/
writing the decomposition of (((x, using of the kernel:
21
leads to the following Mercer docomposition
00
N(d.k)
8 Σ (d
v) x(xTx)= Σ
<(x
(v)
(22)
k=0
j=1
k=
B PROOF OF THEOREM
The proof of Theorem 1 stated below in full as Theorem 7 proceeds as follows. We first derive an upper bound on the decay of of the form & -- (Lemma 5 which is weaker than the desired k-d-2r-1, by exploiting regularity properties of к through integration by parts. The goal is then to apply this result on a function R = R- where & is a function that allows to "cancel" the leading terms in the expansions of while being simple enough that it allows a precise estimate of its decay. In the proof of Theorem 7 we follow this strategy by considering va sum of functions of the form -> (1 11-120 ()) and / + 1(1 - (2)",
for which we provide a precise computation of the decay in Lemma 6
Decay upper bound through regularity. We begin by establishing a weak upper bound on the decay of K (Lemma 5) by leveraging its regularity up to the terms of order (1 1 22) This is achieved by iteratively applying the following integration by parts lemma, which is conceptually similar integrating by parts on the sphere by leveraging the spherical Laplacian relation (14) in Appendix A but directly uses properties of к and of Legendre
polynomials instcad (namely, the differential equation (20)). We note that the final state- ment in Thcorem | on infinitely differentiable a directly follows from Lemma 5
Lemma 4 (Integration by parts lemma). Let k [-1, + R be function that is C on (-1,1) and such that (1())( 12)1+ O(1). We have
1 [ -)) k(k + d 2) ( (-x(t)(1
- x(t)(1 - (00011-)44400)) ((()""
(23)
+ +1)(1)(1 - +)++ P,(0) + / -10P)(00(11110---1 (24)
with R(1) = -00==xx((((1-000 (d-1)xx(()).
Proof. In order to perform integration by parts, we use the following differential equation
satisfied by Legendre polynomials (see, e.g., Efthimiou & Frye 2014 Proposition 4.20):
(1 (1- ()) + (1-)))((()) + k(k + d (1) 0.
(25)
14

---

Published as a conference paper at ICLR 2021
Using this equation, may write for k 1,
f < (1)) - (2)ld-3//2dt = kck + d - 2) (d- (00100000 -8) di (26)
f ((0))((((-1))+++)))
(27)
We may integrate the second term by parts using
dt (k(t)L1- (((t)(-+)))0)) -)) - 1
d
2t(1 (d (d- (1133)))x(t(11--)))
- (d- (1- (2)
(28)
Noting that the first term in term in (28) then obtain
26
cancels out with the integral resulting from the second
(()) - By(e 3)/2 2/10-
- (
k:k + d - 2) 12)
+ +f (1)1--3)144 P((()dt)
Integrating by parts once more, the second term becomes
S (0011-)) Pl(t)dt x()( - -1)a++ - Pa(t)
S/ (10(00 - - - (dd=))=(0))P)(01) - 8)dd-3)/22
(29)
The desired result follows.
Lemma (Weak upper bound on the decay). Let k: [-1, - TR be a function that is on (-1,1) and has the following expansions around +1 on its derivatives:
C
x0) p.. - (111))
(30)
x (t) = Pj. p).- + 0 ((1++)))
(31)
for [-1,1] and j 2 O, where Pj.1.Pj--1 are polynomials and v may be non-integer. Then the Legendre coefficients (x)) of given in 18) satisfy
(k(R) = O a-2++3).
(32)
Proof. Tet fo = and for j21
(t) == (0)0 ()))
(33)
Then fj is C on (-1,1) and has similar expansions to of the form
= - +000= + = (1))= + 0 + t)-
(34)
(35)
for some polynomials 6,11- We may apply Lemma repeatedly as long as the terms in brackets vanish, until we obtain, for j j= T d-3 I.
S. (())P)()(1 (1)d-33/22
(Kilk + d -dd22)? 2) 8) + S- (01 - ()dd-3)/2
Given our choice for j, we have 11(((1
12 == =0(1) and (+= - (d)
O(11 12)) for some 0. Since Pa(()) [-1,1] for any E [-1, we obtain
(k( 01-21(+1) O(k- Okk--3243)
15

---

Published as a conference paper at ICLR 2021
Precise decay for simple function. We now provide precise decay estimates for func- 2²)
tions of the form t + (1- and t f(1- y which will lead to the dominant terms in the decomposition of in the main theorem.
Lemma (Decay for simple functions @u and ē.). Let dv - (1 By, with v > 0 non- integer, and let pa((v) denote its Legendre coefficients in d dimensions given by wa-2 22y (a 3//2 (t)dd.. We have
wa- f (1-
mx(ov) 0 if k is odd me(ov) C(d, dd
-----1 for lo even, k - 0o, with v(d,v) a constant.
Analogously, let (t) == t(1 - --.. We have
(u(dv) = 0 is k is even
mu(ov) C(d, d-) 1-2 for h odd, ks co, with C(d, v) constant.
Proof. We recall the following representation of Legendre polynomials based on the hyper-
geometric function (e.g.. Ismail 2005, Section 4.5) $
(t()) (-k, + d - 2: (d 1)/2: (1 1
2))
(36)
where the hypergeometric function is given in its generalized form by
Σ (a1)s (ap)s x²
p Api b ................................ byi
(37)
(b)). ... (by)s s!
where (a), [(a + (a) is the rising factorial or Pochhammer symbol.
Using the above definitions and the integral representation of Beta functions, we then have
S (1 - Pa(t)dtt = 220-d-3 [
1+
Px(t)
2
2
(d)) 2 k),
1
1-1
4t 2 t
(1+8) 2+
22v+d-3
dt
(1)1) s!
2
220-d-2
(d) 2 k))
(1- x) 1 1-
x. u+ - dx
(d=1) 1 s!
==
(-k)a(d -2 2+k)) k), (12)) s!
Plv+ + 1
2 2 + ا +
22
T(2 + d d1 1)
8=0
2 d 22 ['v + 2
d=1)²
(-k), - 2 k), ا
I(2v + d 1)
(5 (2v + 1)ss!
2 d T(v + 1=1)2
(-k d (d-
T(2v + d 1)
1
Now, we use Watson's thcorem (e.g., Ismail 2005 Eq. (1.4.12)). which states that
F (a+b+1)/2.0 1)/2, 1)
a, b.c.
[(())((c++ )))(( [[c 1-a-b r( (( 1
(38)
We remark that with a = k + (d 1)/2, our expression above is of the form of Watson's 's thcorem, and we may thus evaluate l* in closed form. Indeed, have
k. (d-1)/2,22) d
( 11)
I(E) + 2)r( ( +1)
3 F2
(39)
T + ((v++1
Here normalize such that Pa(1) 1 as is standard for Legendre polynomials, in contrast
[smail] 2005) where the standard Jacobi/ /Gegenbaner normalization is used.
16

---

Published as a conference paper at ICLR 2021
When k is odd, then (1 - k is a non-positive integer that the denominator is infinite and thus μy vanishes. We assume from now on that is even, making the denominator is finite. Using the following relation, for e& Z and an integer n.
T(1 + c) I(e- n)
1). ()-)))))---) P(++ 1-
(40)
I(-c)
we may then rewrite
F2 (
- k, k + - (d (d- 1)/2 -
I(u+ (T(
T k - v)
( 10/21)2 + +
5)
(41)
When k- + 00, Stirling's formula [(x) ~ xt- xtI = yields the equivalent
I(
2 )(
v)
-d-2++1
(42)
I(
myd+k=11
I す/
+ d)
2
2
This yields
14 ~ (dd, ui -d-20+1
(43)
with
1'v و 1 ) C(d,v) 22o4d-2 2
W4-1 I'2v d - 1) r( ( (1/2) (1/2)-d-20+1, d-22011
(44)
Decay for oy. The decay for o, follows from the decay of S and the recurrence rela- tion (Efthimiou & Frye 2014 Eq. (4.36))
k
k d - 2
(L)
2k d PR (1)
2k + d (t)
(45)
which ensures the same decay with a change parity.
Final theorem. We are now ready to prove our main theorem, which differs from the simplified statement of Theorem | by the technical assumption that only a finite number r of terms of order between and
are present in the series expansions around #1.
Theorem 7 (Main theorem, full version). Let K [-1, - R be function that is O on (-1,1) and has the following expansions around #1:
<(t) p1 -t)+ + Σ 1)) O(11 t11)
(46)
x(t) -t)=p--(1++)) Σ c. + +0(+)))+000(0+++)))))))) t)
(47)
for E 1,, where P-.P-1 are polynomials and 0 < 11 .... < Vr are not integers and 0<E< 1/ -1. We also assume that the derivatives (s) of k. have the following expansions:
T(1, + 1)
(1) PL. - 1) + (-1)²
9111 I(v; +1- (1 1)- ((1 +0(L-t)uttte (48)
rly; +1)
(0 = Px.- (1
Σ jml
+ +0(11 Cj T(U; +1 +1 (1 (1 +
(49)
for some polynomials P- on d and Vl,
Then we have, for an absolute constant C(d, v1) depending only
For k even, if CoL,1 + -1,-11 ph (c1,1 + II.-1) vn -d-1+++
For l even, if C1,1 -C1-11 1i olk ok:-d-2u+11;
17

---

Published as a conference paper at ICLR 2021
For l odd, if C1,1 # c1,-1 14 (01, - c1, C 11 dd-
For & odd, if C1,1 c1,-1 pe o(k ((=
Proof Deline the functions
(t)() = C₁,1 Øu, (t) ou, (t)
Dr, (t) δu, (t)
+ Cg.-1
(50)
2
2",+1
Cj,1 + cj
2 Uug (t) + 9j,1 cj.-1
Øu (t),
(51)
2
for j = I,...,,,, r, where ov, oy are defined in Lemma We have the asymptotic expansions
(1( = c1,1 - 1) (1 v1).1,1 + C1,-1 (1 1) + O(11 - t)t)
(1 - 11,-1 + C1,1 - (1+ 1) (1+ + 0((11 + 1)(++++))
2
and for j2 2,
- +0
(t(() cj 1 + t) 0((1 + +))
Define additionally Wr+1 the same way as the other thj, with 1p- is + 1, Gr+1.1 =
((1 + 21)01,1 + -1, and Cy+1.-1 (c1.1 (1 + 1)) which satisfies a similar asymptotic expansion as the above ones for j 2 2. One can check that the derivatives of the b can be expanded with the derivatives of the expansions above. Then, defining
R == KK-- Ej Wij we have for 8 2 0,
R R(0) (t) = P1.1(1 - 1) + 0(11 - t)ntttte-)
(52)
(()(() Ps, Ps.-1 +t O((1 + +))
(53)
The functions by satisfy
suutcs 2"
Mr (0v,),
if k even,
N& (x(y)
(54)
2n pa (0v))
if ls odd.
By Lemma have
(k(K) = pe (R) + Σ
Me (1bs))
(55)
jml
(x(()) + OOK -d(0---2(1s+ttt)--
(56)
(xb,))) + o(k -d-20
(57)
The result then follows from Lemma 6 with constant C(d, 21)2 where C'dd, v1) is given by the proof of Lemma
B. DIMENSION-PREE DESCRIPTION
While our above description of the RKHS depends on the dimension d, in some cases dimension- description given by Taylor coefficients of the kernel K at 0 may be useful, for instance for the study of kernel methods in certain high-dimensional regimes (e.g., El Karoui regiin
2010 Ghorbani et al. 2019 Liang et al. 2020). Here we remark that such coefficients and
These are obtained by writing (t) (a b1) t) - t)" and computing, e.g-, the first terms in the analytic expansion of + (a + (1) +)" around
18

---

Published as a conference paper at ICLR 2021
their decay may be recovered from the Legendre cocfficients in d dimensions, by taking high- dimensional limits d + cc. We illustrate this on the functions (t( = (1-t*)² for which Lemma 6 provides precise estimates of the Legendre coefficients (k.a( in d dimensions (this only serves as an instructive illustration, since in this case Taylor coefficients may be computed directly through a power series expansion of d, using the Binomial formula).
Lemma 8 (Recovering Taylor coelficients of Φv through high-dimensional limits).
2 Let ((((b)) = R. for some non-inleger v > Por even, we have
bx(dw) C.2k r( - 1 -
1)
for constant C₁ depending only on v. This leads to an equivalent by ~ C. for k + co with k even.
Proof- Assume throughout that k is even. Recall the expression of the Legendre coefli- cients pr,a(ov) of Φh in dimensions (we include d as a subscript for more clarity here) from the proof of Lemma 6
W []
(k,d(00)== Wd-1
kc(t) - -P) dt
(58)
=22ttd-246-2
[(v 1 T(p + +T
v)
Wd-1 + 1
d
2
(59)
Now, note that when d is large enough compared to k. we may use the Rodrigues formula [6
and integration by parts to obtain the following alternative expression:
( = 2 w ((
(1)
wa-1 [ d-1
2
Following similar arguments Ghorbani al. (2019), we may then use dominated conver- gence to show:
(
2 (t) -100111-++000 dt (0) as d + oc.
TT
Indeed, VRT( 2=1 (1 (2)(d-3) 3)/2 is a probability density that approaches a Dirac mass at
when d + 0c. This yields
r( 411
be(()) = k!
d Wa-2 ( 4- ] (k.)
lim 2* W
Plugging 59 and using Stirling's formula to take limits d + 0o yields
bx((r) C T( k-1 T -)
11
where Co only depends on v. Using Stirling's formula once again yields the desired equiva- lent be(dv) ~ -=-= for k + 00, even, with different constant Cy
We note that similar asymptotic equivalent holds for (x() for k odd. The next sult leverages this to derive asymptotic decays of (x) for any x of the form r(uu) = Exzo by (K)u* satisfying similar conditions as in Theorem
Corollary 9 (Taylor coefficients of k). Let k: [-1, 1] - R. be function admilling power series expansion n(w)=
= Σx20 b with the following expansions around #1:
<(1) = (1 (1 1) + Σ
G11 - 113s + 0(11 (m1112)
(60)
j=1
<(t) = - + Σ
C (1 +1) 0(11 + +))11)+1),
(61)
j=1
19

---

Published as a conference paper at ICLR 2021
for t E [-,,1], where Pr, P-1 are polynomials and 0 11 < ... < Vr are not integers and
0 c < 1/ - v1. Then we have, for an absolute constant ((vi) depending only on V1,
For k even, if crr F -1 by ~ (Cuy.1 + coj (1)()))
For k even, if Cul,1 - bg = o(k -ok--1111 1);
For k odd, if Cui.1 + -1 by (Cu,,1 - Cu1,- (1(1))
For & odd, if Cvi.1 cvi.-1 by o(k u01
Proof. As in the proof of Theorem we may construct a function da == E, agHu, ŌzOuz
with t1 σ1 2-111
C1 -11-01-- for 1, the other terms being of higher orders Vi > Vi, such that = - (which is also a power series with convergence radius 1) satisfies
2"1
a(t) p1 - t) 0 ()(
(62)
R(t) = p-p(p11++pp + + (11+)))) +
(63)
It follows that (1)))++)11 is bounded, so that the Taylor coefficients of k, denoted (R), satisfy
(R) oaA (1/--(11-1) o(k-
The result then follows from Lemma by using the decays of bx(áv) and by (ō()..
C OTHER PROoFS
In this section, we provide the proofs for results Section 3.3 related to obtaining power series expansions (with generalized exponents) of kernels arising from deep networks, which leads to the corresponding decays by Theorem [ We note that for the kernels considered in this section, we differentiate the expansions since the kernel function is A-analytic (see Theorem 7), so that the technical assumption in Theorem verified.
Chen & Xu 2021
C.1 PROOF OF COROLLARY 2
Proof. Let k = Ki o...or. KEF We have
times
2v2
Ry (1 -1--t 3t2 +0t33/2).
c:= 3
We now show by induction that n t) = 1- + ast + of ((22)) with = (1-1)c. This obviously true for = since x² K1, and for > 3 we have
net (1 - t) = =1 t))
= Kx (1 - 1 + at 1 13/2 + 0(1312))
1 (t - a 1 3/2 + 0(t312)) + c +
1 + ar 1//2 + at 3/2 0 ((t2/2)
= 1 - t + ar 1/ 3/2 + at 3/2 (1 0tt o
1 3/12 + o(13/2),
which proves the result.
Around -1, we know that
Ri (-1+t)
0(1312).
We then have (f(1+ = by + c,23/2 22 + o(t3/2), with 0 s by < and < c; S c (and
the upper bound strict. for l > 3). Indeed, this is true for f = 2, and for l > 3 have,
20

---

Published as a conference paper at ICLR 2021
for t >>> O,
(-1+tt
-ki(be-1 + ce- 1t 1//2
+ o(t
= =ni(be-1) + K1 (bc-1))ee 1//2 + o(t3/2).
Now, note that iy and wy are both positive and strictly increasing on [0, 1], with (1) <i (1) 1. Thus, we have by x1(66-1) (0.1), 1), and xi(ac-1)ce-1 < ce-1, thus completing the proof.
Since c2 is bounded while as grows linearly with &, the constants in front of the asymptotic decay -d-2 grow linearly with L.
C.2 PROOF OF COROLLARY 3
Proof. We show by induction that "VTTK as defined in 7
satisfies
;: v2
TK (1 - =-- Σ et2 =(1112)
For f= we have " (1) = uno(w)) K5 (u); so that
"NTK( (1 - () -1 (1 /2 2 + o(l 0(11 1+ 0(1) = 2211 011113).
By induction, for 8>3. 3, we have 1ONTR (2) f-1 (u) n² (u), with n¹ as in the
proof of Corollary 2 which hence satisfies n² t) = =1 ot)) for all 12 2. We then have
Ko(k (1 ()) = ko - ++ o(())
1 - c o(t)) 1/2 + o(t
a5 + o(1 + 0(1112)
= 1 1/2 + 0(2112).
This yields
2-2
#K -t) (f--- ②
(1- 1/2 + (16t1/21((1- +
$=1
= [ s)ct + 1(2
= 1) ct 1/2 tott
Ell 1)
2
which proves the claim for the expansion around +1.
Around -1, recall the expansion from the proof of Corollary 2 x=111++1 1) = by + 0(13/2),
with 0 < by 1. For & = 2, we have
(-1+ tcctt//2 + o(t1/2)) b2 + o(t1/2) b2 1/2 + o22)/2).
Note also that for 8> 2,
ku(k' 1 +11++)) = nolbe + 0(1212)) ko(be) + (11/22)
since (be) is finite for by < 1. We also have Na (be) (0, since in is positive and strictly increasing on [0, 1] with Ko = 1. Then, by an easy induction, we obtain
* (-1 1) az c0 of ((2)
21

---

Published as a conference paper at ICLR 2021
with de S E and 0 c <.
Similar to the case the RF kernel, the constant in front of t grows with l for the expansion around +1 but is bounded for the expansion around -1, that the final constants in front of the asymptotic decay km grow quadratically with l. However, they grow linearly with & when considering the NTK normalized by L, R KkvI//, which then satisfies (1) = 1.
C.3 DEEP NETWORKS WITH STEP ACTIVATIONS
In this section, we study the decay of the random weight kernel arising from deep networks with step activations, as presented in Section 3.3 For an L-layer network, this kernel of the form N Ko k...
times
Corollary 10. Ny has decuy d- 201+1 with vr. = 1/24-1 for L layers.
Proof. We show by induction that we have, for 8 2,
(1-
t) = -1 11/251 + 0
with x2, This is true for == due to the expansion for Ro- Now assume it holds
for l 2 2. We have
K5 ++ (1 - t) Ko(nn (1 t))
-/ 2 22/2" + + ))
Kg
E 11/2 +0011120 3) 1/2
+o(o(11/22 29102)
1 E/ 2-1 11/2/ (1 + o(1) + 121)
Ei 2- 112 + 12112
proving the desired claim.
Around -1, we have No(- 1) cl2/2 + 011222, and for 22 3, x-(-+()) ag + (
by an easy induction using the fact that ko( 1)) (0.1) and Ko is smooth on [0. 1). Thus
the behavior around -1 does not affect the decay of n. for f 8 3, and Theorem leads to
the desired decay, with a constant that only depends on through E 2- which lies in the interval [e c| for any l.
22


Reviews:
[{"review_id": "qnGo0DXAws", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows that the kernel derived from deep fully-connected networks on the sphere have the same approximation properties as their two-layer counterpart for ReLU activations. This implies the limitations of the kernel framework for studying the benefits of such deep networks. The authors derive the asymptotic eigenvalue decay of dot-product kernels from differentiability properties of the kernel function.\n\nOverall, I vote for accepting. The paper is overall well-written and has a solid contribution. It addresses the limitation of the kernel framework, which is very interesting and phenomenal. The experiments are clear to illustrate the theory.\n\nSome concerns are as follows:\n\nThe paper only considers ReLU activations and step activations (Section 3.3). Can the analyses be generalized to other network architectures? \n\nThe proof only analyzes the kernels on the sphere. It seems hard to generalize the proof to other larger region like R^d. The extension seems to be limited from my side.\n\nSome related literature are missing. To name a few:\nZ. Fan and Z. Wang. Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks (2020).\nA. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the similarity between the laplace and neural tangent kernels (2020).\nY. Cao, Z. Fang, Y. Wu, D.-X. Zhou, and Q. Gu. Towards understanding the spectral bias of deep learning (2019).\nY. Cho and L. K. Saul. Kernel methods for deep learning (2009). \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "jT7Da9X7YwL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nRecently, there are a large number of deep learning theory papers related to the property of neural tangent kernel. This paper shows that for ReLU, the kernels derived from deep fully-connected networks have the same approx. properties as their shallow two-layer counterpart. This highlights the limitation of the kernel framework for understanding the benefits of deep networks from such perspective.\n\nI really like the idea of this paper. This paper is very well-written. I verified the proofs, it looks correct. I think this paper should be clearly accepted. \n\nHere are some minor comments about references.\n\nIn page 1, several references should be added into NTK literature\n\nSanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.\nFine-grained analysis of optimization and generalization for overparameterized two-layer neural networks (ICML)\n\nZeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. (NeurIPS)\n\nZeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. (NeurIPS)\n\nJan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein. Training (Overparametrized) Neural Networks in Near-Linear Time. (ITCS)\n\nZhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound.\n\nIn page 6, there is a section talking about ''finite neuron case''. It might be reason to slightly mention about ''infinite neuron case''. The work by Arora et al and Lee et al, shows a connection between infinite case and (ridge) kernel regression.\n\nSanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. (NeurIPS)\n\nJason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. (NeurIPS) \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fBANV54B_ya", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Summary:\n\nThis paper analyzed the expressive power of kernels by studying the reproducing kernel Hilbert space (RKHS) associated with the kernels. Specifically, the authors analyzed the eigenvalue decays in terms of the power series expansions of the kernel function around some points, which is related to the RKHS of the kernel. This analysis can be used to recover some previous results. Besides, using this analysis, the authors have shown several interesting results, including that NTK (which corresponds to fully-connected ReLU networks with infinite width, small learning rate, and proper initialization) with any depth has the same RKHS. The main result also has other corollaries about other kinds of kernels, e.g., Laplace kernel and infinitely differentiable kernels. Experiments were done to validate the theoretical results on synthetic datasets and MNIST/Fashion-MNIST.\n\nPros:\n\n1. Analyzing the role of depth in deep neural networks is a very important problem, and people observed empirically depth separation phenomena, i.e., deeper networks have more expressive power. The authors analyzed this problem and showed that NTK constrained to the unit sphere does not have the depth separation phenomenon, which makes this paper interesting.\n\n2. The authors did experiments in a nice way to validate the theoretical results. They did experiments on both synthetic datasets and real datasets, compare different kernels and repeat the experiments multiple times.\n\n3. The experimental methodologies and theoretical computations appear to be correct.\n\nCons:\n\n1. As mentioned by the authors, there is a recent concurrent work (Chen & Xu, 2020) that also obtains the result that NTK with any depth have the same RKHS, but the authors did not provide enough comparisons to that work. It would be better if a more detailed comparison can be provided.\n\n2. The experiments are only done on synthetic datasets/MNIST/Fashion-MNIST with RF/NTK. It would be more convincing if the authors could do experiments with more kernels (e.g., Laplace kernel) or on larger datasets (e.g., CIFAR).\n\nRecommendation:\n\nI tend to vote for accepting this paper. The main reason is that the problem analyzed in this paper is important, and the results in this paper are interesting and kind of surprising. It showed the limitations of NTK in explaining the depth separation phenomenon, which could give people more insights and understandings about NTK.\n\nSupporting arguments for recommendation:\n\nSee \"Pros\", especially point 1 there.\n\nQuestions for the authors:\n\nPlease address the cons mentioned above.\n\nAdditional feedback:\n\nThe lines in Figure 1 are a bit hard to distinguish, and it would be better to plot it more clearly, e.g., somehow separate the lines farther away.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-ojbv1Rdwp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-------------- Overview of the paper ----------------\n\nThe paper establishes the similarity between kernels (random feature kernel and neural tangent kernel) induced by shallow neural networks and deep ones. In particular, the approximation power is analyzed through the eigenvalue decay of the corresponding kernels --- shallow and deep networks share the same order of decay, expect the difference in parity and constants.\n\n-------------- Contribution and strength ----------------\n\nThe message of the paper tends to be a negative perspective on viewing overparameterized neural networks as kernels, which motivates a surge of recent works on showing overparameterized neural networks are easy to optimize and generalize as well as kernels. Yet viewing neural networks as kernels cannot explain the advantage of neural networks, and leaves a large gap between the established theory and practice. This paper, provides theoretical justifications of the insufficiency of the kernel view point.\n\nThe organization of the paper is clear and it is relatively easy to read through, although some background on kernels and overparameterized neural networks are needed. Given the tight page limit, the paper makes a good balance between introductory materials and theoretical results.\n\nTheoretically results appear to be correct and sound.\n\n-------------- Weakness ----------------\n\nThe data distribution is a bit restricted. However, this is acceptable for later explicit computations of the eigenfunctions and eigenvalues (spherical harmonics and gegenbauer polynomials). Is it possible to consider more general data distributions?\n\n-------------- Questions ----------------\n\n1. The main result (theorem 1) asserts the expansion of the kernel around point 1 and -1. Is it an artifact of the proof (in order to apply integration by part)? Or it in fact reveals some interesting facts on distinguishing identical and orthogonal data points?\n\n2. In Figure 1, we see 2-layer outperforms other models. This is not covered in the proposed theory --- any intuitions on its connection to Theorem 1? Meanwhile, the network width in ReLU random features experiment is smaller than the sample size, which is not the standard overparameterization discussed in lazy training regime. Can the authors elaborate on the choice of the network width?\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the expressive power of NTK corresponding to deep neural network. It is shown that the depth hardly affects the behavior of the spectrum of the corresponding integral operator, which indicates that depth separation does not occur as long as NTK is considered.
The analysis is novel and gives a significant insight to the NTK research literature. The theoretical framework considered in this paper is considerably broad and potentially can be applied to several types of activation functions (while only ReLU is analyzed as a concrete example in the paper). Moreover, some numerical experiments are conducted that support the validity of the theoretical analysis. 
All reviewers are positive on this paper. I agree with their evaluations. For these reasons, I think this paper is worth acceptance.
Decision: Accept (Poster)