Deep Learning Is Composite Kernel Learning
Authors: Chandra Shekar Lakshminarayanan
Amit Vikram Singh
Venue:  (2021)
Keywords: deep learning
kernel methods

Abstract: Recent works have connected deep learning and kernel methods. In this paper, we show that architectural choices such as convolutional layers with pooling, skip connections, make deep learning a composite kernel learning method, where the kernel is a (architecture dependent) composition of base kernels: even before training, standard deep networks have in-built structural properties that ensure their success. In particular, we build on the recently developed `neural path' framework that characterises the role of gates/masks in fully connected deep networks with ReLU activations. 

Under review as a conference paper at ICLR 2021
DEEP LEARNING IS COMPOSITE KERNEL LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent works have connected deep learning and kernel methods. In this paper, we show that architectural choices such as convolutional layers with pooling, skip connections, make deep learning composite kernel learning method, where the kernel is (architecture dependent) composition of base kernels: even before training, standard deep networks have in-built structural properties that ensure their success. In particular, we build the recently developed 'neural path' framework that characterises the role of gates/masks in fully connected deep networks with ReLU activations.
INTRODUCTION
The success of deep learning is attributed to feature learning. The conventional view is that feature learning happens in the hidden layers of deep network: in the initial layers simple low level features are learnt, and sophisticated high level features are learnt as one proceeds in depth. In this viewpoint, the penultimate layer output is the final hidden feature and the final layer learns a linear model with these hidden features. While this interpretation of feature learning is intuitive, beyond the first couple of layers it is hard make any meaningful interpretation of what happens in the intermediate layers.
Recent works Jacot al. (2088;; Arora et al. (219):; Cao and Gu 2019) have provided kernel learning interpretation for deep learning by showing that in the limit of infinite width deep learning becomes kernel learning. These works are based on neural langents, wherein, the gradient of the network output with respect to the network parameters known as the neural tangent features (NTFs) considered the features. Arora et al. (2099) show that randomised initialisation of weights, the kernel matrix associated with the NTFs, known as the neural tangent kernel (NTK) converges to deterministic matrix and that optimisation and generalisation of infinite width deep neural networks is characterised by this deterministic kernel matrix. Cao and Gu (019) provided generalisation bounds terms of the NTK matrix. Arora al. (2019) also proposed pure-kernel method based on CNTK (NTK of convolutional neural networks, i.e., CNNs) which significantly outperformed the previous state-of-the-an kernel methods. The NTK either as an interpretation or as a method in itself has been very successful. Nevertheless it has some open issues namely i) non-interpretable: the kernel is the inner product of gradients and has no physical interpretation, ii) no feature learning: the NTFs are random and fixed during training and iii) performance gap: finite width CNN outperforms the infinite width CNTK, i.e., NTK does not fully explain the success of deep learning.
Recently, Lakshminarayanan and Singh 2020) developed a neural path (NP) framework provide kernel interpretation for deep learning that addresses the open issues in the current NTK framework. Here, DNNs with ReLU activations in the so called neural path feature (NPF) and the weights in the network in the so called neural path value (NPV). The key findings can be broken into the following steps.
considered, and the gates (onfofff state of ReLU) are encoded
Step 1: The NPFs and NPV are decoupled. Gates are treated as masks, which are held in a separate feature network and applied to the main network called the value network. This enables one study the various kinds of gates (i.e., NPFs), such as random gates (of a randomly initialised network), semi-leamt gates (sampled an intermediate epoch during training), and learnt gates (sampled from a fully trained network). This addresses the feature learning issue.
Step 2:
When the gates/masks are decoupled and applied externally it follows that NTK const X NPK, at random initialisation of weights. For pair of input examples, NPK is a similarity measure
Introduced for the first time the work of Lakshminarayanan and Singh 2020

---

Under review as a conference paper at ICLR 2021
that depends the size of the sub-network formed by the gates that active simultancously for examples. This addresses the interpretability issue.
Step 3: CNTK performs better than random gates/masks and gates/masks from fully trained networks perform better than CNTK. This explains the performance gap between CNN and CNTK. was also observed (on standard datasets) that when learnt gates/masks used, the weights of the value network can be reset and re-trained from scratch without significant loss of performance.
1.1 CONTRIBUTIONS IN THIS WORK
We attribute the success of deep learning to the following two key ingredients: (i) a composite kernel with gates as fundamental building blocks and (ii) allowing the gates to learn/adapt during training. Formally, we extend the NP framework of Lakshminarayanan and Singh 2020 as explained below.
Composite Kernel: The NPK matrix has a composite structure (architecture dependent).
1. Cotle-Cooneeted networks: H is the Hadamard product of the input data Gram matrix, and the kernel matrices corresponding to the binary gating features of the individual layers.
2. Residual networks (ResNets) with skip connections: H assumes a sum of products form. In particular, consider ResNet with (b 2) blocks and b skip connections. Within this
ResNet there are i = 1,..., 2 possible dense networks, and then Hus Σ C,H.e where C; > 0 are positive constants based on normalisation layers.
3. Convolutional neural networks (CNN) with pooling: 1 is rotation invariant.
Gate Learning: We show that learnt gates perform better than random gates. Starting with the setup of Lakshminarayanan and Singh 2020), we build combinatorially many models by,
1. permuting the order of the layers when we apply them as external masks,
2. having two types of modes based on input provided to the value network namely 'standard': input the actual image and ii) 'all-ones': input is tensor with all entries as '
We observe in our experiments that the performance is robust to such combinatorial variations.
Message: This work along with that of Lakshminaaaaaaann and Singh (020 provides paradigm shift in understanding deep learning. Here, gates play a central role. Each gate related to a hyper- plane, and gates together form layer level binary features whose kernels out these binary features depth-wise gives rise to a product of the base kernels. The skip connections gives 'sum of product' structure, and convolution with pooling gives rotation invariance.
the base kernels. Laying
Section describes the network architectures namely colly-connected, convolutional and residual, which we take up for theoretical analysis. [Section 3 Textends the neural path framework to CNN and ResNet. [Section 4 exxlains the composite kernel. Sectionn 5 connects the NTK and NPK for CNN and ResNet. [Section 6 consists of numerical experiments.
Organisation:
2 ARCHITECTURES: FULLY CONNECTED, CONVOLUTIONAL AND RESIDUAL
In this section, we present the three architectures that we take up for theoretical analysis. These are i) fully connected (FC or FC-DNN), ii) convolutional (CNN) and iii) residual (ResNets). In what follows, [x]] is the set .......,,,, and the dataset is given by (Iz, Uo ) E Rd R.
Fully Connected: We consider fully connected networks with width 'w" and depth 'd'.
CNN: We consider 1-dimensional convolutional neural network with circular convolutions (see Table 2 with d,, convolutional layers (1 = 1,.... d.v). followed by a global saaad-avveeeeeee-paeoo
layer (1 dg. 1) and di (1 dey 2, ... dev di + 1) FC layers. The convolutional window size is Wey < din the number filters per convolutional layer is w, and the width of the FC is also w.
Definition 2.1 (Cireular Convolution). For dRd i [die] and r t0,..., dic 1}, define
(ii = i ++rr for i +r S di and @ + r- d for i + r > dim- (ii) ()) æ0i r). [dm]
2

---

Under review as a conference paper at ICLR 2021
Input Layer
2x, (,,
I
Pre-activation
La (Jout:
Li, (Tin: Rours Zz 22, (tin: 1)
Gating Value
Gz, e (Houss 1)
= 1 (gr (kun))))
Hidden Unit Output
Rir, e (Bout: 1) = 20.0 (Hout; 1) Gz (Vou,
Final Output
Ve
= Σn, O Rout, Zx,0 Pins d 1)
Table I: Information flow in FC-DNN with ReLU, Here, "q's pre- activatiion inputs, "z's output of the hidden layers, 'G's are the gating values. E [d - 1] the index of layer, four and are indices of nodes the current and previous layer respectively.
ship
stops
Ir Reo
Blocko
Blocky
pre
poo
Blocks
prc
poet
Blocks
de (ic)
abijy
ignneed/rerovee
akipy pntained/coomootee
3.E Re
Blacko
Monkk
pre
post
Blacks
pood
Blocks
(is
Blockk
retained, /comectedd
Blocks
ignored fremoowed
ResNet Architecture is shown in the top. Process of obtaining Sub-FC-DNN by ignoring skip (retaining block) or retaining skip (ignoring block) shown the bottom.
Figure 1:
1), Rin, the indices (taking values in (uc)) of the input/oulpul filters. iev denotes the indices of the convolutional window (taking values in [wev]] between input and output filters iin and ious ifout denotes the indices (taking values [din], the dimension of input features) of individual nodes in a given output filter.
(iii) qa, e (bfour Rour: - Leocd (iiers hins Pours Zx, (Hjour 2 10,,
where /
Definition 2.2 (Pooling). Let Goool (ifours hour; dev + 1) denote the pooling mask, then we have
Za,00 (a,ur dev + 1) = Σ Z (ijours Rours dee) Gran (isour; hours dev + 1),
where in the case of global-average-poolle Grae bonay dev + +1) 1 Viou <[w], djow E [dmm] and in the case of max-pooling, for given iow E [w], Goool (imax: Tours dey + 1) where mmax arg iax Z (ifoue lours d and Gogel (ifouas lowrs des + 1) = O, Visour o imax.
di,"
ResNet: We consider ResNets with '(b+ 2)" blocks and "b' skip connections between the blocks
post Figure 1) Each block is a FC-DNN of depth 'dan" and width 'w". Here, 7: 7 E [b] are normalisation variables.
Definition 2.3 (Sub FC-DNNs). Lei 20 denote the power set of [b] and let J E 2 denote any subset of (b). Define the' Tuh sub-FC-DNN of the ResNet be the fully connected network obtained (see Figure TV the skip connections skip,, Vj E I (see Figure
by
NEURAL PATH FRAMEWORK
In this section, we extend the neural path framework developed by LS2020 to CNN and ResNet architectures described in the previous section. The neural path framework exploits the gating property of ReI.U activation, which can be thought of as gate/mask that blocks/allows its pre-activation input depending on its 0/1 state ( ( if pre-activation is negative and 1 if pre-ace are-activation is positive). The key idea here is to break DNN (with RcLU) into paths, and express its output as a summation of the contribution of the paths. The contribution of path is the product of the signal in its input node, the weights in the path and the gates in the path. For a DNN with P paths, for an input & E Rd,, the gating information is encoded in novel neural path feature (NPF), Φz,0 E IR P and novel neural path value (NPV). Ue Rº encodes the weights. The output of the DNN is then the inner product of the NPFs and NPVs, i.e., (x.)) = (dz,, ve) (Proposition 3.4h.
Definition 3.1. A path starts from input node, passes through weights, hidden nodes, and normal- isation constants and ends at the output node.
Proposition 3.1. The total number of paths in FC-DNN, CNN and ResNet are respectively given by pk (d-1, pomn din (weroW)o do and pies d Ei (?) w wf(++))du-11
3

---

Under review as a conference paper at ICLR 2021
Notation 3.1 (Index Maps). The ranges of index maps Iy If", Ii are [din]. [Wer] and [w] respec- rively. The index maps are used to identify the nodes through which a path p passes. Further, let I (p): [PM]] + 2 specify the indices of the skip connections ignored in path p. Also, we follow the convention that weights and gating values of layers corresponding to blocks skipped are 1.
Definition 3.2 (Path Activity). The product of the gating values in a path p is its 'activity' denoted by Ae p). We define:
(a) Ae (x. p) I Ga FC-DNN and ResNet.
(b) (x. = G GT,( 1=du+2 -d. ( G2,s(T((p),)),oo CNN.
In CNN, the pooling layer is accounted by letting G = Goool for 1 = der + 1.
Definition 3.3 (Bundle Paths of Sharing Weights). Let pemn pm
and {Bi,... B Bonn) be collection of sets such that Vi. j E [Pom i f we have B; BB, and U B, = [ Further, paths p/ E B,, then (p) =
de
dey and Ip(p) = I (p')), 1I = 0..... dev.
Proposition 3.2. There are exactly dm paths in a bundle.
Definition 3.4 (Normalisation Factor). Define ((J)= - 11 2 JEJ
past J'E( 4
Weight sharing is shown in the the cartoon in Figure 2
which shows a CNN with dnp = w = 1,
Wey dev 3, di = O. Here, the red coloured paths all share the same weights (1, 1,,, 1, 2, 3 and the blue coloured paths all share the same weights given by 0 1, 11, = 1,2,3.
(30
K00=
230
Figure 2: Shows weight sharing and rotational symmetry of internal variables and the output after pooling in a CNN. Left most cartoon uses GAP layer, and the other two cartoons use max-pooling. Circles are nodes and the 1/0 in the nodes indicate the gating. Pre activations/node output are shown in brown/purple.
Definition 3.5 (Neural Path Value). The product of the weights and normalisation factors in a path p its 'value'. The value of a path bundle is the value of any path in that bundle. The path/bundle values denoted by ue (p) vve (Bp) and are defined as follows:
(a) (p) (T)
(b) (Bp) =
U2 ((( for ==d+t2
for any p E Bp.
(c) (p -T (
The neural path value is defined as ve - (vo(p),p E [P E P ve ف (ve(Bp), E [ e
T prm and ee _ (ve(p).p E [Pret) E TTP for FC-DNN, CNN and ResNet respectively.
Proposition 3.3 (Rotational Invariance). Internal variables in the convolutional layers are circularly symmetric, fer, E {0, (O..... dim - 1} it follows that (i) Zrot(a,r), ( -.-) Zz, e (ifour T r, ", (ii) (rot(a.r).e) (i -) Qa ( + .)) and (iii) Grot(a,r), ( - -) Gz. e @ :. Definition 3.6. The neural path feature (NPF) corresponding to a path p is given by (a) (p) A x((((())) (o(()) for FC-DNN and ResNet. (b) ( 2 Epen, x (e) () CNN.
The NPF is defined as 62.0 - (dr,0(p),PE [PCT) E Td 62,0 - (Or,a(Bp), e [P E A and 62.9 (p, E [Pre]) E R pm for FC-DNN, CNN and ResNet respectively.
Proposition 3.4 (Output=(NPE.NPY) The output of the network can be written as an inner product of the NPF and NPV, ie., (0 (I) (Øz.0; vo).
4

---

Under review as a conference paper at ICLR 2021
4 NEURAL PATH KERNEL: COMPOSITE KERNEL BASED ON SUB-NETWORKS
In this section, we will discuss the properties of neural path kernel (NPK) associated with the NPFs defined in [Section 3 Recall that co-ordinate of NPF be non-zero only if the corresponding path is active. Consequently, the NPK for a pair of input examples is a similarity measure that depends on the number of paths that are active for both examples. Such common active paths are captured in quantity denoted by A @Deinition 4.2). The number of active paths are in turn dependent on the number of active gates each layer, a fact that endows the NPK with a hierarchical/compssiii structure. Gates are the basic building blocks, and the gates in a layer for a w-dimensional binary feature whose kernels are the base kernels. When the layers are laid out depth-wise, we obtain product of the base kernels. When skip connections are added, we obtain a sum of products of base kernels. And presence of convolution with pooling provides rotational invariance.
Definition 4.1. Define the NPK matrix be He - &g De, where De ( oz.,o) I2 is the NPF matrix.
Definition 4.2. Define Ae(i, x. xx)) 2 KipE [P]: Io(p) = i, (z. p) = Ae(xx, = 1} to be total number of "active' paths for both F. and Eg that pass through input node i.
Definition 4.3 (Layer-wise Kernel). Let Gz,a(-,1) E R be w-dimensional feature of the gating values in layer I. for input I E RRd.. Define layer-wise kernels:
Hi (s)
Lemma 4.1 (Product Kernel). Let H denote the NPK of FC-DNN, and for D E Rdded be diagonal matrix with strictly positive entries, and u, v E Rd let (u, u') Ei= ((i)u(i)ul()).
H (s, s') = (II.: (gs.:s))aaa. M( (I,, 2' 21) H (s.s')
Lemma 4.2 (Sum of Product Kernel). Let Hig be the NPK of the ResNet, and Hg be the NPK of the Sub-FC-DNN within the ResNet obtained by ignoring those skip connections in the set J. Then,
H
Σ Hg
JE2M
Lemma 4.3 (Rotational Invariant Kernel), Let H
denote the NPK of CNN, then
An
Hg (c,, rol F))
(rot(I,; (),))) (()rot(e..)
5 MAIN THEORETICAL RESULT
In this section, we proceed with the final step in extending the neural path theory to CNN and ResNet. As with LS2020 first describe the deep gated network (DGN) setup that decouples the NPFs and NPV, and follow it up with the main result that connects the NPK and the NTK in the DGN setting.
Feature Network sfeer zf
Value Network x "umuit 0) = x²
Fenture Network((P) (+))
R
Laatther 1) = (ef(, D. of gr 1))
Cr Lman 1) = (9"(s, 1), (-. 1)}
(.nrr(inn)) = of, (fm. 1)- Gharltnn (bae
z" 2,jeroo (furs 1) = Φ² gr (bmn 1)- Gr
R.g (hars!)
Guarly
Ca d 1)
(grl (8% fon. d), 21 (vdd 13)
Seppo((a)) = (1" ieu d), good ( 13)
Hard ReLU: C.
(oan.) 1)= 10d, (220) or Soft-ReLU: G. 2, (onn.)
x R
Bipos (x)
Value Networks("))
Figure 3: Shows a deep gated network (DGN). The Roft-ReLU enables gradient flow into the feature network.
DGN set up introduced by LS2020 to analytically characterise the role played by the gates in
a 'standalone' manner. The DGN has two networks namely the feature network parameterised by
of E R which holds the NPFs (i.e., the gating information) and value network parameterised by O' E Th which holds the NPV. The combined parameterisation is denoted by @DIN = (0', O*) E R Re Thus the learning problem in the DGN is jenox (x) (0x.er, ver).
5

---

Under review as a conference paper at ICLR 2021
Definition 5.1. The DGN has 4 regimes namely decoupled learning (DL), fixed learnt (FL), fixed mandom-dependens initialisation (FR-DI) and fixed random-ines iiailom--ddeeeddeet initialisation (FR-II). In all the regimes Depaw is the output, and 0 is always initialised at random and is trainable. However. the regimes differ based on i) trainability of O', ii) initialisation S as described below.
DI.
O is trainable, and 6/ and 0% are random and statistically independent, B > 0. O is non-trainable, and 0g is pre-trained; O is statistically independent of O'- O is non-trainable, and 6g and 0 are random and statistically independent.
FL
FR-11
FR-DI
@ is non-trainable, and 0%= =%--
The flexibility in DGN is that a) O' can be trainable/non -eairaibllnon-traiaabllee trainable and b) o can be random pre-trained using ter as the output (Definition 5.1). By using the DGN setup we can study the role of gates by comparing (a) learnable (DI.) vs fixed gates (FI.,, FR-DI, FR-II), (b) random (FR-DI, FR-II) vs learnt gates (FL.) and (c) dependent (FR-DI) vs independent initialisations (FR-II). In the DL regime "soft-ReLU" is chosen to enable gradient flow through the feature network.
DGN Regimes:
Proposition 5.1. Let Kepar be the NTK matrix of the DGN, then K = Keyoar + K with
Overall NTK
Kgoen (') = (V',, (pOx), where e), goeN = goar Dgpax (x) E Rd
Feature NTK
Kignor (8, (1) 2.,NN vi ) where b 2.g V e DeDeN (x) E R
Value NTK
Kg K (8, (1bt gnoN, vi gnox), where of GpON Ver Depas (x) E R4
Remark:
There are two separate NTKs, each one corresponding to feature and value networks respectively. In the case fixed regimes, Kt = O.
Theorem 5.1. (i) 0% is statistically independent of e (ii) 0j are i.i.d symmetric Bernoulli over for FC and convolutional layers. As w - 0o, we have:
(-0,-o) Let ofe-
Conts and Jes v'w
Cavar
(ii) KY Kgges
+ B3 Ho, Br = do
1) for FC-DNN,
(ii) Ky Lggar
+ Sc.Hle/ Beo = 1
dmz (deno 2(dn
2de Jf
2d., 2(dg 2(15-11) for CNN with GAP, + o ox
2 2(17)+2)d -1 T(T)² for ResNet.
(iii) Ky "gpen + Ejezm BZ HJ 8/
3/ = (1J1+ + 2)dauo
Bies Bovs Bis The simplest of all is Br = do do 2(d-1) where d is due the fact that there are d weights in path and in the exponent of ots factor (d - 1) arises because the gradient of a particular weight product of all the weights in the path excluding the said weight itself, and the factor of 2 is due to the fact that NTK is an inner product of two gradients. Bev is similar to 3ic with separate bookkeeping for the convolutional and FC layers, and 1 dg is due to the GAP layer. In Br, the fre for all the sub-FC-DNNs within the ResNet are scaled by the corresponding normalisation factors and summed.
Decoupling In DNN with ReLU (and FR-DI regime of DGN), NPV and NPF not statistically independent at initialisation, i.e., Theorem 5. does not hold. However, the current state-of-the-ate
analysis Jacot et al. (2018) Arora et al. (2019) Cao and Gu 2019) is in the infinite width (w oo)
regime, wherein, the change in activations during training is only of the order / 4 which goes to
0 as w + co. Hence, though assumption in [Theoemm 5.1 may not hold exactly, is not a strong assumption fix the NPFs for the purpose of analysis. Once the NPFs are fixed, it only natural to statistically decouple the NPV from fixed NPFs (Theorem J. hold in FR-II, FL and DL regimes).
Gates are Key: In simple terms, Theorem 5.1 says that if the gates/masks are known, then the weights are expendable, a fact which we also verify in our extensive experiments.
6 NUMERICAL EXPERIMENTS
We now show via experiments that gates indeed play a central role in deep learning. For this we use the DGN setup (Figure 4) create models in the 4 regimes namely DI., FI., FR-II and FR-DI. In

---

Under review as a conference paper at ICLR 2021
each of the 4 regimes, we create combinatorially many models via a) permutation of the layers when the copied from the feature to the value network, and b) setting the input to the value network to 1 (in training and testing), Le., tensor with all its entries to be 1. We observe that in all the 4 regimes, the models are robust to the combinatorial variations.
Datasets are MNIST and CIFAR-10. For CIFAR-I0, 10, we use Figure 4 with 3 x 3 windows and 128 filters in each layer. For MNIST, we use FC instead of the convolutional layers. All the
Setup:
FC-DNNs and CNNs are trained with 'Adam' ICC (step-size = 3- 10-4, batch size = 32). A ResNet
called DavidNel
12
was trained with SGD ( step-size = 0.5, batch size- = 256). We use 3 = 10.
Reporting of Statistics: The results summarised in Figure 4 For FC-DNN and CNN, in each of the 4 regimes, we train 48 = 2(xx" = 2/x² =1) x 24 [layer permutations) models. Each of these models are trained to almost 100% accuracy and the test performance taken to be the best obtained in given run. Each of the 48 models is run only once. For the ResNet, we train only two model for each of the 4 regimes without permuting the layers, but with image as well as 'all-ones' input variation) and here each mode is run 5 times.
Result Discussion: Recall that in regimes FR-II and FR-DI the gates are fixed and random, and only @" are trained. In DL regime, both O and (* are trained, and FL. regime O is pre-trained and fixed, and only @" is trained. In the following discussion, we compare the performance of the models in various regimes, along with the performance of CNTK of Arora et al. (2019) (77.4%% in CIFAR-10) and the performance of standard DNN with ReLU, The main observations are listed below (those by Lakshminarayanan and Singh (020) are also revisited for the sake of completeness).
1. Decoupling: There is no performance difference between FR-II and FR-DI.Further, decoupled learning of gates (DL) performs significantly better than fixed random gates (FR), and the gap between standard DNN with ReLUU and DL is less than 3%. This marginal performance loss seems to be worthy trade off for fundamental insights of Theorem 5.1 under the decoupling assumption.
2. Recovery: The fixed learnt regime (FL) shows that using the gates of a pre-trained ReLU network, performance can be recovered by training the NPV. Also, by interpreting the input dependent component of a model to be the features and the input independent component to be the weights, it makes sense to look at the gates/NPFs as the hidden features and NPV as the weights.
3. Random Gates: FR-II does perform well in all the experiments (note that for a 10-class problem, a random classifier would achieve only 10% test accuracy). Given the observation that the gates are the true features, and the fact that is no learning in the gates in the fixed regime, and the performance of fixed random gates can be purely attributed to the in-built structure.
4. Gate Learning: We group the models into three sets where S { ReLU, FL, DL), S. }R} and 53- = { CNTK) }. and explain the difference in performance due to gate learning. S₂ and S3 have no gate learning. However, S3 due to its infinite width has better averaging resulting in well formed kernel and hence performs better than S2 which is finite width. Thus, the difference between S2 and S3 can be attributed to finite versus infinite width. Both S1 and S2 are finite width, and hence, conventional feature learning happens in both S and S2, but, S1 with gate learning is better (77.5% or above in CIFAR-10) than S₂ (67% in CIFAR-10) with no gate learning. Thus neither finite width, nor the conventional feature learning explain the difference between S₁ and S2. Thus, 'gate learning' discriminates the regimes 51, S2 and S3 better than the conventional feature learning view.
Feature Network (ef) surovidss the gates
Inpat 12
FC
CNN
ResNet
D
(g)(x)
FR-I1
94.1%
67.5%
89.8%
G(,,
G
3
(ndipat made pre-mmz 86)
FR-DI
94.1%
67.6%
89.8%
consolutional layer couf purattooooon
DL 98.1%
77.6%
92.4%
(i. Permutation 2,3,4
barsel:3 & stride:) paodiaginnce
FL
98.6%
4%
92.5%
Cl 1 CC..j C0. Cl.a
umber outges filters: 138
ReLU
98.5%
80.4%
93.1%
In all cases, standard deviation was less
6 R
D
(gnox(s))
than 0.5%. MNIST for FC, CIFAR-10 for CNN and ResNet.
(ontget mode DGN)
Value Netwock (9") : uses the gates provided by the featurr neswork
Figure 4: cf, C, i E [4] are the convolutional layers, which are followed by global-average-poolin (GAP) layer then by a dense layer (D'/D'), and a softmax layer to produce the final logits.
7

---

Under review as a conference paper at ICLR 2021
(Leff) Standard KeL.U DNN and (Right) LKN with Fixed Leurnt Gates from model on the left with f11 22. da. Ja m 4, and xe" rand
tensor
For each model, inpui shown finst and then starting from the finst layer, the finst filters of each of 4 layers are shown.
Figure Hidden layer outputs for fixed random input to the value network of DGN with permuted gating.
5. Permutation and Input Invariance: The performance (in all the regimes) is robust to 'all-ones' inputs. Note that in the 'all-ones' case, the input information affects the models only via the gates. Here, all the entries of the input Gram matrix are identical, and the NPK depends only A, which is the measure of sub-network active simultaneously for the various input pairs. The performance (in all the 4 regimes) is also robust to permutation of the layers. This can be attributed the product ([--1) H of the layer level base kernels being order invariant.
6. Visualisation: Figure 5 compares the hidden layer outputs of a standard DNN with ReLU with 4 layers, and that of DGN which copies the gates from the standard DNN, but, reverses the gating masks when applying to the value network. Also, the value network of the DGN was provided with a fixed random input (as shown in Figure 5). Both the models achieved about 80% test accuracy, an otherwise surprising outcome, yet, as per the theory developed in this paper, a random input to the value network should not have much effect performance, and this experiment confirms the same.
RELATED AND FUTURE WORK
Our paper extended the work of aakssminarayanan and Singh (220 to CNN and ResNet. Further, we pointed out the composite nature of the underlying kernel. Experiments with permuted masks and constant inputs are also significant and novel evidences, which to our knowledge are first of their kind in literature. Gated linearity was studied recently by Fiat et al. (2019), however, they considered only single layered gated networks Jacot et al. (2018;; Arora et al. 2019); Cao and Gu (2019); Jacol et al. (211)); Du et al. (2018) have all used the NTK framework to understand questions related to optimssation and/or generalisation in DNNs. We now discuss the future work below.
1. Base Kernel: At randomised initialisation, for each I, 11 (s.=") is the fraction of gates that are simultancously active for input examples s.s', which in the limit of infinite width is equal to - -anglele= (-, (), Zz_ (+))) (Xie et al. 2017). Further, due to the property of ReLU to pass only positive components, we conjecture that the parrwise angle between input examples measured at the
(s,5²)
hidden layer outputs is decreasing function of depth and 1 + co,
1/2 Ys, s' [nx].
We reserve a formal statement on the behaviour of Hlyr for the future.
2. Multiple Kernel Learning (önen and Alpaydın 2011 Bach et al. 2004] Sonnenburg et al. 2006
Cortes al. 2009) is the name given to a class of methods that learn linear or non-linear combination of one or many base kernels. For instance, Cortte et al. 2009) consider polynomial combinations of base kernels, which also has 'sum of products' form. Our experiments do indicate that the learning in the gates (and hence the underlying base kernels) has a significant impact. Understanding K" (Proposition 5.1 might be a way to establish the extent and nature of kernel learning in deep learning. It is also interesting to check if in ResNet the kernels of its DD-FFC-DNNs are combined optimally.
8 CONCLUSION
We attributed the success of deep learning to the following two key ingredients: (i) a composite kernel with gates as fundamental building blocks and (ii) allowing the gates to learn/adapt during training. We justified our claims theoretically as well as experimentally. This work along with that of Lakshminarayanal and Singh (2200) provides a paradigm shift in understanding deep learning. Here, gates play central role. Each gate is related to a hyper-plane, and gates together form layer level binary features whose kernels are the base kernels. Laying out these binary features depth-wise gives rise to a product of the base kernels. The skip connections gives 'sum of product' structure, and convolution with pooling gives rotation invariance. The learning in the gates further enhances the generalisation capabilities of the models.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
[1] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 8139-811 8148, 2019.
[2] Francis R Bach, Gert RG Lanckriet, and Michael Jordan. Multiple kernel learning, conic duality, and the smo algorithm. In Proceedings of the twenty-firt international conference on Machine learning, page 6, 2004.
[3] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pages 10835-10845, 2019.
[4] Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Learning non-linear combinations of kernels. In Advances in neural information processing systems, pages 396-404, 2009.
[5] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint, 10IXi::811.03300 2018.
[6] Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz. Decoupling gating from linearity. CoRR, abs/1906.05032, 2019. URL httpt::://axii..rrrttt http://awxwv..oaab///////// 05032
05032]
[7] Mchmet Gönen and Ethem Alpaydın. Multiple kernel learning algorithms. The Journal of Machine Learning Research, 12:2211-2266 2011.
[8] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580 2018.
[9] Arthur Jacot, Franck Gabriel, and Clément Hongler. Freeze and chaos for dnns: ntk view of batch normalization, checkerboard and boundary effects. arXiv preprint arXiv: (eXx::907.00710 2019.
[10] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014.
[11] Chandrashekar Lakshminarayaman and Amit Vikram Singh. Neural path features and neural path kernel Understanding the role of gates in deep learning. arXiv preprint, arXiv:2006. 10529 (Accepted in NewrIPS 2020), 2020. URL /2 10529
[12] David C. Page.
Davidnet.
URL https://github.com htwp://c.cooavvv.cccco.o... dcpagee
http:///gttbbb.ccom/vvv.coggg
ci fifarlo-fast]
[13] Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer, and Bernhard Schölkopf. Large scale multiple kernel learning. Journal of Machine Learning Research,
2006.
[14] Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In
Artificial Intelligence and Statistics, pages 1216-1224, 2017.


Reviews:
[{"review_id": "yxk49SeaxVS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 work characterising deep neural networks in terms of Neural Tangent Kernels and Neural Path Features. Over the past few years, a number of papers have developed the theory of Neural Tangent Kernels, which can be used to interpret infinite width deep neural networks in the context of a particular type of kernel. A recent paper (Lakshminarayanan and Singh, NeurIPS 2020) provided a new perspective on Neural Tangent Kernels for Gated Neural Networks, by decomposing the network into independent paths. For a fixed set of network weights, we can consider each path to give rise to a feature, corresponding to whether this path is active (i.e., is not switched off by one of the gates on the path). Then, the output of the neural network can be viewed as a weighted sum of active paths, equivalently the dot product of the neural path feature vector and a neural path value vector. Lakshminarayanan and Singh showed that under certain assumptions, a kernel defined in terms of the neural path feature is approximately equal to the neural tangent kernel (up to a constant). Specifically, they show that the value of the neural tangent kernel matrix tends to a constant multiple of the neural path kernel matrix as the width of the network goes to infinity. This suggests that the key component in a deep neural network with RELU activations is the gating structure, which defines active subnetworks, as opposed to the values. \n\nAs far as I can see, this work extends the analysis of (Lakshminarayanan and Singh, NeurIPS 2020) in two ways. Firstly, the analysis is extended to certain ResNet and Convolutional architectures, showing that in both of these cases we can relate the neural tangent kernel matrix to the neural path kernel matrix using a result analogous to Theorem 5.1 in (Lakshminarayanan and Singh, NeurIPS 2020). Secondly, they provide an interpretation of the neural path kernel as a composite kernel composed of layer-wise kernels, giving rise to the title of the paper.\n\nI was not very familiar with the work on neural tangent kernels and encountered (Lakshminarayanan and Singh, NeurIPS 2020) for the first time when reviewing this paper. As such, there were things which I didn't fully understand and may have misunderstood in my review.  \n\nI have one question regarding the theoretical results in both papers. Theorem 5.1 (in both papers) relates the neural path kernel to the neural tangent kernel by showing that the neural tangent kernel for a network in which the gates have been fixed tends to a constant multiple of the neural path kernel as the width of the nerwork goes to infinity. This felt counter-intuitive to me at first reading, as fixing the gates and growing the width to infinity seem to be mutually exclusive. Is it correct to interpret the result as follows? For any fixed gating structure, there is a relationship between the neural path kernel matrix and the neural tangent kernel matrix for a network with that gating structure (i.e., one in which we are only learning the neural path values). As we allow the width go to infinity this relationship tends to one of equality (up to a constant multiple).\n\nI also have a number of questions regarding the empirical results in this paper.\n1. In the experiments where we have fixed the weights, is the model learning parameters in a network in which the gating structure is fixed or is it learning the neural path value vector as part of a linear model?\n2. The discussion mentions performance when we fixed the input gram matrix to be a constant in the definition of the neural path kernel (and hence define the neural path kernel in terms of the gating structure only), but does not include numerical results for this case. I understand that this may be due to a desire to keep the paper within the recommended 8 pages, but don't see why these results could not have been added in the appendix.\n3. The discussion mentions performance when we permute the layers of the model and claims this is robust to permutation of the layers, but but does not include numerical results for this case. As above, I understand that this may be due to a desire to keep the paper within the recommended 8 pages, but don't see why these results could not have been added in the appendix. Moreover, I wasn't not sure what being robust to permutation of the layers means for the case where we are learning the both components of the DGN. Is this claiming that the results do not change if we permute the layers after training in the DL regime?\n\nAdditional comments\n1. LS2020 is used in several places to refer to (Lakshminarayanan and Singh, NeurIPS 2020), the recent paper on which this builds. These should be corrected to match the format of the other citations.\n2. Table 1 contains the information flow for the FCNN. Arguably, this is the simplest of the three architectures and an illustration of the information flow for a CNN could be more useful here. At the very least, the authors should direct the reader to Appendix A, where the CNN is described in more detail.\n3. The authors refer to this work and the previous work of (Lakshminarayanan and Singh, NeurIPS 2020) as a \"paradigm shift in understanding deep learning\". While this work seems to be an interesting and promising line of research, I think it is fair to say that we will need to wait to see if it really does provide a paradigm shift in how we understand deep learning.\n\nIn gener`al, I think the neural tangent kernel is an interesting and promising line of research in the study of deep neural networks. The recent work of Lakshminarayanan and Singh (NeurIPS 2020) seems to add to this and this paper provides a relevant follow-up up that and as such is likely to be of interest to the ICLR community. However, I was did not check the proofs in the appendix or the appendix of (Lakshminarayanan and Singh, NeurIPS 2020), on which the results in this paper depend, and hope another reviewer more familiar with this line of work was able to do so.", "extra_scores": {}, "extra_text": {}}, {"review_id": "V6odCZ5MAsy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "#### General Comments\nThis paper establishes close relationship between CNN and FC-DNN with a composite kernel method. Specially,  this paper shows that architectural choices such as convolutional layers with pooling, skip\nconnections, make deep learning a composite kernel learning method, where the\nkernel is a (architecture dependent) composition of base kernels. This interestingly indicates that  standard deep networks have in-built structural properties that may explain their success before training them. \nMoreover, this paper develops neural path framework to characterize the role of gates/ masks in FC-DNN. \n#### Specific Comments\n(1) It would be more interesting if some superiority of deep learning relative to kernel methods can be provided. \n(2) Lakshminarayanan and Singh (2020) has developed a neural path framework in the NTK regime.  Are there additional challenges when establishing   these similar conclusions for DNNs with Relu activation? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "LI6Z4tf659", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Paper proposes and extension of neural path framework to include composite kernels which comprise of a) FC networks (Hadamard product of gram matrices), b) residual networks (sum of products of base kernels), and c) CNN max-pooling layer. Furthermore, they also include learnt gates instead of static initialized random gates and show learnt gates perform better.  \n\nPaper is well written with main technical contribution being theorem 5.1 which shows for infinite width case $w \\rightarrow \\infty $ the NTK is independent of the weights. It also presents experimental result on MNIST and CIFAR for four proposes regimes of (Definition 5.1) that models are robust to combinatorial variations in layers and inputs.  This results in novel makes an important theoretical contribution towards understanding of why DNN with composite kernels perform well in practice.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DJE2LYjDrer", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Overview: The authors examine deep learning from the perspective of kernel methods and demonstrate that convolution layers in these architectures can make DNNs a form of composite kernel learning.\n\nSignificance: Understanding and interpreting neural networks is an important problem in general; similarly extracting good features key to downstream performance of a neural network. Hence the paper tries to address some important and relevant problems in the field, however, I'm not fully convinced as to whether their procedure is  any more interpretable than existing methods or extracts features optimally.\n\nQuality and Clarity: While the work provides sufficient details to understand prior work and the method itself, the key contribution section of the paper needs more work. \n\nNovelty: There are many works that focus on understanding neural networks and learning features for downstream prediction from the perspective of kernels. The novelty in this work is limited to allowing gating functions to adapt during training, such that the learnt gates can perform better than random gates.\n\nPros:\n1) Paper presents a potential solution to a relevant problem\n2) Paper provides good overview of an existing method that form the basis of the approach.\n\nCons:\n\n1) The most significant weakness of this paper is lack of thorough discussion about what the kernels actually mean in terms of understanding what the neural network is doing. How are these kernels learnt? For this, I think the authors need to make concrete comparisons with methods that are deeply rooted in kernels such as GPs or BNNs. For instance, does using a particular composite kernel structure give you the same predictive performance as when using a GP? Can we directly interpret such models as forms of BNNs or GPs? How does this work compare to more classic work that uses composite kernels in support vector machines? \n\n2) I would have also liked to have seen a better exposition of the interpretability of the method. How does using these composite kernels together compare to other approaches for interpreting deep neural networks like for instance layerwise relevance propagation?\n\n3) There is hardly any reference material which suggests the authors need to include a more thorough description and comparison of related work.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new perspective on deep networks by showing that NPK is composed of base kernels and their dependence on the architecture is explicitized. It is further shown that learning the gates can perform better than random gates.

While the paper provides interesting understanding neural networks, it is unclear what practical benefit can be drawn from it. On the architectures considered such as FC, ResNet and CNN (btw, it seems restricted to 1-D), it will be important to show that such insights lead to new models or learning algorithms that improve upon the standard practice in deep learning (or get very close to).  It is debatable whether drawing such a nontrivial insight alone warrants publication at ICLR, while "nontrivial" itself is a subjective judgement.  I understand people differ in their opinions, and the NTK paper has been impactful.  Unfortunately since there are quite a few other papers that are stronger, I have to recommend not accepting this paper to ICLR this time.
Decision: Reject