Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

Introduction

A recent line of research seeks to understand Neural Networks through their kernel approximation, as given by the Neural Tangent Kernel (NTK, Jacot et al., 2018). The premise of the approach is that in certain regimes, the dynamics of training neural networks are essentially the same as those of its first order Taylor expansion at initialization, which in turn is captured by the Tangent Kernel at initialization. It is then possible to obtain convergence, global optimality and even generalization guarantees by studying the behaviour of training using the Tangent Kernel (e.g. Li and Liang, 2018, Du et al., 2019b, Chizat et al., 2019b, Zou et al., 2020, Allen-Zhu et al., 2019, Arora et al., 2019b, Du et al., 2019a, and many others). Some have also suggested using Tangent Kernel directly for training (e.g. Arora et al., 2019a), even suggesting it can sometimes outperform training by GD on the actual network (Geiger et al., 2020).

Can all the success of deep learning be explained using the NTK? This would imply that we can replace training by gradient descent on a non-convex model with a (potentially simpler to train, and certainly better understood) kernel method. Is anything learnable using gradient descent on a neural network or other differentiable model also learnable using a kernel method (i.e. using a kernelized linear model)?

This question was directly addressed by multiple authors, who showed examples where neural networks trained with gradient descent (or some variant thereof) provably outperform the best that can possibly be done using the tangent kernel or any linear or kernel method, under different settings and assumptions (Yehudai and Shamir, 2019, Allen-Zhu and Li, 2019, 2020, Li et al., 2020, Daniely and Malach, 2020, Ghorbani et al., 2019b, 2020). However in these examples, while training the model with gradient descent performs better than using the NTK, the error of the NTK is still much better then baseline, with a significant “edge” over random guessing or using a constant, or null, predictor. That is, the NTK at least allows for “weak learning”. In fact, in some of the constructions, the process of leveraging the “edge” of a linear or kernel learner and amplifying it is fairly explicit (e.g. Allen-Zhu and Li, 2019, 2020). The question we ask in this paper is:

Can gradient descent training on the actual deep (non-convex) model only amplify (or “boost”) the edge of the NTK, with the NTK required to have an edge in order to allow for learning in the first place? Or can differentiable learning succeed even when the NTK —or any other kernel— does not have a non-trivial edge?

Can gradient descent succeed at “strong learning” only when the NTK achieves ”weak learning”? Or is it possible for gradient descent to succeed even when the NTK is not able to achieve any significant edge?

The answer turns out to be subtle, and as we shall see, relies crucially on two important considerations: the unbiasedness of the initialization, and whether we can rely on input distribution knowledge for the initialization.

We start, in Section 3, by providing our own example of a learning problem where Gradient Descent outperforms the NTK, and indeed any kernel method. But unlike the previous recent separating examples, where the NTK enjoys a considerable edge (constant edge, or even near zero error, but with a slower rate than GD), we show that the edge of the NTK, and indeed of any (poly-sized) kernel, can be arbitrarily close to zero while the edge of GD can be arbitrarily large. The edge of the NTK in this example is nonetheless vanishing at low rate, i.e., polynomially, and this leads us to ask whether the NTK must have at least a polynomial edge when GD succeeds.

In Theorem 1 of Section 4.1 we show that when using an unbiased initialization, that is, where the output of the model is at initialization, then indeed the NTK must have a non-trivial edge (polynomial in the accuracy and scale of the model) in order for gradient descent to succeed.

The requirement that the initialization is unbiased turns out to be essential: In Section 5 we show an example where gradient descent on a model succeeds, from a biased initialization, even though no (reasonably sized) kernel method (let alone the NTK) can ensure a non-trivial edge.

But all is not lost with biased initialization. In Theorem 2 of Section 4.2 we show that at least for the square loss, if gradient descent succeeds from any (possibly biased) initialization, then we can construct some alternate random “initialization” such that the Tangent Kernel at this random initialization (i.e. in expectation over the randomness) does ensure a non-trivial edge. Importantly, this random initialization must depend on knowledge of the input distribution. Again, our example in Section 5 shows that this distribution-dependence is essential. This also implies a separation between problems learnable by gradient descent using an unbiased vs arbitrary initialization, emphasizing that the initialization being unbiased should not be taken for granted.

This subtle answer that we uncover is mapped in Table 1.

Differentiable Learning and Tangent Kernels

The gradient estimates $g_{t}$ can be obtained by computing the gradient on an empirical sample of $m$ training examples drawn from $\mathcal{D}$, in which case we can ensure accuracy $\tau\propto C_{f}/\sqrt{m}$. And so, we can think of $C^{2}_{f}/\tau^{2}$ as capturing the sample size, and when we refer to the relative accuracy $\tau/C_{f}$ being polynomial, one might think of the sample size used to estimate the gradients being polynomial. But here we only assume the gradient estimates $g_{t}$ are good approximations of the true gradients of the population loss, and do not specifically refer to sampling.In some regimes, one should in fact distinguish the setting of large sample sets and approximate population gradients in view of the universality result proved for SGD in Abbe and Sandon (2020a, b). We focus here on the approximate setting that better reflects the noisier regime; see discussion in Abbe and Sandon (2020a) for parities. We say that $\tau$-approximate gradient descent with model $f_{\theta}$, initialization $\theta_{0}$, gradient accuracy $\tau$ and $T$ steps ensures error $\varepsilon$ on a distribution $\mathcal{D}$ if with any gradient estimates satisfying (2), the gradient descent iterates (1) lead to an iterate $\theta^{(T)}$ with population loss $\mathcal{L}_{\mathcal{D}}(f_{\theta^{(T)}})\leq\varepsilon$.

which corresponds to a linear model with the feature map as in (5), and thus can also be represented using the kernel:

In some regimes or model limits (e.g. Daniely et al., 2016, Jacot et al., 2018, Chizat et al., 2019a), the approximation (3) about the initialization remains valid throughout training, and so gradient descent on the actual model $f_{\theta}(x)$ can be approximated by gradient descent on the linear model (4), i.e. a kernalized linear model specified by the tangent kernel $\mathsf{NTK}_{\theta_{*}}^{f}$ at initialization. One can then consider analyzing differentiable learning with the model $f$ using this NTK approximation, or even replacing gradient descent on $f$ with just using the NTK. How powerful can such an approximation be relative to the full power of differentiable learning? Can we expect that anything learnable with differentiable learning is also learnable under the NTK approximation?

To understand the power of a kernalized linear model with some kernel $K$, we should consider predictors realizable with bounded norm in the corresponding feature map (i.e. norm balls in the corresponding Reproducing Kernel Hilbert Space):

where $K(x,x^{\prime})=\left\langle\phi(x),\phi(x^{\prime})\right\rangle$ and $\left\lVert f\right\rVert_{K}$ is the $K$-RKHS-normThe direct definition (6) is sufficient for our purposes, and so we refrain from getting into the definition of an RKHS and the RKHS norm. See, e.g. Schölkopf and Smola (2002), for a definition and discussion. In (7) we take the norm of $f$ to be infinite if $f$ is not in the RKHS. of $f$. Predictors in $\mathcal{F}(K,B)$ can be learned to within error $\varepsilon$ with $O(B^{2}/\varepsilon^{2})$ samples using $O(B^{2}/\varepsilon^{2})$ steps of gradient descent on the kernalized linear model. And since any predictor learned in this way will be in $\mathcal{F}(K,B)$, showing that there is no low-error predictor in $\mathcal{F}(K,B)$ establishes the limits of what can be learned using $K$. We thus study the norm ball of the Tangent Kernel, which, slightly overloading notations, we denote:

For a fixed source distribution $\mathcal{D}$, there is always a trivial procedure for “learning” it, where a good predictor specific to $\mathcal{D}$ is hard-coded into the “procedure”. E.g., we can use a kernel with a single feature corresponding to this hard coded predictor. Instead, in order to capture learning as inferring from data, and be able to state when this is not possible using some class of methods, e.g. using kernel methods, we refer to a “learning problem” as a family $\mathcal{P}$ of source distributions over $\mathcal{X}\times\mathcal{Y}$, and say that a learning procedure learns the problem to within error $\varepsilon$ if for any distribution $\mathcal{D}\in\mathcal{P}$ the method learns a predictor with population error at most $\varepsilon$.

We consider learning both when the input distribution, i.e. the marginal distribution $\mathcal{D}_{\mathcal{X}}$ over $\mathcal{X}$, is known (or fixed) and when it is unknown. Distribution dependent learning refers to learning when the input distribution is either fixed (i.e. all distributions $\mathcal{D}\in\mathcal{P}$ have the same marginal $\mathcal{D}_{\mathcal{X}}$), or when the model or kernel is allowed to be chosen based on the input distribution $\mathcal{D}_{\mathcal{X}}$, as might be the case when using unlabeled examples to construct a kernel. In distribution independent learning, we seek a single model, or kernel, that ensures small error for all source distributions in $\mathcal{P}$, even though they might have different marginals $\mathcal{D}_{\mathcal{X}}$.

Remark. Typically, we would have a probabilistic quantifier (e.g. in expectation, or with high probability) over sampling the training set, but we define differentiable learning, and learning using a kernel, without any probabilistic quantifier: For differentiable learning, we required that for any $\mathcal{D}\in\mathcal{P}$, gradient descent yields error at most $\varepsilon$ using any sequence of gradient estimates satisfying (2) (this happens with high probability if we use $m=O(B^{2}/\tau^{2})$ to obtain the gradient estimates, but we do not get into this in our results). For kernel learning, we require that for any $\mathcal{D}\in\mathcal{P}$ there exists a predictor in $\mathcal{F}(K,B)$ with error at most $\varepsilon$, as these are the predictors that can be learned (with high probability) using the kernel method (but we do not get into the exact learning procedure).

Gradient Descent Outperforms the NTK

In this section, we exhibit a simple example of a learning problem for which (i) approximate gradient descent on a differentiable model of size $p$ ensures arbitrarily small (in fact zero) error, whereas (ii) the tangent kernel for this model, or in fact any reasonably sized kernel, cannot ensure error better than $0.5-\gamma$, for arbitrarily small $\gamma$, where recall $0.5$ is the error of the null prediction and $\gamma$ depends polynomially on the parameters of the model and of gradient descent.

Several authors have already demonstrated a range of examples where gradient descent ensures smaller error than can be ensured by any reasonably sized kernel, including the tangent kernel (Yehudai and Shamir, 2019, Ghorbani et al., 2019a, b, Allen-Zhu and Li, 2019, 2020, Li et al., 2020, Daniely and Malach, 2020). In Section 6 and Table 2 we survey these papers in detail and summarize the separations they establish. Here, we provide a concrete, self-contained and simple example for completeness, so that we can explicitly quantify the edge a kernel method might have. Our emphasis is on showing that the error for kernel methods is not just worse than gradient descent, but in fact not much better than null prediction—this is in contrast to prior separations, where the error possible using a kernel is either some constant between the error of null prediction and zero error, or more frequently, close to zero error, but not as close as the error attained by gradient descent (see Section 6 for details). In our example, we also pay attention to whether the model’s predictions at initialization are zero—a property that, as we will later see, plays a crucial role in our analysis.

We consider the problem of learning $k$-sparse parities over $n$ biased bits, i.e. where the marginal distribution of each bit (i.e. coordinate) is non-uniform. In order to easily obtain lower bounds for any kernel (not just the tangent kernel), we let the input distribution be a mixture of independent biased bits and a uniform distribution, so that we can argue that no kernel can do well on the uniform component, and hence bound its error also on the mixture. The key is that when $k$ is moderate, up to $k=O(\log n)$, due to the bits being biased, a linear predictor based on all the bits in the parity has enough of an edge to be detected. This does give the tangent kernel a small edge over a trivial predictor, but this is the best that can be done with the tangent kernel. However, in a differentiable model, once this linear predictor is picked up, its support can be leveraged to output a parity of these bits, instead of their sum, thereby obtaining zero error.

Formally, for integers $2\leq k\leq n$ and for $\alpha\in(0,1)$, we consider the “biased sparse parities” problem $\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$ over $\mathcal{X}=\{-1,1\}^{n}$ and $\mathcal{Y}=\{-1,1\}$, and learning w.r.t. the square loss. The problem consists of $\binom{n}{k}$ distributions over $\mathcal{X}\times\mathcal{Y}$, each corresponding to a subset $I\subseteq[n]$ with $|I|=k$. The distribution $\mathcal{D}_{I}$ is defined by the following sampling procedure:

Set $y\leftarrow\chi_{I}(x):=\prod_{i\in I}x_{i}$, the parity over the subset $I$.

To learn $\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$, we construct a differentiable model that is a combination of a linear predictor $\left\langle\theta,x\right\rangle$ and a “selected-parity”, which outputs the parity of the subset of bits indicated by the (essential) support of $\theta$, that is, $\prod_{\left\lvert\theta_{i}\right\rvert\geq\nu}x_{i}$ (for a suitable threshold $\nu$). Importantly, both use the same weights $\theta$ (see Figure 2). The weak edge of the linear predictor allows gradient descent to learn a parameter vector $\theta$ such that $\left\{i\mid\left\lvert\theta_{i}\right\rvert\geq\nu\right\}=I$, and once this is learned, the “selected-parity” kicks in and outputs a perfect predictor.

where $\approx$ stands for the first order approximation of $f_{\theta}$ about $\theta=0$. The behaviour (8) is the only property we need to show that approximate gradient descent learns $\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$: as formalized in 3.1, a single step of gradient descent starting at $\theta^{(0)}=0$ will leave $\theta^{(1)}_{i}\in\left[-\frac{2}{n},\frac{2}{n}\right]$ for $i\not\in I$, while increasing $\theta^{(1)}_{i}\geq\frac{3}{n}$ for $i\in I$, thus yielding the correct parity. In what follows we show how to implement $f_{\theta}$ as a continuous differentiable model with scale $C_{f}=O(n)$, and furthermore how this can implemented as a feed-forward neural network with piece-wise quadratic sigmoidal activations:

$z<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>σ</mi><mo stretchy="false">(</mo><mi>z</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\sigma(z)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0359em;">σ</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.044em;">z</span><span class="mclose">)</span></span></span></span></span>1$$1$ The model $f_{\theta}$, illustrated in Figure 2, is defined below (where $\theta\circ x:=(\theta_{1}x_{1},\ldots,\theta_{n}x_{n})$).

where $\sigma_{a,b}^{c,d}(z):=c+\sigma\left(\frac{z-a}{b-a}\right)(d-c)$, defined for all $a<b$ and $c,d$, satisfies (i) $\sigma_{a,b}^{c,d}(z)=c$ for every $z\leq a$, (ii) $\sigma_{a,b}^{c,d}(z)=d$ for every $z\geq b$ and (iii) $\left\lvert\frac{d}{dz}\sigma_{a,b}^{c,d}(z)\right\rvert\leq\frac{2\left\lvert d-c\right\rvert}{b-a}$. We visualize $\xi$, which is a (coordinate-wise) soft implementation of the $\operatorname*{sign}(\cdot)$ function, in Figure 1.

Furthermore, we show how to implement $S$, $H$ (and hence $\mathcal{G}$) as a neural network using the activation $\sigma$. This is based on observing that we can compute squares in a bounded range by exploiting the quadratic part of the nonlinearity, i.e., $z^{2}=2r^{2}\left(\sigma(z/2r)+\sigma(-z/2r)\right)$ for $z\in[-r,+r]$. The $n$-term products in (11) and (12) can be implemented with subnetworks of depth $O(\log n)$ and width $O(n)$ that recursively computes products of pairs, using $uv=\frac{1}{2}((u+v)^{2}-u^{2}-v^{2})$; if $u,v\in$, we only need to compute squares in the range $$. There is a slight issue in computing the final product because$H(\xi(\theta\circ x))-\left\langle\theta,x\right\rangle$can be unbounded. However,$\left\langle\theta,x\right\rangle\leq 5$in the relevant regime of$\theta$and so we can correctly compute the final product in this regime; the product is not implemented correctly outside the relevant regime, but that doesn’t affect the learning algorithm. The overall network thus has depth$O(\log n)$and$O(n)$ edges.

We can also calculate that for any $i\in[n]$, $\theta$ and $x\in\{-1,1\}^{n}$, it holds that $\lvert\frac{\partial}{\partial\theta_{i}}f_{\theta}(x)\rvert\leq O(n)$ and $|f_{\theta}(x)|\leq 1$. Thus, we get that $C^{2}_{f}=\sup_{\theta,x}\|\nabla_{\theta}f_{\theta}(x)\|^{2}+f_{\theta}(x)^{2}\leq O(n^{2})$.

The following Claim (proved in Section B.1) formalizes how a single step of gradient descent is sufficient for $\theta$ to be away from zero on $I$, and hence for the network to output the correct labels.

For any $n$, $k$ and $\alpha\in(0,1)$, and any $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$, $\tau$-approximate gradient descent on the model $f$ of size $p=n$ and $C_{f}=O(n)$ described above, with initialization $\theta_{0}=0$ (at which $\forall_{x}f_{\theta_{0}}(x)=0$), accuracy $\tau\leq\alpha/2^{k}$, step size $\eta=2^{k}/(\alpha n)$ and $T=1$ step ensures $\mathcal{L}_{\mathcal{D}_{I}}(f_{\theta^{(T)}})=0$. In particular, if $k\leq\log n$ then an accuracy of $\tau\leq\alpha/n$ is sufficient.

On the other hand, the next claim (proof in Section C.1.1), establishes that the tangent kernel at initialization only has a small edge over the null prediction.

The tangent kernel of the model $f$ at $\theta_{0}=0$ is the scaled linear kernel $\mathsf{NTK}^{f}_{\theta_{0}}(x,x^{\prime})=4\left\langle x,x^{\prime}\right\rangle$, and for any $2\leq k\leq n$, $\alpha\in(0,1)$ and $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$ the error with this kernel is $\inf_{h\in\mathsf{NTK}^{f}_{\theta_{0}}(B)}\mathcal{L}_{\mathcal{D}_{I}}(h)\geq\frac{1}{2}-\frac{\alpha}{2}=\frac{1}{2}-O\left(\frac{n^{2}\tau}{C_{f}}\right)$ for all $B\geq 0$, where $\tau=\alpha/2^{k}$ as in 3.1. On the other hand, $\exists{h\in\mathsf{NTK}^{f}_{\theta_{0}}(n)}$ s.t. $\mathcal{L}_{\mathcal{D}_{I}}(h)\leq\frac{1}{2}-\frac{\alpha^{2}}{2^{2k}}=\frac{1}{2}-\Omega\left(\frac{n^{2}\tau^{2}}{C_{f}^{2}}\right)$

We already see that gradient descent can succeed where the tangent kernel at initialization can only ensure an arbitrarily small edge over the error achieved by null prediction, $\mathcal{L}(0)=1/2$:

For any $\gamma>0$, there exists a source distribution (with binary labels and w.r.t. the square loss), such that

[Gradient Descent] Using a differentiable model with $p=2$ parameters, $T=1$ steps, and accuracy $\frac{\tau}{C_{f}}=\Theta(\gamma)$, $\tau$-approximate gradient descent can ensure zero squared-loss, but

[Tangent Kernel] The tangent kernel of the model at initialization does not ensure square loss lower than $\frac{1}{2}-\gamma=\frac{1}{2}-\Theta(\tau/C_{f})$ (compare to the null prediction that always has square loss $\mathcal{L}(0)=\frac{1}{2}$).

Furthermore, the gradient descent algorithm has an initialization $\theta_{0}$ s.t. $\forall_{x}f_{\theta_{0}}(x)=0$.

Apply Claims 3.1 and 3.2 to the sole source distribution in $\mathcal{P}^{\mathsf{bsp}}[n=2,k=2,\alpha=2\gamma]$, (corresponding to $I=\{1,2\}$). ∎

Even though the tangent kernel at the initialization used by gradient descent might have an arbitrarily small edge, one might ask whether better error can be ensured by the tangent kernel at some other “initialization” $\theta$, or perhaps by the tangent kernel of some other model, or perhaps even some other kind of kernelFor each instance $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$, there is of course always a point $\theta$ at which the tangent kernel allows for prediction matching that of Gradient Descent, namely the iterate $\theta^{(T)}$ reached by Gradient Descent. But to learn using a kernel, the kernel should be chosen without knowing the instance, i.e. without knowing $I$.. The following claim shows that this is not the case (proof in Section C.2.1).

For all $\alpha<1/2,k,p,B,n$, and any kernel $K$ corresponding to a $p$-dimensional feature map, there exists $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$ such that

where $\mathcal{L}_{\mathcal{D}_{I}}$ is w.r.t. the square loss, and note that $|\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]|=\binom{n}{k}$.

And so, setting $k=\Theta(\log n)$ and $\alpha=1/\operatorname{poly}(n)$, we see that gradient descent with polynomial parameters can learn $\mathcal{P}^{\mathsf{bsp}}[n,k,\alpha]$, while no tangent kernel of a polynomial sized model (i.e. with $p=\operatorname{poly}(n)$) can ensure better than an arbitrarily small polynomial edge:

For any sequence $\gamma_{n}=1/\operatorname{poly}(n)$, there exists a sequence of learning problems $\mathcal{P}_{n}$ with fixed input distributions (with binary labels and w.r.t. the square loss,), such that

[Gradient Descent] for each $n$, using a differentiable model with $p=n$ parameters, realizable by a neural network of depth $O(\log n)$ with $O(n)$ edges (where some edges have trainable weights and some do not), $T=1$ steps, polynomial accuracy $\frac{\tau}{C_{f}}=O\left(\frac{\gamma_{n}}{n^{2}}\right)$, and initialization $\theta_{0}$ s.t. $\forall_{x}f_{\theta_{0}}(x)=0$, $\tau$-approximate gradient descent learns $\mathcal{P}_{n}$ to zero loss; but

[Poly-Sized Kernels] no sequence of kernels $K_{n}$ corresponding to feature maps of dimension $\operatorname{poly}(n)$ (and hence no tangent kernel of a poly-sized differentiable models) can allow learning $\mathcal{P}_{n}$ to square loss better than $\frac{1}{2}-\gamma_{n}$ for all $n$; and

[Arbitrary Kernel, Poly Norm] no sequence of kernels $K_{n}$ of any dimension can allow learning $\mathcal{P}_{n}$ to square loss better than $\frac{1}{2}-\gamma_{n}$ for all $n$ using predictors in $\mathcal{F}(K_{n},B_{n})$ of norm $B_{n}=\operatorname{poly}(n)$.

Consider $\mathcal{P}_{n}=\mathcal{P}^{\mathsf{bsp}}[n,k=\log_{2}n,\alpha=\gamma_{n}=1/\operatorname{poly}(n)]$. Learnability using GD follows from 3.1, noting that $\frac{\tau}{C_{f}}=\frac{\alpha}{n2^{k}}=\frac{\gamma_{n}}{n^{2}}$ is inverse-polynomial in $n$. Since $\binom{n}{\log_{2}n}=n^{\Omega(\log n)}\gg\operatorname{poly}(n)$, if the kernel dimension $p(n)$ (or similarly, the norm $B_{n}$) is polynomial in $n$, then $\frac{p}{2\binom{n}{k}}=o(1)$, and so for large enough $n$, the error lower bound in 3.3 would be $>\frac{1}{2}-\gamma_{n}$. ∎

While for ease of analysis we presented a fairly specific model, with many fixed (non-trainable) weights and only few trainable weights, we expect the same behaviour occurs also in more natural, but harder to analyze models. To verify this, we trained a two-layer fully-connected ReLU network on the source distribution $\mathcal{D}_{\alpha}$ analyzed above, for $n=128$ and $k=7$. We observe that indeed when $\alpha>0$, and thus a linear predictor has at least some edge, gradient descent training succeeds in learning the sparse parity, while the best predictor in the Tangent Kernel cannot get error much better than $0.5$. See Figure 3 for details.

Ensuring the Tangent Kernel has an Edge

In the example of Section 3 we saw that the Tangent Kernel at initialization cannot ensure small error, and even though Gradient Descent finds a perfect predictor, the tanget kernel only has an arbitarily small edge over the null prediction. But this edge isn’t zero: the second part of 3.2 tells us that at least in the example of Section 3, the tangent kernel will have an edge, and this edge is polynomial (even linear) in the accuracy required of gradient descent. Is this always the case? We now turn to asking whether whenever gradient descent succeeds in ensuring small error, then the Tangent Kernel must indeed have an edge that is at least polynomial in the gradient descent parameters.

We begin by considering situations where gradient descent succeeds starting at an initialization yielding zero predictions on all inputs, i.e. such that:

Following Chizat et al. (2019a), we refer to $\theta_{0}$ satisfying (14) as unbiased initializations. With an unbiased initialization, the Taylor expansion (3) does not have the zero-order, or “bias” term, there is no need for the first coordinate in the feature vector $\phi_{\theta_{0}}$, and the Tangent Kernel becomes $\mathsf{NTK}_{\theta_{0}}^{f}(x,x^{\prime})=\left\langle\nabla_{\theta}f_{\theta_{0}}(x),\nabla_{\theta}f_{\theta_{0}}(x^{\prime})\right\rangle$, simplifying the Neural Tangent Kernel analysis. Chizat et al. (2019a), Woodworth et al. (2020) and others discuss how to construct generic unbiased initializations, namely by including pairs of units that cancel each other out at initialization, but quickly diverge during training and allow for meaningful learning. The initialization used in 3.1 of Section 3 also satisfies (14).

In Theorem 1 below, we show that if gradient descent improves over the loss at initialization, then the Tangent Kernel must also have an edge over initialization, which for an unbiased initialization means an edge over the null prediction.

We can also considered a relaxation of the unbiasedness assumption (14), and instead require only that the output of the network at initialization is very close to zero. This would be the case with some random initialization schemes which initialize the network randomly, but with small magnitude. As long as the deviation from unbiasedness is smaller than the edge guaranteed by Theorem 1, the Theorem would still ensure the tangent kernel has an edge over null prediction.

In particular, if $\theta_{0}$ is an unbiased initialization and $\varepsilon<\mathcal{L}_{\mathcal{D}}(0)$, then

At a high level, we argue that if gradient descent is going to move at all, the gradient at initialization must be substantially non-zero, and hence move the model in some direction that improves over initialization. But since the tangent kernel approximates the true model close to the initialization, this improvement translates also to an improvement over initialization also in the Tangent Kernel. If the initialization is unbiased, initialization is at the null predictor, and this is an improvement over null predictions.

For any $\alpha>0$, denoting ${\bm{w}}_{*}=-\alpha\frac{\nabla_{{\bm{w}}}\mathcal{L}(h_{0})}{\left\lVert\nabla_{{\bm{w}}}\mathcal{L}(h_{0}))\right\rVert}$, we have:

Theorem 1 relies on the initialization being unbiased, or at the very least the predictions at initialization not being worse than the null predictions. Can we always ensure the initialization satisfies such a condition? And what happens if it does not? Might it then be possible for Gradient Descent to succeed even though the Tangent Kernel does not have an edge over the null prediction?

The example in Section 5 shows that, indeed, some learning problems might be learnable by gradient descent, but only using an initilization that is not unbiased. That is, we should not expect initializations to always be unbiased, nor can we expect to always be able to “fix” the initialization to be unbiased. And furthermore, the example shows that with an initilization that is not unbiased, the Tangent Kernel at initilization might not have a significant edge over the null predictor.

But before seeing this example, let us ask: What can we ensure when the initialization is not unbiased?

2 With Distribution Dependence

In Theorem 2 we show that, at least for the square loss, for an arbitrary initialization, even though the Tangent Kernel at initialization might not have an edge, we can construct a distribution $\mathcal{W}$, which we can think of as an alternate “random initilization”, such that the Tangent Kernel of the model at a random point $\theta\sim\mathcal{W}$ drawn from this distribution, does have an edge over null prediction. But the catch is that this distribution depends not only on the true initialization $\theta_{0}$, but also on the input distribution $\mathcal{D}_{\mathcal{X}}$. That is, the Tangent Kernel for which we are establishing an edge is distribution dependent. In Section 5 we will see that this distribution-dependence is unavoidable.

On the other hand, we have for every $t$:

Using the above, taking $\alpha=\frac{\sqrt{2\gamma^{\prime}}}{C_{f}}$ we get that for every $t$:

No Edge with the Tangent Kernel

As promised, we will now present an example establishing:

Some learning problems are learnable by gradient descent, but only with a biased initialization

Theorem 1 cannot be extended to biased initializations: Even if gradient descent, with a biased initialization, ensures small error, the Tangent Kernel at initialization might not have a significant edge.

Theorem 2 cannot be made distribution-independent: Even if gradient descent, with a biased initialization, ensures small error on a learning problem, there might not be any distribution-independent random “initialization” that yields a significant edge in a Tangent Kernel at a random draw from this “initialization”.

More formally, $\mathcal{D}_{I}^{(0)}$ is the distribution obtained by sampling $x\sim\mathcal{U}(\{\pm 1\}^{n})$ and setting $y=\chi_{I}(x):=\prod_{i\in I}x_{i}$, while $\mathcal{D}_{I}^{(1)}$ is the distribution obtained by (deterministically) setting $x:=x^{I}$ and sampling $y\sim\mathcal{U}(\{-1,1\})$, and recall $\mathcal{D}_{I}:=(1-\alpha)\mathcal{D}_{I}^{(0)}+\alpha\mathcal{D}_{I}^{(1)}$. In other words, $\mathcal{D}_{I}$ corresponds to first choosing $b\in\{0,1\}$ with $\Pr[b=1]=\alpha$ and sampling $(x,y)\sim\mathcal{D}_{I}^{(b)}$.

As with the model of Section 3, we can implement (27) as a continuous differentiable model with scale $C_{f}=O(n)$, through a slight modification of the architecture described in Equations (9)-(13):

where $S$, $H$ and $\xi$ are as defined in (11), (12) and (13). The first term in (28) is $-1$ at $\theta^{(0)}=0$ and satisfies $\nabla_{\theta}~{}\sigma_{0,\frac{2}{n}}^{-1,0}\left(\left\langle\theta^{(0)},\mathbf{1}\right\rangle\right)=0$. The second term is essentially the same as (9), with only difference being the linear term $\left\langle\theta,x\right\rangle$ is replaced with $\left\langle\theta,x+\frac{5}{3}\alpha\mathbf{1}\right\rangle$. Similar to the construction in Section 3, we get that (27) holds and that $C_{f}^{2}\leq O(n^{2})$. Furthermore, we can implement $f_{\theta}$ using a similar feed-forward network of depth $O(\log n)$ and $O(n)$ edges.

We prove the following claims in Section B.2 and Section C.1.2 respectively (cf. Claims 3.1 and 3.2).

For any $n$ and $\alpha\in(0,1)$, for any $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{lp}}[n,\alpha]$, gradient descent on the model $f$ of size $p=n$ with $C^{2}_{f}=O(n^{2})$ described above, with initialization $\theta_{0}=0$, accuracy $\tau=\frac{4}{3}\alpha$, step size $\eta=1$ and $T=1$ step ensures error $\mathcal{L}_{\mathcal{D}_{I}}(f_{\theta^{(T)}})\leq\alpha$.

The tangent kernel of the model $f$ at $\theta_{0}=0$ is the scaled linear kernel endowed with a bias term, $\mathsf{NTK}_{\theta_{0}}^{f}(x,x^{\prime})=(1+\frac{100}{9}\alpha^{2})+4\left\langle x,x^{\prime}\right\rangle$, and for any $n\geq 2$, $\alpha\in(0,1)$, and any $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{lp}}[n,\alpha]$, the error with this kernel is $\inf_{h\in\mathsf{NTK}_{\theta_{0}}^{f}(B)}\mathcal{L}_{\mathcal{D}_{I}}(h)=\mathcal{L}_{\mathcal{D}_{I}}(0)=\frac{1}{2}$ for any $B\geq 0$.

We already see that in contrast to a situation where the initialization is unbiased, and so Theorem 1 ensures the tangent kernel has at least a polynomial edge, even if gradient descent succeeds, but with an initialization which is not unbiased, the tangent kernel at initialization might not have any edge at all, and so we cannot hope to remove the requirement of the initialization being unbiased from Theorem 1:

For any $\varepsilon>0$, there exists a source distribution (with binary labels and w.r.t. the square loss), such that

[Gradient Descent] Using a differentiable model with $p=2$ parameters, $T=1$ steps, and accuracy $\frac{\tau}{C_{f}}=\Theta(\varepsilon)$, $\tau$-approximate gradient descent ensures square loss of $\varepsilon$, but

[Tangent Kernel] The tangent kernel of the model at initialization cannot ensure square loss lower than $\frac{1}{2}$ (which is the loss of null prediction).

Apply Claims 5.1 and 5.2 to the sole source distribution in $\mathcal{P}^{\mathsf{lp}}[n=2,\alpha=2\varepsilon]$. ∎

But what about the tangent kernel at a different “initialization”, or of some other model, or even some other kernel altogether? The following Claim (proved in Section C.2.2) shows that no kernel can get a significant edge over the zero predictor unless the number of features and the norm are both exponentially large in $n$. In order to contrast with guarantee (18) of Theorem 2, we state the Claim also for learning using a random kernel, i.e. in expectation over an arbitrary distribution of kernels.

For all $\alpha\in(0,1),p,B,n$, and any randomized kernel $K$ with $\textrm{rank}(K)=p$ almost surely (i.e. a distribution over kernels, each of which corresponding to a $p$-dimensional feature map), there exists $\mathcal{D}_{I}\in\mathcal{P}^{\mathsf{lp}}[n,\alpha]$ such that

where $\mathcal{L}_{\mathcal{D}_{I}}$ is w.r.t. the square loss, and note that $|\mathcal{P}^{\mathsf{lp}}[n,\alpha]|=2^{n}-n-1$.

In particular, we see that in contrast to the distribution-dependent situation of Theorem 2, where we could ensure a polynomial edge for the tangent kernel at a specified randomized “initialization”, this is not possible in general, and we cannot hope to remove the dependence on the input distribution in Theorem 2.

For any sequence $\varepsilon_{n}=1/\operatorname{poly}(n)$, there exists a sequence of learning problem $\mathcal{P}_{n}$ (with binary labels and w.r.t. the square loss), such that

[Gradient Descent] for each $n$, using a differentiable model with $p=n$ parameters, realizable by a neural network of depth $O(\log n)$ and $O(n)$ edges (where some edges have trainable weights and some do not), $T=1$ steps, and accuracy $\frac{\tau}{C_{f}}=O(\frac{\varepsilon_{n}}{n})$, $\tau$-approximate gradient descent learns $\mathcal{P}_{n}$ to square loss of $\varepsilon_{n}$, but

[Poly-Sized Kernels] no sequence of (randomized) kernels $K_{n}$ corresponding to feature maps of dimension $\operatorname{poly}(n)$ (and hence no tangent kernel of a poly-sized differentiable models, even with randomized “initialization”) can allow learning $\mathcal{P}_{n}$ (in expectation) to square loss smaller than $\frac{1}{2}-2^{-\Omega(n)}$ for all $n$; and

[Arbitrary Kernel, Poly Norm] no sequence of (randomized) kernels $K_{n}$ of any dimension can allow learning $\mathcal{P}_{n}$ (in expectation) to square loss smaller than $\frac{1}{2}-2^{-\Omega(n)}$ for all $n$ using predictors in $\mathcal{F}(K_{n},B_{n})$ of norm $B_{n}=\operatorname{poly}(n)$.

Apply Claims 5.1 and 5.3 to $\mathcal{P}_{n}=\mathcal{P}^{\mathsf{lp}}[n,\alpha=\varepsilon_{n}]$. ∎

Since we are working over a domain $\mathcal{X}=\{-1,+1\}^{n}$ or cardinality $2^{n}$, we can always ensure an edge of $(1-\alpha)p/2^{n+1}$ using indicator features on $p$ of the $2^{n}$ inputs, thus allowing memorization of these tiny fraction of inputs. An edge of $2^{-\Theta(n)}$ is thus a “trivial” edge attained by this kind of memorization, and 5.3 and 4 establish the tangent kernel, or even any other kernel, cannot be significantly better.

We can also conclude that even though we saw that our learning problem is learnable with gradient descent, we cannot hope to learn it with an unbiased initialization, since this would imply existence of a kernel with a polynomial edge. We thus get the following separation between learnability with gradient descent using biased versus unbiased initialization (importantly, only for distribution independent learning).

For any sequence $\varepsilon_{n}=1/\operatorname{poly}(n)$, there exists a sequence of learning problem $\mathcal{P}_{n}$ (with binary labels and w.r.t. the square loss), such that

[GD with biased initialization] for each $n$, using a differentiable model with $p=n$ parameters, realizable by a neural network of depth $O(\log n)$ and $O(n)$ edges (where some edges have trainable weights and some do not), $T=1$ step, and accuracy $\frac{\tau}{C_{f}}=O\left(\frac{\varepsilon_{n}}{n}\right)$, and some (not unbiased) initialization, $\tau$-approximate gradient descent learns $\mathcal{P}_{n}$ to square loss $\varepsilon_{n}$, but

[GD with unbiased initialization] It is not possible to ensure error better than $\frac{1}{2}$ on $\mathcal{P}_{n}$, for all $n$, using $\tau$-approximate gradient descent starting with an unbiased initialization (as in Eq. (14)), and any differentiable models of size $p=\operatorname{poly}(n)$ and accuracy $\tau/C_{f}=1/\operatorname{poly}(n)$, and any number of steps $T$.

Consider $\mathcal{P}_{n}=\mathcal{P}^{\mathsf{lp}}[n,\alpha=\varepsilon_{n}]$. 5.1 ensures learnability with a biased initialization. Suppose $\mathcal{P}_{n}$ was also learnable by $\tau$-approximate gradient descent with unbiased initialization, using a model $f$ of size $p_{n}=\operatorname{poly}(n)$, scale $C_{f}$ satisfying $\tau/C_{f}=1/\operatorname{poly}(n)$, to within any error better than $0.5$, then Theorem 1 would imply the tangent kernel at initialization would ensure error $\leq\frac{1}{2}-\frac{1}{\operatorname{poly}(n)}$. This is a fixed kernel that depends only on the model $f_{\theta}$, and corresponds to a feature map of dimension $p_{n}+1$. Since $p_{n}=\operatorname{poly}(n)$, this would contradict 5.3. ∎

Survey of Separation Results

In Sections 3 and 5 we described learning problems for which gradient descent learning succeeds, but where the NTK, or indeed any other (reasonably sized) kernel, has either a very small edge, or even no edge at all. Our emphasis was on establishing not only that the NTK or kernel methods get worse error than gradient descent (as in previous separation results), but on bounding how close to the null prediction they must be (i.e. how small an edge they must have). Here we survey such prior separation results, understanding the relationships between them, and how they relate to the new separations from this paper.

The middle set of green columns indicate what error can be ensured by running the indicated type of gradient descent variant on the indicated type of model. An error of “$\rightarrow 0$” indicates that the learning problem only depends on $n$, and that for every $n$, gradient descent on a fixed model (that depends on $n$ but not $\varepsilon$) can make the error $\varepsilon$ arbitrarily small using $\operatorname{poly}(n/\varepsilon)$ samples and/or steps. An error of “$\leq\varepsilon$” indicates that the learning problem also depends on $\varepsilon$: for all $n$ and $\varepsilon>0$, there exists a learning problem on which gradient descent ensures error $\leq\varepsilon$ (but kernel methods incur larger error). The annotations $0/\approx/\times$ under column “I” indicates: if the initialization used is unbiased, or could be easily made unbiased; $\approx$ if it is nearly unbiased (error at initialization close to null prediction); or $\times$ if the initialization is far from null.

The right set of pink columns shows the lower bound on the error for the kernel, or class of kernels indicated, or under other restrictions (“dim” is the number of features or rank of the kernel, “norm $\leq B$” means restricting to $\mathcal{F}(K,B)$ as in (6), NTK is the tangent kernel of the model used for gradient descent unless otherwise specified). In all cases, the error is normalized so that the error of null perdition is $\mathcal{L}(0)=\nicefrac{{1}}{{2}}$. For our separations, the error is given in terms of the edge (if any) over null prediction. In all prior separations, the error lower bound is bounded away from the null prediction (the edge is at least $0.1$), and the actual error lower bound is indicated. The notation $\geq\varepsilon^{\prime}(c)>0$ and $\geq\varepsilon^{\prime}(\rho)>\varepsilon(\rho)$ indicates that for any choice of $c$ or $\rho$, there is some $\varepsilon^{\prime}(c)>0$ or $\varepsilon^{\prime}(\rho)>\varepsilon(\rho)$ which lower bounds the error.

The last column indicates the nature of the learning problem used to establish the lower bound, and thus whether the separation is distribution dependent or independent (in the sense introduced in Section 2): “$-$” indicates that the separation is for a specific source distribution (or sequence of source distribution with increasing input dimension $n$). This is the strongest form of separation, implying also distribution dependent separation, and is only possible by restricting to a specific kernel or kernel class. The notation “$y$” indicates the lower bound is for a learning problem $\mathcal{P}$ where the input distribution $\mathcal{D}_{\mathcal{X}}$ is fixed, and the source distributions in $\mathcal{P}$ vary only in the labeling function $y(x)$ (which is deterministic in all such problems considered in the table). This yields a “distribution dependent” separation (i.e. a separation that holds even if the kernel is allowed to depend on hte input distribution). The notation “${x}$” indicates that the lower bound is for a learning problem $\mathcal{P}$ where different source distributions $\mathcal{D}\in\mathcal{P}$ have varying input distributions $\mathcal{D}_{\mathcal{X}}$, but we seek a kernel that would work well for all distributions in the learning problem. This yields a weaker “distribution independent” separation, as it only implies a separation if the kernel choice is not allowed to depend on the input distribution $\mathcal{D}_{\mathcal{X}}$. It should be noted that these differences are due to differences in how the lower bound is established, and not differences in limitations or generality of the gradient descent guarantees (in all settings considered, the gradient descent guarantees are under severe restrictions on the input distribution, but the model used for training is independent of the specific input distribution meeting these restrictions).

As can be seen from Table 2, in all the prior separation results, the lower bound on the error of kernel methods is bounded away from $\mathcal{L}(0)$, i.e. the upper bound on the edge is $O(1)$. In fact, in all prior separations except for Daniely and Malach (2020), the kernel error goes to zero when the error of gradient descent goes to zero, it just goes to zero slower (Daniely and Malach establish a lower bound on the error that is bounded away from zero, but it still corresponds to a constant edge). In contrast, we exhibit a situation where the NTK, or any kernel method, has only vanishing (or zero) edge, and study how quickly this edge goes to zero. In order to obtain a separation where the edge of the NTK at initialization is zero, and the edge of any kernel is exponentially small, we construct a learning problem where the input distribution is not fixed, and where gradient descent learning is possible only with a biased initialization—this is necessary otherwise Theorems 1 and 2 would tell us the edge must be at least polynomial. It is interesting to note that none of the prior constructions are of this nature: the only prior construction that relies on variable input distributions is that of Daniely and Malach (2020), but they use an unbiased initialization.

The different separation results differ in the type of kernels for which they establish lower bounds. Many of the separation results (including our Separations 2 and 4) establish lower bounds for any kernel corresponding to a poly-dimensional feature space, and thus for the NTK of any poly-sized model. When considering the square loss, such lower bounds also imply lower bounds for any kernel (of any dimensionality) using poly-norm predictors, as in our Claims 3.3 and 5.3 (also see Lemma 5 in Kamath et al., 2020). Since Daniely and Malach (2020) considered the hinge loss, they required that both the dimension and the norm be polynomial (see Kamath et al. (2020) for a discussion on kernel lower bounds for the squared norm versus the hinge loss. In yet unpublished followup work, we obtain lower bounds on the hinge loss also without a norm bound).

As discussed in Section 2, in order to establish lower bounds with respect to any kernel, one necessarily needs to consider an entire learning problem (with multiple different possibly labelings) rather than a specific source distribution. Ghorbani et al. (2019a, b) take a different approach: they restrict the kernels being considered to NTKs of a specific model, NTKs of a class of models, or general rotationally invariant kernels, and so are able to establish separations for specific source distributions (between differentiable learning and using one of these specific kernels). These separations are more similar to our Separations 1 and 3, which are specific to the NTK of the model being used (theirs are more general), but their separations holds only for large input dimensions $n$, while ours holds already for dimension $n=2$.

A deficiency of our Separations 3 and 4, shared also by Li et al. (2020), Allen-Zhu and Li (2019), Daniely and Malach (2020) and Ghorbani et al. (2019a), is that we do not demonstrate a fixed learning problem where the gradient descent error goes to zero. Instead, for every $\varepsilon>0$, we construct a different problem where the gradient descent error is $\leq\varepsilon$ (while the kernel error is high; close to that of the null predictor). Ghorbani et al. (2019b) and Allen-Zhu and Li (2020), as well as our Separations 1 and 2, do use learning problem where gradient descent can get arbitrarily small error. It would be interesting to strengthen Separations 3 and 4 so that gradient descent could converge to zero error (with a fixed learning problem and model).

The separation results also differ in the form of gradient descent they analyze. Ghorbani et al. (2019a) and Daniely and Malach (2020) analyze gradient descent or gradient flow on the population, which is the limit of GD/SGD when the number of samples and/or iterations goes to infinity (although how quickly these should increase is not analyzed). But most analysis is for batch or stochastic gradient descent (which is what would be used in practice) with polynomial samples and iterations (Soltanolkotabi, 2017, Mei et al., 2018, Allen-Zhu and Li, 2019), perhaps with slight modifications or regularization (Li et al., 2020, Allen-Zhu and Li, 2020). Our analyses is for $\tau$-approximate gradient descent with polynomial accuracy $\tau$, which subsumes batch (or mini-batch) gradient descent with polynomially many samples (or batch size). But our analysis is perhaps odd and unnatural in that it relies on a single step with a large stepsize, rather than allowing the number of steps to increase and the stepsize to decrease. It should be possible, though is technically much more complicated, to extend our analysis to cover also gradient descent with any stepsize smaller than the one we use, and thus also gradient flow. This would establish strong separation also based on a more restrictive definition of differentiable learning, which requires robustness with respect to the stepsize.

Finally, the models we use are chosen to be simple to analyze, but they are perhaps not “natural”. We do show how they can be implemented with a sigmoidal network, but this is a network with a very specific architecture, or alternatively a fully connected network with very specific initialization and where some of the weights are fixed rather than trained. Showing similarly strong separations with more natural architectures and random initialization would be desirable. The empirical demonstration in Figure 3 indicates this should be possible (though perhaps technically involved). Allen-Zhu and Li (2019, 2020) also use a specialized residual architecture (though perhaps not as specific as ours), while the others (Soltanolkotabi, 2017, Mei et al., 2018, Ghorbani et al., 2019a, Li et al., 2020, Daniely and Malach, 2020) use fairly benign networks and initialization.

Conclusion and Discussion

With the study of Neural Tangent Kernels increasing in popularity, both as an analysis and methodological approach, it important to understand the limits of the relationship between the Tangent Kernel approximation and the true differentiable model. Furthermore, the notion of “gradual” learning of deep models, where we learn progressively more complex models, or more layers, and so the success of deep learning rests on being able to make progress even with simpler, e.g. linear models, is an appealing approach to understanding deep learning. Indeed, when we first asked ourselves whether the tangent kernel must always have an edge in order for gradient descent to succeed, and we sought to quantify how large this edge must be, we were guided also by understanding the “gradual” nature of deep learning. We were surprised to discover that in fact, with biased initialization, deep learning can succeed even without the tangent kernel having a significant edge.

Our results also highlight the importance of the distinction between distribution dependent and independent learning, and between biased and unbiased initialization. The gap between distribution dependent and independent learning relates to kernel (i.e. linear) methods inherently not being able to leverage information in $\mathcal{D}_{\mathcal{X}}$: success or failure is based on whether $y|x$ is well represented by a predictor in $\mathcal{F}(K,B)$, and has little to do with the marginal over $x$. In contrast, gradient descent on a non-linear model, could behave very differently depending on $\mathcal{D}_{\mathcal{X}}$, as we also see empirically in the experiment in Figure 3. Perhaps even more surprising is the role of the bias of the initialization. It might seem like a benign property, and that we should always be able to initialize with zero, or nearly-zero predictions, or at least at $\theta_{0}$ that is not much worse than null, or perhaps correct for the bias as in Chizat et al. (2019a). But we show that at least for distribution-independent learning, this is not a benign property at all: for some problems we must use biased initialization (5). This observation may be of independent interest, beyond the role it plays in understanding the Neural Tangent Kernel.

The learning problems and models we used to demonstrate the separation results are artificially extreme, so as to push the separation to the limit, and allow easy analytical study. But we believe they do capture ways in which gradient descent is more powerful than kernel methods. In the example of Section 3, gradient descent starts by selecting a few “simple features” (the $k\ll n$ relevant coordinates), based on simple correlations. But unlike kernel methods, gradient descent is then able to use these features in more complex ways. We see this happening also empirically in Figure 3 with a straightforward two-layer ReLU network, where gradient descent is able to succeed in learning the complex parity function, once there is enough signal to easily identify the few relevant coordinates. In the example of Section 5, we see how gradient descent is also able to pick up on structure in the input (unlabeled data) distribution, in a way that kernel methods are fundamentally unable to.

Acknowledgements

We thank Gilad Yehudai for clarifying our questions about Yehudai and Shamir (2019). This work was done while NS was visiting EPFL. This research is part of the NSF/Simons funded Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations.ai). PK was partially supported by NSF BIGDATA award 1546500.

References

Appendix A Prior work on Separations between Differentiable Learning and Kernels

We provide more details on the prior work presented in Table 2 that demonstrate learning tasks where gradient-descent based learning can ensure smaller error than any reasonably sized kernel method.

In the summary below, whenever a $\operatorname{poly}(\cdot)$ terms appears under “Learnability with Gradient Descent”, it is always for a particular $\operatorname{poly}(\cdot)$ that has been explicitly or implicitly specified in the corresponding reference. On the other hand, for every $\operatorname{poly}(\cdot)$ term that appears under “Non-learnability with any Kernel Method”, it is always meant to hold for any $\operatorname{poly}(\cdot)$.

Yehudai and Shamir (2019), Ghorbani et al. (2019b) : Class of ReLU neurons over Gaussian inputs

Learnability with Gradient Descent: Soltanolkotabi (2017), Mei et al. (2018) showed that, in the case when $b=0$, projected batch gradient descent over the ReLU model with $\operatorname{poly}(n/\varepsilon)$ samples with zero initialization (i.e., unbiased initialization with $w^{(0)}=0$), can ensure square loss at most $\varepsilon$ with $O(\operatorname{poly}(n)\log(1/\varepsilon))$ steps. Importantly, this holds for any $\varepsilon>0$. In the analysis of the positive result, initializing from zero is important, since in this case the first step of gradient-descent already captures the “direction” of the target neuron.

Non-learnability with any Kernel Method: Yehudai and Shamir (2019) show that any randomized feature map of dimension at most $2^{c_{1}n}$ with coefficients of the predictors bounded by $2^{c_{1}n}$, for some universal constant $c_{1}$, must incur a square loss of at least $\Omega(1/n^{8})$; this is a scaled version of their stated result, which was for $\|w\|=n^{3}$ and $|b|\leq 6n^{4}+1$. Subsequently, Kamath et al. (2020) showed the same bound can be obtained without the restriction on coefficients of the predictors, leading to the lower bound as presented in the Table 2. Both of these lower bounds crucially rely on a non-zero bias term $b$.

Because the upper bounds are specific to the case $b=0$ where there is no bias term, while the lower bound relies on a bias term $b\neq 0$, the analysis of Yehudai and Shamir does not establish a separation between differentiable learning and kernel methods. It was communicated to use by Gilad Yehudai that ongoing work with Ohad Shaimr and Gal Vardi indicates that gradient descent also succeeds in the presence of a non-zero bias term, which would yield a separation. Alternatively, in our own yet unpublished work, we observed it is also possible to obtain a lower bound for ReLU without the bias term, which also yields a separation.

Ghorbani et al. (2019b) show that for any constant $c_{2}$, any kernel method that is either (i) a rotationally invariant kernel using at most $n^{c_{2}}$ samples or (ii) NTK of a depth-$2$ ReLU Net with at most $n^{c_{2}}$ units must incur a square loss of at least $\varepsilon^{\prime}(c_{2})$, which is a positive constant that depends only on $c_{2}$. This result holds even for a fixed source distribution $\mathcal{D}$, that is, a fixed choice of $w$ and $\mathcal{D}_{\mathcal{X}}=\mathcal{N}(0,I_{n})$. This result holds with probability approaching $1$, as the dimension $n$ and the number of features grow to infinity.

Ghorbani et al. (2019a) : (i) Convex Quadratic Functions, (ii) Mixture of Gaussians (Binary Labels)

Learning Problems: Two learning problems are considered here; both w.r.t. square loss.

Learnability with Gradient Descent: For a depth-$2$ network with quadratic activations, with $N$ units and any random initialization that is absolutely continuous w.r.t. Lebesgue measure (in particular, the initialization can be chosen to nearly unbiased), it is shown that in the asymptotic regime as $n,N\to\infty$ with $\rho=N/n<1$, gradient flow w.r.t. population loss ensures square loss that approaches $\varepsilon(\rho)$, which is a closed form expression that also depends on the specific source distribution (i.e. the quadratic target or the covariances of the classes), or rather sequence of source distributions as $n\rightarrow\infty$. The requirement on the initialization is needed since there is a measure-zero set of initializations that converge to a saddle point. Depending on the problem, the saddle points can be escaped also from an unbiased initialization.

Non-learnability with any Kernel Method: It is shown in the same asymptotic regime of $n,N\to\infty$ with $\rho=N/n<1$, that the NTK at initialization of the same model incurs a square loss of $\varepsilon^{\prime}(\rho)$, which is a closed form expression that also depends on the sequence of source distributions as $n\rightarrow\infty$. It is shown that for non-degenerate distribution sequences, and any $\rho<1$, that $\varepsilon^{\prime}(\rho)>\varepsilon(\rho)$.

Li et al. (2020) : A depth-$2$ Net, with abs. value activations and restricted weights, over Gaussian inputs

Learnability with Gradient Descent: It is shown that there exists a depth-$2$ ReLU network with $\operatorname{poly}(n)$ units and a random normal initialization that is not unbiased, a type of truncated batch gradient descent (where large coordinates of the gradient are set to zero) using $\operatorname{poly}(n)$ samples, is shown to ensure square loss at most $\varepsilon:=1/n^{1+\delta}$ for a constant $\delta\in(0,0.01)$ (that depends on $\kappa$) with $\operatorname{poly}(n)$ steps. Notably, this procedure is not shown to ensure an arbitrarily small error.

Non-learnability with any Kernel Method: It is shown that any kernel method with at most $\operatorname{poly}(n)$ features (for any $\operatorname{poly}(n)$) must incur a square loss of at least $\Omega(1/n)\geq\varepsilon^{1-\delta/2}$.

Allen-Zhu and Li (2019) : Sparse Variable Selection + Parity (implementable as a depth-$2$ ResNet)

Learnability with Gradient Descent: For an overparameterized depth-$2$ ResNet with $\operatorname{poly}(n/\varepsilon)$ units and a random normal initialization (that has a high variance, leading to a biased initialization), stochastic gradient descent is shown to ensure square loss of $\varepsilon\leq\alpha^{3.9}$ with $\operatorname{poly}(n,1/\varepsilon)$ steps. Notably, it is not shown to ensure an arbitrarily small error.

Non-learnability with any Kernel Method: It is shown that any kernel method with at most $\operatorname{poly}(n)$ (for any $\operatorname{poly}(n)$) features must incur a square loss of at least $\Omega(\varepsilon^{0.52})\geq\Omega(\alpha^{2})$.

Remark: Note that the learning problem here depends on the choice of $\varepsilon$. That is, for every $n$ and $\varepsilon>0$, there is a learning problem where stochastic gradient descent ensures square loss $\leq\varepsilon$ whereas no kernel method of dimension at most $\operatorname{poly}(n)$ can achieve a loss smaller than $\varepsilon^{0.52}$.

Allen-Zhu and Li (2020) : A depth-$L$ Net with quadratic activations

Learnability with Gradient Descent: For an overparameterized depth-$L$ Net with quadratic activations, with identical layer structure as $N_{\theta}$, with $\operatorname{poly}(n)$ units and zero initialization (unbiased), regularized stochastic gradient descent (with a non-standard regularizer) is shown to ensure square loss $\varepsilon$, with $\operatorname{poly}(n/\varepsilon)$ number of steps. Importantly, this holds for any $\varepsilon>0$.

Non-learnability with any Kernel Method: It is shown that any kernel method of dimension at most $\operatorname{poly}(n)$ (for any $\operatorname{poly}(n)$) must incur a square loss of at least $\Omega(1/n^{0.01})$.

Daniely and Malach (2020) : Sparse parities over a mixture of uniform and leaky marginals

Learning Problem: With $\mathcal{X}=\{-1,1\}^{n}$ and $\mathcal{Y}=\{-1,1\}$, the learning problem is similar to $\mathcal{P}^{\mathsf{lp}}[n,\alpha]$ that we consider in Section 5 with $\alpha=1/2$. There are two differences: (i) The label under $\mathcal{D}_{I}^{(1)}$ is given by the parity, instead of being random and (ii) the sparsity of the parity is fixed to be $k$, which can be taken to be $k=\Theta(\sqrt{n})$.

Appendix B Proofs of Gradient Based Learning

We only rely on Equation 8, which gives us that at $\theta^{(0)}=0$, we have for all $x\in\{-1,1\}^{n}$ that

and hence $\nabla_{\theta}\mathcal{L}_{\mathcal{D}_{I}}(f_{\theta^{(0)}})$ is given by

With step size $\eta=2^{k}/(\alpha n)$, we have that after the first gradient step, (i) for all $j\in I$, $\theta_{j}^{(1)}\in[\frac{2^{k}}{\alpha n}\cdot(\frac{4\alpha}{2^{k}}\pm\tau)]=[\frac{3}{n},\frac{5}{n}]$, (ii) for all $j\notin I$, $\theta_{j}^{(1)}\in[\frac{2^{k}}{\alpha n}\cdot(\frac{\alpha}{2^{k}}\pm\tau)]=[0,\frac{2}{n}]$ (since $\tau=\alpha/2^{k}$). From Equation 8 we get $f_{\theta^{(1)}}(x)=\prod_{i\in I}x_{i}$, thereby concluding the proof. ∎

B.2 Proof from Section 5

We only rely on Equation 27, which gives us that at $\theta^{(0)}=0$, we have for all $x\in\{-1,1\}^{n}$ that

and hence $\nabla_{\theta}\mathcal{L}_{\mathcal{D}_{I}}(f_{\theta^{(0)}})$ is given by

With gradient accuracy of $\tau=\frac{4}{3}\alpha$, we get that any valid gradient estimate $g$ must satisfy $g_{i}\in[-\frac{12\alpha}{3},-\frac{20\alpha}{3}]$ for $i\in I$, and $g_{i}\in[0,-\frac{8\alpha}{3}]$ for $i\notin I$. Using step size $\eta=\frac{3}{4\alpha n}$, we get

From Equation 27, we get that $f_{\theta^{(1)}}(x)=\prod_{i\in I}x_{i}$ and it is easy to see that $\mathcal{L}_{\mathcal{D}_{I}}(f_{\theta^{(1)}})=\alpha$. ∎

Appendix C Lower Bounds on Kernel Methods

It follows from (30) and (31) that the tangent feature map is $\phi_{\theta_{0}}(x)=x$, establishing that the NTK is the standard linear kernel, and that predictors in the NTK are just linear in $x$. For uniform inputs (i.e. from $\mathcal{D}_{0}$), no linear predictor $h_{w}(x)=\left\langle w,x\right\rangle$ is correlated with the parity if $k\geq 2$ bits, and so the expected square loss of any such predictor on $\mathcal{D}_{0}$ will be at least $\frac{1}{2}$, yielding $\mathcal{L}_{\mathcal{D}_{I}}(h_{w})\geq(1-\alpha)\frac{1}{2}=\frac{1}{2}-\frac{\alpha}{2}$.

The actual optimal linear predictor is of the form $h(x)=c\sum_{i\in I}x_{i}+b\sum_{i\not\in I}x_{i}$, and has a slightly better edge. ∎

C.1.2 NTK Edge in Section 5

C.2 Lower Bounds for General Kernels

In order to prove lower bounds against general kernels, we recall the lower bounds proved on the dimension or norm of a (probabilistic) feature map needed to be able to represent certain hypothesis classes that were proved by Kamath et al. (2020), via probabilistic variants of dimensional and margin complexity.

then, it holds that (i) $p\geq 2\gamma\cdot|\mathcal{P}|$ and (ii) $B^{2}\geq\Omega(\gamma^{3}\cdot|\mathcal{P}|)$.

Equivalently, we have that there exists $\mathcal{D}\in\mathcal{P}$ such that

Part (i). The claim of $p\geq 2\gamma\cdot|\mathcal{P}|$ follows immediately from Theorem 19 in Kamath et al. (2020).

We set $\eta=\gamma/2$, so that we can take $p^{\prime}\leq B^{2}\cdot O(1/\gamma^{2})$. From Part (i), we now have that $p^{\prime}\geq 2(\gamma-\eta)\cdot|\mathcal{P}|=\gamma\cdot|\mathcal{P}|$. Putting everything together, we get that $B^{2}\geq\Omega(\gamma^{3}\cdot|\mathcal{P}|)$. ∎

We now use Theorem 3 to prove lower bounds in Sections 3 and 5. The key idea is that while, the learning problems considered are either not orthogonal, or do not have fixed marginals, they contain a large component that is a learning problem with fixed marginals that is orthogonal.

Fix a probabilistic kernel $K$ corresponding to $p$-dimensional feature maps. For all $\mathcal{D}_{I}\in\mathcal{P}$, we have

where $\mathcal{D}_{I}^{(b)}$ corresponds to sampling $x\sim\mathcal{D}_{b}$ and setting $y=\chi_{I}(x)$. We note that the second term, involving $\mathcal{D}_{I}^{(0)}$ is non-negative. To lower bound the first term, observe that the learning problem $\mathcal{P}^{(0)}$, consisting of distributions $\mathcal{D}_{I}^{(0)}$, has a fixed-marginal, and is orthogonal and normalized. Thus from Theorem 3 it follows that

This completes the proof by noting that $\mathcal{L}_{\mathcal{D}_{I}}(0)=1/2$ for all $\mathcal{D}_{I}\in\mathcal{P}$. ∎

C.2.2 Proof from Section 5

Fix a probabilistic kernel $K$ corresponding to $p$-dimensional feature maps. For all $\mathcal{D}_{I}\in\mathcal{P}$, we have

Note that $\mathcal{L}_{\mathcal{D}_{I}^{(1)}}(h)~{}\geq~{}1/2$ for any $h$. Now, the learning problem $\mathcal{P}^{(0)}$, consisting of distributions $\mathcal{D}_{I}^{(0)}$, has a fixed-marginal, and is orthogonal and normalized. Thus we have from Theorem 3 that

This completes the proof by noting that $\mathcal{L}_{\mathcal{D}_{I}}(0)=1/2$ for all $\mathcal{D}_{I}\in\mathcal{P}$. ∎