Neural tangent kernels and lazy training

Let $r\in L^2(\gamma )$ be orthogonal to every $h_m$. Each monomial $x^j$ is a finite linear combination of $H_0,\dots ,H_j$ by [F2], and each fixed polynomial is square-integrable under $\gamma$ because a polynomial times $e^{-x^2\mathrm{/}2}$ has an integrable tail. Therefore $\int r(x)x^{j}d\gamma (x)=0$ for every $j\ge 0$.

Put $v(x)=r(x)\varphi (x)$, so $v\in L^1(\mathbb{R})$ by [F1] and [F6]. For every $a\ge 0$, Cauchy–Schwarz and completion of the square give $\int \mathrm{\mid }r(x)\mathrm{\mid }{e}^{a\mathrm{\mid }x\mathrm{\mid }}d\gamma (x)\le \mathrm{\parallel }r{\mathrm{\parallel }}_2(\int e^{2a\mathrm{\mid }x\mathrm{\mid }}d\gamma {)}^{1\mathrm{/}2}<\mathrm{\infty }$, since each half-line integral is at most $e^{2a^2}$.

Fix $\xi \in \mathbb{R}$. The partial sums $S_M(x)={\sum }_{j=0}^M(-2\pi i\xi x{)}^j\mathrm{/}j!$ converge pointwise to $e^{-2\pi i\xi x}$ and satisfy $\mathrm{\mid }{S}_M(x)\mathrm{\mid }\le e^{2\pi \mathrm{\mid }\xi \mathrm{\mid }\mathrm{\mid }x\mathrm{\mid }}$ by [F5]. Applying [F7] with the integrable majorant from step 1.2 gives $\widehat{v}(\xi )={\lim }_{M\to \mathrm{\infty }}\int r(x)S_M(x)d\gamma (x)=0$, because every term is a scalar multiple of a zero moment from step 1.1.

By [F4], $\widehat{v}=0$ implies $v=0$ Lebesgue-almost everywhere. Since $\varphi (x)>0$ for all $x$, $r=0$ $\gamma$-almost everywhere. Thus the only $L^2(\gamma )$ function orthogonal to all the $h_m$ is zero.

For arbitrary real $f\in L^2(\gamma )$, set $a_m=\int f{h}_{m}d\gamma$ and $S_M={\sum }_{m=0}^M{a}_m{h}_m$. Orthogonality in [F2] gives $\mathrm{\parallel }f-S_M{\mathrm{\parallel }}_2^2=\mathrm{\parallel }f{\mathrm{\parallel }}_2^2-{\sum }_{m=0}^M{a}_m^2\ge 0$ and, for $M>K$, $\mathrm{\parallel }{S}_M-S_K{\mathrm{\parallel }}_2^2={\sum }_{K<m\le M}{a}_m^2$; hence the partial sums are Cauchy. View them in complex $L^2(\gamma )$; by [F3] and [A1] they converge there, and their limit is real because every $S_M$ is real. The residual $f-S$ is orthogonal to each $h_m$, hence zero by step 3.1. Therefore $f=S$ in $L^2(\gamma )$ and taking norms yields Parseval’s identity.

If only finitely many $a_m$ are nonzero, step 4.1 makes $f$ equal almost everywhere to a polynomial $p$. If $f$ is continuous and differs from $p$ at some point, it differs on a nonempty open interval, which has positive $\gamma$ measure by [F1]; hence $f=p$ everywhere, contrary to nonpolynomiality. Thus a continuous nonpolynomial $f$ has unbounded coefficient support. A globally Lipschitz $f$ obeys $\mathrm{\mid }f(x)\mathrm{\mid }\le \mathrm{\mid }f(0)\mathrm{\mid }+L\mathrm{\mid }x\mathrm{\mid }$; [F8] gives $\int \mathrm{\mid }x{\mathrm{\mid }}^{2}d\gamma <\mathrm{\infty }$, so this growth bound implies $f\in L^2(\gamma )$.

Write $C_n=\left(\begin{array}{cc}{v}_n& c_n\\ c_n& w_n\end{array}\right)$ and $d_n=\det C_n\ge 0$. Since $v_n,w_n>0$, $\mathrm{tr}{C}_n+2\sqrt{d_n}>0$. The matrix $A_n=(C_n+\sqrt{d_n}{I}_2)\mathrm{/}\sqrt{\mathrm{tr}{C}_n+2\sqrt{d_n}}$ is positive semidefinite. The identity $C_n^2-(\mathrm{tr}{C}_n)C_n+d_n{I}_2=0$ gives $A_n^2=C_n$ by expansion; the same formula defines $A$ for $C$, and entrywise convergence gives $A_n\to A$.

Fix a variance $s>\max (C_{11},C_{22})$. For all sufficiently large $n$, the marginal variances of $U_n,V_n$ lie in a compact subinterval of $(0,s)$, so their normal densities are bounded above by a common constant times the density of $N(0,s)$. The isometry $h\mapsto h\sqrt{{\varphi }_s}$ from $L^2(N(0,s))$ into Lebesgue $L^2$ and [F3] provide bounded continuous functions $g_k$ with $\mathrm{\parallel }g-g_k{\mathrm{\parallel }}_{L^2(N(0,s))}\to 0$. The density bound makes these approximation errors tend to zero uniformly for the marginals of all sufficiently large $n$ and for the two limiting marginals.

Let $G=(G_1,G_2)$ have independent standard-normal coordinates. The vectors $A_{n}G$ and $AG$ have centered Gaussian laws with covariances $C_n$ and $C$ by [F1] and step 1.1. Gaussian uniqueness in [F1] identifies their laws with those stipulated in the statement, even when singular. We may therefore compute all expectations using this coupling; $A_n\to A$ gives $(U_n,V_n)\to (U,V)$ almost surely.

By [F4], for each such $n$ the difference between $\mathbb{E}[g(U_n)g(V_n)]$ and $\mathbb{E}[g_k(U_n)g_k(V_n)]$ is bounded by $\mathrm{\parallel }g-g_k{\mathrm{\parallel }}_{L^2(U_n)}\mathrm{\parallel }g{\mathrm{\parallel }}_{L^2(V_n)}+\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_{L^2(U_n)}\mathrm{\parallel }g-g_k{\mathrm{\parallel }}_{L^2(V_n)}$, which tends to zero uniformly in sufficiently large $n$ as $k\to \mathrm{\infty }$ by step 1.2; the same bound applies to $(U,V)$.

If $\tau$ is globally Lipschitz, then it is continuous and has at most linear growth. The matrices $A_n$ are bounded, so $\mathrm{\mid }\tau (U_n)\tau (V_n)\mathrm{\mid }\le M(1+\mathrm{\parallel }G{\mathrm{\parallel }}_2^2)$ for one finite $M$ independent of all sufficiently large $n$; [F2] makes this majorant integrable. Almost-sure convergence in step 2.1 and [F5] prove the first expectation limit.

For fixed $k$, $g_k$ is bounded and continuous, so step 2.1 and [F5] give $\mathbb{E}[g_k(U_n)g_k(V_n)]\to \mathbb{E}[g_k(U)g_k(V)]$. First take $n\to \mathrm{\infty }$, then $k\to \mathrm{\infty }$ in the error bounds of step 2.2. This proves the bounded-Borel expectation limit, including singular $C$.

On every compact interval, [F1] gives differentiability of $\sigma$ outside a null set. Taking a countable union over intervals $[-n,n]$ gives one Lebesgue-null exceptional set on $\mathbb{R}$. The continuous difference quotients $s_n(x)=n(\sigma (x+1\mathrm{/}n)-\sigma (x))$ are bounded in modulus by the Lipschitz constant; their pointwise upper limit is a bounded Borel function and equals ${\sigma }^{\mathrm{\prime }}(x)$ wherever the derivative exists. Thus a representative $s$ as in the Statement exists.

Let $A=C^{1\mathrm{/}2}$ and $G$ be the independent standard-normal vector in [F2]. Positive definiteness of $C$ makes $A$ invertible: if $Av=0$, then $v^{T}Cv=v^T{A}^{2}v=\mathrm{\parallel }Av{\mathrm{\parallel }}_2^2=0$, so $v=0$. The product standard-normal density is positive on every nonempty open box; since $A^{-1}$ maps nonempty open sets to nonempty open sets, $Z=AG$ assigns positive probability to every nonempty open set in ${\mathbb{R}}^m$.

By [F2], each $Z_i$ has a scalar normal law with variance $C_{ii}>0$, hence a density. Therefore changing $s$ on the exceptional null set changes none of the random variables $s(Z_i)$ almost surely.

Fix a nonzero vector $c\in {\mathbb{R}}^m$ and set $F(z)={\sum }_{i=1}^m{c}_i\sigma (z_i)$. This function is continuous. If $\mathbb{E}[F(Z{)}^2]=0$, then for every integer $k\ge 1$, $F(Z{)}^2\ge k^{-2}{\mathbf{1}}_{\{\mathrm{\mid }F(Z)\mathrm{\mid }\ge 1\mathrm{/}k\}}$ forces $\mathbb{P}(\mathrm{\mid }F(Z)\mathrm{\mid }\ge 1\mathrm{/}k)=0$; the countable union gives $F(Z)=0$ almost surely. By the full-support conclusion of step 1.2, continuity forces $F(z)=0$ for every $z\in {\mathbb{R}}^m$. Choose $u,v$ with $\sigma (u)\mathrm{\ne }\sigma (v)$. For each $j$, evaluate this identity at vectors whose coordinates other than $j$ are zero and whose $j$th coordinates are $u$ and $v$, then subtract; it gives $c_j(\sigma (u)-\sigma (v))=0$, so $c_j=0$. This contradicts $c\mathrm{\ne }0$. Hence $\mathbb{E}[F(Z{)}^2]>0$ and $c^{T}Sc=\mathbb{E}[F(Z{)}^2]+{\beta }^2({\sum }_i{c}_i{)}^2>0$.

For any $c\in {\mathbb{R}}^m$, $c^{T}Dc=\mathbb{E}[({\sum }_i{c}_{i}s(Z_i){)}^2]\ge 0$; the expectation is finite because $s$ is bounded. Thus $D$ is positive semidefinite.

Apply [F3] to $T$. Each eigenvalue $\lambda$ is nonnegative because for a unit eigenvector $q$, $\lambda =q^{T}Tq\ge 0$. If $q_1,\dots ,q_m$ is an orthonormal eigenbasis with eigenvalues ${\lambda }_1,\dots ,{\lambda }_m$, the vectors $u_i=(\sqrt{{\lambda }_1}(q_1{)}_i,\dots ,\sqrt{{\lambda }_m}(q_m{)}_i)$ satisfy $T_{ij}=⟨u_i,u_j⟩$. For $D$, the same finite-dimensional factorization applies because step 3.1 proves it is positive semidefinite, so there are vectors $v_i$ with $D_{ij}=⟨v_i,v_j⟩$.

Then $(T\circ D{)}_{ij}=⟨u_i\otimes v_i,u_j\otimes v_j⟩$, so $T\circ D$ is positive semidefinite. Adding the strictly positive quadratic form of $S$ from step 2.2 shows $T\circ D+S$ is strictly positive definite.

For real $s$ and $x$, set $G_x(s)=\exp (sx-s^2\mathrm{/}2)$. By [F7]–[F8], $G_x^{\mathrm{\prime }}(s)=(x-s)G_x(s)$. Put $P_m(x)=G_x^{(m)}(0)$. Then $P_0=1$ and $P_1=x$; differentiating the identity $G_x^{\mathrm{\prime }}=(x-s)G_x$ $m$ times and setting $s=0$ gives $P_{m+1}=x{P}_m-m{P}_{m-1}$ for $m\ge 1$. The Hermite recurrence in [F2] therefore gives $P_m=H_m$ for every $m$.

For real $s,t$, [F3] gives $sX+tY\sim N(0,v)$ with $v=s^2+2\rho st+t^2\ge 0$. Completing the square in the standard-normal density gives $\mathbb{E}{e}^{aZ}=e^{a^2\mathrm{/}2}$ for real $a$ and $Z\sim N(0,1)$, so $\mathbb{E}{e}^{sX+tY}=e^{v\mathrm{/}2}$ by the scalar normal's affine definition; when $v=0$, its law is a point mass and the same formula holds. Thus [F7] gives $\mathbb{E}[G_X(s)G_Y(t)]=e^{-(s^2+t^2)\mathrm{/}2}\mathbb{E}{e}^{sX+tY}=e^{\rho st}$. This uses the given pair directly and includes $\rho =\pm 1$.

For any fixed finite $m,n$, differentiating the expectation identity in step 2.1 $m$ times in $s$ and $n$ times in $t$ at $(0,0)$ is justified as follows. On a bounded parameter rectangle, each required derivative of the integrand is bounded by $K(1+\mathrm{\mid }X\mathrm{\mid }{)}^q(1+\mathrm{\mid }Y\mathrm{\mid }{)}^q{e}^{R(\mathrm{\mid }X\mathrm{\mid }+\mathrm{\mid }Y\mathrm{\mid })}$ for finite $K,q,R$. This is integrable by [F6], since completing the square gives finite second moments for each marginal factor $(1+\mathrm{\mid }Z\mathrm{\mid }{)}^q{e}^{R\mathrm{\mid }Z\mathrm{\mid }}$ under $Z\sim N(0,1)$. On a slightly larger rectangle, [F9] gives the same majorant for each difference quotient, so [F5] passes each of the finitely many derivatives through expectation. By step 1.1 the derivative on the left is $\mathbb{E}[H_m(X)H_n(Y)]$; differentiating $e^{\rho st}$ on the right gives $m!{\rho }^m$ if $m=n$ and $0$ otherwise. Hence $\mathbb{E}[H_m(X)H_n(Y)]=m!{\delta }_{mn}{\rho }^m$.

For finite partial sums $f_M={\sum }_{m=0}^M{a}_m{h}_m$ and $g_M={\sum }_{m=0}^M{b}_m{h}_m$, step 3.1, finite expectation linearity and orthonormality give $\mathbb{E}[f_M(X)g_M(Y)]={\sum }_{m=0}^M{a}_m{b}_m{\rho }^m$.

By [F1], $f_M\to f$ and $g_M\to g$ in $L^2(\gamma )$. Since both marginals of $(X,Y)$ are $\gamma$, [F6] bounds the product-expectation error by $\mathrm{\parallel }{f}_M-f{\mathrm{\parallel }}_2\mathrm{\parallel }{g}_M{\mathrm{\parallel }}_2+\mathrm{\parallel }f{\mathrm{\parallel }}_2\mathrm{\parallel }{g}_M-g{\mathrm{\parallel }}_2$, which tends to zero. Also ${\sum }_m\mathrm{\mid }{a}_m{b}_m{\rho }^m\mathrm{\mid }\le ({\sum }_m{a}_m^2{)}^{1\mathrm{/}2}({\sum }_m{b}_m^2{)}^{1\mathrm{/}2}$ by [F1] and Cauchy–Schwarz for sequences. Taking $M\to \mathrm{\infty }$ proves the stated identity and endpoint absolute convergence; the case $f=g$ gives the dual-kernel formula.

By [F1], $A$ has an orthonormal eigenbasis; self-adjointness and positive definiteness make each eigenvalue positive. Thus $A^{-1}$ exists, is self-adjoint and positive definite, and $\mathrm{\parallel }v{\mathrm{\parallel }}_{A^{-1}}^2:=⟨v,A^{-1}v⟩$ is a norm squared. Since $\mathrm{\nabla }C$ is locally Lipschitz, the vector field $-A\mathrm{\nabla }C$ is locally Lipschitz and [F3] gives a unique local solution.

For $0<s\le 1$, convexity gives $C(z+s(z_{\ast }-z))\le (1-s)C(z)+sC(z_{\ast })$. Subtract $C(z)$, divide by $s$, and let $s\downarrow 0$; differentiability and the definition of $\mathrm{\nabla }C$ give $⟨\mathrm{\nabla }C(z),z_{\ast }-z⟩\le C(z_{\ast })-C(z)$. Along any solution, expanding the squared inverse-metric norm to first order then gives $\frac{d}{dt}\mathrm{\parallel }z-z_{\ast }{\mathrm{\parallel }}_{A^{-1}}^2=-2⟨z-z_{\ast },\mathrm{\nabla }C(z)⟩\le -2(C(z)-C(z_{\ast }))\le 0.$ Hence the solution remains in the closed $A^{-1}$-metric ball centered at $z_{\ast }$ through $z_0$. In orthonormal coordinates its radius bounds the Euclidean norm because the smallest eigenvalue of $A^{-1}$ is positive, and continuity of that norm makes the ball closed. If $\dim V\ge 1$, [F4] makes it compact; if $\dim V=0$, it is a subset of the singleton $V=\{0\}$ and is compact.

The vector field is bounded and Lipschitz on a compact neighborhood of this ball. Picard–Lindelöf therefore supplies a uniform positive local existence time at every point of the ball. If the maximal forward solution had a finite endpoint, boundedness of the vector field would make $z(t)$ Cauchy as $t$ approached that endpoint; its limit lies in the ball, and the uniform local solution there extends the original solution, a contradiction. Thus the solution exists uniquely for all $t\ge 0$.

Integrating the inequality in step 2.1 over $[0,T]$ gives ${\int }_0^T(C(z(t))-C(z_{\ast }))dt\le \frac{1}{2}\mathrm{\parallel }{z}_0-z_{\ast }{\mathrm{\parallel }}_{A^{-1}}^2$. By [F5] and the flow equation, $\frac{d}{dt}C(z(t))=-⟨\mathrm{\nabla }C(z(t)),A\mathrm{\nabla }C(z(t))⟩\le 0$. The gap is therefore nonnegative, nonincreasing and integrable; it tends to zero.

The trajectory lies in a compact set, so it has a convergent subsequence $z(t_j)\to \bar{z}$ with $t_j\to \mathrm{\infty }$. Continuity of $C$ and step 4.1 give $C(\bar{z})=C(z_{\ast })$, so $\bar{z}$ is a global minimizer. Apply step 2.1 with $\bar{z}$ in place of $z_{\ast }$: the distance $\mathrm{\parallel }z(t)-\bar{z}{\mathrm{\parallel }}_{A^{-1}}$ is nonincreasing and has a subsequence tending to zero, hence tends to zero. Thus the full trajectory converges to $\bar{z}$.

For a finite data set, [F2] makes $K$ symmetric positive semidefinite; if it is positive definite, then $A=K\mathrm{/}N$ is self-adjoint positive definite because $N\ge 1$. The preceding argument applies.

The marginal variance is $q$, and the standardized correlation is $r(x,y)=\frac{{\beta }^2+(x\cdot y)\mathrm{/}{n}_0}{q}=\alpha (x\cdot y)+\delta ,\alpha =\frac{1}{1+n_0{\beta }^2}>0,\delta =\frac{n_0{\beta }^2}{1+n_0{\beta }^2}>0,\alpha +\delta =1.$ The correlation lies in $[-1,1]$ because $\mathrm{\mid }x\cdot y\mathrm{\mid }\le 1$ and the displayed covariance is a valid two-dimensional Gram covariance of the input and bias features. Applying [F2] to $\mu$ gives $k(x,y)={\beta }^2+{\sum }_{r=0}^{\mathrm{\infty }}{a}_r^2(\alpha x\cdot y+\delta {)}^r\mathrm{.}$ The series is absolutely convergent since $\mathrm{\mid }r(x,y)\mathrm{\mid }\le 1$ and ${\sum }_r{a}_r^2<\mathrm{\infty }$.

Expanding by the binomial theorem, for each $x,y$ on the sphere the absolute double series is ${\sum }_{r=0}^{\mathrm{\infty }}{a}_r^2{\sum }_{m=0}^r\left(\genfrac{}{}{0px}{}{r}{m}\right){\alpha }^m{\delta }^{r-m}\mathrm{\mid }x\cdot y{\mathrm{\mid }}^m={\sum }_{r=0}^{\mathrm{\infty }}{a}_r^2(\alpha \mathrm{\mid }x\cdot y\mathrm{\mid }+\delta {)}^r\le {\sum }_{r=0}^{\mathrm{\infty }}{a}_r^2<\mathrm{\infty }$, since $\mathrm{\mid }x\cdot y\mathrm{\mid }\le 1$ and $\alpha +\delta =1$. Tonelli applied to this nonnegative absolute series justifies reordering the sign-changing binomial terms. Define $d_m={\mathbf{1}}_{\{m=0\}}{\beta }^2+{\alpha }^m{\sum }_{r=m}^{\mathrm{\infty }}{a}_r^2\left(\genfrac{}{}{0px}{}{r}{m}\right){\delta }^{r-m}(m\ge 0)$; then $k(x,y)={\sum }_{m=0}^{\mathrm{\infty }}{d}_m(x\cdot y{)}^m$. Also, [F3] and $\alpha +\delta =1$ give ${\sum }_m{d}_m={\beta }^2+{\sum }_r{a}_r^2<\mathrm{\infty }$.

The rescaled function $\mu (z)=\sigma (\sqrt{q}z)$ is continuous and nonpolynomial: if it were a polynomial, then $\sigma (u)=\mu (u\mathrm{/}\sqrt{q})$ would be a polynomial because $q>0$. It is globally Lipschitz, so [F1] supplies its $L^2(\gamma )$ membership and Parseval. The function $\mu$ has infinitely many nonzero Hermite coefficients: otherwise [F1] would make it equal almost everywhere to a polynomial, and continuity would make that equality hold everywhere, contradicting nonpolynomiality. Thus for each $m$ there is an $r\ge m$ with $a_r\mathrm{\ne }0$, and the corresponding term in [F3]’s sum is strictly positive because $\alpha ,\delta >0$. Hence $d_m>0$ for every $m$, including $m=0$ because $\beta >0$.