Title: No title found

Abstract: Recent work has focused on combining kernel methods and deep learning. With this in mind, we introduce Deepström networks -a new architecture of neural networks which we use to replace top dense layers of standard convolutional architectures with an approximation of a kernel function by relying on the Nyström approximation. Our approach is easy highly flexible. It is compatible with any kernel function and it allows exploiting multiple kernels. We show that Deepström networks reach state-of-the-art performance on standard datasets like SVHN and CIFAR100. One benefit of the method lies in its limited number of learnable parameters which make it particularly suited for small training set sizes, e.g. from 5 to 20 samples per class. Finally we illustrate two ways of using multiple kernels, including a multiple Deepström setting, that exploits a kernel on each feature map output by the convolutional part of the model.

1. INTRODUCTION:

Kernel machines and deep learning have mostly been investigated separately. Both have strengths and weaknesses and appear as complementary family of methods with respect to the settings where they are most relevant. Deep learning methods may learn from scratch relevant features from data and may work with huge quantities of data. Yet they actually require large amount of data to fully exploit their potential and may not perform well with limited training datasets. Moreover deep networks are complex and difficult to design and require lots of computing and memory resources both for training and for inference. Kernel machines are powerful tools for learning nonlinear relations in data and are well suited for problems with limited training sets. Their power comes from their ability to extend linear methods to nonlinear ones with theoretical guarantees. However, they do not scale well to the size of the training datasets and do not learn features from the data. They usually require a prior choice of a relevant kernel amongst the well known ones, or even require defining an appropriate kernel for the data at hand. Although most research in the field of deep learning seems to have evolved as a "parallel learning strategy" to the field of kernel methods, there are a number of studies at the interface of the two domains which investigated how some concepts can be transferred from one field to another. Mainly, there are two types of approaches that have been investigated to mix deep learning and kernels. Few works explored the design of deep kernels that would allow working with a hierarchy of representations as the one that has been popularized with deep learning (2; 14; 7; 6; 20; 23) . Other studies focused on various ways to plug kernels into deep networks (13; 24; 5; 12; 25) . This paper follows this latter line of research, it focuses on convolutional networks. Specifically, we propose Deepström networks which are built by replacing dense layers of a convolutional neural network by an adaptive approximation of a kernel function. Our work is inspired from Deep Fried Convnets (24) which brings together convolutional neural networks and kernels via Fastfood (9), a kernel approximation technique based on random feature maps. We revisit this concept in the context of Nyström kernel approximation (22) . One key advantage of our method is its flexibility that enables the use of any kernel function. Indeed, since the Nyström approximation uses an explicit feature map from the data kernel matrix, it is not restricted to a specific kernel function and not limited only to RBF kernels, as in Fastfood approximation. This is particularly useful when one wants to use or learn multiple different kernels instead of a single kernel function, as we demonstrate here. In particular we investigate two different ways of using multiple kernels, one is a straightforward extension to using multiple kernels while the second is a multiple Deepström variant that exploits a Nyström kernel approximation for each of the feature map output by the convolutional part of the neural network.

Furthermore the specific nature of our architecture makes it use only a limited number of parameters, which favours learning with small training sets as we demonstrate on targeted experiments.

Our experiments on four datasets (MNIST, SVHN, CIFAR10 and CIFAR100) highlight three important features of our method. First our approach compares well to standard approaches in standard settings (using ful training sets) while requiring a reduced number of parameters compared to full deep networks and of the same order of magnitude as Deep Fried Convnets. This specific feature of our proposal makes it suitable for dealing with limited training set sizes as we show by considering experiments with tens or even fewer training samples per class. Finally the method may exploit multiple kernels, providing a new tool with which to approach the problem of multiple kernel learning (MKL) (4), and enabling taking into account the rich information in multiple feature maps of convolution networks through multiple Deepström layers.

The rest of the paper is organized as follows. We provide background on kernel approximation via the Nyström and the random Fourier features methods and describe the Deep Fried Convnet architecture in Section 2. The detailed configuration of the proposed Deepström network is described in Section 3. We also show in Section 3 how Deepström networks can be used with multiple kernels. Section 4 reports experimental results on MNIST, SVHN, CIFAR10 and CIFAR100 datasets to first provide a deeper understanding of the behaviour of our method with respect to the choice of the kernels and the combination of these, and second to compare it to state of the art baselines on classification tasks with respect to accuracy and to complexity issues, in particular in the small training set size setting.

2. BACKGROUND ON KERNEL APPROXIMATION AND DEEP FRIED CONVNETS:

Kernel approximation methods have been proposed to make kernel methods scalable. Two popular methods are Nyström approximation (22) and random features approximation (16) . The former approximates the kernel matrix by an efficient low-rank decomposition, while the latter is based on mapping input features into a low-dimensional feature space where dot products between features approximate well the kernel function.

Nyström approximation (22) It computes a low-rank approximation of the kernel matrix by randomly subsampling a subset of instances. Let consider a training set of n training samples,

x i ∈ R d , i = 1, .., n , K be the kernel matrix defined as K(i, j) = k(x i , x j ), ∀ i, j ∈ [1, . . . , n] and L be a subset of examples L = {x i } m i=1 which is selected from the training set. Assuming the subset includes the first samples, or rearranging the training samples this way, K may be rewritten as:

K = K 11 K T 21 K 21 K 22 ,

where K 11 is the Gram matrix on subset L. Nyström approximation is obtained as follows

K K = K 11 K 21 K -1 11 K 11 K T 21 .

From this approximation the Nyström nonlinear representation of a single example x is given by

EQUATION

where k x,L = [k(x, x 1 ), . . . , k(x, x m )] T with x i ∈ L.

Random features approximation (16) It computes a low-dimensional feature map φ of dimension

q such that φ(•), φ(•) = k(•, •) k(•, •).

Two instances of this method are Random Kitchen Sinks (RKS) and Fastfood (17; 9). RKS approximates a Radial Basis Function (RBF) kernel using a random feature map defined as

EQUATION

where z ∈ R p , Q ∈ R q×p and Q i,j are drawn randomly. If Q i,j are drawn according to a Gaussian distribution then the method is shown to approximate the Gaussian kernel, i.e. φ rks (x 1 ),

φ rks (x 2 ) ≈ exp(-||x1-x2|| 2 σ

) where σ is the hyper-parameter of the kernel. Note that σ is related to the parameters of the Gaussian distribution that generate the random features.

The Fastfood method ( 9) is a variant of RKS with reduced computational cost for the Gaussian kernel. It is based on approximating the matrix Q in Eq. 2, when q = p, by a product of diagonal and hadamard matrices according to

V = 1 σ √ p SHGΠHB,

where S,G and B are diagonal matrices of size p × p, Π ∈ {0, 1} p×p is a random permutation matrix, H is a Hadamard matrix which does not requite to be stored, and σ is an hyperparameter.

Matrix V may be used in place of Q in Eq. 2 to define the Fastfood nonlinear representation map

EQUATION

Note that this definition requires p to be a power of 2 to take advantage of the recursive structure of the Hadamard matrix. Note also that to reach a representation dimension q > p one may compute multiple V and concatenate the corresponding φ f f .

Deep Fried Convnets (24) Our attention in this work is especially focused on combining kernel approximation with deep learning architecture. Deep Fried Convnets is a deep learning architecture that replaces dense layers of a convolutional neural architecture by a Fastfood approximation of a kernel. This allows to take advantage of the low complexity cost in terms of computation and memory of Fastfood to reduce significantly the computation cost and the number of parameters of the fully-connected layers of the deep convolutional neural network. More formally, let conv(x) be the representation of the data sample x learned by a convolutional neural network. It may include a number of convolution blocks, each including convolution and pooling layers, batch normalization and nonlinear activation. In Deep Fried Convnets, an input x ∈ R d is mapped to the representation spaces conv(x) ∈ R p and then the Fastfood feature map φ f f is applied to the convolutional representation conv(x) instead of the fully-connected layers. The feature representation of x with Deep Fried Convnets is then (

φ f f •conv)(x) ∈ R q .

It is of note that this method is dedicated to RBF kernels. In (24) , wo architectures have been proposed. The first one relies on the Fastfood kernel approximation method as described above. The second one is a variant of Fastfood called Adaptive-Fastfood. It involves learning the weights of matrices S, G and B through gradient descent rather than setting them randomly, while matrices Π and H are kept unchanged.

In the next section we introduce Deepström Networks as an alternative to Deep Fried Convnets. They are based on Nyström approximation and are not limited to RBF kernels. They also allow the use of multiple different kernels and find an appropriate kernel function.

3 Deepström NETWORKS

In this section, we describe our new Deepström model which combines the desirable characteristics of Nyström approximation and convolutional neural networks. First, we start by revisiting the concept of Nyström kernel approximation from a feature map perspective.

Nyström approximation from an empirical kernel map perspective The empirical kernel map is an explicit n-dimensional feature map that is obtained by applying the kernel function on the training data x i (18) . It is defined as

EQUATION

An interesting feature of the empirical kernel map is that if we consider the inner product in R n •, • M = •, M • with a positive semi-definite (psd) matrix M , we can recover the kernel matrix K using the empirical kernel map by setting M equals to the inverse of the kernel matrix. In other words,

K emp := φ emp (x i ), φ emp (x j ) K -1 n i,j=1 = K.

Since K is a psd matrix, one can consider the feature φ emp : x → K -1/2 φ emp (x) as an explicit feature map that allows to reconstruct the kernel matrix. This feature map is of dimension n and then is not interesting when the number of example is large. The feature map of the Nyström approximation is given by

φ nys (x) = k x,L K -1 2 11 ,

where k x,L = [k(x, x 1 ), . . . , k(x, x m )] T with x i ∈ L. From an empirical kernel map point of view,φ nys (x) can be seen as an "empirical kernel map" (18) and K -1 2 11 as a metric in the "empirical feature space". From this viewpoint, we think that it could be useful to learn a metric W in the empirical feature space instead of assuming it to be equal to K -1 2 11 . In a sense, this should allow to learn a kernel by learning its Nyström feature representation. In the following, we call the setting where W is learned by the network Adapative Deepström Network.

Principle Deepström networks we propose are an alternative to Deep Fried Convnets. They are based on using the Nyström approximation rather than the Fastfood one to integrate any kernel function on top of convolutional layers of a deep net. Indeed, although Deep Fried Convnets yield state-of-the-art results with a significant gain with respect to memory resource and to inference complexity, it is restricted to the Gaussian kernel Fastfood, which may not be always the best choice in practice. In addition, our method can deal with multiple kernels. Deepström nets are Neural Networks that make use of a nonlinear representation function computed with the Nyström approximation (see Figure 1 ). Starting from Deep Fried Convnets we replace φ f f with φ nys so that a Deepström net implements a function f (x) = (lc • φ nys • conv)(x). In order to compute the above Nyström representation of a sample x one must consider a subsample L of training instances. Since the kernel k is computed on the representations given by convolutional layers, the samples in L must be represented in the same space, and hence must be processed by the convolutional layers as well. Once convolutional representations are calculated, the kernel function may be computed with an input sample and each instance in L in order to get the k x,L , which is then linearly transformed by W before the linear classification layer (see Figure 1 ).

Two main structural differences between Deep Fried Convnets and our Deepström nets: (I) Nyström has the flexibility to use different kernel functions and to combine multiple kernels, and (II) in contrast to Fastfood the Nyström approximation is data dependent. However, one problem arises with the computation of K -1 2 11 which requires the computation of the Singular Value Decomposition (SVD) of K 11 . In the case where the size of the subsample L, m, is large, the computational complexity of the SVD is O(m 3 ).This issue can be at least partially settled via Adaptative-Deepström network where, instead of setting the weights W as in Eq. 3, we learn these weights as parameters of the 

4. EXPERIMENTS:

We present a series of experimental results that explore the potential of Deepström networks with respect to various classification settings. First we consider a rather standard setting and compare our approach with standard models on image classification tasks. We explore in particular the behaviour of Deepström networks with various kernels and stress the very limited subsample size needed to reach state-of-the-art accuracy. Next we investigate the use of Deepström networks in a small training set setting, which shows that our approach may allow to learn new classes with only very few training samples, taking advantage of the reduced number of parameters learned by our model. Before describing all these results we detail the datasets used. Finally we investigate first the multiple kernel architecture and illustrate its interest when learning with RBF kernel to overcome the hyperparameter selection, and second we demonstrate the benefit of a multiple Deepström approach, combining kernels computed from individual feature maps.

4.1. EXPERIMENTAL SETTINGS:

We conducted experiments on four well known image classification datasets: MNIST (11) , SVHN (15) , CIFAR10 and CIFAR100 (8), details on these datasets are provided in Table 1 . We pretrained the convolutional layers using standard architectures on both datasets: Lenet (10) for MNIST and VGG19 (19) for SVHN, CIFAR10 and CIFAR100. We slightly modified the filters' sizes in Lenet network to ensure that the dimension of data after the convolution blocks is a power of 2 (needed for the Deep Fried Convnets architecture).

We compare three convolutional architectures in all conducted experiments. Pretrained convolutional parts are shared by the three architectures, which differ from the layers on top of it: (1) Dense architectures use dense hidden layers, i.e. these are classical convnets architectures ; (2) Deep Fried implements the Fastfood approximation (Equation 3) ; (3) Deepstrom stands for our proposal.

For Dense architectures, we considered one hidden layer with relu activation function, and varied the output dimension as {2, 4, 8, 16, 32, 64, 128, 1024} in order to highlight accuracies as a function of the number of parameters. For the Fastfood approximation in Deep Fried Convnets we consider that φ f f is gained with one stack of random features to form V in equation 3, except in the experiments of section 4.3 which yields a representation dimension up to 5 times larger. Regarding our approach φ nys , we varied the subset size L ∈ {2, 4, 8, 16, 32, 64, 128}, we tested with the linear, the RBF, and the Chi2 kernels, and we chose as output dimension the same size as the subset sample size. Finally we explored the adaptive as well as non-adaptive variants.

Models were learned to optimize the cross entropy criterion with Adam optimizer and a gradient step fixed to 1e -4 . Dropout was used on representation layers with probability equal to 0.5. By default the RBF bandwidth was set to the inverse of the mean distance between the representations, after the convolutional part, of pairs of training samples. All experiments were performed with Keras (3) and Tensorflow (1). Note that the aim of all the experiments below is to investigate the potential of out architecture, not to reach or beat state of the art results on the datasets considered. We then compare results gained with our architecture and with state-of-the-art models, given a shared convolutional model. Consequently, we did not use tricks such as data augmentation and extensive tuning and, in particular, we did not use the best known convolutional architecture for each of the dataset, we rather used a reasonable deep architecture, VGG19, for the three datasets CIFAR10, CIFAR100 and SVHN.

4.2. EXPLORING THE POTENTIAL OF THE METHOD:

We compare now Deepström networks to two similar architectures, Deep Fried Convnets and classical convolutional networks (inspired from VGG19 and Lenet depending on the dataset). We vary the number of parameters of each architecture in order to highlight classification accuracy with respect to needed memory space.

Figure 2 shows the compared networks accuracy with respect to the number of parameters, and ignore parameters for convolutions layers to ease the readability. We repeated each experiments 10 times and plot average scores with standard deviations. Deepström models of increasing complexity (number of parameters) correspond to the use of subsample of increasing size from 2 (leftmost point) to 128 (rightmost point). One may see that there is no need of a large subsample here. This may be explained since the convolutional part of the network has been learned to yield quite robust and stable representations of input images. We provide a figure in the Appendix that illustrates this.

The Deepström network is able to reach state-of-the-art performance using much fewer parameters than both classical networks and Deep Fried Convnets. Moreover, we also observe smaller variations that points out the robustness of our model. The flexibility in the choice of the kernel function is a clear advantage of out method. The best kernel is clearly dependent on the dataset (linear on MNIST, Chi2 on SVHN and CIFAR100, RBF on CIFAR10). While Random Features in DeepFried are restricted to RBF kernels, we show for instance a gain by using the Chi2 Kernel (k(

x 1 , x 2 ) = ||x 1 -x 2 || 2 /(x 1 +x 2 ))

that had been used for image classification (21) . We also notice the benefit of adaptive variants of Deepström model, suggesting that our model is able to learn and adapt useful Kernel function.

Finally, note that we obtained very similar results with neural architectures exploiting two hidden layers instead of one after the convolution module conv.

4.3. LEARNING WITH SMALL TRAINING SETS:

Here we explore the ability of our model to work with few training samples, from very few to tens of samples per class. It is an expected benefit of the method since the use of kernels could take advantage of small training samples.

Note that we do not exactly deal with a real small training set setting. These preliminary experiments aim to show how the final layers of a convolutional model may be learned from very few samples, given a frozen convolutional model. We actually performed the following experiments by exploiting a trained convolution model conv that has been learned on the full CIFAR100 training set and investigate the performance of Deepström architectures as a function of the training set used to learn the classification layers. One perspective of this work is to exploit such a strategy for domain adaptation settings where the convolutional model is trained on a training set within a different domain as the classes to be recognized.

Having at our disposal such a trained convolution model conv, we leverage on the additional information that one may easily include in our models, which is brought by the subsample set. Notice that this subsample may include unlabeled samples since their labels are not used for optimizing the model. First we exploited the Multiple Kernels strategy that we described in section 3 for exploiting multiple kernels in the output of the convolutional blocks, conv. Second, we investigated another architecture that exploits Multiple Deepström approximations as presented in section 3. Here we use in parallel multiple Nyström approximations where kernels are dedicated to deal each with the output of a single feature map of the conv part. Table 3 reports results on CIFAR100. We show the best performances obtained for each method by grid-searching on various hyper-parameters depending on the models, within a similar range of number of parameters.

For Dense model, we considered one or two hidden layers of 16, 64, 128, 1024, 2048 or 4096 neurons. Deepfried is the adaptive variant where we varied the number of stacks in 1, 3, 5, 7. Deepström is also the adaptive variant where the subsample size is in 16, 64, 128, 256, 512. We observe that both Deepström models outperform the considered baselines, demonstrating the interest in combining Deepström approximations.

5. CONCLUSION:

We proposed Deepström, a new hybrid architecture that mixes deep networks and kernel methods. It is based on the Nyström approximation that allow considering any kind of kernel function in contrast to Deep Fried Convnets. Our proposal allows reaching state of the art results while significantly reducing the number of parameters on various datasets, enabling in particular learning from few samples. Moreover the method allows to easily deal with multiple kernels and with multiple Deepström architectures.

:



Figures and Tables:

Figure 1: The Deepström network architecture involves a usual convolutional part, conv , including multiple convolutional blocks, and a Deepström layer which is then fed to (eventually multiple) standard dense layers up to the classification layer. The Deepström layer computes the kernel between the output of the conv block for a given input and the corrsponding representations of the trains samples in the subsample L.

Figure 2: Accuracy of models as a function of the number of parameters (conv part not included) for various kernels on MNIST (top-left), SVHN (top-right), CIFAR10 (bottom-left) and CIFAR100 (bottom-right) datasets.

reports results gained when using a combination of RBF kernels with various bandwidths and for different subsample sizes. Our multiple kernel strategy, exploiting kernels defined with various values of the hyperparameter allows automatically handling this hyper-parameter which usually requires to be tuned either through cross validation or to be manually chosen. The plots show the accuracy on the CIFAR10 dataset as a function of σ value, where the performance of the multiple kernel Deepström is shown as a horizontal line. Plots report results for various subsample size equal to 2 (left), 4 (middle) and 8 (right), averaged over 10 runs. As may be seen, using our Multiple kernel strategy allows adapting the kernel combination optimally from the data without requiring any prior choice on the RBF bandwith hyper-parameter.

Figure 3: Comparison of Multiple Kernels that combines RBF kernels with various values of the bandwidth hyper-parameter. Multiple kernels performance is shown as an horizontal line while single kernel using one specific value of the bandwidth hyper-parameter σ. Plots correspond to a subsample size equal to 2 (left), 4 (middle) and 8 (right).

Datasets statistics network via stochastic gradient descent. In the case of multiple kernels, k 1 , . . . , k l , l Deepström layers can be computed in parallel then merged to encode the information provided by the different kernel representations. Learning the weights W 1 , . . . , W l in this case is, in a way, related to multiple kernel learning. Alternatively one may exploit a Deepström layer on top of each of the output feature map by the convolutional part conv and concatenate these as input to a classification layer, we call this a multiple Deepström architecture hereafter.

Table content: <table><tr><td>Dataset</td><td>Input shape</td><td colspan="4"># classes Training set size Validation set size Test set size</td></tr><tr><td>MNIST</td><td>(28 × 28 × 1)</td><td>10</td><td>40 000</td><td>10 000</td><td>10 000</td></tr><tr><td>SVHN</td><td>(32 × 32 × 3)</td><td>10</td><td>63 257</td><td>10 000</td><td>26 032</td></tr><tr><td colspan="2">CIFAR10 (32 × 32 × 3)</td><td>10</td><td>50 000</td><td>10 000</td><td>10 000</td></tr><tr><td colspan="2">CIFAR100 (32 × 32 × 3)</td><td>100</td><td>50 000</td><td>10 000</td><td>10 000</td></tr></table>

Table2reports the comparison of network architectures on four datasets. We consider Adaptive Deepström using Linear, RBF or Chi2 kernels and compare with Dense and Adaptive Deepfried for training set sizes of 5, 10 and 20 samples per class. We only consider here adaptive variants since they brought better results than their non adaptive counterparts. We obtain models with different complexities: by increasing the hidden layer size in standard convolutional models, or by stacking the number of matrices V in DeepFried (up to 8 times, more was untractable on our machines), and by increasing the subset size in Deepström. Reported results are averaged over 30 runs.

Table content: <table><tr><td/><td colspan="2">MNIST</td><td colspan="2">SVHN</td><td colspan="2">CIFAR10</td><td colspan="2">CIFAR100</td></tr><tr><td/><td>5</td><td>20</td><td>5</td><td>20</td><td>5</td><td>20</td><td>5</td><td>20</td></tr><tr><td>D</td><td>49.7 (4)</td><td colspan="2">94.4 (0.5) 65.6 (11.6)</td><td>81.7 (3.9)</td><td colspan="4">39.1 (3.3) 87.1 (3.7) 19.2 (2.2) 35.7 (2.7)</td></tr><tr><td>ADF</td><td colspan="2">12.4 (3.3) 12.4 (1.4)</td><td>16.7 (5)</td><td>21.0 (6.4)</td><td colspan="2">28.3 (9.2) 41.2 (3.6)</td><td>3.9 (1.2)</td><td>6.4 (0.8)</td></tr><tr><td colspan="3">ADSL 48.1 (5.5) 95.0 (0.5)</td><td>22.4 (6.9)</td><td colspan="3">29.6 (13.5) 12.0 (5.6) 27.8 (7.6)</td><td>1.2 (0.6)</td><td>1.9 (0.8)</td></tr><tr><td colspan="9">ADSR 41.2 (7.7) 95.5 (0.3) 42.1 (29.6) 53.5 (33.6) 70.8 (4.4) 92.2 (0.1) 24.7 (2.6) 62.1 (1.2)</td></tr><tr><td colspan="3">ADSC 26.4 (7.7) 92.3 (1.8)</td><td>89.6 (3.1)</td><td>93.3 (1.3)</td><td>67.1 (4.7)</td><td>92.2 (1)</td><td colspan="2">20.2 (2.2) 55.4 (1.9)</td></tr></table>

Classification accuracy of Dense layers architectures (D); Adaptive DeepFried (ADF), Adaptive Deepström with linear (ADSL), RBF (ADSR), Chi2 (ADSC) kernels, on small training sets with 5 and 20 training samples per class. Variance of results, computed on 30 runs, are given in brackets.One may see first that Deepstrom architectures outperfom baselines on every setting except for 5 training samples per class on MNIST. The linear kernel performs well on MNIST but is significantly worse than baselines on harder datasets. At the opposite, both ADSR and ADSC significantly outperfom Adaptive DeepFried for any dataset and perform on par or significantly better than Dense architectures on the hardest CIFAR100 dataset. Moreover one sees that no single kernel based Deepstrom architecture dominate on all settings, showing the potential interest of combining multiple kernels as following experiments will show.

Table content: <table><tr><td>Model</td><td>Accuracy (std)</td><td>Architecture</td></tr><tr><td>Dense</td><td>68.0 (0.7)</td><td>1 hidden layer 1024 neurons</td></tr><tr><td>Deepfried</td><td>67.6 (0.5)</td><td>5 stacks</td></tr><tr><td>Deepström</td><td>69.1 (0.2)</td><td>256 subsamples + 512 Linear Kernels</td></tr><tr><td>Deepström</td><td>67.6 (0.2)</td><td>16 subsamples + 512 Chi2 Kernels</td></tr></table>

Multiple Deepström experiments on CIFAR100 obtained on top of VGG19 convolutions.

Table content: <table/>

Peer review (iclr2019):
 DEEPSTRÖM NETWORKS Quality: good Originality: original Significance: relevant for ICLR Pros: - interesting idea -- see detailed comments Cons: a number of open issues in the presentation -- see detailed comments The paper is based on some concepts to link non-linear data representations by means of non-linear kernel mappings, with the deep learning approach. The presented concept is compared to former methods going into this direction and random fourier feature approaches. Additionally an adaptive scheme is suggested where the internally used landmark matrix (which forms a kind of mahalanobis like weighting matrix to the data) is adapted. I think the main idea of the paper is interesting but the presentation lacks a number of details in the description/parametrization and the experimental design. - *Indeed, since the Nyström approximation uses an explicit feature map from the data kernel matrix, it is not restricted to a specific kernel function and not limited only to RBF kernels, as in Fastfood approximation.* -- well yes an no, Nystroem works only effectively if the intrinsic dimensionality of the data is reasonable small - otherwise you need a lot of disjunct landmarks. Additionally the parameterization - how many landmarks and which one is not so easy - in this sense random fourier features are easier to handle. Further the random fourier features are not restricted to RBF kernel and not even to shift-invariant ones - there are a few proposals - The *feature map* obtained by the Nystroem approximation is only helpful as long as the number of landmarks is reasonable small - otherwise an out of sample extension (mapping new test points) in the spanned feature space may not be very reliable - please correct the spell errors like *using ful training sets* (full); *In (24), wo architectures* -- two? - random subsampling of the landmarks can lead to rather high approximation errors if the number of landmarks is small - there are some proposal to address this using leverage score sampling and other see e.g. work of K. Zhang, Suykens, C. Musco - *it is restricted to the Gaussian kernel* - well this is not true - see comments above (but I agree that there may not have been done much work to show this in practice, and it is probably not possible to be used for - all - kinds of psd kernels) - *Singular Value Decomposition (SVD) of K 11 . In the case where the size of the subsample L, m,is large, the computational complexity of the SVD is O(m 3 ).* -- well - yes and no, with Nystroem you would expect that N is much ! larger than m - than the m^3 may still be somewhat ok. To learn the weightings on the fly in your adaptive approach will address the complexity issue but may in parts degenerate performance - now it is a question what the user is more interested on - You mainly ignore the point how the landmarks have to be selected - random is (often) not a very reasonable choice - see respective work around this In your datasets the problem may not show up because you have images only which have very strong characteristics and are intrinsically very low dimensional. --> I think you have to add another section here - evaluating either different sampling schemes or just use a more state of the art one like leverage score sampling (getting I think O(N^2) complexity); you should also address how you find a good guess for the number of landmarks - I suggest to use also additional non-image data. Basically one motivation in your approach is to go beyond the classical deep learning data representation - this may not be so interesting for image recognition problems - I may suggest to spend a small subsection to a complexity analysis (including parameter optimization) of the various methods - Figure 2 - what do you mean by number of parameters? - there are a few strong fluctuations (fully connected, addative deep linear) - why - please increase the level of details of the accuracy axis in Figure 2 - so far it basically has 10% steps - if I have not missed it you did not say how the parameter .sigma (or .gamma) in the rbf kernel has been determined (same for other parametric kernels) - multiple kernels - well how did you combine the kernels (there are many options) - there are number of typos in the refs (see e.g. ref 14); some other references are very incomplete e.g. ref 15 - plots should be (prefered) close to the respective text (the appendix is a bit strange here)