Year: 2020

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’ framework1 that characterises the role of gates/masks in fully connected deep networks with ReLU activations.

heading: 1 INTRODUCTION
text: The success of deep learning is attributed to feature learning. The conventional view is that feature learning happens in the hidden layers of a 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 et al. (2018); Arora et al. (2019); Cao and Gu (2019) have provided a 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 tangents, wherein, the gradient of the network output with respect to the network parameters known as the neural tangent features (NTFs) are considered as the features. Arora et al. (2019) show that at randomised initialisation of weights, the kernel matrix associated with the NTFs, known as the neural tangent kernel (NTK) converges to a deterministic matrix and that optimisation and generalisation of infinite width deep neural networks is characterised by this deterministic kernel matrix. Cao and Gu (2019) provided generalisation bounds in terms of the NTK matrix. Arora et al. (2019) also proposed a pure-kernel method based on CNTK (NTK of convolutional neural networks, i.e., CNNs) which significantly outperformed the previous state-of-the-art 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 to provide a kernel interpretation for deep learning that addresses the open issues in the current NTK framework. Here, DNNs with ReLU activations are considered, and the gates (on/off state of ReLU) are encoded 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.
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 to study the various kinds of gates (i.e., NPFs), such as random gates (of a randomly initialised network), semi-learnt gates (sampled at 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 ⇥ NPK, at random initialisation of weights. For a pair of input examples, NPK is a similarity measure
1Introduced for the first time in the work of Lakshminarayanan and Singh (2020).
that depends on the size of the sub-network formed by the gates that are active simultaneously 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. It was also observed (on standard datasets) that when learnt gates/masks are used, the weights of the value network can be reset and re-trained from scratch without significant loss of performance.

heading: 1.1 CONTRIBUTIONS IN THIS WORK
text: 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. Fully-Connected networks: H fc 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 res assumes a sum of products form. In particular, consider a ResNet with (b + 2) blocks and b skip connections. Within this ResNet there are i = 1, . . . , 2b possible dense networks, and then H res = P2b i=1 CiH fc i
, where Ci > 0 are positive constants based on normalisation layers.
3. Convolutional neural networks (CNN) with pooling: Hcnn 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 i) ‘standard’:
input is the actual image and ii) ‘all-ones’: input is a tensor with all entries as ‘1’.
We observe in our experiments that the performance is robust to such combinatorial variations.
Message: This work along with that of Lakshminarayanan and Singh (2020) provides a paradigm shift in understanding deep learning. Here, gates play a central role. Each gate is related to a hyperplane, 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 a ‘sum of product’ structure, and convolution with pooling gives rotation invariance.
Organisation: Section 2 describes the network architectures namely fully-connected, convolutional and residual, which we take up for theoretical analysis. Section 3 extends the neural path framework to CNN and ResNet. Section 4 explains the composite kernel. Section 5 connects the NTK and NPK for CNN and ResNet. Section 6 consists of numerical experiments.

heading: 2 ARCHITECTURES: FULLY CONNECTED, CONVOLUTIONAL AND RESIDUAL
text: 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, [n] is the set {1, . . . , n}, and the dataset is given by (xs, ys)ns=1 2 Rdin ⇥ R. Fully Connected: We consider fully connected networks with width ‘w’ and depth ‘d’.
CNN: We consider a 1-dimensional convolutional neural network with circular convolutions (see
Table 2), with dcv convolutional layers (l = 1, . . . , dcv), followed by a global-average/max-pooling layer (l = dcv + 1) and dfc (l = dcv + 2, . . . , dcv + dfc + 1) FC layers. The convolutional window size is wcv < din, the number of filters per convolutional layer is w, and the width of the FC is also w. Definition 2.1 (Circular Convolution). For x 2 Rdin , i 2 [din] and r 2 {0, . . . , din 1}, define :
(i) i r = i+ r, for i+ r  din and i r = i+ r din, for i+ r > din. (ii) rot(x, r)(i) = x(i r), i 2 [din].
(iii) qx,⇥(ifout, iout, l) = P
icv,iin ⇥(icv, iin, iout, l) · zx,⇥(ifout (icv 1), iin, l 1), where iin/iout are
the indices (taking values in [w]) of the input/output filters. icv denotes the indices of the convolutional window (taking values in [wcv]) between input and output filters iin and iout. ifout denotes the indices (taking values in [din], the dimension of input features) of individual nodes in a given output filter.
Definition 2.2 (Pooling). Let Gpool x,⇥(ifout, iout, dcv + 1) denote the pooling mask, then we have
zx,⇥(iout, dcv + 1) = X
ifout
zx,⇥(ifout, iout, dcv) ·Gpoolx,⇥(ifout, iout, dcv + 1),
where in the case of global-average-pooling Gpool x,⇥(ifout, iout, dcv + 1) = 1 din , 8iout 2 [w], ifout 2 [din], and in the case of max-pooling, for a given iout 2 [w], Gpoolx,⇥(imax, iout, dcv + 1) = 1 where imax = argmaxifout zx,⇥(ifout, iout, dcv), and G pool x,⇥(ifout, iout, dcv + 1) = 0, 8ifout 6= imax.
ResNet: We consider ResNets with ‘(b + 2)’ blocks and ‘b’ skip connections between the blocks (Figure 1). Each block is a FC-DNN of depth ‘dblk’ and width ‘w’. Here, pre i , post i
, i 2 [b] are normalisation variables. Definition 2.3 (Sub FC-DNNs). Let 2[b] denote the power set of [b] and let J 2 2[b] denote any subset of [b]. Define the‘J th’ sub-FC-DNN of the ResNet to be the fully connected network obtained by ignoring/removing (see Figure 1) the skip connections skip
j , 8j 2 J (see Figure 1).

heading: 3 NEURAL PATH FRAMEWORK
text: 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 ReLU activation, which can be thought of as gate/mask that blocks/allows its pre-activation input depending on its 0/1 state ( 0 if pre-activation is negative and 1 if pre-activation is positive). The key idea here is to break a DNN (with ReLU) into paths, and express its output as a summation of the contribution of the paths. The contribution of a 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 x 2 Rdin , the gating information is encoded in a novel neural path feature (NPF), x,⇥ 2 RP and a novel neural path value (NPV), v⇥ 2 RP encodes the weights. The output of the DNN is then the inner product of the NPFs and NPVs, i.e., ŷ⇥(xs) = h xs,⇥, v⇥i (Proposition 3.4). Definition 3.1. A path starts from an 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
P fc = dinw(d 1), P cnn = din(wcvw)dcvw(dfc 1) and P res = din ·
P b
i=0
b
i
w (i+2)dblk 1.
Notation 3.1 (Index Maps). The ranges of index maps I f l , Icv l , Il are [din], [wcv] and [w] respectively. The index maps are used to identify the nodes through which a path p passes. Further, let IJ (p) : [P res] ! 2[b] 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 A⇥(x, p). We define:
(a) A⇥(x, p) = ⇧ d 1 l=1 Gx,⇥(Il(p), l), for FC-DNN and ResNet.
(b) A⇥(x, p) = ⇧ dcv+1 l=1 Gx,⇥(I f l (p), Il(p), l) ·⇧ dcv+dfc+1 l=dcv+2 Gx,⇥(Il(p), l), for CNN.
In CNN, the pooling layer is accounted by letting G = Gpool for l = dcv + 1.
Definition 3.3 (Bundle Paths of Sharing Weights). Let P̂ cnn = P cnn din , and {B1, . . . , BP̂ cnn} be a collection of sets such that 8i, j 2 [P̂ cnn], i 6= j we have Bi \Bj = ; and [P̂ cnn i=1Bi = [P cnn]. Further, if paths p, p 0 2 Bi, then Icvl (p) = Icvl (p0), 8l = 1, . . . , dcv and Il(p) = Il(p0), 8l = 0, . . . , dcv.
Proposition 3.2. There are exactly din paths in a bundle.
Definition 3.4 (Normalisation Factor). Define (J ) = ⇧ j2J pre j · ⇧ j02[b] post j0
Weight sharing is shown in the the cartoon in Figure 2, which shows a CNN with din = 3, w = 1, wcv = 2, dcv = 3, dfc = 0. Here, the red coloured paths all share the same weights ⇥(1, 1, 1, l), l = 1, 2, 3 and the blue coloured paths all share the same weights given by ⇥(2, 1, 1, l), l = 1, 2, 3.
Definition 3.5 (Neural Path Value). The product of the weights and normalisation factors in a path p is its ‘value’. The value of a path bundle is the value of any path in that bundle. The path/bundle
values are denoted by v⇥(p)/v⇥(Bp̂) and are defined as follows:
(a) v⇥(p) = ⇧dl=1⇥(Il 1(p), Il(p), l).
(b) v⇥(Bp̂) = ⇧ dcv l=1⇥(Icvl (p), Il 1(p), Il(p), l) ·⇧ dcv+dfc+1 l=dcv+2 ⇥(Il 1(p), Il(p), l), for any p 2 Bp̂.
(c) v⇥(p) = ⇧dl=1⇥(Il 1(p), Il(p), l) · (IJ (p)).
The neural path value is defined as v⇥ = (v⇥(p), p 2 [P fc]) 2 RP
fc
, v⇥ = (v⇥(Bp̂), p̂ 2 [P̂ cnn]) 2
RP̂ cnn , and v⇥ = (v⇥(p), p 2 [P res]) 2 RP res for FC-DNN, CNN and ResNet respectively.
Proposition 3.3 (Rotational Invariance). Internal variables in the convolutional layers are circularly symmetric, i.e., for r 2 {0, . . . , din 1} it follows that (i) zrot(x,r),⇥(ifout, ·, ·) = zx,⇥(ifout r, ·, ·), (ii) qrot(x,r),⇥(ifout, ·, ·) = qx,⇥(ifout r, ·, ·) and (iii) Grot(x,r),⇥(ifout, ·, ·) = Gx,⇥(ifout r, ·, ·). Definition 3.6. The neural path feature (NPF) corresponding to a path p is given by
(a) x,⇥(p) = x(I f0(p))A⇥(xs, p) for FC-DNN and ResNet.
(b) x,⇥(p̂) = P p̂2Bp̂ x(I f 0(p))A⇥(x, p) for CNN.
The NPF is defined as x,⇥ = ( x,⇥(p), p 2 [P fc]) 2 RP
fc
, x,⇥ = ( x,⇥(Bp̂), p̂ 2 [P̂ cnn]) 2 RP̂
cnn
,
and x,⇥ = ( x,⇥(p), p 2 [P res]) 2 RP
res
for FC-DNN, CNN and ResNet respectively.
Proposition 3.4 (Output=hNPF,NPVi). The output of the network can be written as an inner product of the NPF and NPV, i.e., ŷ⇥(x) = h x,⇥, v⇥i.

heading: 4 NEURAL PATH KERNEL: COMPOSITE KERNEL BASED ON SUB-NETWORKS
text: In this section, we will discuss the properties of neural path kernel (NPK) associated with the NPFs defined in Section 3. Recall that a co-ordinate of NPF can 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 a quantity denoted by ⇤ (Definition 4.2). The number of active paths are in turn dependent on the number of active gates in each layer, a fact that endows the NPK with a hierarchical/composite 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 a 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 to be H⇥ = >⇥ ⇥, where ⇥ = ( x1,⇥, . . . , xn,⇥) 2 RP⇥n is the NPF matrix. Definition 4.2. Define ⇤⇥(i, x, xs0) = |{p 2 [P ] : I0(p) = i, A⇥(xs, p) = A⇥(xs0 , p) = 1}| to be
total number of ‘active’ paths for both xs and xs0 that pass through input node i.
Definition 4.3 (Layer-wise Kernel). Let Gx,⇥(·, l) 2 Rw be w-dimensional feature of the gating values in layer l for input x 2 Rdin . Define layer-wise kernels:
H lyr l,⇥(s, s 0) = hGxs,⇥(·, l)Gxs0 ,⇥(·, l)i
Lemma 4.1 (Product Kernel). Let H fc denote the NPK of a FC-DNN, and for D 2 Rdin⇥din be a diagonal matrix with strictly positive entries, and u, u 0 2 Rdin let hu, u0iD = P din i=1 D(i)u(i)u 0(i).
H fc ⇥(s, s 0) = hxs, xs0i⇤(·,xs,xs0 ) = hxs, x 0 s i⇧d 1 l=1 H lyr l,⇥(s, s 0)
Lemma 4.2 (Sum of Product Kernel). Let Hres⇥ be the NPK of the ResNet, and H J ⇥ be the NPK of the sub-FC-DNN within the ResNet obtained by ignoring those skip connections in the set J . Then,
H res ⇥ = X
J22[b] H
J ⇥
Lemma 4.3 (Rotational Invariant Kernel). Let Hcnv⇥ denote the NPK of a CNN, then
H cnv ⇥ (s, s 0) =
din 1X
r=0
hxs, rot(xs0 , r)i⇤(·,xs,rot(xs0 ,r)) = din 1X
r=0
hrot(xs, r), xs0i⇤(·,rot(xs,r),xs0 )

heading: 5 MAIN THEORETICAL RESULT
text: In this section, we proceed with the final step in extending the neural path theory to CNN and ResNet. As with LS2020, we 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.
DGN set up was 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 ⇥f 2 Rdfnet which holds the NPFs (i.e., the gating information) and a value network parameterised by ⇥v 2 Rdvnet which holds the NPV. The combined parameterisation is denoted by ⇥DGN = (⇥f,⇥v) 2 Rdfnet+dvnet . Thus the learning problem in the DGN is ŷ⇥DGN(x) = h x,⇥f , v⇥vi.
Definition 5.1. The DGN has 4 regimes namely decoupled learning (DL), fixed learnt (FL), fixed random-dependent initialisation (FR-DI) and fixed random-independent initialisation (FR-II). In all the regimes ŷ⇥DGN is the output, and ⇥ v
0 is always initialised at random and is trainable. However, the regimes differ based on i) trainability of ⇥f, ii) initialisation ⇥f0 as described below.
DL : ⇥f is trainable, and ⇥f0 and ⇥ v 0 are random and statistically independent, > 0. FL : ⇥f is non-trainable, and ⇥f0 is pre-trained; ⇥ v 0 is statistically independent of ⇥ f 0. FR-II : ⇥f is non-trainable, and ⇥f0 and ⇥ v 0 are random and statistically independent. FR-DI : ⇥f is non-trainable, and ⇥f0 = ⇥ v 0.
DGN Regimes: The flexibility in a DGN is that a) ⇥f can be trainable/non-trainable and b) ⇥f0 can be random or pre-trained using ŷ⇥f as the output (Definition 5.1). By using the DGN setup we can study the role of gates by comparing (a) learnable (DL) vs fixed gates (FL, 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.
Proposition 5.1. Let K⇥DGN be the NTK matrix of the DGN, then K⇥DGN = K v ⇥DGN +K f ⇥DGN , with
Overall NTK K⇥DGN(s, s0) = h xs,⇥DGN , xs0 ,⇥DGNi, where x,⇥DGN = r⇥DGN ŷ⇥DGN(x) 2 R dnet Feature NTK Kv⇥DGN(s, s 0) = h v xs,⇥DGN , v xs0 ,⇥ DGNi, where vx,⇥DGN = r⇥v ŷ⇥DGN(x) 2 R d v net
Value NTK K f⇥DGN(s, s 0) = h f xs,⇥DGN , f xs0 ,⇥ DGNi, where fx,⇥DGN = r⇥f ŷ⇥DGN(x) 2 Rd f net
Remark: There are two separate NTKs, each one corresponding to feature and value networks respectively. In the case of fixed regimes, K f = 0.
Theorem 5.1. (i) ⇥v0 is statistically independent of ⇥ f 0 (ii) ⇥ v 0 are i.i.d symmetric Bernoulli over { ,+ }. Let fc = cscalepw and cv = cscalep wwcv for FC and convolutional layers. As w ! 1, we have:
(ii) K v ⇥DGN0 ! fcH⇥f0 , fc = d 2(d 1) fc for FC-DNN,
(ii) K v ⇥DGN0 ! cvH⇥f0 , cv = 1 din 2
⇣ dcv 2(dcv 1) cv 2dfc fc + dfc 2dcvcv 2(dfc 1) fc ⌘ for CNN with GAP,
(iii) K v ⇥DGN0 !
P J22[b] J rs H
J ⇥f0 , J rs
= (|J |+ 2)dblk 2 (|J |+2)dblk 1 fc (J )2 for ResNet.
• fc, cv, rs : The simplest of all is fc = d 2(d 1)fc , where d is due the fact that there are d weights in a path and in the exponent of fc, factor (d 1) arises because the gradient of a particular weight is 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. cv is similar to fc with separate bookkeeping for the convolutional and FC layers, and 1
d 2 in is due to the GAP layer. In rs, the fc for all the sub-FC-DNNs within the ResNet are scaled by the corresponding normalisation factors and summed.
• Decoupling In a DNN with ReLU (and FR-DI regime of DGN), NPV and NPF are not statistically independent at initialisation, i.e., Theorem 5.1 does not hold. However, the current state-of-the-art analysis Jacot et al. (2018); Arora et al. (2019); Cao and Gu (2019) is in the infinite width (w ! 1) regime, wherein, the change in activations during training is only of the order q 1 w
, which goes to 0 as w ! 1. Hence, though assumption in Theorem 5.1 may not hold exactly, it is not a strong assumption to 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 5.1 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.

heading: 6 NUMERICAL EXPERIMENTS
text: We now show via experiments that gates indeed play a central role in deep learning. For this we use the DGN setup (Figure 4) to create models in the 4 regimes namely DL, FL, FR-II and FR-DI. In
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), i.e., a tensor with all its entries to be 1. We observe that in all the 4 regimes, the models are robust to the combinatorial variations.
Setup: Datasets are MNIST and CIFAR-10. For CIFAR-10, we use Figure 4 with 3⇥ 3 windows and 128 filters in each layer. For MNIST, we use FC instead of the convolutional layers. All the FC-DNNs and CNNs are trained with ‘Adam’ [10] (step-size = 3 ·10 4 , batch size = 32). A ResNet called DavidNet [12] was trained with SGD ( step-size = 0.5, batch size = 256). We use = 10.
Reporting of Statistics: The results are summarised in Figure 4. For FC-DNN and CNN, in each of the 4 regimes, we train 48 = 2(xv = x/xv = 1)⇥ 24(layer permutations) models. Each of these models are trained to almost 100% accuracy and the test performance is taken to be the best obtained in a 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 ⇥v are trained. In DL regime, both ⇥f and ⇥v are trained, and FL regime ⇥f is pre-trained and fixed, and only ⇥v 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.43% in CIFAR-10) and the performance of standard DNN with ReLU. The main observations are listed below (those by Lakshminarayanan and Singh (2020) 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 ReLU 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 S1 = { ReLU, FL , DL}, S2 = { FR} and S3 = { CNTK }, and explain the difference in performance due to gate learning. S2 and S3 have no gate learning. However, S3 due to its infinite width has better averaging resulting in a well formed kernel and hence performs better than S2 which is a 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 S1 and S2, but, S1 with gate learning is better (77.5% or above in CIFAR-10) than S2 (67% in CIFAR-10) with no gate learning. Thus neither finite width, nor the conventional feature learning explain the difference between S1 and S2. Thus, ‘gate learning’ discriminates the regimes S1, S2 and S3 better than the conventional feature learning view.
5. Permutation and Input Invariance: The performance (in all the 4 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 on ⇤, 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 to the product ⇧(d 1)
l=1 H lyr l,⇥ 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 a 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 on performance, and this experiment confirms the same.

heading: 7 RELATED AND FUTURE WORK
text: Our paper extended the work of Lakshminarayanan and Singh (2020) 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); Jacot et al. (2019); Du et al. (2018) have all used the NTK framework to understand questions related to optimisation and/or generalisation in DNNs. We now discuss the future work below.
1. Base Kernel: At randomised initialisation, for each l, H
lyr l,⇥0 (s,s0)
w is the fraction of gates that
are simultaneously active for input examples s, s0, which in the limit of infinite width is equal to 1 2 angle(zxs(·, l), zxs0 (·, l)) (Xie et al., 2017). Further, due to the property of ReLU to pass only positive components, we conjecture that the pairwise angle between input examples measured at the
hidden layer outputs is a decreasing function of depth and as l ! 1, H
lyr l,⇥0 (s,s0)
w ! 12 , 8s, s 0 2 [n]. We reserve a formal statement on the behaviour of H lyr
l,⇥0 for the future.
2. Multiple Kernel Learning (Gönen and Alpaydın, 2011; Bach et al., 2004; Sonnenburg et al., 2006; Cortes et al., 2009) is the name given to a class of methods that learn a linear or non-linear combination of one or many base kernels. For instance, Cortes et al. (2009) consider polynomial combinations of base kernels, which also has a ‘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 f (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 sub-FC-DNNs are combined optimally.

heading: 8 CONCLUSION
text: 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 Lakshminarayanan and Singh (2020) provides a paradigm shift in understanding deep learning. Here, gates play a 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 a ‘sum of product’ structure, and convolution with pooling gives rotation invariance. The learning in the gates further enhances the generalisation capabilities of the models.

Review summaries:
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.