Enhanced Convolutional Neural Tangent Kernels
Authors: Dingli Yu
Ruosong Wang
Zhiyuan Li
Wei Hu
Ruslan Salakhutdinov
Sanjeev Arora
Simon S. Du
Venue:  (2020)
Keywords: neural tangent kernel
data augmentation
global average pooling
kernel regression
deep learning theory
kernel design

Abstract: Recent research shows that for training with l2 loss, convolutional neural networks (CNNs) whose width (number of channels in convolutional layers) goes to infinity, correspond to regression with respect to the CNN Gaussian Process kernel (CNN-GP) if only the last layer is trained, and correspond to regression with respect to the Convolutional Neural Tangent Kernel (CNTK) if all layers are trained. An exact algorithm to compute CNTK (Arora et al., 2019) yielded the finding that classification accuracy of CNTK on CIFAR-10 is within 6-7% of that of the corresponding CNN architecture (best figure being around 78%) which is interesting performance for a fixed kernel.
Here we show how to significantly enhance the performance of these kernels using two ideas. (1) Modifying the kernel using a new operation called Local Average Pooling (LAP) which preserves efficient computability of the kernel and inherits the spirit of standard data augmentation using pixel shifts. Earlier papers were unable to incorporate naive data augmentation because of the quadratic training cost of kernel regression. This idea is inspired by Global Average Pooling (GAP), which we show for CNN-GP and CNTK, GAP is equivalent to full translation data augmentation. (2) Representing the input image using a pre-processing technique proposed by Coates et al. (2011), which uses a single convolutional layer composed of random image patches.
On CIFAR-10 the resulting kernel, CNN-GP with LAP and horizontal flip data augmentation achieves 89% accuracy, matching the performance of AlexNet (Krizhevsky et al., 2012). Note that this is the best such result we know of for a classifier that is not a trained neural network. Similar improvements are obtained for Fashion-MNIST.

Under review as a conference paper at ICLR 2020
ENHANCED CONVOLUTIONAL NEURAL KERNELS
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent research shows that for training with & loss, convolutional neural net- works (CNNs) whose width (number of channels in convolutional layers) goes to infinity correspond to regression with respect the CNN Gaussian Process kernel (CNN-GP) (Novak et al., 2019) if only the last layer is trained, and correspond to regression with respect to the Convolutional Neural Tangent Kernel (CNTK) if all layers are trained. An exact algorithm to compute CNTK (Arora et al., 2019) yielded the finding that classification accuracy of CNTK CIFAR-10 is within 6-7% of that of the corresponding CNN architecture (best figure being around 78%) which interesting performance for fixed kernel.
Here we show how to significantly enhance the performance of these kernels using two ideas. (1) Modifying the kernel using a new operation called Local Average Pooling (LAP) which preserves efficient computability of the kernel and inherits the spirit of standard data augmentation using pixel shifts. Earlier papers were unable to incorporate naive data augmentation because of the quadratic training cost of kernel regression. This idea is inspired by Global Average Pooling (GAP), which we show for CNN-GP and CNTK is equivalent full translation data aug- mentation. (2) Representing the input image using a pre-processing technique proposed by Coates et al. (2011), which uses single convolutional layer com- posed of random image patches.
On CIFAR-1O, the resulting kernel, CNN-GP with LAP and horizontal flip data augmentation, achieves 89% accuracy, matching the performance of AlexNet (Krizhevsky et al., 2012) and outperforms the best previous classifier that is not trained neural network (Mairal, 2016). Similar improvements are obtained for Fashion-MNIST.
INTRODUCTION
Recent research shows that for training with E loss, convolutional neural networks (CNNs) whose width (number of channels in convolutional layers) goes infinity, correspond to regression with respect to the CNN Gaussian Process kernel (CNN-GP) if only the last layer is trained (Novak et al., 2019; Garriga-Alonso et al., 2019), and correspond to regression with respect to the Convolutional Neural Tangent Kernel (CNTK) if all layers are trained (Jacot et al., 2018; Allen-Zhu et al., 2018; Du al., 2019b; Arora et al., 2019). Novak et al. (2019); Garriga-Alonso plemented CNN-GP and tested its empirical performance. An efficient exact algorithm was given (Arora et al., 2019) to compute CNTK for CNN architectures, as well as those that include a Global Average Pooling (GAP) layer (defined below). This is a fixed kernel that inherits some benefits of CNNs, including exploitation of locality via convolution, as well multiple layers of processing. For CIFAR-10, incorporating GAP into the kernel improves classification accuracy by up to 10% compared to pure convolutional CNTK.
al. (2019) also im-
While this performance is encouraging for fixed kernel, the best accuracy is still under 78%, which disappointing even compared to AlexNet. One hope for improving the accuracy further is to somehow capture modern innovations such batch normalization, data augmentation, resid- ual layers, etc. in CNTK. The current paper shows how to incorporate simple data augmentation. Specifically. the idea of creating new training images from existing images using pixel translation and flips, while assuming that these operations should not change the label. Since deep learning uses stochastic gradient descent (SGD), it is trivial to do such data augmentation the fly. However, it's

---

Under review as a conference paper at ICLR 2020
unclear how to efficiently incorporate data augmentation in kernel regression, since training time is quadratic in the number of training images.
Thus somehow data augmentation has to be incorporated into the computation of the kernel itself. The main observation here is that the above-mentioned algorithm for computing CNTK involves a dynamic programming whose recursion depth is equal to the depth of the corresponding finite CNN. is possible to impose symmetry constraints at any desired layer during this computation. In this viewpoint, it can be shown that prediction using CNTK/CNN-GP with GAP is equivalent to predic- tion using CNTK/CNN-GP without GAP but with full translation data augmentation with wrap- around at the boundary. The translation invariance property implicitly assumed in data augmentation is exactly equivalent to an imposed symmetry constraint in the computation of the CNTK which in turn derived from the pooling layer in the CNN. See Section 4 for more details.
Thus GAP corresponds to full translation data augmentation scheme, but in practice such data aug- mentation creates unrealistic images (cf. Figure 2) and training on them can harm performance. However, the idea of incorporating symmetry in the dynamic programming leads to a variant we call Local Average Pooling (LAP). This implicitly is like data augmentation where image labels are assumed to be invariant to small translation, say by a few pixels. Interestingly, LAP corresponds to a average pooling layer for CNNs, named box filtering (Szeliski, 2010).
Experimentally, we find LAP significantly enhances the performance discussed below.
In extensive experiments on CIFAR-IO and Fashion-MNIST, we find LAP consistently improves performance of CNN-GP and CNTK. In particular, we find CNN-GP with LAP achieves 81% on CIFAR-10 10 dataset, outperforming the best previous kernel predictor by 3%.
When using the technique proposed by Coates et al. (2011), which uses randomly sampled patches from training data as filters to do pre-processing.2 CNN-GP with LAP and horizon- tal flip data augmentation achieves 89% accuracy on CIFAR-1O, matching the performance of AlexNet (Krizhevsky et al., 2012) and is the strongest classifier that is not a trained neural net- work.²
We also test performance of CNNs with an extra layer corresponding to LAP and observe that it improves the performance on certain architectures.
2 RELATED WORK
Data augmentation has long been known to improve the performance of neural network and kernel methods (Sietsma & Dow, 1991; Schölkopf et al., 1996). Theoretical study of data augmentation dates back to Chapelle et al. (2001). Recently, Dao et al. (2018) proposed a theoretical framework for understanding data augmentation and showed data augmentation with a kernel classifier can have feature averaging and variance regularization effects. More recently, Chen et al. (2019) quanti- tatively shows in certain settings, data augmentation provably improves the classifier performance. For more comprehensive discussion on data augmentation and its properties, we refer readers to Dao et al. (2018); Chen et al. (2019) and references therein.
CNN-GP and CNTK correspond to infinitely wide CNN with different training strategies (only training the top layer or training all layers jointly). The correspondence between infinite neural networks and kernel machines was first noted by Neal (1996). More recently, this was extended to deep and convolutional neural networks (Lee et al., 2018; Matthews et al., 2018: Novak et al., 2019; Garriga-Alona et al., 2019). These kernels correspond to infinitely wide neural networks where only the last layer is trained. A recent line of work studied overparameterized neural networks where all layers are trained (Allen-Zhu et al., 2018; Du et al., 2019b; 2018; Li & Liang, 2018; Zou et al., 2018). Their proofs imply the gradient kernel is close to a fixed kernel which only depends the training data and neural network architecture. These kernels thus correspond infinitely wide neural networks where are all layers are trained. Jacot et al. (2018) named this kernel, neural tangent kernel (NTK). Arora et al. (2019) formally proved infinitely wide neural net predictor trained by
'Frr CIFAR 10, the bottleneck of using CNN-GP and CNTK is not solving least square hut constructing kernel. The time complexity is O(p²n n²) where p is the number of pixels in each image and n is number of data point.
"See Section 6.2 for the precise procedure.
hhtps:/hhncchmrks.aiiiti
2

---

Under review as a conference paper at ICLR 2020
gradient descent is equivalent NTK predictor. Recently, NTKs induced by various neural network architectures are derived and shown to achieve strong empirical performance (Arora et al., 2019; Yang, 2019; Du et al., 2019a).
Global Average Pooling (GAP) was first proposed in Lin et al. (2013) and is common in modern CNN design (Springenberg et al., 2014; He et al., 2016; Huang et al., 2017). However, current the- oretical understanding on GAP is still rather limited. It has been conjectured in Lin et al. (2013) that GAP reduces the number of parameters in the last fully-connected layer and thus avoids over- fitting, and that GAP is more robust to spatial translations of the input since it sums out the spatial information. In this work, we study GAP from the CNN-GP and CNTK perspective, and draw an interesting connection between GAP and data augmentation.
Here we are interested in methods that are not trained neural networks. If the features are predefined before seeing the data, Oyallon & Mallat (2015) proposed the scattering network which achieves 82% classification accuracy on CIFAR-10 10. If one uses unsupervised learning methods to extract features, the method proposed in Coates et al. (2011) is one of the best-performing approaches on CIFAR-10 preceding modern CNNs. To our knowledge, the best result via unsupervised learning method in this line is by Mairal (2016), who used the convolutional kernel network to achieve 86% accuracy on CIFAR- 10. In this work we combine CNTK with LAP and the idea Coates et al. (2011) 1) to achieve the best performance for classifiers that are not trained neural networks.
3 PRELIMINARIES
3.1 NOTATION
We use bold-faced letters for vectors, matrices and tensors. For a vector let [a]; be its i-th entry; for a matrix A, let [A],,) be its (i,j)-th entry; for an order tensor T, let T sg,rg be its i', entry. For a symmetric tensor, wet let Ir (T) = Eij Tyaa- For an order tensor T E x and an integer [C2], use Tio) E x xC. to denote the order
d - 1 tensor formed by fixing the coordinate of the last dimension of T to be a.
3.2 CNN, CNN-GP AND CNTK
In this section we give formal definitions of CNN, CNN-GP and CNTK that study in this paper. Throughout the paper, we let P be the width and Q be the height of the image. We use E 24 to denote the filter size. practice, q 1, 3, 7.
Padding Schemes. In the definition of CNN, CNTK and CNN-GP, may different padding schemes. Let x E RPxQ be an matrix. For given index pair (i,j) with i S 0, 2 P+1,1 S j 2 Q different padding schemes define different value for [a=),,) For circular padding, define [a=,,, be [æ>; mod P.j mod Q- For zero padding, we simply define [x]s,, to be Note the difference between circular padding and zero padding occurs only on the boundary of images. We
will prove our theoretical results for the circular padding scheme to avoid boundary effects.
CNN.
Now we describe CNN with and without GAP. For any input image æ, after intermediate layers, obtain (L) PPxxx(l where (L)) is the number of channels of the last layer. See Section A for the definition of (D), For the output, there are two choices: with and without GAP.
Without GAP: the final output is defined as f(0,x)) = Eonh
(L+1)
m(()) where a (L) (o) E
(a)
RPxQ, and w-(L+1) RR is the weight of the last fully-connected layer.
(a)
With GAP: the final output is defined as S(0, x) ,े c(4)
W ((++1)
(L) x (T())
(a)
where (L+1)) E IR is the weight of the last fully-connected layer.
(a)
CNN-GP and CNTK. Now describe CNN-GP and CNTK. Let a' be two input images. We denote the L-th layer's CNN-GP kernel ) (æ, x²) [1Px1I) and the L-th layer's CNTK kemel as (2) (xr, x²) R|P]x Q), See Section A for the precise definitions of
3

---

Under review as a conference paper at ICLR 2020
E(1) (æ, x') and ((7.) (z, x'). For the output kernel value, again, there are two choices, without
GAP (equivalent to using a fully-connected layer) or with GAP.
Without GAP: the output of CNN-GP is EF (a, = tr (2, and the output of
CNTK is OO (x, = Lr (ol x')).
With GAP: the output of CNN-GP is EGAP (x,x') E (x, (o)))) Lige
and the @GAP (x, x²) = PAO Ensss//eemm)) (0(2) (x, x') "1g
paQa (.S.''E(PIx(Q)xIPII
output of CNTK
Kernel Prediction. Lastly, we recall the formula for kernel regression. For simplicity, throughout the paper, we will assume kernels are invertible. Given kernel (x, x²) and a dataset (X,y)
with data {< v)) } define Kx E RNNN where [Kx]s = k(),, The prediction for unseen data x' is Σ o;K(<'' mn), where Kx'y.
3.3 DATA AUGMENTATION SCHEMES
In this paper consider two types of data augmentation schemes: translation and horizontal flip.
Translation. Given (i.j) E [P] x [Q], we define the translation operator Tiz PxQxC 7 RPXQXC; for an image E PXQxC [Tej ( [x] [ for (i', [P] [Q]
[C]. Here the precise definition of [z])+,,,'+$,. depends on the padding scheme. Given dataset
D = {( 1)))) the full translation data augmentation scheme creates a new dataset DT {(Tiy (xx) (1))) (1) (L.x))EPPIX(QIXXN and training is performed on DT.
Horizontal Flip. Flip operator PxQxC + IR PxQxO; for an image æ E PxQxC [F (x))a.j.c = = for (i.j,c) E [P] x [Q] x [C]. Given a dataset {(x,,, y:) the horizontal flip augmentation scheme creates a new dataset of the form D, = {(F (ax)) yhh )))) and training is performed Dy D.
EQUIVALENCE BETWEEN AUGMENTED KERNEL AND DATA AUGMENTATION
In this section, we demonstrate the equivalence between using data augmentation and using a aug- mented kernel. To formally discuss the equivalence, we use group theory to describe translation and horizontal flip operators. We provide the definition of group in Section for completeness.
It is easy to verify that (F,I), (Tr, (1.E))I))))))) (Ti,j ((J)E()))) U (Trg) (.aeet) are groups, where I is the identity map. From now on, given a dataset (X, y) with data (a);, N and group G. the augmented dataset (Xg. yg) defined be {g(x;)) yilges,eeN]] For kernel prediction for unseen data x'' the augmented dataset, we have the following formula: Eie[N].EG Di.,K(rt .((;))) where ā = =
Kx Ug.
To proceed, we define the concept of augmented kernel. Let G be a finite group. Define the aug- ((g(K))gg'(()) g'x'))) where a., x are inputs images. A key observation is that for CNTK and CNN-GP, when circular padding and GAP is adopted, these are actually the augmented kernels with the group G (T. Formally, we have Pa FC (x, x'). The proof for these two equations is just by checking the formula of these kernels and using definition of circular padding. By similar proof, one can observe the following invariance property of ΣGAP: ΣFC. O and OFc. under all groups mentioned above, including {F,I} and (T=.))
mented kernel K2 K2 ( x')
I ge EGAP (x, x') = Pe Fc x') and @CAP x') = 1 Og
Definition 4.1. A kernel K. is invariant under a group g if and only if for any g E g, (g((v), (xx)) K K(x,, x').
Now the following theorem formally states the equivalence between using an augmented kernel on the dataset and using the kernel the augmented dataset.
4

---

Under review as a conference paper at ICLR 2020
Theorem 4.1. Given a group 9 and kernel K. such that K is invariant under G, then the prediction of augmented kernel K with dataset (X, y) is equal to that of kernel K and augmented dataset (Xg, Us). Namely, for any x' E PPPxx Σ (x' xi) EvELNiSeg Di.gK(a , .((;))
where a (K&) y. (Kx,) yG.
The proof is deferred to Appendix B. Two corollaries are directly followed.
Corollary 4.1. For G = (1.E)))))) for any given dataset D, the prediction of GAP (or GAP) with dataset D is equal to the prediction of EF (or Fc) with augmented dataset Dr. Corollary 4.2. For G = {F,I), for any given dataset D, the prediction of E (or 6 GAP) with dataset D is equal to the prediction of GAP (or GAP) with augmented dataset D U D.
Now we discuss implications of Theorem 4.1 and its corollaries. Naively applying data augmen- tation, with full translation on CNTK or CNN-GP for example, one needs create a p² times larger kernel matrix since there are PQ translation operators, which is often computationally in- feasible. Instead, we can directly use the augmented kernel (EGAP or GAP for the case of full translation on CNTK or CNN-GP) for prediction, for which one only needs to create a kernel ma- trix that as large as the original one. For horizontal flip, although the augmentation kernel not as conveniently computed as full translation, Corollary 4.2 still provides more efficient method for computing kernel value and solving kernel regression, since the augmented dataset is twice as large as the original dataset.
LOCAL AVERAGE POOLING
In this section, we introduce a new operation called Local Average Pooling (LAP). As discussed in the introduction, full translation data augmentation can create unrealistic images. A natural idea is to do local translation data augmentation, i.e., restricting the distance of translation. More specifically, we only allow translation operations A (cf.. Section 3.3) for (A,, Aj) E [-c, [cccccx[[c,,,.. where a parameter to control the amount of allowed translation. With a proper choice of the parameter e, translation data augmentation will not create unrealistic images (ef. Figure 2). However, naive local translation data augmentation is computationally infeasible for kernel methods, even for moderate choice of c. To remedy this issue, in this section we introduce LAP, which is inspired by the connection between full translation data augmentation and GAP on CNN-GP and CNTK. Here, for simplicity, we assume P Q and derive the formula only for CNTK. Our formula can be generalized to CNN-GP in a straightforward manner.
Recall that for two given images and x', without GAP, the formula for out- With GAP, the formula for output of CNTK is With circular padding, the formula can be rewritten which is again equal to pz AA ir (e (a),, (x)))))))))) We ignore the 1/p2 scaling factor since plays no role in kernel regression.
put of CNTK is ir ( x')). EipNEE 1O (z, x' "aag..""
as pa AY EIJE[PiX(PI
O (z, Dlttsst+t,
Now consider restricted translation operations Takd; with (A,, 1-c,d x |-c, and derive the formula for LAP. Assuming circular padding, we have
EA, ( (TaiA, (z), (ae),,T,,,, (x,,3(")))
(2c+ E EAIAAA E klpp (0 x' ((o.,"")HHAA)H)..... JIHHHHA
(I)
Now we have derived the formula for LAP which is given in Equation 1. Notice that the formula in Equation| is well-defined quantity for all padding schemes. In particular, assuming zero padding. when = P. LAP is equivalent to GAP, When c = 0, LAP is equivalent to no pooling layer. Another advantage of LAP that it does not incur sigmificant additional computational cost, since the formula in Equation can be rewritten as Eij.e' ( [w)]....'."" e (x. x (x..a')) Diig... where each entry in the weight tensor can be calculated in 0(1) time.
Note that the GAP operation in CNN-GP and CNTK corresponds to the GAP layer in CNNs. Here observe the following box filtering layer that corresponds to LAP in CNNs. Box filtering layer
5

---

Under review as a conference paper at ICLR 2020
(BF) is function R + Px such that [BF(x)]a, (2c+1)2 El-coe 2 2i+A.,+4;
This is in fact standard average pooling layer but with stride 1 and pooling size 2c + 1. We prove the equivalence between LAP and box filtering layer in Appendix C. In Section 6.3, we test BF on CNNs to verify its effectiveness.
6 EXPERIMENTS
In this section present our empirical findings CIFAR-10 10 (Krizhevsky, 2009) and Fashion- MNIST (Xiao et al., 2017). The detailed experimental setup is reported in Appendix D. When reporting test accuracies, the best result on the test set is in boldface and the result that corresponds to the hyper-parameter chosen by cross-validation is underlined.
6.1 ABLATION STUDY ON CIFAR-10 10 AND FASHION-MNIST
We perform experiments study the effect of different values of the e parameter in LAP and hori- zontal flip data argumentation on CNTK and CNN-GP. For experiments in this section we set the bias term in CNTK and CNN-GP be 3 0 (cf. Section A). We use the same architecture for CNTK and CNN-GP as in Arora et al. (2019). Le., we stack multiple convolutional layers before the final pooling layer. We use d denote the number of convolutions layers, and in our experiments we set d to be 5, 8, 11 or 14. to study the effect of depth on CNTK and CNN-GP. For CIFAR- -O0, LAP to 0, ,,,..,,.. 32, while for Fashion-MNIST we set the e parameter in LAP to be 0, 4, 28. Notice that when
we set the e parameter
28 for Fashion-MNIST, LAP is equivalent to GAP, and when c = 0. LAP is equivalent to no pooling layer. Results on CIFAR-10 10 are reported in Tables I and 3. Due to space constraint, results on Fashion-MNIST are reported in Tables and 6 in Appendix E. In each table, for each combination of c and d, the first number is the test accuracy without horizontal flip data augmentation (in percentage), and the sec- ond number (in parentheses) is the test accuracy with horizontal flip data augmentation. To perform cross-validation to choose the hyper-parameters, of CIFAR-10 10 and Fashion-MNIST. as the validation set and the rest samples as the training set. We then use the full training set to report the test accuracy. To perform cross-validation. we choose c, d, CNN or CNN-GP, and whether or not to adopt horizontal flip based on the validation accuracy (shown in Appendix F). With cross-validation, the resulting accuracy is 82.09% on CIFAR-10 and 94.07% on Fashion-MNIST.
32 for CIFAR-10
use the last 10000 samples in the training set
We made the following observations regarding our experimental results.
LAP with proper choice of the parameter significantly improves the performance of CNTK and CNN-GP. On CIFAR-10. 10. the serfforfrnmin value of c 12 or 16, while on Fashion- MNIST the best-performing value of is e = 4. We suspect this difference is due to the nature of the two datasets: CIFAR-10 contains real-life images and thus allow more translation, while Fashion-MNIST contains images with centered clothes and thus allow less translation. For both datasets, the best-performing value of c is consistent across all settings (depth, CNTK or CNN- GP) that we have considered.
Horizontal flip data augmentation is less effective on Rashion-MNIS' than on CIFAR-10. There are two possible explanations for this phenomenon. First, most images in Fashion-MNIST nearly horizontally symmetric (e.g.. T-shirts and bags). Second, CNTK and CNN-GP have al- ready achieved relatively high accuracy on Fashion-MNIST, and thus it is reasonable for hori- zontal flip data augmentation to be less effective on this dataset.
Finally, for CNTK, when 0 (no pooling layer) and 32 (GAP) our reported test accuracies are close to those in Arora et al. (2019) on CIFAR-10. 10. For CNN-GP, when e = 0 (no pooling layer) our reported test accuracies are close to those in Novak al. (2019) on CIFAR-10 and Mashion-MNiST. This suggests that we have reproduced previous reported results.
6.2 IMPROVING PERFORMANCE ON CIFAR-10 USING RANDOM PATCHES LAYER
Finally, we explore another interesting question: what is the best performance achievable via a method that is not a trained neural network? To further improve the performance, we com- bine CNTK and CNN-GP with LAP, together with the unsupervised learning approach developed in Coates et al. (2011). Here use the variant implemented in Recht et al. (2019). More specifi- cally, we first sample 2048 random image patches with size 5 x 5 from all training images. Then for the sampled images patches, we subtract the mean of the patches, then normalize them have unit

---

3teature) Under review as a conference paper at ICLR 2020
5
8
11
14
66.55 (69.87)
66.27 (69.87)
65.85
(69.37)
65.47 (68.90)
4
77.06 (79.08)
77.14 (78.96)
77.06 (78.98)
76.52 (78.74)
8
79.24 (80.95)
79.25 (81.03)
78.98 (80.94)
78.65 (80.35)
12
80.11 (81.34)
79.79 (81.28)
79.29 (81.14)
79.13 (80.91)
16
79.80 (81.21)
79.71 (81.40)
79.74 (81.09)
79.42 (81.00)
20
79.24 (80.67)
79.27 (80.88)
79.30 (80.76)
78.92 (80.39)
24
78.07 (79.88)
78.16 (79.79)
78.14 (80.06)
77.87 (80.07)
28
76.91 (78.69)
77.33 (79.20)
77.65 (79.56)
77.65 (79.74)
32
76.79
(78.53)
77.39 (79.13)
77.63 (79.51)
77.63 (79.74)
Table 1: Test accuracy of CNTK on CIFAR-10.
5
8
11
14
c
4
84.63 (86.64)
84.07 (86.23)
83.29
(85.53)
82.57
(84.81)
8
86.36 (88.32)
85.80 (87.81)
85.01 (87.08)
84.57 (86.53)
12
86.74 (88.35)
86.20 (87.90)
85.60 (87.36)
84.95 (86.99)
16
86. 77 (88.36)
86.17 (87.85)
85.60 (87.44)
84.92 (86.98)
20
86.17 (87.77)
85.71 (87.50)
85.14 (87.07)
84.59 (86.84)
Table Test accuracy of random patches layer + CNTK on CIFAR-10.
norm, and finally perform ZCA transformation to the resulting patches. We use the resulting patches as 2048 filters of convolutional layer with kernel size stride 1 and dilation or padding. For an input image æ, we use conv (x) to denote the output of the convolutional layer. As in the implemen- tation in Recht al. (2019), we use (eLU(conv(z)) as the input feature for CNTK and CNN-GP. Here we fix Steature To make the output kernel value invariant under horizontal flip (cf. Defintion 4),,, for each image patch, we horizontally flipped it and add the flipped patch into the convolutional layer as a new filter. Thus, for an input CIFAR-10 image of size 32 x 32, the dimension of the output feature is 8192 x 28 x 28. To isolate the effect of randomness in the choices of the image patches, we fix the random seed to experiment, we set the value of the parameter in LAP to be 4, 8, 12, ... 20 to avoid small and large values of e. The results are reported in Tables and 4. Similar to the experiments Section 6. again set the hyper- parameters by cross- coossvvaidation, and the resulting accuracy is 88.91%. See Appendix F for the validation accuracy for different typer-parametens
Bteature) and ReLU(-convil
as in Recht et al. (2019) and
the bias term 8 in CNTK and CNN-GP to be 3
throughout the experiment. this
From our experimental results, it is evident that combining CNTK or CNN-GP with additional feature extractor can significantly improve upon the performance of using solely CNTK or CNN- GP, and that of using solely the feature extractor Coates al. (2011). Previously, it has been reported in Recht et al. (2019) that using solely the feature extractor Coates et al. (2011) (together with appropriate pooling layer) can only achieve test accuracy of 84.2% using 256, 000 image patches, or 83.3% using 32, 000 image patches. Even with the help of horizontal data augmentation, the feature extractor Coates al. (2011) can only achieve test accuracy of 85.6% using 256, 000 image patches, or 85.0% using 32, 000 image patches. Here we use significantly less image patches (only 2048) but achieve a much better performance, with the help of CNTK and CNN-GP. In particular, we achieve performance of 88.91% % on CIFAR-10, 10, matching the performance of AlexNet on the same dataset. In the setting reported in Coates et al. (2011), increasing the number of sampled image patches will further improve the performance. Here also conjecture that in our setting, further increasing the number of sampled image patches can improve the performance and get close modern CNNs. However, due the limitation computational resources, we leave exploring the effect of number of sampled image patches as a future research direction.
6.3 EXPERIMENTS ON CNN WITH BOX FILTERING LAYER
In Figure I, we verify the effectiveness of BF on a 10-layer CNN (with Batch Normalization) on CIFAR-10. 10. The setting of this experiment is reported in Appendix G. Our network structure has pooling layer except for the BF layer before the last fully-commn conlececddeeedd layer. The fully-connected layer is fixed during the training. Our experiment illustrates that even with fixed last FC layer, using

---

Under review as a conference paper at ICLR 2020
8
11
14
63.53 (67.90)
65.54 (69.43)
66.42
(70.30)
66.81
(70.48)
4
76.35 (78.79)
77.03 (79.30)
77.39
(79.52)
77.35
(79.65)
8
79.48 (81.32)
79.82 (81.49)
79.76 (81.71)
79.69 (81.53)
12
80.40 (82.13)
80.64 (82.09)
80.58 (82.06)
80.32 (81.95)
16
80.36 (81.73)
80.78 (82.20)
80.59 (82.06)
80.41 (81.83)
20
79.87 (81.50)
80.15 (81.33)
79.87 (81.46)
79.98 (81.35)
24
78.60 (79.98)
78.91 (80.48)
79.22 (80.53)
78.94 (80.46)
28
77.18 (78.84)
78.03 (79.86)
78.45 (79.87)
78.48 (80.07)
32
77.00 (78.49)
77.85 (79.65)
78.49 (80.04)
78.45 (80.01)
Table 3: Test accuracy of CNN-GP on CIFAR-10.
5
11
14
85.49 (87.32)
85.37 (87.22)
85.16
(87.11)
84.79 (86.81)
8
87.07 (88.64)
86.82 (88.68)
86.53 (88.40)
86.39 (88.15)
12
87.23 (88.91)
87.12 (88.92)
86.87 (88.66)
86.62 (88.29)
16
87.28
(88.90)
87.11 (88.66)
86.92 (88.61)
86.74 (88.24)
20
86.81 (88.26)
86.77 (88.24)
86.61 (88.14)
86.26 (87.84)
Table 4: Test accuracy random patches layer + CNN-GP on CIFAR-10.
GAP could improve the performance CNN. Our experiments also show that BF with appropriate choice of e achieves better performance than GAP.
Accuracy
Accuracy
92
92
91
average accuracy
average accuracy
90
best test accuracy
best test accuracy
91
10
15
10
15
(a) With Flip Agumentation
(b) Without Flip Agumentation
Figure Test accuracy 10-layer CNN with various values for the parameter in BF.
7 CONCLUSION
In this paper, inspired by the connection between full translation data augmentation and GAP, we derive new operation, LAP, on CNTK and CNN-GP, which consistently improves performance on image classification tasks. Combining CNN-GP with LAP and the pre-processing technique pro- posed by Coates et al. (2011), the resulting kernel achieves 89% accuracy on CIFAR-10, matching the performance of AlexNet and is the strongest classifier that is not trained neural network.
Here we list a few future research directions. Is it possible to develop analogs of CNTK or CNN- GP incorporating modern techniques such as batch norm and residual layers, further improve the performance? Moreover, it an interesting direction to study other components in modern CNNs through the lens of CNTK and CNN-GP.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: .03962, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904.1999 2019.
Olivier Chapelle, Jason Weston, Léon Bottou, and Vladimir Vapnik. Vicinal risk minimization. In Advances in neural information processing systems, pp- 416-422, 2001.
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint arXhv:1907.10903, 2019.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis single-layer networks unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelli- gence and statistics, pp. 215-223, 2011.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Christopher De Sa, and Christopher Ré. A kernel theory of modern data augmentation. arXiv preprint arXiv: 1803. 0603,6684, 2018.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: /8/ 18/1.03804 2018.
Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. ArXiv, 0tss/995513192. 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizeed neural networks. In International Conference on Learning Representations, 2019b.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional net- works shallow gaussian processes. In International Conference on Learning Representations, 2019. URL https::////...........ttt : / openrevi seeervview.. net. forum? d=Bk1 Oc
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and gen- cralization in neural networks. arXiv preprint 1XXiv:8806.0772 2018
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Jaehoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. International Confer- ence on Learning Representations, 2018. URL http://///pppeeeee...es.. htt.eewwwee//ottttaaeeee BIEA-M- 10-0--0222
Yuanzhi Li and Yingyu Liang- Learning overparameterized neural networks via stochastic gradient descent on structured data. arXiv preprint arXiv:1808.01200 2018.
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400, 2013.

---

Under review as a conference paper at ICLR 2020
Julien Mairal. End-to-end kernel learning with supervised convolutional kernel networks. In Ad- vances neural information processing systems, pp. 1399-19-9000 1399-1407, 2016.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv:1804.1227) 2018.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Roman Novak, Lechao Xiao, Yasaman Bahri. Jachoon Lec, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many chan- nels are gaussian processes. In International Conference on Learning Representations, 2019.
wwwp:/ttteetteeteeeeeeeee URL httpttppe///pneeeeeww net/ forum? 1d
Edouard Oyallon and Stéphane Mallat. Deep roto-translation scattering for object classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2865- 2873, 2015.
Benjamin Recht, Rehecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902. 2019.
Bernhard Schölkopf, Chris Burges, and Vladimir Vapnik. Incorporating invariances in support tor learning machines. In International Conference on Artificial Neural Networks, pp. 47-52. Springer, 1996.
Jocelyn Sietsma and Robert JF Dow. Creating artificial neural networks that generalize. Neural networks, 4(1):67-79, 1991.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. arXiv preprint arXiv:1412.6800 2014.
Richard Szeliski. Computer vision: algorithms and applications. Springer Science Business Media, 2010.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmin a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1902.0000 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterizee deep ReLU networks. arXiv preprint arXiv: 1ee.1111..8000 088888, 2018.
10

---

Under review as a conference paper at ICLR 2020
A FORMAL DEFINITIONS OF CNN-GP AND CNTK
We add some additional notations. Let I be the identity matrix, and [n] = {1. 2. 2........., n.. Let e be an indicator vector with i-th entry being 1 and other entries being 0, and let denote the all-one vector. We use @ to denote the pointwise product and & to denote the tensor product. We use diag(-) to transform vector to diagonal matrix. We use a (+) to denote the activation function, such the rectified linear unit (ReLU) function: a (z) = max (z 0}. and o (-) to denote the derivative of a (.). We set Ca Denote by (N,, 2) the Gaussian distribution with mean μ and covariance E.
Equation equation shows patch [w * m)i depends on [a)] - i4 2 J-
2 1f 25
For
(i,j,'', E [P] QQ) [P] [Q), define
Dy,ey {(i + a, b, d', j + +b [P] [Q)
Q
(q 1)/2 a a, . s (q 1)/23.
Now define the convolution operation. For convolutional filter w E R and an image a E IR PxQ, the convolution operator is defined as
W Ejj
[ wit b will [+]ati044 for i E [P].j E (Q)
(2)
e-1
Now we formally define CNN.
Let x: E E be the input image where (10) is the initial number of channels.
For h = 1, l,...,,o L. = I,..., C(A), the intermediate outputs are defined as
()
(h) a
(3) = Σ
(h-1) + b(a), way (a).(8) * (aa)
Co
(1h)
(B)
V
C XQXQ
(9)
where each (h (h)
(a).(2) E R is filter with Gaussian initialization and b(3) is a bias term with Gaussian initialization scaled by
CNN-GP and CNTK
For = I,..., CO,), (P) [Q] [P] X [Q]. define
C(0)
K(0) (a)
(x,x') (a) 2((a) and
Σ (0) (x, x')
tr [ ((x )
Disey 32.
"3.5'"'
9² a=1
E [L],
For (i,j,', E [P] x [Q]
x [P] [Q), define
|Σ(611 1) (x, x) (9.0
1 1) (xx, x²) 19,83
A A (x,x')
(h)
E =R2x2
(x' 1)
Σ 1) (x', x') 11y.)))))
Define K (0, (x,x²) (h) (x) E R rx xxQ for (i. 1' J') E [P] [Q] x [P] x [Q]
K (h) (xxxx')
=co
E
1 (u) (v))
(3)
K3,88g'
(w.0)N (0.1 B. (a,)"))
(k)
K (2(h) a²)
=Cr
E (6.0)
(0(4) (v))
(4)
19.83'
(a)
Define ( (x, x') E PXXXXXX for (1.j,
[P] [Q] [P] x [Q]
(h) (x)
(2r, xt)
1 ij,y T ([x1))(rr x¹) D:g.0 + 82.
Note that E(x, x') and E(x, x') share similar structures as their NTK counterparts (Jacot et al., 2018). The only difference is that have more step, taking the trace over patches. This step represents the convolution operation in the corresponding CNN. Next, we can use a recursion to compute the final kernel value.
11

---

Under review as a conference paper at ICLR 2020
1. First, we define ( (0) ( x.. x').
For 1..... and (i.j,', E [P] x Q x [P] x [Q), we define
( x²)
1 13 Taa tr ([ x') о θ th 11 (2, x') + K (21 2e)) ) + 82.
B ADDITIONAL DEFINITION AND PROOF FOR SECTION 4
Definition B.1 (Group). (G, a group, if and only if
1. each element g E G is a operator: PxQxC - RxxQx;;
Vgi, 92 E 9. 91 92 E g. where (g1 o (2) defined as 91 (92(2=)).
3. Vgi, 92.93 E 9, (gt 92) Is = (92 gs).
Be E 9, such that Vg E, es g = gooe- m-e=g
5. lyy G. 3g2 E G, such that 91 22 g2 gi = We denote g2 as the inverse of gt, namely, 91
Proof of Theorem 4.1. Since we assume K and Kx, are invertible, both a and ā are uniquely defined. Now we claim ãg [ RV is equal to To for all g E g.
By the invariance of K under for all j E [N] and g' E
Σ
K ((g((
E
K(gg o')'(
g
kEEg),Egg
Σ
[E[N]
Σ
o (x,,
a
iE[N]
Note that ā is defined as the unique solution of Kx, ā = yg. the claim has been verified. Similarly, we have
Σ
K(x',g(a
Σ
L.EgeeK(g
Σ (x',
iE(N]
iE[M]
C EQUIVALENCE BETWEEN LAP AND BOx FILTERING LAYER.
For a CNN with box filtering layer before the final fully-connected layer, the final output is defined
as f(0 2am1 (w(l+t)) BF (x((z) )) where x ((()) E RPQQ and (((+1) E RxxQ is the
weight of the last fully-connected layer.
Now we establish the equivalence between BF and LAP on CNTK. The equivalence on CNN- GP can be derived similarly. Let OBF (æz, x²) E IR (I be the CNTK kernel of BF a (.) Since BF just linear operation, we have
(0B (æ, a Dis..
Σ
(0(1) (x, x²)
(2c+ 1)4
A.A.
By the formula of the output kernel value for CNTK without GAP, we obtain
Ln (OBF (xe x²)) = (2c + 1)a
Σ
Σ
0 a "l
12

---

Under review as a conference paper at ICLR 2020
(a) GAP
(b) LAP with
Figure 2: Randomly sampled images with full translation data augmentation and local translation data augmentation from CIFAR- 10. Full translation data augmentation can create unrealistic images that harm the performance whereas local translation data augmentation creates more realistic images.
D EXPERIMENTAL SETUP IN SECTION 6
For both CIFAR-10 and Fashion-MNIST we the full training and report the test accuracy on the full test set. Throughout this section we only consider 3 x 3 convolutional filters with stride and no dilation. the convolutional layers CNTK and CNN-GP, we use zero padding with pad size 1 to ensure the input of each layer has the same size. We use zero padding for LAP throughout the experiment. We perform standard preprocessing (mean subtraction and standard deviation division) for all images.
In experiments, we perform kernel ridge regression utilize the calculated kernel values We normalize the kernel matrices so that all diagonal entries are ones. Equivalently, we ensure all features have unit norm in RKHS. Since the resulting kernel matrices are usually ill-conditioned, set the regularization term À 5 10 10-5, to make inverting kernel matrices numerically stable. We use one-hot encodings the labels as regression targets. We use scipy. linalg. solve to solve the corresponding kernel ridge regression problem.
The kernel value CNTK and CNN-GP are calculated using the CuPy package. We write native CUDA codes to speed up the calculation of the kernel values. All experiments performed on Amazon Web Services (AWS), using (possibly multiple) NVIDIA Tesla V100 GPUs. For efficiency considerations, all kernel values computed with 32-bit precision.
One unique advantage of the dynamic programming algorithm for calculating CNTK and CNN- GP is that we do not need repeat experiments for, say, different values of in LAP and different depths. With our highly-optimized native CUDA codes, we spend roughly 1,000 GPU hours on calculating all kernel values for each dataset.
"We also tried kernel SVM but found significantly degrading the performance, and thus do not include the results.
13

---

Under review as a conference paper at ICLR 2020
E
TEST ACCURACY OF CNTK AND CNN-GP ON FASHION-MNIST
8
11
14
92.25 (92.56)
92.22 (92.51)
92.11 (92.29)
91.76 (92.17)
4
93. 76 (94.07)
93.69 (93.86)
93.55 (93.74)
93.37 (93.58)
93.72 (93.96)
93.67 (93.78)
93.50 (93.58)
93.32 (93.51)
12
93.59 (93.80)
93.58 (93.70)
93.35 (93.44)
93.21 (93.40)
16
93.50 (93.62)
93.42 (93.63)
93.27 (93.40)
93.10 (93.25)
20
93.10 (93.34)
93.17 (93.49)
93.20 (93.34)
92.99 (93.18)
24
92.77 (93.04)
93.07 (93.44)
93.11 (93.31)
93.02 (93.21)
28
92.80 (92.98)
93.08 (93.42)
93.12 (93.28)
92.97 (93.19)
Table 5: Test accuracy of CNTK on Fashion-MNIST.
14
91.47 (91.1)
91.96 (92.37)
92.09 (92.60)
92.22
(92.72)
4
93.44 (93.60)
93.59
(93.79)
93.63 (93.76)
93.59 (93.64)
93.26 (93.16)
93.41 (93.51)
93.31 (93.52)
93.39 (93.46)
12
92.83 (92.94)
93.07 (93.20)
93.11 (93.15)
92.94 (93.09)
16
92.46 (92.51)
92.58 (92.83)
92.64 (92.92)
92.68 (93.07)
20
91.83 (91.72)
92.35 (92.42)
92.49 (92.79)
92.51 (92.69)
24
91.15 (91.40)
92.10 (92.18)
92.29 (92.60)
92.41 (92.77)
28
91.30 (91.37)
92.03 (92.27)
92.41 (92.79)
92.41 (2..74)
Table 6: Test accuracy of CNN-GP on MaShIon-MNIST.
F VALIDATION ACCURACY OF CNTK AND CNN-GP ON CIFAR- 10 AND FASHION-MNIST
d
8
0
64.26 (68.4) 42)
64.47 (68.23)
63.94 (67.80)
63.29
(67.00)
75.97 (78.87)
75.89 (78.99)
75.65 (78.56)
75.40 (78.19)
8
77.93 (80.65)
77.90 (80.69)
77.65 (80.41)
76.92 (79.94)
12
78.51 (80.73)
78.47 (80.85)
78.18 (80.57)
77.71 (80.19)
16
78.47 (80.39)
78.69 (80.56)
78.34 (80.17)
77.74 (79.97)
20
77.86
(79.69)
77.81 (79.81)
77.38 (79.55)
76.88 (79.46)
24
76.59
(78.12)
76.80 (78.63)
76.44 (78.79)
76.18 (78.73)
28
75.44
(77.08)
76.15 (78.20)
76.10 (78.30)
75.95 (78.37)
32
75.33 (76.99)
76.04 (78.09)
76.08 (78.27)
75.99 (78.32)
Table 7: Validation accuracy of CNTK CIFAR-10.
14

---

Under review as a conference paper at ICLR 2020
5
11
14
62.49 (66.63)
64.25 (68.20)
64.94 (69.01)
65.35 (69.29)
4
75.31 (78.59)
76.05 (79.20)
76.05 (79.17)
76.20 (79.09)
8
78.17 (81.02)
78.53 (81.29)
78.36 (81.20)
78.05 (80.98)
12
79.19 (81.38)
79.08 (81.66)
79.13 (81.52)
78.90 (81.10)
16
79.26 (81.18)
79.24 (81.37)
78.85 (81.33)
78.82 (80.84)
20
78.72 (80.61)
78.72 (80.85)
78.45 (80.60)
78.08 (80.22)
24
77.31 (79.01)
77.59 (79.49)
77.41 (79.56)
77.26 (79.38)
28
76.01
(77.60)
76.60 (78.32)
76.57 (78.76)
76.86 (79.01)
32
75.72 (77.54)
76.42 (78.47)
76.56 (78.94)
76.63 (78.87)
Table 8: Validation accuracy of CNN-GP on CIFAR- 10.
8
14
83.89
(85.76)
83.13
(85.40)
82.62 (84.95)
82.02
(84.43)
8
85.52
(87.59)
84.88
(87.12)
84.30 (86.69)
83.84
(86.10)
12
85.71
(87.85)
85.32 (87.42)
84.81
(87.02)
84.26 (86.58)
16
85.68
(87.76)
85.19 (87.30)
84.71
(86.83)
84.47 (86.40)
20
85.26
(87.11)
84.91 (86.67)
84.44 (86.40)
84.09 (86.17)
Table 9: Validation accuracy of additional feature extractor + CNTK on CIFAR-10.
5
11
14
84.03 (86.16)
84.21 (86.38)
84.15 (86.33)
83.98
(86.04)
8
85.85 (87.94)
85.87 (88.03)
85.70 (87.87)
85.49
(87.62)
12
86.37 (88.3)
86.38 (88.25)
86.06 (88.12)
85.69 (87.82)
16
86.06
(88.22 28)
86.21 (88.05)
86.01 (87.87)
85.58
(87.74)
20
85.73
(87.71)
85.79 (87.60)
85.73 (87.54)
85.27 (87.21)
Table 10: Validation accuracy of additional feature extractor + CNN-GP on CIFAR-10.
5
8
11
14
92.07 (92.30)
92.08 (92.21)
91.79 (91.99)
91.51 (91.72)
4
93.84 (93.96)
93.82 (93.83)
93.58 (93.74)
93.40
(93.57)
93.82 (93.96)
93.80 (93.77)
93.56 (93.71)
93.37 (93.57)
12
93.71 (93.83)
93.60 (93.72)
93.45 (93.58)
93.41
(93.45)
16
93.59 (93.73)
93.39 (93.63)
93.34 (93.53)
93.21 (93.45)
20
93.24 (93.44)
93.29 (93.42)
93.26 (93.30)
93.19 (93.31)
24
93.16 (93.28)
93.21 (93.39)
93.30 (93.32)
93.22 (93.32)
28
93. (93.23)
93.21 (93.33)
93.29 (93.29)
93.28 (93.31)
Table 11: Validation accuracy of CNTK on Fashion-MNIST.
15

---

Under review as a conference paper at ICLR 2020
5
11
14
0
91.13
(91.43)
91.57 (91.77)
91.85 (91.92)
91.94 (92.08)
4
93.44 (93.55)
93.57 (93.54)
93.69 (93.68)
93.58 (93.64)
8
93.57 (93.67)
93.51 (93.68)
93.52 (93.72)
93.44 (93.58)
12
93.15 (93.36)
93.49 (93.59)
93.25 (93.52)
93.23 (93.44)
16
92.83 (92.84)
93.01 (93.19)
93.01 (93.27)
92.95 (93.18)
20
92.29 (92.45)
92.60 (92.82)
92.60 (92.93)
92.78 (93.10)
24
91.76
(92.04)
92.28 (92.63)
92.57 (92.86)
92.58 (92.78)
28
91.79 (92.00)
92.32 (92.56)
92.56 (92.77)
92.70 (93.00)
Table 12: Validation accuracy of CNN-GP on Feshion-MNIST.
G SETTING OF THE EXPERIMENT IN SECTION 6.3
The total number of training epochs is 80, and the learning rate is 0.1 initially, decayed by 10 at epoch 40 and 60 respectively. The momentum is 0.9 and the weight decay factor is 0.0005. In Figure 1, the blue line reports the average test accuracy of the last epochs, while the red line reports the best test accuracy of the total 80 epochs. Each experiment is repeated for 3 times. We use circular padding for both convolutional layers and the BF layer. The last data point with largest r-coordinate reported in Figure corresponds to GAP.
16


Reviews:
[{"review_id": "ryltv8TTFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers architectures that do not involve learning (up to the classification layer) and tries to improve their accuracies. They're based on CNTK and CNN-GP works. This is purely a numerical paper and its contribution is to show that despite being not learned, the obtained representations are competitive with supervised neural networks.\n\nOverall, despite the fact if I find this numerical result interesting, I found too many flaws to justify its acceptance. (fine tuning on the test set, lack of comparison with the state of the art...) \n\nPros:\n- Good numerical performances.\n\nCons:\n- Given the claim in the abstract about accuracies, it should be pointed out that: \n* in the unsupervised setting, with a kernel engineering method, you can obtain ~86% on cifar10 (cf https://arxiv.org/abs/1605.06265 )\n* in the no-data(up to a linear model) setting, it is possible to get ~82% on cifar10 with the scattering networks (cf https://arxiv.org/abs/1412.8659 )\nThose two works are also mainly empirical, and thus some accuracies of this paper should be compared to them.\n- There is a significant amount of experiments (table 1/2/3/4). While this should have been a positive aspect of the paper, I noticed that the accuracies reported here are computed from the test set. A validation set should have been used with a careful cross-validation. I'm aware this is a standard practice in deep learning, yet here it seems obvious to me that some hyper parameters have been fine-tuned on the testing set.\n- Section 4: isn't it a rephrasing of (Dao et al, 2018)? (which is cited) I think this should be clearly stated.\n- Section 5: The paper cites the Local Average Pooling as a \"new operation\", but this is clearly standard in the literature. \"Boxblurring\" has always been named average pooling in deep learning, low-pass filtering in signal processing. It was used before researchers employ a stride of 2 in convolutions. A similar pooling is also present in https://arxiv.org/abs/1605.06265  \n- I'm nicely surprised that the authors didn't encounter any significant conditioning issues. Would it be possible to show the spectrum of the kernel? This could be commented.\n- Nothing about the future release of the code is indicated.\n\nMinor:\n- I find the Figure 1 is not informative to the reader.\n\nPost-discussion:\nThe revision clarifies all my concerns and this work is likely to induce interesting discussions.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1gzyEd6FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper builds on recent developments of CNN-GP and CNTKs in multiple fronts obtaining significant performance boost on CIFAR-10 dataset (and some mild boost on Fashion-MNIST). One way is by usage of Local Average Pooling (LAP) layers which interpolates between Global Average Pooling (GAP) and no Pooling layer. The authors also introduce flip data augmentation by doubling the dataset. With the help of additional feature extractor, this paper obtained 89% classification accuracy on CIFAR-10 which is the best among methods not using trained neural networks. \n\nThe discussion on section 4 regarding augmented kernel and data augmentation is quite clear and revealing. It’s unfortunate that the flip augmentation could not be introduced in kernel level. It would be interesting for future work to find kernel operation similar to GAP that encodes symmetries of the dataset. \n\nWhile the paper is clearly written and the results are strong, there are few criticisms I’d like to address and hope the authors address. \n\nAFAIK both GAP and LAP for CNN-GP are already introduced and analyzed in [1]. It seems best results on CIFAR-10 all comes from CNN-GP (with without flip augmentation, with and without using extra feature extractor), and I think the authors should properly credit [1] for GAP/LAP in convolutional kernels. It’s fair that this paper along with [2] was able to efficiently implement and scale up to  full CIFAR-10 dataset and demonstrated pooling layer’s full potential for kernels corresponding to infinitely wide CNNs. Also in this regard the title could be misleading. It’s strange to have paper’s strongest result is based on CNN-GP while the title only mentions CNTK.\n\nAs the author’s mention in the paper, Box Blur is just an average pooling operation. This is already widely use by practitioners(e.g. [3]) and I don’t understand how author’s claim: “This operation also suggests a new pooling layer for CNNs which we call BBlur” \n\nFew question/comments:\n\nBest parameters for trained CNN’s BBlur c is smaller than best c values for kernels, do authors understand the cause of discrepancy? \n\nIt would benefit the research community if authors could share code to generate the CNN-GP Kernels / CNTKs with LAP.  Also I would encourage authors to share actual numerical values of kernel matrix for other research groups to analyze and encourage reproducibility.\n\n\n[1] Novak et al., Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes, ICLR 2019\n[2] Arora et al., On Exact Computation with an Infinitely Wide Neural Net, NeurIPS 2019\n[3] Huang et al., Densely Connected Convolutional Networks, CVPR 2017\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Byxqt4VztH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that there is a one-to-one correspondence between pixel-shift based data augmentation and average pooling operations in CNN-NNGP/NTK based ridge regression. Interestingly, the authors show that standard average pooling + flatten can lead to a better performance than simple global average pooling. This paper further shows that using the data pre-processing step proposed in (Coates et al., 2011) can boost performance of CNN-NNGP/NTK based ridge regression by ~7% which allowed the authors to achieve classification accuracy in high 80s which is AFAIK SOTA on CIFAR-10 when not using learned representations.\n\nMy current assessment of the paper is “weak accept”. There are two main reasons why I am on the verge of recommending rejection of this paper: (1) I believe that the experiment evaluation is not done entirely correctly leading to inflation of the reported results (my guesstimate is by ~0.5-2%)---please see my “Major comments”. If this is not fixed, I am very likely to downgrade my score. (2) While the observation of the relationship between pixel-shifts and average pooling is very nice (which is why my current score is “weak accept”), it seems that most of the improvement comes from application of the pre-processing step of Coates et al. (2011) (seems like a ~7% improvement!). Given the large computational cost of CNN-NNGP/NTK (authors say about 1000 GPU hours), I wonder whether a simpler algorithm like some of the newer variants of boosting combined with the Coates et al. algorithm wouldn’t also perform at around 87-88% like CNN-NNGP/NTK (given the baseline 85-86% accuracy of the Coates et al. (2011) algorithm reported by the authors).\n\n\nMajor comments:\n\n- Can you please clarify why you decided to give a new name (Box Blur) to standard average pooling? Why not just use the existing name?\n\n- I believe that the way you report results in all the tables (i.e., tables 1-6) and the text based upon them is flawed. The right approach would be to select the hyperparameters “c” and “d” on a validation set, and then report the performance with these hyperparameters on the test set. While the experiments are somewhat rescued by the fact that you report results for (almost) all the possible hyperparameter settings (which allows us to see samples from the population distribution of the generalisation error), type-setting the best results in boldface and thus implying that these are valid estimates of the generalisation error is not appropriate since you are effectively selecting the best hyper-parameters on the test set! Unfortunately, I cannot accept these results to be published “as-is”. While re-running the experiments with hyperparameter selection on validation set is already a somewhat imperfect solution, I am not sure I can see a better way forward. However, I do understand that this could be prohibitively expensive in which case I would like to ask you to suggest an alternative solution please (of course, other reviewers are welcome to chime in as well)?!\n\n- While most of the paper is about Local Average Pooling (LAP) and the equivalence between averaging and pixel shifts, the experimental results seem to show that most of the improvement comes from the use of Coates et al.’s preprocessing step. Could you please run the experiments in tables 3 and 4 with c=0 and c=32 to see what the effect of the preprocessing is without LAP?\n\n- In sect.6.3, you say “Our experiment illustrates that even with a fixed last FC layer, using GAP could improve the performance of CNN, and challenges the conjecture that GAP reduces the number of parameters in the last fully-connected layer and thus avoids overfitting.” I am not sure I see why fixing the last FC layer should provide more convincing evidence than training it? I do not know the conjecture to which you refer but from your description, the overfitting without GAP should occur because the FC layer has more parameters than with GAP?! If this is true, then the overfitting would happen in the last layer (due to the large number of parameters) which you have (at least partially) prevented by not training it?! Can you clarify and also report the results of this experiment with all the layers trained please?\n\n- In Appendix D, you say that you have used lambda = 10^{-5} for all configurations. How have you selected this particular value please? Do you have a sense of how far from optimal this value is for all the different configurations (or at least for NTK vs NNGP models---in my experience, the optimal setting between the two can differ quite a bit)?\n\n\nMinor comments:\n\n- In the abstract and throughout the paper, you claim that the cost of kernel regression is quadratic. AFAIK without any approximations, the cost is cubic (or O(n^{2.67}) to be more precise). Please clarify.\n\n- In par.1 on p.1, you say “convolutional neural networks (CNNs) whose width (number of channels in convolutional layers) **goes to infinity**” (emphasis mine) and cite the Jacot et al. (2018) paper. AFAIK this paper only works with infinite networks but does not actually prove that **deep** networks of finite width (in each layer) converge to the NTK limit; IMHO you should cite the Allen-Zhu et al. (2018) and Du et al. (2018) papers from your references for that result. Based on p.2 (end of par.2 in sect.2), you seem to be aware of this distinction but cite Arora et al. (2019) instead of these two; I would suggest either citing Allen-Zhu et al. and Du et al. only, or citing all three as the Arora et al. paper came out later than the first versions of the other two paper which AFAIK already contained all the necessary derivations (even if the words “Neural Tangent Kernel” were not spelled out there).\n\n- Also in par.1 on p.1, you say that Arora et al. (2019) was the first to provide an algorithm to compute the CNTK kernel which is a bit of a stretch given that both Garriga-Alonso et al. (2019) and Novak et al. (2019) have implemented the CNTK kernel in their experiments. AFAIK the claim in (Arora et al., 2019) is that they provided first **efficient** implementation of the CNTK-GAP kernel which should be made clearer in the next revision of your paper.\n\n- On p.2, you say “These kernels correspond to neural networks where only the last layer is trained.” In reality, the correspondence is not exact for finite networks because the induced kernel will not be exactly equal to the one at the limit.\n\n- Bottom of p.2, “Global Average Pooling (GAP) is proposed” -> “... was proposed”.\n\n- Top of p.3, “..., and GAP is more robust” -> “..., and that GAP is more robust”.\n\n- On p.3 in the “Padding Schemes” paragraph, do you mean to assume that the input image has only a single channel (not necessary later)?\n\n- On p.4, I am slightly confused by your definition of the “augmented kernel”. Specifically, it does not seem K^G (x , x’) = K^G (x’, x) holds in general. Can you please clarify? If there’s no symmetry, I do not think it necessary to use a different name, but perhaps a clarifying note would be beneficial to the reader?!\n\n- On p.5, fig.1 is too small when printed and one needs to use the computer screen to see what is depicted; given the amount of white space around, can you please try to make the images larger (you can perhaps also only include 2 or 4 images instead of 16 which will give you additional space)?\n\n- On p.5, you say that for small “c”, circular padding will not create unrealistic images. Looking at fig.1b, it seems like the images are not as unrealistic as in fig.1a but human eye can still tell they are not realistic (potentially even more so with other images than the one selected for this figure). I am not sure whether there is a reason to assume this issue does not affect CNNs too?! Further, I am not convinced the motivation is correct in the first place given that the optimal “c” for CIFAR-10 is 12 which will presumably create clearly unrealistic images; perhaps it would be best to omit this motivation?!\n\n- On p.6, you claim “Another advantage of LAP is that it **does not incur any extra computational cost**” (emphasis mine) while at the next line you say that there is a constant additional computational cost. Perhaps say that the extra computational cost is relatively small?\n\n- It might be nice to swap tables 3 and 4 so at least the results for NNGP are next to each other. Even better would be the current table 3 was closer to table 1 to achieve the same effect for NTK.\n\n- I am not sure I fully understand the description in sect.6.3: isn’t the number of channels on the input irrelevant after computation of the kernel in the first layer? In other words, why have you opted to use only 2,048 patches in your experiments and not 32,000 or 256,000 as used by Recht et al. (2019)? Do you have an estimate of how different could the performance of NNGP/NTK be with the larger number of features? Do you know what is the performance of Coates et al.’s algorithm with only 2,048 features? Relatedly, do you know how AlexNet would perform if its PCA data augmentation was replaced by the Coates et al.’s feature extractor?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was assessed by three reviewers who scored it as 6/3/6. 
The reviewers liked some aspects of this paper e.g., a good performance, but they also criticized some aspects of work such as inventing new names for existing pooling operators, observation that large parts of improvements come from the pre-processing step rather than the proposed method, suspected overfitting.  Taking into account all positives and negatives, AC feels that while the proposed idea has some positives, it also falls short of the quality required by ICLR2020, thus it cannot be accepted at this time. AC strongly encourages authors to go through all comments (especially these negative ones), address them and resubmit an improved version to another venue.


Decision: Reject