{'fraction_non_alphanumeric': 0.04160857908847185, 'fraction_numerical': 0.023699731903485254, 'mean_word_length': 4.513154005320721, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks

Recent research shows that the following two models are equivalent: (a) infinitely wide neural networks (NNs) trained under l2 loss by gradient descent with infinitesimally small learning rate (b) kernel regression with respect to so-called Neural Tangent Kernels (NTKs) (Jacot et al., 2018). An efficient algorithm to compute the NTK, as well as its convolutional counterparts, appears in Arora et al. (2019a), which allowed studying performance of infinitely wide nets on datasets like CIFAR-10. However, super-quadratic running time of kernel methods makes them best suited for small-data tasks. We report results suggesting neural tangent kernels perform strongly on low-data tasks. 1. On a standard testbed of classification/regression tasks from the UCI database, NTK SVM beats the previous gold standard, Random Forests (RF), and also the corresponding finite nets. 2. On CIFAR-10 with 10 - 640 training samples, Convolutional NTK consistently beats ResNet-34 by 1% - 3%. 3. On VOC07 testbed for few-shot image classification tasks on ImageNet with transfer learning (Goyal et al., 2019), replacing the linear SVM currently used with a Convolutional NTK SVM consistently improves performance. 4. Comparing the performance of NTK with the finite-width net it was derived from, NTK behavior starts at lower net widths than suggested by theoretical analysis(Arora et al., 2019a). NTK's efficacy may trace to lower variance of output.


Introduction
Modern neural networks (NNs) have way more parameters than training data points, which allow them to achieve near-zero training error while simultaneously -for some reason yet to be understood -have low generalization error . This motivated formal study of highly overparametrized networks, including networks whose width (i.e., number of nodes in layers, or number of channels in convolutional layers) goes to infinity. A recent line of theoretical results shows that with ℓ 2 loss and infinitesimal learning rate, in the limit of infinite width the trajectory of training converges to kernel regression with a particular kernel, neural tangent kernel (NTK) (Jacot et al., 2018). For convolutional networks, the kernel is CNTK. See Section 2 for more discussions. Arora et al. (2019a) gave an algorithm to exactly compute the kernel corresponding to the infinite limit of various realistic NN architectures with convolutions and pooling layers, allowing them to compute performance on CIFAR-10, which revealed that the infinite networks have 6 to 8% higher error than their finite counterparts. This is still fairly good performance for a fixed kernel.
kernel. Therefore, RF may be considered as a reference (gold-standard) to compare with new classifiers. Olson et al. (2018) followed this testing strategy to evaluate the performance of modern neural networks concluding that modern neural networks, even though being highly over-parameterized, still give reasonable performances on these small datasets, though not as strong as RFs. Our paper follows the same testing strategy to evaluate the performance of NTK.
The focus of this paper, neural tangent kernel is induced from a neural network architecture. The connection between infinitely wide neural networks and kernel methods is not new (Neal, 1996;Williams, 1997;Roux & Bengio, 2007;Hazan & Jaakkola, 2015;Lee et al., 2018;Matthews et al., 2018;Novak et al., 2019;Garriga-Alonso et al., 2019;Cho & Saul, 2009;Daniely et al., 2016;Daniely, 2017). However, these kernels correspond to neural network where only the last layer is trained. Neural tangent kernel, first proposed by Jacot et al. (2018), is fundamentally different as NTKs correspond to infinitely wide NNs with all layer being trained. Theoretically, a line of work study the optimization and generalization behavior of ultra-wide NNs (Allen-Zhu et al., 2018b,a;Arora et al., 2019b;Du et al., 2018b,a;Li & Liang, 2018;Zou et al., 2018;Yang, 2019;Cao & Gu, 2019a,b). Recently, Arora et al. (2019a) gave non-asymptotic perturbation bound between the NN predictor trained by gradient descent and the NTK predictor. Empirically,  verified on small scale data, NTK is a good approximation to NN. However, Arora et al. (2019a) showed on large scale dataset, NN can outperform NTK which may due to the effect of finite-width and/or optimization procedure.
Generalization to architectures other than fully-connected NN and CNN are recently proposed (Yang, 2019;Du et al., 2019;Bietti & Mairal, 2019). Du et al. (2019) showed graph neural tangent kernel (GNTK) can achieve better performance than its counter part, graph neural network (GNN), on datasets with up to 5000 samples.

Neural Network and Neural Tangent Kernel
Since NTK is induced by a NN architecture, we first define a NN formally. Let x ∈ R d be the input, and denote g (0) (x) = x and d 0 = d for notational convenience. We define an L-hidden-layer fully-connected neural network recursively: where W (h) ∈ R d h ×d h−1 is the weight matrix in the h-th layer (h ∈ [L]), σ : R → R is a coordinate-wise activation function, and c σ is a scaling factor. 3 In this paper, for NN we will consider σ being ReLU or ELU (Clevert et al., 2015) and for NTK we will only consider kernel functions induced by NNs with ReLU activation. The last layer of the neural network is where W (L+1) ∈ R 1×dL is the weights in the final layer, and we let w = W (1) , . . . , W (L+1) be all parameters in the network. All the weights are initialized to be i.i.d. N (0, 1) random variables. When the hidden widths d 1 , d 2 , . . . , d L → ∞, certain limiting behavior emerges along the gradient trajectory. Let x, x ′ ∈ R d be two data points, the covariance kernel of the h-th layer's outputs, , can be recursively defined in an analytical form: for h ∈ [L]. Crucially, this analytical form holds not only at the initialization, but also holds during the training (when gradient descent with small learning rate is used as the optimization routine). Formally, NTK is defined as the limiting gradient kernel Again, one can obtain a recursive formulȧ where we letΣ (L+1) (x, x ′ ) = 1 for convenience. It is easy to check if we fix the first L ′ layers and only train the Note when L ′ = L, then the resulting NTK is Σ (L) (x, x ′ ), which is the NNGP kernel (Lee et al., 2018). L ′ can be viewed as a hyperparameter of NTK classifier, and in our UCI experiment we tune L ′ . Given a kernel function, one can directly use it for downstream classification tasks (Scholkopf & Smola, 2001).

Experiments on UCI Datasets
In this section, we present our experimental results on UCI datasets which follow the setup of Fernández-Delgado et al.  Table 6 in Appendix A for a summary of datasets we used. We compute NTKs containing 1 to 5 fully-connected layers and then use kernel SVM with soft margin for classification. The detailed experiment setup, including the choices the datasets, training / test splitting and ranges of hyperparameters, is described in Appendix A. The code can be found in https://github.com/LeoYu/neural-tangent-kernel-UCI. We note that usual methods of obtaining confidence bounds in these low-data settings are somewhat heuristic. P90/P95 and PMA. This measures, for a given classifier, the fraction of datasets on which it achieves more than 90%/95% of the maximum accuracy among all classifiers. NTK is one of the best classifiers (ties with Gaussian kernel on P95), which shows NTK can consistently achieve superior classification performance across a broad range of datasets. Lastly, we consider the Percentage of the Maximum Accuracy (PMA). NTK achieves the best average PMA followed by RF whose PMA is 0.47% below that of NTK and other classifiers are all below 94.6%. An interesting observation is that NTK, NN with NTK initialization and RF have small standard deviation (5.17%, 5.89% and 5.30%) whereas all other classifiers have much larger standard deviation.

Pairwise Comparisons
NTK vs. RF. In Figure 1a, we compare NTK with RF. There are 42 datasets that NTK outperforms RF and 40 datasets that RF outperforms NTK. 4 The mean difference is 2.51%, which is statistically significant by a Wilcoxon signed rank test. We see NTK and RF perform similarly when the Bayes error rate is low with NTK being slightly better. There are some exceptions. For example, on the balance-scale dataset, NTK achieves 98% accuracy whereas RF only achieves 84.1%. When the Bayes error rate is high, either classifier can be significantly better than the other. NTK vs. Gaussian Kernel. The gap between NTK and Gaussian kernel is more significant. As shown in Figure 1b, NTK generally performs better than Gaussian kernel no matter Bayes error rate is low or high. There are 43 datasets that NTK outperforms Gaussian kernel and there are 34 datasets that Gaussian kernel outperforms NTK. The mean difference is 2.22%, which is also statistically significant by a Wilcoxon signed rank test. On balloons, heart-switzerland, pittsburg-bridges-material, teaching, trains datasets, NTK is better than Gaussian kernel by at least 11% in terms of accuracy. These five datasets all have less than 200 samples, which shows that NTK can perform much better than Gaussian kernel when the number of samples is small.
NTK vs. NN In this section we compare NTK with NN. The goals are (i) comparing the performance and (ii) verifying NTK is a good approximation to NN.
In Figure 2a, we compare the performance between NTK and NN with He initialization. For most datasets, these two classifiers perform similarly. However, there are a few datasets that NTK performs significantly better. There are 50 datasets that NTK outperforms NN with He initialization and there are 27 datasets that NN with He initialization outperforms NTK. The mean difference is 1.96%, which is also statistically significant by a Wilcoxon signed rank test.
In Figure 2b, we compare the performance between NTK and NN with NTK initialization. Recall that for NN with NTK initialization, when the width goes to infinity, the predictor is just NTK. Therefore, we expect these two predictors give similar performance. Figure 2b verifies our conjecture. There is no dataset the one classifier is significantly better than the other. We do not have the same observation in Figure 1a, 1b or 2a. Nevertheless, NTK often performs better than NN. There are 52 datasets that NTK outperforms NN with He initialization and there are 25 datasets NN with He initialization outperforms NTK. The mean difference is 1.54%, which is also statistically significant by a Wilcoxon signed rank test.

Experiments on Small CIFAR-10 Dataset
In this section, we study the performance of CNTK on subsampled CIFAR-10 dataset. We randomly choose n samples from CIFAR-10 training set, use them to train CNTK and ResNet-34, and test both classifiers on the whole test set. In our experiments, we vary n from 10 to 1280, and the number of convolutional layers of CNTK varies from 5 to 14. After computing CNTK, we use kernel regression for training and testing. See Appendix B for detailed experiment setup.   The results are reported in Table 2. It can be observed that in this setting CNTK consistently outperforms ResNet-34. The largest gap occurs at n = 320 where 14-layer CNTK achieves 36.57% accuracy and ResNet achieves 33.15%. The smallest improvement occurs at n = 10: 15.33% vs. 14.59%. When the number of training data is large, i.e., n = 1280, ResNet can outperform CNTK. It is also interesting to see that 14-layer CNTK is the best performing CNTK for all values of n, suggesting depth has a significant effect on this task.

Experiments on Few-shot Learning
In this section, we test the ability of NTK as a drop-in classifier to replace the linear classifier in the few-shot learning setting. Using linear SVM on top of extracted features is arguably the most widely used strategy in few-shot learning as linear SVM is easy and fast to train whereas more complicated strategies like fine-tuning or training a neural network on top of the extracted feature have more randomness and may overfit due to the small size of the training set. NTK has the same benefits (easy and fast to train, no randomness) as the linear classifier but also allows some non-linearity in the design. Note since we consider image classification tasks, we use CNTK in experiments in this section. Experiment Setup. We mostly follow the settings of Goyal et al. (2019). Features are extracted from layer conv1, conv2, conv3, conv4, conv5 in ResNet-50 (He et al., 2016) trained on ImageNet (Deng et al., 2009), and we use these features for VOC07 classification task.    . . , 8} and for each class, we randomly choose 10 independent sets with 20k training samples in each set. We report the mean and standard deviation of mAP on the test split of VOC07 dataset. This setting has been used in numbers of previous few-shot learning papers (Goyal et al., 2019;Zhang et al., 2017).
We take the extracted features as the input to CNTK. We tried CNTK with 0-6 convolution layers, a global average pooling layer and a fully-connected layer. We normalize the data in the feature space, and finally use SVM to train the classifiers. Note without the convolution layer, it is equivalent to directly applying linear SVM after global average pooling and normalization. We use sklearn.svm.LinearSVC to train linear SVMs, and sklearn.svm.SVC to train kernel SVMs (for CNTK). To train SVM, we choose the cost value C from 2 [−19,−4] ∪ 10 [−7,2] and set the class weight ratio to be 2 : 1 for positive/negative classes as in Goyal et al. (2019).
Since the number of given samples is usually small, Goyal et al. (2019) chooses to report the performance of the best cost value C. In our experiments, we use a more standard method to perform cross-validation. We use the first 10 classes of VOC07 to tune C, and report the performance of selected C in the other 10 classes in Table 3-5. We also report the performance of the best C as in Goyal et al. (2019), in Tables 7-9 in the appendix for completeness.
Discussions. First, we find CNTK is a strong drop-in classifier to replace the linear classifier in few-shot learning. Tables 3-9 clearly demonstrate that CNTK is consistently better than linear classifier. Note Tables 3-9 only show the prediction accuracy in an average sense. In fact, we find that on every randomly sampled training set, CNTK always gives a better performance. We conjecture that CNTK gives better performance because the non-linearity in CNTK helps prediction. This is verified by looking at the performance gain of CNTK for different feature extractors. Note Conv5 is often considered to be most useful for linear classification. There, CNTK only outperforms the linear classifier by about 1%. On the other hand, with Conv3 and Conv4 features, CNTK can outperform linear classifier by around 2% and sometimes by 3%-4% (last two rows in Table 5). We believe this happens because Conv3 and Conv4 correspond to middle-level features, and thus non-linearity is indeed beneficial for better accuracy.
We also observe that CNTK often performs the best with a single convolutional layer. This is expected since features extracted by ResNet-50 already produce a good representation. Nevertheless, we find for middle-level features Conv3 with k = 7 or 8, CNTK with 3 convolutional layers give the best performance. We believe this is because with more data, utilizing the non-linearity induced by CNTK can further boost the performance.

Conclusion
The Neural Tangent Kernel, discovered by mathematical curiosity about deep networks in the limit of infinite width, is found to yield superb performance on low-data tasks, beating extensively tuned versions of classic methods such as random forests. The (fully-connected) NTK classifiers are easy to compute (no GPU required) and thus should be a good off-the-shelf classifier in many settings. We plan to release our code to allow drop-in replacement for SVMs and linear regression.
Many theoretical questions arise. Do NTK SVMs correspond to some infinite net architecture (as NTK ridge regression does)? What explains generalization in small-data settings? (This understanding is imperfect even for random forests.) Finally one can derive NTK corresponding to other architectures, e.g., recurrent neural tangent kernel (RNTK) induced by recurrent neural networks. It would be an interesting future research direction to test their performance on benchmark tasks.

A Additional Experimental Details on UCI
In this section, we describe our experiment setup.
Dataset Selection Our starting point was the pre-processed UCI datasets from Fernández-Delgado et al. (2014), which can be downloaded from http://persoal.citius.usc.es/manuel.fernandez.delgado/papers/jmlr/data.t Their preprocessing involved changing categorical features to numerical, some normalization, and turning regression problems to classification. Of these we only retained datasets with number of samples less than 5000, since we are interested in low-data regime. Furthermore, we discovered an apparent bug in their preprocessing on datasets with explicit training/test split (specifically, their featurization was done differently on training/test data). Fixing the bug and retraining models on those datasets would complicate an applesto-apples comparison, so we discarded these datasets from our experiment. This left 90 datasets. See Table  6 for a summary of the datasets. Even on these 90 remaining datasets, their ranking of different classifiers was almost preserved, with random forest the best followed by SVM with Gaussian kernel.

NTK Specification
We calculate NTK induced fully-connected neural networks with L layers where L ′ bottom layers are fixed, and then use C-support vector classification implemented by sklearn.svm. We tune hyperparameters L from 1 to 5, L ′ from 0 to L − 1, and cost value C as powers of ten from −2 to 4. The number of kernels used is 15, so the total number of parameter combinations is 105. Note this number is much less than the number of hyperparameter of Gaussian kernel reported in Fernández-Delgado et al. (2014) where they tune hyperparameters with 500 combinations.

NN Specification
We use fully-connected NN with L layers, 512 number of hidden nodes per layer and use gradient descent to train the neural network. We tune hyperparameters L from 1 to 5, with / without batch normalization and learning rate 0.1 or 1. We run gradient descent for 2000 epochs. 5 We treat NN with He initialization and NTK initialization as two classifiers and report their results separately.