One can substitute each neuron in any neural network with a kernel machine and obtain a counterpart powered by kernel machines. The new network inherits the expressive power and architecture of the original but works in a more intuitive way since each node enjoys the simple interpretation as a hyperplane (in a reproducing kernel Hilbert space). Further, using the kernel multilayer perceptron as an example, we prove that in classification and under certain losses, an optimal representation that minimizes the risk of the network can be characterized for each hidden layer. This result removes the need of backpropagation in learning the model and can be generalized to any feedforward kernel network. Moreover, unlike backpropagation, which turns models into black boxes, the optimal hidden representation enjoys an intuitive geometric interpretation, making the dynamics of learning in a deep kernel network transparent. Empirical results are provided to complement our theory.
****Reply to authors' rebuttal****
Dear Authors,
Thank you very much for all the effort you have put into the rebuttal. Based on the improved theoretical and experimental results, I have decided to increase my score from 5 to 6.
Best wishes,
Rev 1
****Original review****
This paper explores integration of kernel machines with neural networks based on replacing the non-linear function represented by each neuron with a function living in some pre-defined RKHS. From the theoretical standpoint, this work is a clear improvement upon the work of Zhang et al. (2017). Authors further propose a layer-wise training algorithm based on optimisation of a particular similarity measure between embeddings based on their class assignments at each layer, which eliminates necessity of gradient-based training. However, the experimental performance of the proposed algorithm is somewhat lacking in comparison, perhaps because the authors focus on kernelised equivalents of MLPs instead of CNNs as Zhang et al.
My rating of the paper is mainly due to the lack of experimental evidence for usefulness of the layer-wise training, and absence of experimental comparison with several baselines (see details below). It is also unclear whether the structure of KNs is significantly better than that of NNs in terms of interpretability. Apart from the comments below, I would like to ask the authors to discuss relation to the following related papers:
	1) Kulkarni & Karande, 2017: "Layer-wise training of deep networks using kernel similarity" https://arxiv.org/pdf/1703.07115.pdf
	2) Scardapanea et al., 2017: "Kafnets: kernel-based non-parametric activation functions for neural networks" https://arxiv.org/pdf/1707.04035.pdf
Detailed comments:
Theory
- (Sec 4.1) Backpropagation (BP) is being criticised: BP is only a particular implementation of gradient calculation. It seems to me that your criticisms are thus more related to use of iterative gradient-based optimisation algorithms, rather than to obtaining gradients through BP?! Regarding the criticism that BP forces intermediate layers to correct for "mistakes" made by layers higher up: it seems your layer-wise algorithm attempts to learn the best possible representation in first layer, and then progresses to the next layer where it tries to correct for the potential error of the first layer and so on. In other words it seems that the errors of layers are propagated from first to last, instead of last to first as in BP, but are still being propagated in a sense. I do not immediately see why propagation forward should be preferable. Can you please further explain this point?
- It is proven in the appendix (Lemma B.3) that under certain conditions stacking additional layers never leads to degradation of training loss. Can you please clarify whether additional layers can be helpful even in the case where previous layers already succeeded in learning the optimal representation?
- (Sec 4.1) Layer-wise vs. network-wise optimality: I find the claim that BP-based learner is not aware of the network-wise optimality confusing. BP explicitly optimises for network-wise optimality and the relative contribution to the network-wise error of each weight is propagated accordingly. I suppose my confusion stems from lack of a clear description of what defines a learner "aware" or "blind" to network-wise optimality. In general, I am not convinced layer-wise optimality is a useful criterion when what we want to achieve is network-wise optimality. As you show in the appendix, if layer-wise optimality is achieved then it implies network-wise optimality; however, layer-wise optimality is only a sufficient condition and likely not a necessary one (except for the simplified scenario studied in B.3). It is thus not clear to me why layer-wise training would always be preferable to network-wise training (e.g. using BP) especially because its greedy nature might intuitively prevent learning of hierarchical representations which are commonly claimed to be key to the success of neural networks. Can you please clarify?
- (Sec 4.2) I think it would be beneficial to state in the introduction that the "risk" is with respect to the hinge loss which is common in the SVM/kernel literature but much less in the deep learning literature and thus could surprise a few people when they reach this point. 
Futher questions:
	- From Lemma 4.3, it seems that the derived representation is only optimal with respect to the **upper bound** on the empirical risk (which for \tau >= 2 will be an upper bound on the population risk). I got slightly confused at this point as my interpretation of the previous text was that the representation is optimal with respect to the population risk itself. Does the upper bound have the same set of optima? Please clarify.
	- (p.5) There are two assumptions that I find somewhat restrictive. Just before Lemma 4.3 you assume that the number of points in each class must be the same. Can you comment on whether you expect the same representation to be optimal for classification problems with significantly imbalanced number of samples per class? The second assumption is after Lemma 4.4 where you state that the stationary kernel k^{l-1} should attain its infinum for all x, y s.t. || x - y || greater than some threshold. This does not hold for many of the popular kernels like RBF, Matern, or inverse multiquadric. Do you think this assumption can be relaxed?
	- (p.5) Choice of the dissimilarity measure for G: Can you provide more intuition about why you selected L^1 distance and whether you would expect different results with L^2 or other common metrics?
- (Sec 4.3) Can you please provide more detaild about the relation of the proposed objective (\hat(R)(F) + \tau max_j ||f_j||_H) to Lemmas 4.3 and 4.5 where the optimal representation was derived for functions that optimise an upper bound in terms of Gaussian complexity (e.g. is the representation that minimises risk w.r.t. the Gaussian bound also optimal with respect to functions that optimise this objective)?
Experiments
- I would appreciate addition of some standard baselines, like MLP combined with dropout or batch normalisation, and optimised with RMSProp (or similar). These would greatly help with assessing competitiveness with current SOTA results.
- It would be nice to see the relative contribution of the two main components of the paper. Specifically, an experiment which would evaluate empirical performance of KNs optimised by some form of gradient descent vs. by your layer-wise training rule would be very insightful.
Other
- (p.2, 1st par in Sec 2) [minor] You state "a kernel machine is a universal function approximator". I suppose that might be true for a certain class of kernels but not in general?! Please clarify.
- (p.2, 3rd par in Sec 2) [minor] Are you using a particular version of the representer theorem in the representation of f_j^{(i)} as linear combination of feature maps? Please clarify.
- (p.2, end of 1st par in Sec 3) L^{(i)} is defined as sup over X_i. It is not clear to me that this constant is necessarily finite and I suspect it will not be in general (it will for the RBF kernel (and most stationary kernels) used in experiments though). Finiteness of L^{(i)} is necessary for the bound in Eq. (2) to be non-vacuous. Please clarify.
- (p.3, after 1st display in Sec 4.2.1) [minor] Missing dot after "that we wish to minimise". Next sentence states "**the** optimal F" (emphasis mine) -- I am sorry if I overlooked it, but I did not notice a proof that a solution exists and is unique, and am not familiar enough with the literature to immediately see the answer. Perhaps a footnote clarifying the statement would help.
- (p.4, 1st par in Sec 4) You say "A generalisation to regression is reserved for future work". I did not expect that based on the first few pages. On high-level, it seems that generalisation to regression need not be trivial as, for example, the optimal representation derived in Lemma 4.3 and Lemma 4.5 explicitly relies on the classification nature of the problem. Can you comment on expected difficulty of extension to regression? Possibly state in the introduction that only classification is considered in this paper.
	- (p.7, 1st par in Sec 6) [related] "However they did not extend the idea to any **arbitrary** NN" (emphasis mine). Can you please be more specific here?
- (p.5-6) [minor] Last sentence in Lemmas 4.3 and 4.5 is slightly confusing. Can you rephrase please?
- (p.6) [minor] You say "the learned decision boundary would generalise better to unseen data". Can you please clarify the last sentence (e.g. being more precise about the meaning of the word "simple" in the same sentence) and provide reference for why this is necessarily the case?