Efficient kernel surrogates for neural network-based regression
Despite their immense promise in performing a variety of learning tasks, a
theoretical understanding of the limitations of Deep Neural Networks (DNNs) has
so far eluded practitioners. This is partly due to the inability to determine
the closed forms of the learned functions, making it harder to study their
generalization properties on unseen datasets. Recent work has shown that
randomly initialized DNNs in the infinite width limit converge to kernel
machines relying on a Neural Tangent Kernel (NTK) with known closed form. These
results suggest, and experimental evidence corroborates, that empirical kernel
machines can also act as surrogates for finite width DNNs. The high
computational cost of assembling the full NTK, however, makes this approach
infeasible in practice, motivating the need for low-cost approximations. In the
current work, we study the performance of the Conjugate Kernel (CK), an
efficient approximation to the NTK that has been observed to yield fairly
similar results. For the regression problem of smooth functions and logistic
regression classification, we show that the CK performance is only marginally
worse than that of the NTK and, in certain cases, is shown to be superior. In
particular, we establish bounds for the relative test losses, verify them with
numerical tests, and identify the regularity of the kernel as the key
determinant of performance. In addition to providing a theoretical grounding
for using CKs instead of NTKs, our framework suggests a recipe for improving
DNN accuracy inexpensively. We present a demonstration of this on the
foundation model GPT-2 by comparing its performance on a classification task
using a conventional approach and our prescription. We also show how our
approach can be used to improve physics-informed operator network training for
regression tasks as well as convolutional neural network training for vision
classification tasks.
Saad Qadeer, Andrew Engel, Amanda Howard, Adam Tsou, Max Vargas, Panos Stinis, Tony Chiang
# Efficient kernel surrogates for neural network-based regression

###### Abstract

Despite their immense promise in performing a variety of learning tasks, a theoretical understanding of the effectiveness and limitations of Deep Neural Networks (DNNs) has so far eluded practitioners. This is partly due to the inability to determine the closed forms of the learned functions, making it harder to assess their precise dependence on the training data and to study their generalization properties on unseen datasets. Recent work has shown that randomly initialized DNNs in the infinite width limit converge to kernel machines relying on a Neural Tangent Kernel (NTK) with known closed form. These results suggest, and experimental evidence corroborates, that empirical kernel machines can also act as surrogates for finite width DNNs. The high computational cost of assembling the full NTK, however, makes this approach infeasible in practice, motivating the need for low-cost approximations. In the current work, we study the performance of the Conjugate Kernel (CK), an efficient approximation to the NTK that has been observed to yield fairly similar results. For the regression problem of smooth functions and classification using logistic regression, we show that the CK performance is only marginally worse than that of the NTK and, in certain cases, is shown to be superior. In particular, we establish bounds for the relative test losses, verify them with numerical tests, and identify the regularity of the kernel as the key determinant of performance. In addition to providing a theoretical grounding for using CKs instead of NTKs, our framework provides insights into understanding the robustness of the various approximants and suggests a recipe for improving DNN accuracy inexpensively. We present a demonstration of this on the foundation model GPT-2 by comparing its performance on a classification task using a conventional approach and our prescription.

**Keywords:** Finite-width neural networks, Empirical kernel machines, Neural Tangent Kernel, Function regression, Logistic regression, Generalization errors, Foundation models

## 1 Introduction

Deep Neural Networks (DNNs) have shown immense promise in performing a variety of learning tasks including, among others, image classification [1, 2], natural language processing [3, 4, 5, 6], function approximation [7, 8], solving differential equations [9, 10, 11], etc. However, a theoretical understanding of their effectiveness and limitations has proven elusive, thereby hindering their universal acceptance in practical applications and limiting their usage in scientific computing. This is partly down to their somewhat unwieldy architectures and complex loss landscapes that do not permit precise closed-form characterizations of the optimally learned functions, thus making it harder to assess their precise dependence on the training data and to study their generalization properties on test sets.

Recent work has established that randomly initialized DNNs in the infinite width limit converge to kernel machines relying on a deterministic Neural Tangent Kernel (NTK) [12, 13]. The NTK for a DNN,
defined as the Gram matrix of the Jacobian of the DNN with respect to the network parameters, controls the evolution of the DNN training [14]. In the infinite width limit, the NTK can be shown to not deviate from its known closed form. As a consequence, the result of fully training an infinite width DNN can be _a priori_ identified as a kernel machine employing the known NTK. These insights also allow one to study the performance of the DNN architecture in the extremal over-parameterized limit and benefit from the double-descent phenomenon [15, 16, 17].

It should be emphasized that this limiting regime does not leverage the changes in the DNN during training and hence fails to make use of any features learned by the architecture. However, these results suggest the tantalizing possibility that empirical kernel machines could also act as surrogates for finite width DNNs. As shown elsewhere [18] as well as later in the article, under certain assumptions this claim is not only corroborated by strong evidence, both mathematical (equation (21) and Sections 5 and 4) and experimental (Section 6), but also considerably improved upon. This enables a precise determination of the superior learned functions and a thorough study of their performance on unseen data.

The high computational cost of assembling the complete NTK for DNNs employed in practical applications [19, 20], however, makes this approach infeasible, motivating the need for low cost approximations. In this article, we study the performance of the Conjugate Kernel (CK) [21], a "zeroth-order" approximation to the NTK, that has been observed to yield fairly similar results (see Section 6). For the problems of regression of smooth functions and logistic regression, we prove that the CK approximations are only marginally worse than the NTK approximations and, in some cases, are much superior. In particular, we establish bounds for the errors, verify them with numerical tests, and identify the regularity of the kernel as the key determinant of performance. In addition to providing a theoretical grounding for using CKs instead of NTKs, our framework provides insights into understanding the robustness of the various approximations and suggests a recipe for boosting DNN accuracy inexpensively. We duly present a demonstration of this on GPT-2 by comparing its performance on a classification task using a conventional approach and our prescription.

## 2 Preliminaries

In this section, we introduce our notation and the define the basic terms and tools. We denote by \(f_{\mathrm{NN}}:\mathbb{R}^{d_{0}}\rightarrow\mathbb{R}^{d_{L+1}}\) a fully connected network (FCN) with \(L\) hidden layers of the form

\[\mathbf{z}^{(l)} = \sigma\left(W^{(l)}\mathbf{z}^{(l-1)}+\mathbf{b}^{(l)}\right),\quad 1 \leq l\leq L,\] \[\mathbf{z}^{(L+1)} = W^{(L+1)}\mathbf{z}^{(L)}+\mathbf{b}^{(L+1)}. \tag{1}\]

Here, \(\sigma\) is the activation function, \(W^{(l)}\in\mathbb{R}^{d_{l}\times d_{l-1}}\) and \(\mathbf{b}^{(l)}\in\mathbb{R}^{d_{l}}\) are the trainable parameters, \(\mathbf{z}^{(0)}\in Z\) is the input, and \(\mathbf{z}^{(L+1)}\in\mathbb{R}^{d_{L+1}}\) is the output, i.e., \(f_{\mathrm{NN}}\left(\mathbf{z}^{(0)}\right)=\mathbf{z}^{(L+1)}\). We denote all the trainable parameters \(\{W^{(l)},\mathbf{b}^{(l)}\}_{1\leq l\leq L+1}\) by \(\theta\) and their number by \(|\theta|\) for brevity, and indicate the dependence of the neural network on them by writing \(f_{\mathrm{NN}}^{\theta}\). Since this is the only type of neural network (NN) we shall consider in this article, henceforth we refer to FCNs of this type as NNs.

Architectures of this type can be deployed for various tasks. For instance, let \(f:Z\rightarrow\mathbb{R}\) be a given function, where \(Z\) is a compact subset of \(\mathbb{R}^{d_{0}}\), with training input-output pairs \(\{(\mathbf{x}_{i},y_{i})\}_{0\leq i\leq N}\subset Z\times\mathbb{R}\) (so that \(y_{i}=f(\mathbf{x}_{i})\)). In order to solve the function regression problem, the parameters can be trained so as to minimize the weighted squared loss

\[L_{0,\mathrm{NN}}\left(\theta\right)=\sum_{i=0}^{N}w_{i}\left|y_{i}-f_{\mathrm{ NN}}^{\theta}\left(\mathbf{x}_{i}\right)\right|^{2}, \tag{2}\]

for some non-negative weights \(\{w_{i}\}_{0\leq i\leq N}\), and yield an approximation \(f_{\mathrm{NN}}^{\theta^{*}}\) to the target function. We further define the norms

\[\left\|g\right\|_{0}:=\left(\sum_{i=0}^{N}w_{i}\left|g(\mathbf{x}_{i})\right|^{2} \right)^{1/2},\qquad\left\|g\right\|_{1}:=\left(\sum_{i=0}^{M}v_{i}\left|g(\mathbf{ y}_{i})\right|^{2}\right)^{1/2} \tag{3}\]

for any \(g:Z\rightarrow\mathbb{R}^{d_{L+1}}\), where \(\{(\mathbf{y}_{i},v_{i})\}_{0\leq i\leq M}\) is a collection of test nodes and associated non-negative weights. The training and test errors are then \(\left\|f-f_{\mathrm{NN}}^{\theta^{*}}\right\|_{0}=\left[L(\theta^{*})\right]^{ 1/2}\) and \(\left\|f-f_{\mathrm{NN}}^{\theta^{*}}\right\|_{1}\) respectively.
Similarly, we can employ NNs for classifications tasks. Let \(\{(\mathbf{x}_{i},\chi_{i})\}_{0\leq i\leq N}\subset Z\times\{0,1\}\) be the training set, where \(\chi_{i}\) is the class label assigned to \(\mathbf{x}_{i}\). Set \(d_{L+1}=2\) (so that \(f_{\mathrm{NN}}^{\theta}:\mathbb{R}^{d_{0}}\rightarrow\mathbb{R}^{2}\)) and apply the softmax function to get

\[p_{\mathrm{NN}}^{\theta}(\mathbf{z})=\frac{\exp\left(f_{\mathrm{NN},1}^{\theta}( \mathbf{z})\right)}{\sum_{i=1}^{2}\exp\left(f_{\mathrm{NN},i}^{\theta}(\mathbf{z}) \right)}=\frac{1}{1+\exp\left[-\left(f_{\mathrm{NN},1}^{\theta}(\mathbf{z})-f_{ \mathrm{NN},2}^{\theta}(\mathbf{z})\right)\right]}. \tag{4}\]

This is the likelihood, according to this model, of \(\mathbf{z}\in Z\) belonging to the class labelled \(1\). The training requires the minimization of the logistic loss (i.e., the cross-entropy)

\[\ell_{0,\mathrm{NN}}(\theta)=-\sum_{i=0}^{N}\chi_{i}\ln\left(p_{\mathrm{NN}}^ {\theta}(\mathbf{x}_{i})\right)+(1-\chi_{i})\ln\left(1-p_{\mathrm{NN}}^{\theta}( \mathbf{x}_{i})\right), \tag{5}\]

with the corresponding test loss

\[\ell_{1,\mathrm{NN}}(\theta)=-\sum_{i=0}^{M}\mu_{i}\ln\left(p_{\mathrm{NN}}^ {\theta}(\mathbf{y}_{i})\right)+(1-\mu_{i})\ln\left(1-p_{\mathrm{NN}}^{\theta}(\bm {y}_{i})\right), \tag{6}\]

where \(\{\mu_{i}\}_{0\leq i\leq M}\subset\{0,1\}\) are the class labels of the test nodes.

These tasks can also be performed with the aid of kernel methods [22, 23]. Given a valid kernel function \(\ker:Z\times Z\rightarrow\mathbb{R}\), define the kernel matrix \(H_{\ker}=\left(\ker(\mathbf{x}_{i},\mathbf{x}_{j})\right)_{0\leq i,j\leq N}\), and the weighted kernel matrix \(\widehat{H}_{\ker}=W^{1/2}H_{\ker}W^{1/2}\), where \(W^{1/2}=\mathrm{diag}(\sqrt{w_{0}},\ldots,\sqrt{w_{N}})\). The corresponding kernel approximation for the function regression problem above seeks \(\mathbf{\delta}^{*,\ker}\in\mathbb{R}^{N+1}\) to minimize

\[L_{0,\ker}(\mathbf{\delta})=\sum_{i=0}^{N}w_{i}\left|y_{i}-\sum_{j=0}^{N}\mathbf{ \delta}_{j}\ker(\mathbf{x}_{j},\mathbf{x}_{i})\right|^{2}. \tag{7}\]

It possesses the closed form solution

\[f_{\ker}(\mathbf{z})=\mathbf{y}^{\top}W^{1/2}\left(\widehat{H}_{\ker}\right)^{\dagger }W^{1/2}\left(\ker(\mathbf{x}_{j},\mathbf{z})\right)_{0\leq j\leq N}, \tag{8}\]

where \(\mathbf{y}=\left(y_{i}\right)_{0\leq i\leq N}\) contains the training target values, with training and test losses \(\left\|f-f_{\ker}\right\|_{0}\) and \(\left\|f-f_{\ker}\right\|_{1}\) respectively.

The logistic regression problem can likewise be solved by finding an \(\mathbf{\alpha}^{*,\ker}\in\mathbb{R}^{N+1}\) that minimizes

\[\ell_{0,\ker}(\mathbf{\alpha})=\sum_{i=0}^{N}\chi_{i}\ln\left[1+\exp(-H_{\ker,(i,:)}\mathbf{\alpha})\right]+(1-\chi_{i})\ln\left[1+\exp(H_{\ker,(i,:)}\mathbf{\alpha} )\right], \tag{9}\]

thus yielding the likelihood

\[p_{\ker}(\mathbf{z})=\left[1+\exp\left(-\sum_{j=0}^{N}\ker(\mathbf{z},\mathbf{x}_{j})\bm {\alpha}_{j}^{*,\ker}\right)\right]^{-1}, \tag{10}\]

according to this classifier, of \(\mathbf{z}\in Z\) lying in class \(1\). The test loss \(\ell_{1,\ker}\) is defined similarly to (6) with (4) replaced by (10).

In case \(\ker\) is induced by a feature map \(\Phi_{\ker}:Z\rightarrow\mathbb{R}^{K}\), so that \(\ker(\mathbf{x},\mathbf{z})=\Phi_{\ker}(\mathbf{x})^{\top}\Phi_{\ker}(\mathbf{z})\), (8) can be understood as an orthogonal projection on \(\mathcal{S}_{\ker}=\mathrm{span}\left(\{\Phi_{\ker,k}\}_{k=1}^{K}\right)\) with respect to \(\langle\cdot,\cdot\rangle_{0}\), the inner product that induces \(\left\|\cdot\right\|_{0}\); a technique for obtaining an optimal representation of this projection is presented in Appendix B. Equivalently, we can interpret (8) as weighted linear regression on the data-points \(\left\{(\Phi_{\ker}(\mathbf{x}_{i}),y_{i})\right\}_{0\leq i\leq N}\), i.e., it implicitly finds \(\mathbf{\gamma}^{*,\ker}\in\mathbb{R}^{K}\) that minimizes the training loss

\[\widetilde{L}_{0,\ker}(\mathbf{\gamma})=\sum_{i=0}^{N}w_{i}\left|y_{i}-\mathbf{\gamma}^ {\top}\Phi_{\ker}(\mathbf{x}_{i})\right|^{2}, \tag{11}\]
so the approximation (8) can also be written as

\[f_{\rm ker}(\mathbf{z})=\left(\mathbf{\gamma}^{*,{\rm ker}}\right)^{\top}\Phi_{\rm ker}( \mathbf{z}). \tag{12}\]

This equivalence between the apparently more general form \(\mathbf{\gamma}^{\top}\Phi_{\rm ker}(\mathbf{z})\) in (12) and the kernel form \(\mathbf{\delta}^{\top}\left(\ker(\mathbf{x}_{j},\mathbf{z})\right)_{0\leq j\leq N}\) in (8) can be viewed as a consequence of the representer theorem [24] or, equivalently, as a corollary of the (easily proven) fact that

\[{\rm range}(A^{\top}A)={\rm range}(A^{\top}), \tag{13}\]

for any matrix \(A\): applied to the weighted feature map matrix \(\widehat{\Xi}_{\rm ker}=\left(\Phi_{{\rm ker},m}(\mathbf{x}_{i})w_{i}^{1/2}\right)_ {1\leq m\leq K,0\leq i\leq N}\in\mathbb{R}^{K\times(N+1)}\), we deduce that for an optimal \(\mathbf{\gamma}^{*,{\rm ker}}\), there exists some \(\mathbf{\delta}^{*,{\rm ker}}\in\mathbb{R}^{N+1}\) such that

\[\widehat{\Xi}_{\rm ker}^{\top}\mathbf{\gamma}^{*,{\rm ker}}=\widehat{\Xi}_{\rm ker }^{\top}\widehat{\Xi}_{\rm ker}\mathbf{\delta}^{*,{\rm ker}}=\widehat{H}_{\rm ker }\mathbf{\delta}^{*,{\rm ker}}, \tag{14}\]

since \(\widehat{H}_{\rm ker}=\widehat{\Xi}_{\rm ker}^{\top}\widehat{\Xi}_{\rm ker}\), and hence that we can restrict our search for \(\mathbf{\gamma}^{*,{\rm ker}}\) in \({\rm range}\left(\widehat{\Xi}_{\rm ker}\right)\). This implies that

\[\left\|f-f_{\rm ker}\right\|_{\nu}^{2}=\widetilde{L}_{\nu,{\rm ker}}(\mathbf{ \gamma}^{*,{\rm ker}}), \tag{15}\]

for \(\nu=0,1\), where the test loss \(\widetilde{L}_{1,{\rm ker}}\) is defined in the same manner as (11) with the test points and weights replacing the training ones.

Similarly, solving the kernel logistic problem can be interpreted as a linear classifier in the feature space, i.e., identifying the decision boundary

\[\left\{\mathbf{x}\in\mathbb{R}^{d_{0}}:\left(\mathbf{\beta}^{*,{\rm ker}}\right)^{\top }\Phi_{\rm ker}(\mathbf{x})=0\right\}, \tag{16}\]

which can be seen as a hyperplane in \(\mathbb{R}^{K}\), by finding \(\mathbf{\beta}^{*,{\rm ker}}\in\mathbb{R}^{K}\) that minimizes

\[\widetilde{\ell}_{0,{\rm ker}}(\mathbf{\beta})=\sum_{i=0}^{N}\chi_{i}\ln\left[1+ \exp\left(-\mathbf{\beta}^{\top}\Phi_{\rm ker}(\mathbf{x}_{i})\right)\right]+(1-\chi_ {i})\ln\left[1+\exp\left(\mathbf{\beta}^{\top}\Phi_{\rm ker}(\mathbf{x}_{i})\right) \right]. \tag{17}\]

Following an argument similar to that used above, we have

\[\ell_{\nu,{\rm ker}}(\mathbf{\alpha}^{*,{\rm ker}})=\widetilde{\ell}_{\nu,{\rm ker }}(\mathbf{\beta}^{*,{\rm ker}}), \tag{18}\]

for \(\nu=0,1\).

## 3 Problem formulation

Given a (fully or partially trained or untrained) neural network \(f_{\rm NN}:\mathbb{R}^{d_{0}}\to\mathbb{R}\), the corresponding Neural Tangent Kernel (NTK) is the kernel induced by the feature map

\[\Phi_{{\rm NTK},k}:=\frac{\partial f_{\rm NN}^{\theta}}{\partial\theta_{k}}, \quad 1\leq k\leq|\theta|, \tag{19}\]

i.e., the Jacobian of the neural network with respect to the trainable parameters [14]. In the infinite width limit, it has been established that, over the course of training a randomly initialized NN, the NTK possesses an unchanging closed form, and that the NN converges to the corresponding NTK machine [12]. This highlights the linear dependence of the NN on the underlying parameters, to wit,

\[f_{\rm NN}^{\theta}=f_{\rm NN}^{\theta_{0}}+(\theta-\theta_{0})^{\top}\left. \left(\frac{\partial f_{\rm NN}^{\theta}}{\partial\theta_{k}}\right)\right|_ {\theta=\theta_{0}}. \tag{20}\]
In fact, since \(f_{\rm NN}^{\theta_{0}}\) is a linear combination of the neurons in the last hidden layer (from (1)) and which correspond the Jacobian entries corresponding to the last layer of parameters, it can be subsumed in the second term in (20) to yield

\[f_{\rm NN}^{\theta}=\mathbf{\gamma}^{\top}\Phi_{\rm NTK} \tag{21}\]

for some \(\mathbf{\gamma}\in\mathbb{R}^{|\theta|}\). Since this is precisely the form of an NTK approximation (from the equivalence of (8) and (12)), we deduce that, in the infinite width limit, a fully trained NN is identical to an optimal regressor employing the NTK.

However, using this insight to obtain performance guarantees and assess limitations of finite width network runs into two problems. First, the assumption of linear dependence on parameters in (20) does not hold [25], so the optimal NTK machine can only be viewed as the best approximator in the tangent space of the NN at \(\theta_{0}\), and not on the manifold of all NNs. Secondly, computing the NTK in practice is a computationally daunting task [19, 20]. In the infinite width regime and under random initialization, a closed form for the NTK can be calculated. However, empirical kernels do not possess such characterizations in general, necessitating the use of low-cost approximations.

The Conjugate Kernel (CK) is defined as the kernel induced by the Jacobian only with respect to the parameters \(\{W^{(L+1)},\mathbf{b}^{(L+1)}\}\) in the last layer [21]. Consequently, its feature map can be seen as a truncation of the full Jacobian employed by the NTK. Observe that we have set \(d_{L+1}=1\) so \(W^{(L+1)}\in\mathbb{R}^{d_{L}}\) and \(\mathbf{b}^{L+1}\in\mathbb{R}\), and hence

\[\Phi_{\rm CK,k}:=\begin{cases}\frac{\partial f_{\rm NN}^{\theta_{ \rm NN}^{\theta}}}{\partial W_{k}^{(L+1)}},&\text{if }1\leq k\leq d_{L},\\ \frac{\partial f_{\rm NN}^{\theta}}{\partial\mathbf{b}^{(L+1)}},&\text{if }k =d_{L}+1.\end{cases} \tag{22}\]

A moment's thought then reveals that

\[\mathrm{CK}(\mathbf{z},\widetilde{\mathbf{z}}):=\Phi_{\rm CK}(\mathbf{z})^{ \top}\Phi_{\rm CK}(\widetilde{\mathbf{z}})=1+\mathbf{z}^{(L)}\cdot\widetilde{\mathbf{z}}^ {(L)}. \tag{23}\]

**Remark 3.1**: _For an NN trained for the binary classification problem described in the previous section, we have \(d_{L+1}=2\). In this setting, we define the NTK and CK for \(f_{\text{diff}}:=f_{\text{NN},1}^{\theta}-f_{\text{NN},2}^{\theta}\) since, as shown in (4), this difference dictates the output of the logistic predictor._

Denoting by \(\mathrm{E}\) the contribution towards the NTK from every layer but the last allows us to write

\[\mathrm{NTK}(\mathbf{z},\widetilde{\mathbf{z}})=\mathrm{CK}(\mathbf{z}, \widetilde{\mathbf{z}})+\mathrm{E}(\mathbf{z},\widetilde{\mathbf{z}}). \tag{24}\]

The CK can therefore be viewed as a "zeroth-order" approximation to the NTK. All these components are valid kernels that can be calculated from a given NN. However, the cost of computing the CK at a pair of points is the same as that of evaluating the NN at those points since, according to (23), it makes use of the neuron values at the last hidden layer. Moreover, numerical evidence suggests that, while the NTK expectedly outperforms the CK on test sets, the improvement is only marginal and is dwarfed by the superiority both kernels exhibit over the NN architecture from which they are derived (see Section 6). In other words, the CK appears to yield substantive gains in accuracy over a given finite width neural network while being easier to calculate than the NTK and much cheaper to train further than the NN. This raises the intriguing possibility that the CK can serve as a low-cost proxy for the NTK, i.e., lead to a comparable boost in performance over the NN, while being significantly less expensive to assemble than the NTK and considerably easier to train than the NN. Since training the CK is the same as further training the last parameter layer of the NN, our work provides a recipe for boosting NN accuracy and also sheds light on the robustness (or lack thereof) conferred on the approximations by the choice of the activation function.

In the following sections, we provide a mathematical treatment of this phenomenon for two types of problems: regression of smooth functions and classification using logistic regression. For ease of exposition and analysis, we concentrate on these problems in low dimensions with structured training and test nodes. The analyses of these problems are presented in Sections 4 and 5, and are complemented by numerical experiments presented in Section 6.
Function regression

### Preliminaries

We consider the approximation problem for a smooth function \(f:[a,b]\rightarrow\mathbb{R}\) whose values are known at the equispaced training nodes \(x_{j}=a+j\Delta x\) for \(0\leq j\leq N\), where \(\Delta x=(b-a)/N\). The performance is assessed on the equispaced test nodes \(y_{j}=a+j\Delta y\) for \(0\leq j\leq M\), where \(\Delta y=(b-a)/M\); we take \(M=\tau N\), for some integer \(\tau>1\), and set

\[w_{i}=\begin{cases}\Delta x,&1\leq i\leq N-1\\ \Delta x/2,&i=0,N\end{cases},\qquad v_{i}=\begin{cases}\Delta y,&1\leq i\leq M -1\\ \Delta y/2,&i=0,M\end{cases}, \tag{25}\]

so for any \(g:[a,b]\rightarrow\mathbb{R}\), we have

\[\left\|g\right\|_{0}=\left(\frac{\Delta x}{2}\sum_{j=0}^{N-1} \left(g(x_{j})^{2}+g(x_{j+1})^{2}\right)\right)^{1/2},\quad\left\|g\right\|_{1 }=\left(\frac{\Delta y}{2}\sum_{j=0}^{M-1}\left(g(y_{j})^{2}+g(y_{j+1})^{2} \right)\right)^{1/2}. \tag{26}\]

These can be recognized as the trapezoidal rule approximations to the \(L^{2}\) norm on \([a,b]\); recall that this approximation is second-order accurate with respect to the step-size in general and spectrally accurate for periodic functions. Moreover, these choices serve to considerably simplify the analysis: for instance, since \(y_{\tau j}=x_{j}\) for \(0\leq j\leq N\), we have, for any function \(g\),

\[\left\|g\right\|_{0}^{2}=\frac{\Delta x}{2}\sum_{j=0}^{N-1} \left(g(x_{j})^{2}+g(x_{j+1})^{2}\right) \leq \frac{\Delta x}{2}\sum_{j=0}^{N-1}\sum_{i=0}^{\tau}g(y_{\tau j+i} )^{2}=\left(\frac{M}{N}\right)\left\|g\right\|_{1}^{2}\]

so that

\[\left\|g\right\|_{0} \leq \tau^{1/2}\left\|g\right\|_{1}. \tag{27}\]

This straightforward result allows us to describe the size of the function on the lower-resolution training grid in terms of the higher-resolution test grid. The next two results enable us to move in the opposite direction, i.e., bounding the norm on the finer grid by the norm on the coarser grid. This naturally requires some assumptions about the behaviour of the function away from the training nodes; the following lemmas consider two different settings.

### Two Lemmas

**Lemma 4.1**: _Suppose that \(g\) is monotonic on every sub-interval \([x_{i},x_{i+1}]\). Then,_

\[\left\|g\right\|_{1}\leq\sqrt{2}\left\|g\right\|_{0}. \tag{28}\]

**Proof:** The monotonicity of \(g\) on every sub-interval implies

\[\left|g(y_{\tau i+k})\right|\leq\max\left\{\left|g(x_{i})\right|,\left|g(x_{i+1})\right|\right\},\quad 1\leq k\leq\tau-1,\ 0\leq i\leq N-1, \tag{29}\]

with the result

\[\left\|g\right\|_{1}^{2} = \frac{\Delta y}{2}\sum_{j=0}^{M-1}g(y_{j})^{2}+g(y_{j+1})^{2}\] \[= \frac{\Delta y}{2}\sum_{j=0}^{N-1}\left[g(x_{j})^{2}+g(x_{j+1})^{ 2}\right]+\frac{\Delta y}{2}\sum_{i=0}^{N-1}\sum_{k=1}^{\tau-1}g(y_{\tau i+k })^{2}\] \[\leq \frac{\Delta y}{2}\sum_{j=0}^{N-1}\left[g(x_{j})^{2}+g(x_{j+1})^ {2}\right]+(\tau-1)\frac{\Delta y}{2}\sum_{i=0}^{N-1}\max\left\{g(x_{i})^{2},g(x_{i+1})^{2}\right\}\] \[\leq \frac{1}{\tau}\left\|g\right\|_{0}^{2}+\frac{2(\tau-1)}{\tau} \left\|g\right\|_{0}^{2}\] \[\leq 2\left\|g\right\|_{0}^{2},\]

and hence \(\left\|g\right\|_{1}\leq\sqrt{2}\left\|g\right\|_{0}\).
Combining this with (27), we have the norm equivalence

\[\tau^{-1/2}\left\|g\right\|_{0}\leq\left\|g\right\|_{1}\leq\sqrt{2}\left\|g \right\|_{0}. \tag{30}\]

**Lemma 4.2**: _Suppose that \(g\) is Lipschitz on \([a,b]\) with Lipschitz constant \(L_{g}\). Then,_

\[\left\|g\right\|_{1}^{2}\leq 4\left(\left\|g\right\|_{0}^{2}+\frac{2(b-a)^{2}L_{g }^{2}}{N^{2}}\right). \tag{31}\]

**Proof:** The Lipschitz property implies that

\[\left|g(y_{\tau j+k})\right|\leq\max\left\{\left|g(x_{j})\right|+kL_{g}\Delta y,\left|g(x_{j+1})\right|+(\tau-k)L_{g}\Delta y\right\}\]

for \(0\leq k\leq\tau\). It follows that

\[g(y_{\tau j+k})^{2} \leq 2\left[g(x_{j})^{2}+k^{2}L_{g}^{2}(\Delta y)^{2}+g(x_{j+1})^{2} +(\tau-k)^{2}L_{g}^{2}(\Delta y)^{2}\right]\] \[\leq 2\left[g(x_{j})^{2}+g(x_{j+1})^{2}+2L_{g}^{2}(\Delta x)^{2} \right],\]

so for \(0\leq l\leq\tau-1\), we have

\[g(y_{\tau j+l})^{2}+g(y_{\tau j+l+1})^{2}\leq 4\left[g(x_{j})^{2}+g(x_{j+1})^{2 }+2L_{g}^{2}(\Delta x)^{2}\right].\]

As a result,

\[\sum_{l=0}^{\tau-1}g(y_{\tau j+l})^{2}+g(y_{\tau j+l+1})^{2} \leq 4\tau\left[g(x_{j})^{2}+g(x_{j+1})^{2}+2L_{g}^{2}(\Delta x)^{2}\right]\] \[\Rightarrow\sum_{j=0}^{N-1}\sum_{l=0}^{\tau-1}g(y_{\tau j+l})^{2} +g(y_{\tau j+l+1})^{2} \leq 4\tau\sum_{j=0}^{N-1}\left[g(x_{j})^{2}+g(x_{j+1})^{2}+2L_{g}^{2 }(\Delta x)^{2}\right],\]

and hence

\[M\left\|g\right\|_{1}^{2}\leq 4N\tau\left[\left\|g\right\|_{0}^{2}+2L_{g}^{2}( \Delta x)^{2}\right]\Rightarrow\left\|g\right\|_{1}^{2}\leq 4\left(\left\|g \right\|_{0}^{2}+\frac{2(b-a)^{2}L_{g}^{2}}{N^{2}}\right).\]

### Approximation properties

For a smooth target function \(f:[a,b]\rightarrow\mathbb{R}\), let \(f_{\text{CK}}\) and \(f_{\text{NTK}}\) be the CK and NTK approximations to \(f\) with respect to the training nodes. Recall that (8) can be viewed as an orthogonal projection \(\mathcal{P}_{\text{ker}}\) on \(\mathcal{S}_{\text{ker}}\), the span of the feature map components corresponding to the kernel. Since \(\mathcal{S}_{\text{CK}}\subset\mathcal{S}_{\text{NTK}}\), we have

\[\left\|f-f_{\text{NTK}}\right\|_{0}\leq\left\|f-f_{\text{CK}}\right\|_{0}. \tag{32}\]

Next, we establish that the error of the CK approximation may also be controlled by that of the NTK approximation for most target functions. More precisely, we define, for any \(\beta\leq 1\)

\[\mathcal{F}_{\beta}=\left\{f:[a,b]\rightarrow\mathbb{R}\text{ is smooth with }\left\|\mathcal{P}_{\text{NTK}}f\right\|_{0}\leq\beta\left\|f\right\|_{0}\right\}. \tag{33}\]

We note that since \(\mathcal{P}_{\text{NTK}}\) is an orthogonal projection, its norm is one and so \(\mathcal{F}_{1}\) contains all smooth real-valued functions. However, most functions of interest would not lie in \(\mathcal{S}_{\text{NTK}}\) and hence would belong to some \(\mathcal{F}_{\beta}\) with \(\beta<1\).

**Lemma 4.3**: _Let \(f\in\mathcal{F}_{\beta}\). Then,_

\[\left\|\mathcal{P}_{\text{NTK}}(f-f_{\text{CK}})\right\|_{0}\leq\beta\left\|f -f_{\text{CK}}\right\|_{0}. \tag{34}\]
**Proof:** We have

\[\left\|f\right\|_{0}^{2}=\left\|\mathcal{P}_{\rm NTK}f\right\|_{0}^{2}+\left\|(I- \mathcal{P}_{\rm NTK})f\right\|_{0}^{2}=\left\|f_{\rm NTK}\right\|_{0}^{2}+ \left\|f-f_{\rm NTK}\right\|_{0}^{2} \tag{35}\]

and

\[\left\|f-f_{\rm CK}\right\|_{0}^{2} = \left\|\mathcal{P}_{\rm NTK}(f-f_{\rm CK})\right\|_{0}^{2}+\left\| (I-\mathcal{P}_{\rm NTK})(f-f_{\rm CK})\right\|_{0}^{2} \tag{36}\] \[= \left\|f_{\rm NTK}-f_{\rm CK}\right\|_{0}^{2}+\left\|f-f_{\rm NTK} \right\|_{0}^{2}\]

since \((I-\mathcal{P}_{\rm NTK})f_{\rm CK}=0\) due to \(\mathcal{P}_{\rm NTK}\mathcal{P}_{\rm CK}=\mathcal{P}_{\rm CK}\). Combining (35) and (36) yields

\[\frac{\left\|f-f_{\rm CK}\right\|_{0}^{2}}{\left\|f\right\|_{0}^ {2}} = \frac{\left\|f_{\rm NTK}-f_{\rm CK}\right\|_{0}^{2}+\left\|f-f_{ \rm NTK}\right\|_{0}^{2}}{\left\|f_{\rm NTK}\right\|_{0}^{2}+\left\|f-f_{\rm NTK }\right\|_{0}^{2}}\] \[\geq \frac{\left\|f_{\rm NTK}-f_{\rm CK}\right\|_{0}^{2}}{\left\|f_{ \rm NTK}\right\|_{0}^{2}}\]

where we used the elementary inequality

\[\frac{\epsilon+\zeta}{\rho+\zeta}\geq\frac{\epsilon}{\rho}, \tag{37}\]

for \(0<\epsilon\leq\rho\) and \(\zeta\geq 0\). As a result,

\[\left\|f_{\rm NTK}-f_{\rm CK}\right\|_{0}^{2} \leq \left(\frac{\left\|f_{\rm NTK}\right\|_{0}^{2}}{\left\|f\right\|_ {0}^{2}}\right)\left\|f-f_{\rm CK}\right\|_{0}^{2}\] \[\leq \beta^{2}\left\|f-f_{\rm CK}\right\|_{0}^{2}\] \[\Leftrightarrow\left\|\mathcal{P}_{\rm NTK}(f-f_{\rm CK})\right\|_ {0} \leq \beta\left\|f-f_{\rm CK}\right\|_{0}\qquad(\because\mathcal{P}_{ \rm NTK}\mathcal{P}_{\rm CK}=\mathcal{P}_{\rm CK}).\]

**Lemma 4.4**: _For any function \(f\in\mathcal{F}_{\beta}\) with \(\beta<1\),_

\[\left\|f-f_{\rm CK}\right\|_{0} \leq \frac{1}{1-\beta}\left\|f-f_{\rm NTK}\right\|_{0}.\]

**Proof:** We have

\[\left\|f-f_{\rm CK}\right\|_{0} \leq \left\|f-f_{\rm NTK}\right\|_{0}+\left\|f_{\rm NTK}-f_{\rm CK} \right\|_{0} \tag{38}\] \[= \left\|f-f_{\rm NTK}\right\|_{0}+\left\|\mathcal{P}_{\rm NTK}(f-f _{\rm CK})\right\|_{0}\qquad(\because\mathcal{P}_{\rm NTK}\mathcal{P}_{\rm CK }=\mathcal{P}_{\rm CK})\] \[\leq \left\|f-f_{\rm NTK}\right\|_{0}+\beta\left\|f-f_{\rm CK}\right\|_ {0}\qquad(\because\text{Lemma \ref{lem:20}})\] \[\Rightarrow\left\|f-f_{\rm CK}\right\|_{0} \leq \frac{1}{1-\beta}\left\|f-f_{\rm NTK}\right\|_{0}.\]

For such functions, we have the following approximation results.

**Theorem 4.1**: _Let \(f\in\mathcal{F}_{\beta}\) for some \(\beta<1\) and suppose that both \((f-f_{\rm CK})\) and \((f-f_{\rm NTK})\) are monotonic on every sub-interval \([x_{i},x_{i+1}]\) for \(0\leq i\leq N-1\). Then, there exist constants \(C_{1},C_{2}\geq 1\) such that_

\[C_{1}^{-1}\left\|f-f_{\rm NTK}\right\|_{1}\leq\left\|f-f_{\rm CK}\right\|_{1} \leq C_{2}\left\|f-f_{\rm NTK}\right\|_{1}. \tag{39}\]

**Proof:** We have

\[\left\|f-f_{\rm NTK}\right\|_{1} \leq \sqrt{2}\left\|f-f_{\rm NTK}\right\|_{0}\qquad(\because\text{Lemma \ref{lem:20}}) \tag{40}\] \[\leq \sqrt{2}\left\|f-f_{\rm CK}\right\|_{0}\qquad(\because(\ref{lem:20} ))\] \[\leq \sqrt{2\tau}\left\|f-f_{\rm CK}\right\|_{1}\qquad(\because(\ref{ lem:20})).\]
Similarly,

\[\left\|f-f_{\text{CK}}\right\|_{1} \leq \sqrt{2}\left\|f-f_{\text{CK}}\right\|_{0}\qquad(\because\text{Lemma \ref{lem:CK})} \tag{41}\] \[\leq \frac{\sqrt{2}}{1-\beta}\left\|f-f_{\text{NTK}}\right\|_{0}\qquad( \because\text{Lemma \ref{lem:CK})}\] \[\leq \frac{\sqrt{2\tau}}{1-\beta}\left\|f-f_{\text{NTK}}\right\|_{1} \qquad(\because(27)).\]

Setting \(C_{1}=\sqrt{2\tau}\) and \(C_{2}=\frac{\sqrt{2\tau}}{1-\beta}\) and combining (40) and (41) yields the desired (39).

Note that Theorem 4.1 requires the residuals to be monotonic which may be too stringent. The following results rests on a more relaxed assumption.

**Theorem 4.2**: _Let \(f\in\mathcal{F}_{\beta}\) for some \(\beta<1\) and suppose that both \((f-f_{\text{CK}})\) and \((f-f_{\text{NTK}})\) are Lipschitz, with Lipschitz constants \(L_{\text{CK}}\) and \(L_{\text{NTK}}\). Then, there exist constants \(D_{1},D_{2}\geq 1\) such that_

\[\left\|f-f_{\text{NTK}}\right\|_{1}^{2}\leq D_{1}\left\|f-f_{\text{CK}} \right\|_{1}^{2}+\frac{8(b-a)^{2}L_{\text{NTK}}^{2}}{N^{2}} \tag{42}\]

_and_

\[\left\|f-f_{\text{CK}}\right\|_{1}^{2}\leq D_{2}\left\|f-f_{\text{NTK}} \right\|_{1}^{2}+\frac{8(b-a)^{2}L_{\text{CK}}^{2}}{N^{2}}. \tag{43}\]

**Proof:** We have

\[\left\|f-f_{\text{NTK}}\right\|_{1}^{2} \leq 4\left(\left\|f-f_{\text{NTK}}\right\|_{0}^{2}+\frac{2(b-a)^{2} L_{\text{NTK}}^{2}}{N^{2}}\right)\qquad(\because\text{Lemma \ref{lem:CK})} \tag{44}\] \[\leq 4\left(\left\|f-f_{\text{CK}}\right\|_{0}^{2}+\frac{2(b-a)^{2} L_{\text{NTK}}^{2}}{N^{2}}\right)\qquad(\because(32))\] \[\leq 4\left(\tau\left\|f-f_{\text{CK}}\right\|_{1}^{2}+\frac{2(b-a)^{ 2}L_{\text{NTK}}^{2}}{N^{2}}\right)\qquad(\because(27)).\]

In addition,

\[\left\|f-f_{\text{CK}}\right\|_{1}^{2} \leq 4\left(\left\|f-f_{\text{CK}}\right\|_{0}^{2}+\frac{2(b-a)^{2} L_{\text{CK}}^{2}}{N^{2}}\right)\qquad(\because\text{Lemma \ref{lem:CK})} \tag{45}\] \[\leq 4\left(\frac{1}{(1-\beta)^{2}}\left\|f-f_{\text{NTK}}\right\|_{0} ^{2}+\frac{2(b-a)^{2}L_{\text{CK}}^{2}}{N^{2}}\right)\qquad(\because\text{Lemma \ref{lem:CK})}\] \[\leq 4\left(\frac{\tau}{(1-\beta)^{2}}\left\|f-f_{\text{NTK}}\right\|_ {1}^{2}+\frac{2(b-a)^{2}L_{\text{CK}}^{2}}{N^{2}}\right)\qquad(\because(27)).\]

Setting \(D_{1}=4\tau\) and \(D_{2}=\frac{4\tau}{(1-\beta)^{2}}\) yields the desired (42) and (43).

## 5 Logistic regression

### Preliminaries

In this section, we compare the performance of the two kernels under consideration for logistic regression. For brevity of exposition, we consider the problem in two dimensions. Let \(\{\mathbf{x}_{i,j}\}_{0\leq i\leq N_{1},0\leq j\leq N_{2}}\subset Z=[a_{1},b_{1}] \times[a_{2},b_{2}]\) be the training points given by

\[\mathbf{x}_{i,j}=(a_{1}+i\Delta x_{1},a_{2}+j\Delta x_{2}),\]
where \(\Delta x_{1}=(b_{1}-a_{1})/N_{1}\) and \(\Delta x_{2}=(b_{2}-a_{2})/N_{2}\). We further set \(h=\left(\Delta x_{1}^{2}+\Delta x_{2}^{2}\right)^{1/2}\). The test nodes \(\{\mathbf{y}_{i,j}\}_{0\leq i\leq M_{1},0\leq j\leq M_{2}}\) are similarly chosen as

\[\mathbf{y}_{i,j}=(a_{1}+i\Delta y_{1},a_{2}+j\Delta y_{2}),\]

where \(\Delta y_{1}=(b_{1}-a_{1})/M_{1}\) and \(\Delta y_{2}=(b_{2}-a_{2})/M_{2}\). We also assume that \(\tau_{k}=M_{k}/N_{k}\) is an integer greater than one for \(k=1,2\).

Following Section 2, each training and test point is assigned a class labelled \(0\) or \(1\), and denoted respectively by \(\chi_{ij}\) for every \(0\leq i\leq N_{1},0\leq j\leq N_{2}\) and \(\mu_{ij}\) for each \(0\leq i\leq M_{1},0\leq j\leq M_{2}\). Given a kernel function \(\ker:Z\times Z\to\mathbb{R}\), we can define the kernel matrix

\[H_{\ker}=(\ker(\mathbf{x}_{i,j},\mathbf{x}_{k,l}))_{0\leq i,k\leq N_{1},0\leq j,l\leq N _{2}}\in\mathbb{R}^{N_{1}N_{2}\times N_{1}N_{2}},\]

with the indices arranged suitably.

We note first that the NTK must necessarily outperform the CK on the training points, i.e.,

\[\ell_{0,\mathrm{NTK}}\left(\mathbf{\alpha}^{\star,\mathrm{NTK}}\right)\leq\ell_{ 0,\mathrm{CK}}\left(\mathbf{\alpha}^{\star,\mathrm{CK}}\right). \tag{46}\]

This is most easily seen by rewriting (46) in terms of the feature maps: since

\[\ell_{0,\mathrm{CK}}\left(\mathbf{\alpha}^{\star,\mathrm{CK}}\right)=\widetilde{ \ell}_{0,\mathrm{CK}}\left(\mathbf{\beta}^{\star,\mathrm{CK}}\right),\]

from (18), and \(\Phi_{\mathrm{NTK}}=\left(\Phi_{\mathrm{CK}}\ \ \Phi_{\mathrm{E}}\right)^{\top}\), setting \(\mathbf{\gamma}=\left(\mathbf{\beta}^{\star,\mathrm{CK}}\ \ \mathbf{0}\right)^{\top}\in \mathbb{R}^{|\theta|}\) yields

\[\ell_{0,\mathrm{CK}}\left(\mathbf{\alpha}^{\star,\mathrm{CK}}\right)=\widetilde{ \ell}_{0,\mathrm{CK}}\left(\mathbf{\beta}^{\star,\mathrm{CK}}\right)=\widetilde{ \ell}_{0,\mathrm{NTK}}\left(\mathbf{\gamma}\right)\geq\widetilde{\ell}_{0,\mathrm{ NTK}}\left(\mathbf{\beta}^{\star,\mathrm{NTK}}\right)=\ell_{0,\mathrm{NTK}}\left(\mathbf{ \alpha}^{\star,\mathrm{NTK}}\right). \tag{47}\]

In order to show that an equivalence result in the manner of Theorem 4.1 holds for the test errors, we follow a similar strategy to that for the function regression problem in Section 4:

1. identify two cases that permit a transfer of information from training to test nodes;
2. extend (46) to an equivalence result on the training nodes for the two kernels

These ingredients can then be combined to yield the desired conclusion.

### Another pair of lemmas

We begin by noting that

\[\ell_{0,\ker}(\mathbf{\alpha}^{\star,\ker})\leq\ell_{1,\ker}(\mathbf{\alpha}^{\star, \ker}) \tag{48}\]

simply by virtue of the fact that every training point is also a test point. To complete (a), we need to bound the error on the finer grid by that on the coarser grid. The quantity of interest is the linear combination of the feature map components

\[\psi_{\ker}(\mathbf{z})=\sum_{m=1}^{|\theta|}\Phi_{\ker,m}(\mathbf{z})\mathbf{\beta}_{m}^{ \star,\ker} \tag{49}\]

as it determines the size of the gap between \(\mathbf{z}\in Z\) and the separating hyperplane in the feature space. However, we also need to keep track of the class label that should be associated with \(\mathbf{z}\) as that determines how it shows up in the loss function (17). Let \(\eta:Z\to\{0,1\}\) be the true class label for every point (so that, e.g., \(\chi_{ij}=\eta(\mathbf{x}_{i,j})\) and \(\mu_{ij}=\eta(\mathbf{y}_{i,j})\)), and set

\[\widehat{\psi}_{\ker}(\mathbf{z})=\left(1-2\eta(\mathbf{z})\right)\psi_{\ker}(\mathbf{z}). \tag{50}\]
Using this function, we can write the minimized training and test losses as simply

\[\widetilde{\ell}_{0,\ker}=\sum_{i=0}^{N_{1}}\sum_{j=0}^{N_{2}}\ln \left[1+\exp\left(\widehat{\psi}_{\ker}(\mathbf{x}_{i,j})\right)\right] \tag{51}\]

and

\[\widetilde{\ell}_{1,\ker}=\sum_{i=0}^{M_{1}}\sum_{j=0}^{M_{2}}\ln \left[1+\exp\left(\widehat{\psi}_{\ker}(\mathbf{y}_{i,j})\right)\right], \tag{52}\]

where we have suppressed the dependence on \(\mathbf{\beta}^{*,\ker}\) for clarity of exposition. For any \(0\leq i\leq N_{1}-1\) and \(0\leq j\leq N_{2}-1\), we also define

\[\Lambda_{ij}=\{\mathbf{x}_{i,j},\mathbf{x}_{i+1,j},\mathbf{x}_{i,j+1},\mathbf{x}_ {i+1,j+1}\}\]

to make it easier to navigate the training grid.

The two regimes that interest us are a corner maximum condition and Lipschitz continuity. We make these precise in the following lemmas.

**Lemma 5.1**: _Suppose that on every rectangle with corners \(\Lambda_{ij}\), the function \(\widehat{\psi}_{\ker}\) achieves its maximum value on \(\Lambda_{ij}\). Then,_

\[\widetilde{\ell}_{1,\ker}\leq\tau_{1}\tau_{2}\widetilde{\ell}_{ 0,\ker}, \tag{53}\]

**Proof:** Every test point \(\mathbf{y}_{k,l}\) belongs to some rectangle with corners \(\Lambda_{k^{\prime}l^{\prime}}\). The contribution from this point to the test loss is then dominated by the contributions from the corner points, i.e.,

\[\ln\left[1+\exp\left(\widehat{\psi}_{\ker}(\mathbf{y}_{k,l})\right)\right] \leq \max_{k^{\prime}\leq i\leq k^{\prime}+1,l^{\prime}\leq j\leq l^{ \prime}+1}\ln\left[1+\exp\left(\widehat{\psi}_{\ker}(\mathbf{x}_{i,j})\right) \right], \tag{54}\]

with the result that

\[\sum_{k=0}^{M_{1}}\sum_{l=0}^{M_{2}}\ln\left[1+\exp\left( \widehat{\psi}_{\ker}(\mathbf{y}_{k,l})\right)\right] \leq \left(\frac{M_{1}}{N_{1}}\right)\left(\frac{M_{2}}{N_{2}}\right) \sum_{i=0}^{N_{1}}\sum_{j=0}^{N_{2}}\ln\left[1+\exp\left(\widehat{\psi}_{\ker }(\mathbf{x}_{i,j})\right)\right],\]

and hence

\[\widetilde{\ell}_{1,\ker} \leq \tau_{1}\tau_{2}\widetilde{\ell}_{0,\ker}.\]

We say that the labelling function \(\eta\) possesses the _matching property_ with respect to the given training and test nodes if every test point \(\mathbf{y}_{k,l}\) is contained in an enclosing rectangle with corners \(\Lambda_{k^{\prime}l^{\prime}}\) such that \(\eta\) agrees with \(\eta(\mathbf{y}_{k,l})\) on at least one corner point. In other words, we do not have the matching property if and only if there exists some test point \(\mathbf{y}_{k,l}\) such that, for any rectangle with corners \(\Lambda_{k^{\prime}l^{\prime}}\) that may enclose it, we have \(\eta(\mathbf{y}_{k,l})\notin\eta\left(\Lambda_{k^{\prime}l^{\prime}}\right)\).

**Lemma 5.2**: _Suppose that \(\psi_{ker}\) is Lipschitz continuous on \(D\), with Lipschitz constant \(L_{ker}\), and \(\eta\) possesses the matching property. Then,_

\[\widetilde{\ell}_{1,\ker} \leq \exp(hL_{ker})\tau_{1}\tau_{2}\widetilde{\ell}_{0,\ker}. \tag{55}\]

**Proof:** For any test point \(\mathbf{y}_{k,l}\), let \(\Lambda_{k^{\prime}l^{\prime}}\) contain the corners of the enclosing rectangle that respect the matching property. Without loss of generality, we can assume that \(\eta(\mathbf{y}_{k,l})=\eta(\mathbf{x}_{k^{\prime},l^{\prime}})=0\). We have

\[\psi_{\ker}\left(\mathbf{y}_{k,l}\right)\leq\psi_{\ker}\left(\mathbf{x}_ {k^{\prime},l^{\prime}}\right)+hL_{\ker},\]
and hence

\[\ln\left[1+\exp\left(\psi_{\rm ker}(\mathbf{y}_{k,l}) \right)\right] \leq \ln\left[1+\exp\left(\psi_{\rm ker}\left(\mathbf{x}_{k^{ \prime},l^{\prime}}\right)\right)\exp\left(hL_{\rm ker}\right)\right]\] \[\leq \exp\left(hL_{\rm ker}\right)\ln\left[1+\exp\left(\psi_{\rm ker} \left(\mathbf{x}_{k^{\prime},l^{\prime}}\right)\right)\right],\]

where we used the fact that

\[\ln\left(1+\rho x\right)\leq\rho\ln(1+x) \tag{56}\]

whenever \(\rho\geq 1\) and \(x\geq 0\). In the case \(\eta(\mathbf{y}_{k,l})=\eta(\mathbf{x}_{k^{\prime},l^{ \prime}})=1\), we similarly obtain

\[\ln\left[1+\exp\left(-\psi_{\rm ker}(\mathbf{y}_{k,l}) \right)\right] \leq \exp\left(hL_{\rm ker}\right)\ln\left[1+\exp\left(-\psi_{\rm ker} \left(\mathbf{x}_{k^{\prime},l^{\prime}}\right)\right)\right],\]

and, consequently,

\[\sum_{k=0}^{M_{1}}\sum_{l=0}^{M_{2}}\ln\left[1+\exp\left(\widehat {\psi}_{\rm ker}(\mathbf{y}_{k,l})\right)\right] \leq \exp\left(hL_{\rm ker}\right)\left(\frac{M_{1}}{N_{1}}\right) \left(\frac{M_{2}}{N_{2}}\right)\sum_{i=0}^{N_{1}}\sum_{j=0}^{N_{2}}\ln\left[1 +\exp\left(\widehat{\psi}_{\rm ker}(\mathbf{x}_{i,j})\right)\right]\]

so that

\[\widetilde{\ell}_{1,{\rm ker}} \leq \exp\left(hL_{\rm ker}\right)\tau_{1}\tau_{2}\widetilde{\ell}_{0,{\rm ker}}.\]

In combination with (48), Lemmas (5.1) and (5.2) allow us to move seamlessly between training and test losses. Note that the assumptions underlying these lemmas can only conceivably be satisfied by smooth \(\psi_{\rm ker}\), thus almost completely ruling out the suitability of ReLU activations. On the other hand, the Tanh activation function equips the kernels with Lipschitz continuity by default; the matching property is a technical assumption to rule out pathological cases where the label of a test point disagrees with those of all of its neighbouring training points.

### Performance comparison

Next, we address task (b) outlined at the end of Subsection 5.1. Note that for any \(0\leq i\leq N_{1}\), \(0\leq j\leq N_{2}\), we have

\[\ln\left[1+\exp\left(\widehat{\psi}_{\rm CK}\left(\mbox{\boldmath $x$}_{i,j}\right)\right)\right] = \ln\left[1+\exp\left(\widehat{\psi}_{\rm CK}\left(\mbox{\boldmath $x$}_{i,j}\right)-\widehat{\psi}_{\rm NTK}\left(\mathbf{x}_{i,j} \right)\right)\exp\left(\widehat{\psi}_{\rm NTK}\left(\mathbf{x}_{i,j }\right)\right)\right]\] \[\leq \max\left\{1,\exp\left(\widehat{\psi}_{\rm CK}\left(\mathbf{x}_{i,j}\right)-\widehat{\psi}_{\rm NTK}\left(\mathbf{x}_{i,j }\right)\right)\right\}\ln\left[1+\exp\left(\widehat{\psi}_{\rm NTK}\left( \mathbf{x}_{i,j}\right)\right)\right]\]

where we used (37) again. Set

\[\omega = \max_{0\leq i\leq N_{1},0\leq j\leq N_{2}}\exp\left(\widehat{\psi }_{\rm CK}\left(\mathbf{x}_{i,j}\right)-\widehat{\psi}_{\rm NTK} \left(\mathbf{x}_{i,j}\right)\right); \tag{57}\]

it follows from (46) that \(\omega\geq 1\). We can therefore write

\[\widetilde{\ell}_{0,{\rm CK}}\leq\omega\widetilde{\ell}_{0,{\rm NTK}}. \tag{58}\]

Combining (46) and (58) with (48) and Lemmas 5.1 and 5.2 then yields the following two results.

**Theorem 5.1**: _Suppose that on every rectangle with corners \(\Lambda_{ij}\), the functions \(\widehat{\psi}_{\rm NTK}\) and \(\widehat{\psi}_{\rm CK}\) achieve their maximum values on \(\Lambda_{ij}\). Then, there exist constants \(C_{1},C_{2}\geq 1\) such that_

\[C_{1}^{-1}\ell_{1,{\rm NTK}}\leq\ell_{1,{\rm CK}}\leq C_{2}\ell_{1,{\rm NTK}} \tag{59}\]
**Proof:** We have

\[\ell_{1,{\rm NTK}} \leq (\tau_{1}\tau_{2})\ell_{0,{\rm NTK}}\qquad(\because\mbox{Lemma \ref{lem:NTK}}) \tag{60}\] \[\leq (\tau_{1}\tau_{2})\ell_{0,{\rm CK}}\qquad(\because(46))\] \[\leq (\tau_{1}\tau_{2})\ell_{1,{\rm CK}}\qquad(\because(48)).\]

Similarly,

\[\ell_{1,{\rm CK}} \leq (\tau_{1}\tau_{2})\ell_{0,{\rm CK}}\qquad(\because\mbox{Lemma \ref{lem:NTK}}) \tag{61}\] \[\leq (\tau_{1}\tau_{2}\omega)\ell_{0,{\rm NTK}}\qquad(\because(58))\] \[\leq (\tau_{1}\tau_{2}\omega)\ell_{1,{\rm NTK}}\qquad(\because(48)).\]

Setting \(C_{1}=\tau_{1}\tau_{2}\) and \(C_{2}=\tau_{1}\tau_{2}\omega\) and combining (60) and (61) yields (59).

**Theorem 5.2**: _Suppose that both \(\psi_{\rm NTK}\) and \(\psi_{\rm CK}\) are Lipschitz continuous on \(D\) and \(\eta\) possesses the matching property. Then, there exist constants \(D_{1},D_{2}\geq 1\) such that_

\[D_{1}^{-1}\ell_{1,{\rm NTK}}\leq\ell_{1,{\rm CK}}\leq D_{2}\ell_{1,{\rm NTK}} \tag{62}\]

**Proof:** As before, let \(L_{\rm ker}\) be the Lipschitz constant of \(\psi_{\rm ker}\) for both the kernels. We then have

\[\ell_{1,{\rm NTK}} \leq e^{hL_{\rm NTK}}\ell_{0,{\rm NTK}}\qquad(\because\mbox{Lemma \ref{lem:NTK}}) \tag{63}\] \[\leq e^{hL_{\rm NTK}}\ell_{0,{\rm CK}}\qquad(\because(46))\] \[\leq e^{hL_{\rm NTK}}\ell_{1,{\rm CK}}\qquad(\because(48)).\]

Similarly,

\[\ell_{1,{\rm CK}} \leq e^{hL_{\rm CK}}\ell_{0,{\rm CK}}\qquad(\because\mbox{Lemma \ref{lem:NTK}}) \tag{64}\] \[\leq e^{hL_{\rm CK}}\ell_{0,{\rm NTK}}\qquad(\because(58))\] \[\leq \omega e^{hL_{\rm CK}}\ell_{1,{\rm NTK}}\qquad(\because(48)).\]

Setting \(D_{1}=e^{hL_{\rm NTK}}\) and \(D_{2}=\omega e^{hL_{\rm CK}}\) and combining (63) and (64) yields (62).

## 6 Numerical tests

In this section, we present numerical evidence to support the theoretical findings established in the Sections 4 and 5. In addition, we identify myriad benefits of employing CK approximations over those coming from NN and NTK, including better conditioning, inexpensive gains in accuracy, and improved robustness.

We first consider the approximation problem for smooth functions \(f:[-1,1]\to\mathbb{R}\). As examples, we use

\[f_{1}(x)=e^{\sin(2\pi x)},\qquad f_{2}(x)=e^{3x},\qquad f_{3}(x)=\cos\left(e^{ 3x}\right). \tag{65}\]

We note that \(f_{3}\) oscillates rapidly close to \(x=1\) so it poses a particularly stiff challenge to NN and kernel approximators alike.

The sizes of the training and testing grids, as defined in Subsection 4.1, are fixed at \(N=200\) and \(M=600\) respectively, so \(\tau=3\). We train NNs of the form (1) with \(L=3\) and \(d_{l}=d=128\) for \(1\leq l\leq 3\) for \(2400\) epochs using the loss function defined in (2) and the weights given in (25). We employ the ADAM optimizer with the learning rate set at \(10^{-3}\) and primarily use Tanh as the activation function.

After training an NN, we assemble the CK and NTK and compute the corresponding kernel approximations (8). The details of the algorithm used for extracting the NTK are given in Appendix A. The CK is easily obtained from the values of the last hidden layer and using (23). Since the feature space dimension for the CK is \((d+1)\), assembling and using the corresponding Jacobian is also inexpensive. The results from using the Jacobian are indicated by CKJ in the following plots; a recipe for using this approximation is detailed in Appendix B.
Figure 1: The results of function regression for 100 different NNs, trained for 2400 epochs, and the corresponding approximations using the NTK, CK, and CKJ extracted from the NN at the end of the training.

Figure 2: The test errors for NNs over the course of being trained to approximate the given functions, and for the corresponding NTK, CK, and CKJ approximations. The errors are averaged over ten iterations to reduce the effects of random initialization.
In Figure 1, we show the test errors for the example target functions for 100 runs of the procedure described above. Owing to randomness in the initialization, the results vary over iterations; nevertheless, a clear separation is evident between the NN test errors and those of the two kernel approximations. More importantly, we note that the latter pair are fairly similar so that, while one may appear to be superior over the other for a particular example (e.g., the NTK for \(f_{1}\)), the difference is only marginal compared to the supremacy both enjoy over the NN.

Figure 1 also shows that the CK Jacobian yields test errors that improve on the kernel approximations by several orders of magnitude. This is a consequence of the much better conditioning possessed by the former: assembling the kernel matrix \(\widehat{H}_{\text{ker}}\) squares the singular values and applying its pseudo-inverse in (8) inflates round-off errors more than the using the Jacobian does, with the result that the test errors plateau earlier. We emphasize that the use of the Jacobian is only afforded by the CK since the dimension of the feature space corresponding to the NTK is prohibitively large.

These claims are further supported by the evolution of the errors over the course of the training, shown in Figure 2. The test errors are computed by averaging over ten iterations to reduce the effect of random initialization. While the NN errors can be seen to decay gradually, the kernel approximations do so more rapidly, particularly over the first few hundred epochs. The close resemblance between the two error profiles is noteworthy and supports our contention that the CK can serve as a proxy for the NTK. Finally, we note that, as expected, the CKJ errors decay even faster and level off at a threshold several orders of magnitude lower.

In Figure 3, we show that these conclusions are also valid when we repeat the experiments with the width of the hidden layers in the NN set to \(d=256\). In particular, this assuages any concerns that the beneficial properties enjoyed by the CK and CKJ approximations may be a consequence of solving an overdetermined least-squares problem: with the larger width, this is no longer the case, and the similarity in the corresponding

Figure 3: Function regression results for 100 NNs with the widths of the hidden layers set to 256, and the corresponding NTK, CK, and CKJ approximations.
Figure 4: The test errors for function regression for 100 trained NNs using the ReLU activation function, and the corresponding NTK and CK approximations.

Figure 5: Averaged test errors for function regression over the course of training ten NNs using ReLU activations, and the corresponding NTK and CK approximations.
error plots in Figures 1 and 3 establishes that our assertions are independent of NN width.

The same, however, cannot be said about the activation functions. Figure 4 shows that using ReLU activations instead of Tanh leads to the erasure of the error segregation seen in the earlier diagrams. In addition, the NTK approximators paradoxically appear to perform the worst, with the CK results only slightly bettering the NN ones. Figure 5 highlights that this is generally the case over the course of the NN training as well. These observations can be explained as a combined effect of the over-parameterization provided by the NTK and \(\mathcal{S}_{\text{NTK}}\) containing discontinuous functions (due to the derivatives of the ReLU activations; see Appendix A, and (78) in particular, for more details). The resulting approximator manages to fit the training data very well but struggles with generalizing to the test data-points. In contrast, the \(\mathcal{S}_{\text{CK}}\) consists only of continuous (albeit non-differentiable) functions, with the result that, while the approximation accuracy is lower than we observed with Tanh, it does not suffer from over-fitting. This can be regarded as indicative of the dangers associated with over-parameterization, the care that must be taken with ReLU-based approximators on unseen data, and the robustness possessed by the CK.

Next, we present the results for binary logistic regression on \(Z=[-1,1]^{2}\). We set \(N_{1}=11\), \(N_{2}=7\), \(M_{1}=22\) and \(M_{2}=21\) (so \(\tau_{1}=2\) and \(\tau_{2}=3\)) to specify the uniform training and testing grids (see Subsection 5.1 for the details). The labels are generated with respect to a known separating boundary \(F(x_{1},x_{2})=0\) for some \(F:Z\rightarrow\mathbb{R}\), so the labelling function is \(\eta(x_{1},x_{2})=\left(\text{sign}\left(F(x_{1},x_{2})\right)+1\right)/2\); we consider two examples:

\[F_{1}(x_{1},x_{2})=4x_{1}^{2}-3x_{1}+5x_{2}-1,\quad F_{2}(x_{1},x_{2})=2x_{1}^{ 3}-0.6x_{1}^{2}-1.94x_{1}+x_{2}+0.2. \tag{66}\]

We train NNs of the form (1), with \(L=2\) and \(d_{l}=d=128\) for \(l=1,2\), until the training accuracy (i.e., the proportion of correctly identified points) crosses \(0.85\), or \(4000\) e

Figure 6: The test cross-entropies and accuracies for logistic regression performed with 100 NNs, and the corresponding NTK and CK results.
Figure 7: The cross-entropies and accuracies for the test dataset for logistic regression performed with 100 NNs with hidden layer widths set to 64, and the corresponding NTK and CK results.
Figure 8: Test results for 100 NNs using the ReLU activation function for logistic regression, and the corresponding NTK and CK metrics.
Figure 9: Evolution of the test metrics, averaged over ten iterations, of NNs used to solve the logistic regression problem, and the corresponding NTK and CK results.
employ the ADAM optimizer, with learning rate \(10^{-5}\), and use Tanh as the primary activation function. The NTK and CK are extracted as detailed before and the respective training cross-entropies, defined in (9), are minimized by using Newton's method to solve \(\nabla_{\boldsymbol{\alpha}}\ell_{0,\text{lev}}(\boldsymbol{\alpha})=\boldsymbol {0}\). We consider both cross-entropy loss values and classification accuracies as assessment metrics on the test points.

The plots in Figure 6 show the results of 100 iterations of this procedure. A clear partition is visible in the performance metrics of the NN and the two kernels on the test datasets. At the same time, while the CK is generally outperformed by the NTK, the degree of improvement is dwarfed by the separation from the NN results.

Figure 7 shows that this is still the case, even when the hidden widths of the NN are halved to 64, thus demonstrating that the CK performance is not simply a consequence of over-parameterization. However, Figure 8 shows that the clear gap in performance vanishes when the activation function employed is ReLU. As in the case of function regression, this is explainable by over-fitting as a result of the volatile mix of over-parameterization and discontinuous feature map components.

Finally, Figure 9 shows the evolution of the performance metrics over the course of the NN training. We again show the average of ten iterations to reduce the effect of random initialization. The separation alluded to earlier is evident throughout, as is the relative proximity of the loss and accuracy values of the two kernels. Moreover, we note that the gaps shrink with training, so much so that the CK metrics are barely distinguishable from the NTK ones; the NN performance improves but a sizeable gulf nevertheless persists. In particular, this highlights a crucial point: even when the two kernels have been extracted from a minimally trained NN, they yield better results than the NN does at the end of training and when its metrics have plateaued. This underscores that using the CK (i.e., explicitly retraining only the last layer of the NN) is a low-cost recipe for significantly improving the accuracy of an NN.

## 7 Application to Foundation Models

In this section, we demonstrate the effectiveness of our prescribed training strategy on a foundation model. Specifically, we make use of the pre-trained GPT-2 [26] for sentiment classification on a human-annotated subset of the Sentiment140 dataset consisting of 359 tweets, all of which are labelled either positive or negative based on the expressed sentiment [27], rather than the entire Sentiment140 dataset due to a distribution shift between the train and test split as reported in [28] and seen in Figure 10. We evaluate two approaches:

* We fine-tune by starting from pre-trained weights, attaching a randomly initialized classification head and train for ten epochs, and allowing _all_ the weights to update.
* We perform linear probing by extracting a feature vector at the final hidden layer and training a logistic regression classifier for ten epochs.

Figure 10: Kernel density estimate of the largest principal component of GPT-2’s pre-trained final embedding representation of Sentiment140 \(P\) (the processed training set) and Sentiment140 \(M\) (the manually curated test set).
We note that these procedures can be seen as analogues of the NN and CK training respectively studied in the earlier sections. In particular, both NN and FT entail updates to all the parameters in the architecture, while the CK and LP approaches employ the feature map from the last hidden layer of a partially-trained architecture for logistic regression. Consequently, while the latter approach is significantly less expensive than the former, it can, as shown in the earlier sections, yield a marked improvement in accuracy.

We use pre-trained weights from Hugging Face for the transformer layers [29]. Furthermore, to establish a baseline, we also perform linear probing with GPT-2 initialized with random weights drawn from the truncated normal distribution \(\mathcal{N}(0,0.02)\)[26], [26]. All experiments are performed 50 times with the training and testing data shuffled. The averaged results, along with the standard errors, are reported in Table 1 with further details about the hyperparameters provided in Appendix C, Table 2.

We first note that the clear superiority (on both training and testing metrics) of linear probing following pre-training over random feature highlights the significant refinement the feature map undergoes after being exposed to a training corpus. Next, the extremely high training accuracy from fine-tuning suggests that the architecture is overfitting and hence prone to poor generalization. This is supported by the considerably lower test accuracy. On the other hand, linear probing performs better on the test dataset, and the significantly smaller disparity between its training and testing accuracies is indicative of its robustness against overfitting. Finally, we applied QLoRA [31] on GPT-2 to efficiently fine-tune the model on \(M.\) The trade-off for using quantized, low rank adapters is apparent compared to fine-tuning GPT-2 and the linear probing approach.

## 8 Discussion

Despite possessing the universal approximation property in theory [32, 33] and enjoying the expressiveness that accompanies increased depth [8], in practice neural networks are stymied by optimization errors in their efforts to approximate given functions to arbitrary accuracy. Finding the optimal parameters requires the navigation of highly complex and non-convex loss landscapes and demands a large number of training epochs, thus driving up the training cost. Furthermore, the somewhat cumbersome architectures do not admit closed-form characterizations of the learned functions, making it harder to determine their generalization properties, e.g., assess them on unseen data or predict their stability under the addition of seemingly negligible noise.

Since the NTK controls the evolution during training of the learned function, it provides one way of supplying the missing characterization. In particular, an optimally trained NN, in the infinite width limit, can be shown to equal a kernel machine with a closed form known _a priori_. From (21), it follows that, for finite width networks, a kernel machine relying on the empirical NTK would necessarily outperform the NN on the training data. The numerical tests in Section 6 confirm that this is also the case on test datasets across different problems, network widths, and training stages, provided the Tanh activation function is used. However, evaluating the resulting approximations (e.g., (8) and (10)) at a new point requires computing the NTK by pairing this point with every training point, which is a highly expensive undertaking for networks used in practical applications. Worse still, the NTK performance may be inferior to that of the NN when ReLU activations are employed (e.g., Figures 4 and 8) due to discontinuities in its feature map components. Furthermore, the resulting sensitivity to small perturbations in the inputs may also leave these approximations singularly susceptible to adversarial attacks.

In this paper, we studied the properties of approximations relying on the CK and found, both theoretically and empirically, that their performance is closely tied to the NTK results, provided certain regularity conditions on the approximations are met. These are satisfied by default for the Tanh activation function,

\begin{table}
\begin{tabular}{l l l} \hline \hline Model & Training Accuracy & Test Accuracy \\ \hline Random feature GPT-2 + LP & \(85.7\pm 0.27\%\) & \(57.8\pm 1.05\%\) \\ Pre-trained GPT-2 + LP & \(95.3\pm 0.15\%\) & \(86.3\pm 0.55\%\) \\ Pre-trained GPT-2 + FT & \(99.9\pm 0.02\%\) & \(83.7\pm 0.81\%\) \\ Pre-trained GPT-2 + QLoRA + FT & \(70.0\pm 0.28\%\) & \(66.9\pm 0.77\%\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Accuracy results for training and testing the LP and FT approaches on a human-curated subset of the Sentiment140 dataset. Mean values \(\pm\) the standard error of the mean are shown.
thus establishing that the gains in accuracy for the NTK over the NN are also inherited by the CK approximations. Importantly, the training cost of a CK machine is significantly lower than for an NN, yielding a closed form formula for function regression (8) and a convex optimization problem for logistic regression (9). In addition, its evaluation on new data-points is as inexpensive as evaluating the NN on the same points. As a result, the CK achieves a boost in accuracy over the NN comparable to that of the NTK while being strikingly cheaper to use than the latter and much easier to train than the former.

The CK also possesses features that, in some settings, make it even more favourable than the NTK. Due to the relatively low dimension of its feature space, the usage of its feature map form (12) for function regression is computationally viable. This approximation is much better conditioned than the corresponding kernel form, with the result that round-off errors are not magnified excessively and the approximation errors can achieve a much lower plateau, as shown in Figures 1, 2 and 3. In addition, the components of the feature map corresponding to the CK are continuous, even when using ReLU activations. As a consequence, the resulting approximations are less prone to overfitting and more robust to noise in the inputs.

We note that training a CK machine is equivalent to finding the optimal weights to attach to the neurons in the last hidden layer. Our work then suggests that a low-cost strategy for improving the accuracy of a trained NN is to simply retrain the last layer of parameters. This recipe does not alter the form of the neurons (i.e., the feature map components for the CK) but, as we have shown, can lead to significant enhancements in approximation accuracy. The regularity of the activation function is a key determinant in the success of this strategy. Observe that the choice of the activation function does not appear to affect the NN approximation errors too much, but the kernel performance is closely tied to it (e.g., compare Figures 1 and 4, and Figures 6 and 8). This indicates that the effects of the regularity of the activation function are realized only on the kernel machines, and that the NN is largely agnostic to it.

Deploying our strategy on a foundation model for classification illustrates that freezing the feature map and training only the last layer of parameters yields performance that compares favourably with full architecture training. In addition, this approach might even lend improved robustness to the predictive capabilities in that the limited degrees of freedom resist overfitting on the training data. Our results therefore hint at the possibility that early stopping for model fitting might be beneficial in more ways than is currently surmised and that there might be subtle procedures to modulate stopping times across various parts of the network. Our recommended approach offers a computational speed up without the large trade-off in accuracy as seen in other efficient fine-tuning methods.

Finally, our results can also offer an explanation as to why feed-forward regression networks perform so well. In essence, the information captured in the last hidden layer's feature representation uniquely determines the CK. While lossy, the CK still preserves enough information from the global feature representation encoded in the NTK. And so by construction, these neuro-architectures learn and then distill the relevant information by the final hidden layer for the regression tasks. Our use of approximation theory not only offers an elegant reason as to why these networks work but also a clever way to enhance them as well.

## Acknowledgements

The work of SQ is supported by the Department of Energy (DOE) Office of Advanced Scientific Computing Research (ASCR) through the Pacific Northwest National Laboratory Distinguished Computational Mathematics Fellowship (Project No. 71268). The work of AD, MV, AE, and TC were partially supported by the Mathematics for Artificial Reasoning in Science (MARS) initiative via the Laboratory Directed Research and Development (LDRD) Program at PNNL. The work of PS is partially supported by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research program under the Scalable, Efficient and Accelerated Causal Reasoning Operators, Graphs and Spikes for Earth and Embedded Systems (SEACROGS) project (Project No. 80278). Pacific Northwest National Laboratory is a multi-program national laboratory operated for the U.S. Department of Energy by Battelle Memorial Institute under Contract No. DE-AC05-76RL01830.