AND

# Disentangling deep neural networks with rectified linear units using duality

Chandrashekar Lakshminarayanan
Indian Institute of Technology Madras
<EMAIL_ADDRESS>
&Amit Vikram Singh
<EMAIL_ADDRESS>

###### Abstract

Despite their success deep neural networks (DNNs) are still largely considered
as black boxes. The main issue is that the linear and non-linear operations
are entangled in every layer, making it hard to interpret the hidden layer
outputs. In this paper, we look at DNNs with rectified linear units (ReLUs),
and focus on the gating property (‘on/off’ states) of the ReLUs. We extend the
recently developed dual view in which the computation is broken path-wise to
show that learning in the gates is more crucial, and learning the weights
given the gates is characterised analytically via the so called _neural path
kernel_ (NPK) which depends on inputs and gates. In this paper, we present
novel results to show that convolution with global pooling and skip connection
provide respectively rotational invariance and ensemble structure to the NPK.
To address ‘black box’-ness, we propose a novel interpretable counterpart of
DNNs with ReLUs namely deep linearly gated networks (DLGN): the pre-
activations to the gates are generated by a deep linear network, and the gates
are then applied as external masks to learn the weights in a different
network. The DLGN is not an alternative architecture per se, but a
disentanglement and an interpretable re-arrangement of the computations in a
DNN with ReLUs. The DLGN disentangles the computations into two
‘mathematically’ interpretable linearities (i) the ‘primal’ linearity between
the input and the pre-activations in the gating network and (ii) the ‘dual’
linearity in the path space in the weights network characterised by the NPK.
We compare the performance of DNN, DGN and DLGN on CIFAR-10 and CIFAR-100 to
show that, the DLGN recovers more than $83.5\%$ of the performance of state-
of-the-art DNNs, i.e., while entanglement in the DNNs enable their improved
performance, the ‘disentangled and interpretable’ computations in the DLGN
recovers most part of the performance. This brings us to an interesting
question: ‘Is DLGN a universal spectral approximator?’

##  1 Introduction

Despite their success deep neural networks (DNNs) are still largely considered
as black boxes. The main issue is that in each layer of a DNN, the linear
computation, i.e., multiplication by the weight matrix and the non-linear
activations are entangled. Such entanglement has its _pros_ and _cons_. The
commonly held view is that such entanglement is the key to success of DNNs, in
that, it allows DNNs to learn sophisticated structures in a layer-by-layer
manner. However, in terms of interpretability, such entanglement has an
adverse effect: only the final layer is linear and amenable to a
feature/weight interpretation, and the hidden layers are non-interpretable due
to the non-linearities.

Prior works (Jacot et al., 2018; Arora et al., 2019; Cao and Gu, 2019) showed
that training an infinite width DNN with gradient descent is equivalent to a
kernel method with the so called _neural tangent kernel_ matrix. As a pure
kernel method, the NTK matrix performed better than other pure kernel methods.
However, in relation to ‘black box’-ness, there are two issues with NTK
theory: (i) Issue I: Infinite width NTK matrix does not explain fully the
success of DNNs because it was observed that finite width DNNs outperform
their infinite width NTK counterparts, and it was an open question to
understand this performance gap (Arora et al., 2019), and (ii) Issue II: Since
the NTK is based on the gradients, it does not offer further insights about
the inner workings of DNNs even for infinite width.

A dual view for DNNs with rectified linear units (ReLUs) was recently
developed by Lakshminarayanan and Singh (2020) who exploited the gating
property (i.e., ‘on/off’ states) of the ReLUs. The dual view is essentially
_linearity in the path space_ , i.e., the output is the summation of path
contributions. While the weights in a path are the same for each input,
whether or not a path contributes to the output is entirely dictated by the
gates in the path, which are ‘on/off’ based on the input. To understand the
role of the gates, a deep gated network (DGN) (see Figure 1) was used to
_disentangle_ the _learning in the gates_ from the _learning in weights_. In a
DGN, the gates are generated (and learnt) in a ‘gating network’ which is a DNN
with ReLUs and are applied as external signals and the weights are learnt in a
‘weight network’ consisting of _gated linear units_ (GaLUs) (Fiat et al.,
2019). Each GaLU multiplies its pre-activation and the external gating signal.
Using the DGN, two important insights were provided: (i) learning in the gates
is the most crucial for finite width networks to outperform infinite width
NTK; this addresses Issue I, and (ii) in the limit of infinite width, learning
the weights with fixed gates, the NTK is equal to (but for a scalar) a so
called neural path kernel (NPK) which is a kernel solely based on inputs and
gates. This shifts Issue II on interpretability to that of interpretability of
the gates as opposed to interpretability of the gradients.

Deep Gated NetworkGating NetworkDNN with ReLUsInputWeight NetworkDNN with
GaLUsInputOutputGating Signal

Deep Linearly Gated NetworkGating NetworkDeep Linear NetworkInputWeight
NetworkDNN with GaLUsInput =$\mathbf{1}$OutputPre-activationsGating
SignalGates

Figure 1: DGN is a setup to understand the role of gating in DNNs with ReLUs.
The DLGN setup completely disentangles and re-arranges the computations in an
interpretable manner. The surprising fact that a constant $\mathbf{1}$ input
is given to weight network of DLGN is justified by theory and experiments in
Sections 3.1 and 3.2.

Our Contribution. We _extend the dual view_ to address ‘black box’-ness by
completely _disentangling_ the ‘gating network’ and the ‘weight network’. Our
contributions are listed below.

$\bullet$ Disentangling Gating Network. For this, we propose a novel Deep
_Linearly_ Gated Network (DLGN) as a _mathematically interpretable_
counterpart of a DNN with ReLUs (see Figure 1). In a DLGN, the gating network
is a deep linear network, i.e., there is disentanglement because of the
absence of non-linear activations. The gating network is mathematically
interpretable, because, the transformations from input to the pre-activations
are entirely linear; we call this primal linearity.

$\bullet$ Dual View (Section 3.1). We present an unnoticed insight in prior
work on fully connected networks that the NPK is a product kernel and is
invariant to layer permutations. We present new results to show that (i) the
NPK is rotationally invariant for convolutional networks with global average
pooling, and (ii) the NPK is an ensemble of many kernels in the presence of
skip connections.

$\bullet$ Disentangling Weight Network. We then argue via theory and
experiments that the _weight network is disentangled in the path space_ ,
i.e., it learns path-by-path and not layer-by-layer. For this, in Section 3.2
we show via experiments that destroying the layer-by-layer structure by
permuting the layers and providing a constant $\mathbf{1}$ as input (see DLGN
in Figure 1) do not degrade performance. These counter intuitive results are
difficult to reconcile using the commonly held ‘sophisticated structures are
learnt in layers’ interpretation. However, these experimental results follow
from the theory in Section 3.1. In other words, it is useful to think that the
learning in the weight network happens path-by-path; we call this dual
linearity, which (for infinite width) is interpreted via the NPK.

Message. The DLGN is not an alternative architecture per se, but a
disentanglement and an interpretable re-arrangement of the computations in a
DNN with ReLUs. The DLGN disentangles the computations into two
‘mathematically’ interpretable linearities (i) the ‘primal’ linearity and (ii)
the ‘dual’ linearity interpreted via the NPK. Using the facts that the NPK is
based on input and the gates, and in a DLGN, the pre-activations in the gating
network are ‘primal’ linear, we have complete disentanglement. We compare the
performance of DNN, DGN and DLGN on CIFAR-10 and CIFAR-100 to show that, the
DLGN recovers more than $83.5\%$ of the performance of state-of-the-art DNNs,
i.e., while entanglement in the DNNs enable their improved performance, the
‘disentangled and interpretable’ computations in the DLGN recovers most part
of the performance. This brings us to an interesting question: ‘Is DLGN a
universal spectral approximator?’ (see Section 3.2).

###  1.1 Related Works.

We now compare our work with the related works.

$\bullet$ Kernels. Several works have examined theoretically as well as
empirically two important kernels associated with a DNN namely its NTK based
on the correlation of the gradients and the conjugate kernel based on the
correlation of the outputs (Fan and Wang, 2020; Geifman et al., 2020; Liu et
al., 2020; Chen et al., 2020; Xiao et al., 2020; Jacot et al., 2018; Arora et
al., 2019; Novak et al., 2018; Lee et al., 2017, 2020a). In contrast, the NPK
is based on the correlation of the gates. We do not build pure-kernel method
with NPK, but use it as an aid to disentangle finite width DNN with ReLUs.

$\bullet$ ReLU, Gating, Dual Linearity. A spline theory based on max-affine
linearity was proposed in (Balestriero et al., 2018; Balestriero and Baraniuk,
2018) to show that a DNN with ReLUs performs hierarchical, greedy template
matching. In contrast, the dual view exploits the gating property to simplify
the NTK into the NPK. Gated linearity was studied in (Fiat et al., 2019) for
single layered networks, along with a non-gradient algorithm to tune the
gates. In contrast, we look at networks of any depth, and the gates are tuned
via standard optimisers. The main novelty in our work in contrast to the above
is that in DLGN the feature generation is linear. The gating in this paper
refers to the gating property of the ReLU itself and has no connection to
(Srivastava et al., 2015) where gating is a mechanism to regulate information
flow. Also, the soft-gating used in our work and in (Lakshminarayanan and
Singh, 2020) enables gradient flow via the gating network and is different
from _Swish_ (Ramachandran et al., 2018), which is the multiplication of pre-
activation and sigmoid.

$\bullet$ Finite vs Infinite Width. Lee et al. (2020b) perform an extensive
comparison of finite versus infinite width DNNs. An aspect that is absent in
their work, but present in the dual view is the disentanglement of gates and
weights, and the fact that the learning in gates is crucial for finite width
network to outperform infinite width DNNs. In our paper, we make use of theory
developed for infinite width DNNs to provide empirical insights into inner
workings of finite width networks.

$\bullet$ Capacity. Our experiments on destruction of layers, and providing
constant $\mathbf{1}$ input are direct consequences of the insights from dual
view theory. These are not explained by mere capacity based studies showing
DNNs are powerful to fit even random labelling of datasets (Zhang et al.,
2016).

##  2 Prior Work : Neural Tangent Kernel and Dual View

In this section, we will focus on the dual view (Lakshminarayanan and Singh,
2020) and how the dual view helps to address the open question in the NTK
theory. We begin with a brief summary of NTK.

###  2.1 Infinite Width DNN = Kernel Method With Neural Tangent Kernel

An important kernel associated with a DNN is its _neural tangent kernel_
(NTK), which, for a pair of input examples
$x,x^{\prime}\in\mathbb{R}^{d_{\text{in}}}$, and network weights
$\Theta\in\mathbb{R}^{d_{\text{net}}}$, is given by:

$\text{NTK}(x,x^{\prime})\quad=\quad\langle\nabla_{\Theta}\hat{y}(x),\nabla_{\Theta}\hat{y}(x^{\prime})\rangle$,
where

$\hat{y}_{\Theta}(\cdot)\in\mathbb{R}$ is the DNN output. Prior works (Jacot
et al., 2018; Arora et al., 2019; Cao and Gu, 2019) have shown that, as the
width of the DNN goes to infinity, the NTK matrix converges to a limiting
deterministic matrix $\text{NTK}_{\infty}$, and training an infinitely wide
DNN is equivalent to a kernel method with $\text{NTK}_{\infty}$. While, as a
pure kernel $\text{NTK}_{\infty}$ performed better than prior kernels by more
than $10\%$, Arora et al. (2019) observed that on CIFAR-10:

CNTK-GAP: $\mathbf{77.43\%}\leq$ CNN-GAP: $\mathbf{83.30\%}$

where, CNN-GAP is a convolutional neural network with global average pooling
and CNTK-GAP is its corresponding $\text{NTK}_{\infty}$ matrix. Due to this
performance gap of about $5-6\%$, they concluded that $\text{NTK}_{\infty}$
does not explain fully the success of DNNs, and explaining this gap was an
open question.

###  2.2 Dual View For DNNs with ReLUs: Characterising the role of gates

In the dual view, the computations are broken down path-by-path. The input and
the gates (in each path) are encoded in a neural path feature vector and the
weights (in each path) are encoded in a neural path value vector, and the
output is the inner product of these two vectors. The learning in the gates
and the learning in the weights are separated in a deep gated network (DGN)
setup, which leads to the two main results of dual view presented in Section
2.2.3 and Section 2.2.4, wherein, the neural path kernel, the Gram matrix of
the neural path features will play a key role.

####  2.2.1 Neural Path Feature, Neural Path Value and Neural Path Kernel

Consider a fully connected DNN with ‘$d$’ layers and ‘$w$’ hidden units in
each layer. Let the DNN accept input $x\in\mathbb{R}^{d_{\text{in}}}$ and
produce an output $\hat{y}_{\Theta}(x)\in\mathbb{R}$.

######  Definition 2.1.

A path starts from an input node, passes through a weight and a hidden unit in
each layer and ends at the output node. We define the following quantities for
a path $p$: _ Activity : $A_{\Theta}(x,p)$ is the product of the ‘$d-1$’ gates
in the path. Value : $v_{\Theta}(p)$ is the product of the ‘$d$’ weights in
the path. Feature : $\phi_{\Theta}(x,p)$ is the product of the signal at the
input node of the path and $A_{\Theta}(x,p)$. _ The _neural path feature_
(NPF) given by
$\phi_{\Theta}(x)=\left(\phi_{\Theta}(x,p),p=1,\ldots,P^{\text{fc}}\right),\in\mathbb{R}^{P^{\text{fc}}}$
and the _neural path value_ (NPV) given by
$v_{\Theta}=\left(v_{\Theta}(p),p=1,\ldots,P^{\text{fc}}\right),\in\mathbb{R}^{P^{\text{fc}}}$,
where $P^{\text{fc}}=d_{\text{in}}w^{(d-1)}$ is the total number of paths.

######  Proposition 2.1.

The output of the DNN is then the inner product of the NPF and NPV:

$\displaystyle\hat{y}_{\Theta}(x)=\langle\phi_{\Theta}(x),v_{\Theta}\rangle=\sum_{p\in[P]}\phi_{\Theta}(x,p)v_{\Theta}(p)$
(1)

Subnetwork Interpretation of DNNs with ReLUs. A path is active only if all the
gates in the path are active. This gives a subnetwork interpretation, i.e.,
for a given input $x\in\mathbb{R}^{d_{\text{in}}}$, only a subset of the gates
and consequently only a subset of the paths are active, and the input to
output computation can be seen to be produced by this active subnetwork. The
following matrix captures the correlation of the active subnetworks for a
given pair of inputs $x,x^{\prime}\in\mathbb{R}^{d_{\text{in}}}$.

######  Definition 2.2 (Overlap of active sub-networks).

The total number of ‘active’ paths for both $x$ and $x^{\prime}$ that pass
through input node $i$ is defined to be:

$\textbf{overlap}_{\Theta}(i,x,x^{\prime})\stackrel{{\scriptstyle\Delta}}{{=}}{\left|\\{p\colon
p\,\text{starts at
node}\,i\,,A_{\Theta}(x,p)=A_{\Theta}(x^{\prime},p)=1\\}\right|}$

######  Lemma 2.1 (Neural Path Kernel (NPK)).

Let $D\in\mathbb{R}^{d_{\text{in}}}$ be a vector of non-negative entries and
for $u,u^{\prime}\in\mathbb{R}^{d_{\text{in}}}$ , let $\langle
u,u^{\prime}\rangle_{D}=\sum_{i=1}^{d_{\text{in}}}D(i)u(i)u^{\prime}(i)$. Then
the neural path kernel (NPK) is given by:

$\displaystyle\text{NPK}_{\Theta}(x,x^{\prime})\stackrel{{\scriptstyle\Delta}}{{=}}\langle\phi_{\Theta}(x),\phi_{\Theta}(x^{\prime})\rangle=\langle
x,x^{\prime}\rangle_{\textbf{overlap}_{\Theta}(\cdot,x,x^{\prime})}$

DGN (prior work)Gating/Feature Network:
$\Theta^{\textrm{f}}$$x$$\hat{y}_{\text{f}}$ReLU$q^{\text{f}}_{x}$$\max(0,q^{\text{f}}_{x})$GHard
: $G(q)=\mathbbm{1}_{\\{q>0\\}}$Soft : $G(q)=\frac{1}{1+\exp(-\beta\cdot
q)}$Weight/Value Network:
${\Theta}^{\text{v}}$$x$$\hat{y}_{\text{DGN}}$GaLU$q^{\text{v}}_{x}$$q^{\text{v}}_{x}\cdot
G(q^{\text{f}}_{x})$

CNN-GAP :
80.32%$\hat{y}(x)$$FC_{2}$$FC_{1}$GAPReLU$C_{4}$ReLU$C_{3}$ReLU$C_{2}$ReLU$C_{1}$$x$CNN-
GAP-DGN(FL: 79.68%, Standalone: 77.12%, FR:
67.09%)$\hat{y}_{\text{f}}(x)$$FC^{\text{f}}_{2}$$FC^{\text{f}}_{1}$GAPReLU$C^{\text{f}}_{4}$ReLU$C^{\text{f}}_{3}$ReLU$C^{\text{f}}_{2}$ReLU$C^{\text{f}}_{1}$$x$$\hat{y}_{\text{DGN}}(x)$$FC^{\text{v}}_{2}$$FC^{\text{v}}_{1}$GAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x$$G_{1}$$G_{2}$$G_{3}$$G_{4}$

Figure 2: Shows the DGN on the left. Training: In the case of fixed learnt
gates, the feature network is pre-trained using $\hat{y}_{f}$ as the output,
and then the feature network is frozen, and the value network is trained with
$\hat{y}_{DGN}$ as the output. In the case of fixed random gates, the feature
network is initialised at random and frozen, and the value network is trained
with $\hat{y}_{DGN}$ as the output. In the case of fixed gates, hard gating
$G(q)=\mathbbm{1}_{\\{q>0\\}}$ is used. Standalone Training: both feature and
value network are initialised at random and trained together with
$\hat{y}_{DGN}$ as the output. Here, soft gating
$G(q)=\frac{1}{1+\exp(-\beta\cdot q)}$ is used to allow gradient flow through
feature network. On the right side is the CNN-GAP and its DGN used in
(Lakshminarayanan and Singh, 2020). In CNN-GAP, $C_{1},C_{2},C_{3},C_{4}$ are
convolutional layers, $FC_{1},FC_{2}$ are fully connected layers. In CNN-GAP-
DGN, $G_{l},l=1,2,3,4$ are the gates of layers, the superscripts f, and v
stand for feature and value network respectively.

####  2.2.2 Deep Gated Network: Separating Gates and Weights

Deep Gated Network (DGN) is a setup to separate the gates from the weights.
Consider a DNN with ReLUs with weights $\Theta\in\mathbb{R}^{d_{\text{net}}}$.
The DGN _corresponding_ to this DNN (left diagram in Figure 2) has two
networks of _identical architecture_ (to the DNN) namely the ‘gating network’
and the ‘weight network’ with distinct weights
$\Theta^{\textrm{f}}\in\mathbb{R}^{d_{\text{net}}}$ and
${\Theta}^{\text{v}}\in\mathbb{R}^{d_{\text{net}}}$.

The ‘gating network’ has ReLUs which turn ‘on/off’ based on their pre-
activation signals, and the ‘weight network’ has gated linear units (GaLUs)
(Fiat et al., 2019; Lakshminarayanan and Singh, 2020), which multiply their
respective pre-activation inputs by the external gating signals provided by
the ‘gating network’. Since both the networks have identical architecture, the
ReLUs and GaLUs in the respective networks have a one-to-one correspondence.
Gating network realises $\phi_{\Theta^{\textrm{f}}}(x)$ by turning ‘on/off’
the corresponding GaLUs in the weight network. The weight network realises
$v_{{\Theta}^{\text{v}}}$ and computes the output
$\hat{y}_{\text{DGN}}(x)=\langle\phi_{\Theta^{\textrm{f}}}(x),v_{{\Theta}^{\text{v}}}\rangle$.
The gating network is also called as the feature network since it realises the
neural path features, and the weight network is also called as the value
network since it realises the neural path value.

####  2.2.3 Learning Weights With Fixed Gates = Neural Path Kernel

During training, a DNN learns both $\phi_{\Theta}(x)$ as well as $v_{\Theta}$
simultaneously, and a finite time characterisation of this learning in finite
width DNNs is desirable. However, this is a hard problem. An easier problem is
to understand in a DGN, how the weights in the value network are learnt when
the gates are fixed in the feature network, i.e., how
$\hat{y}_{DGN}(x)=\langle\phi_{\Theta^{\textrm{f}}}(x),v_{{\Theta}^{\text{v}}}\rangle$
is learnt by learning $v_{{\Theta}^{\text{v}}}$ with fixed
$\phi_{\Theta^{\textrm{f}}}(x)$. While
$\hat{y}_{DGN}(x)=\langle\phi_{\Theta^{\textrm{f}}}(x),v_{{\Theta}^{\text{v}}}\rangle$
is linear in the dual variables, it is still non-linear in the value network
weights ${\Theta}^{\text{v}}$. However, Lakshminarayanan and Singh (2020)
showed that the dual linearity is characterised by the NPK in the infinite
width regime. We state the assumption followed by Theorem 5.1 in
(Lakshminarayanan and Singh, 2020), wherein, the
$\text{NTK}(x,x^{\prime})=\langle\nabla_{{\Theta}^{\text{v}}}\hat{y}_{\Theta^{\text{DGN}}_{0}}(x),\nabla_{{\Theta}^{\text{v}}}\hat{y}_{\Theta^{\text{DGN}}_{0}}(x^{\prime})\rangle$
is due to the gradient of $\hat{y}_{\text{DGN}}$ with respect to the value
network weights, and the
$\text{NPK}(x,x^{\prime})=\langle\phi_{\Theta^{\textrm{f}}_{0}}(x),\phi_{\Theta^{\textrm{f}}_{0}}(x^{\prime})\rangle$
is due to the feature network weights.

######  Assumption 2.1.

${\Theta}^{\text{v}}_{0}\stackrel{{\scriptstyle\text{i.i.d}}}{{\sim}}\text{Bernoulli}(\frac{1}{2})$
over $\\{-{\sigma},+{\sigma}\\}$ and statistically independent of
$\Theta^{\textrm{f}}_{0}$.

######  Theorem 2.1 (Theorem 5.1 in (Lakshminarayanan and Singh, 2020)).

Under 2.1 for a fully connected DGN :

$\displaystyle\text{NTK}^{\texttt{FC}}(x,x^{\prime})\,\,\stackrel{{\scriptstyle(a)}}{{\rightarrow}}\,\,$
$\displaystyle
d\cdot\sigma^{2(d-1)}\cdot\text{NPK}^{\texttt{FC}}(x,x^{\prime}),\quad\text{as}\,\,w\rightarrow\infty$
$\displaystyle=d\cdot\sigma^{2(d-1)}\cdot\langle
x,x^{\prime}\rangle\cdot\textbf{overlap}(x,x^{\prime})$

Remark. In the fully connected case, $\textbf{overlap}(i,x,x^{\prime})$ is
identical for all $i=1,\ldots,d_{\text{in}}$, and hence $\langle
x,x^{\prime}\rangle_{\textbf{overlap}(\cdot,x,x^{\prime})}$ in Lemma 2.1
becomes $\langle x,x^{\prime}\rangle\cdot\textbf{overlap}(x,x^{\prime})$ in
Theorem 2.1. It follows from NTK theory that an infinite width DGN with fixed
gates is equivalent to kernel method with NPK.

####  2.2.4 Learning in Gates Key For Finite Width To Be Better Than Infinite
Width

The fixed gates setting is an idealised setting, in that, it does not
theoretically capture the learning of the gates, i.e., the neural path
features $\phi_{\Theta}(x)$. However, the learning in the gates can be
empirically characterised by comparing fixed learnt (FL) gates coming from a
pre-trained DNN and fixed random (FR) gates coming from randomly initialised
DNN, and the infinite width NTK. Using a CNN-GAP and its corresponding DGN,
Lakshminarayanan and Singh (2020) showed on CIFAR-10 that (see Figure 2 for
details on DGN training and the CNN-GAP architecture):

FR Gates : $\mathbf{67.09\%}\leq$ CNTK-GAP: $\mathbf{77.43\%}\leq$ FL Gates:
$\mathbf{79.68\%}\approx$ CNN-GAP: $\mathbf{80.32\%}$

based on which it was concluded that learning in the gates (i.e., neural path
features) is crucial for finite width CNN-GAP to outperform the infinite width
CNTK-GAP. It was also shown that the DGN can be trained standalone (as shown
in Figure 2) and is only _marginally poor_ to the DNN.

##  3 Deep Linearly Gated Networks: Complete Disentanglement

$\text{DLGN}:x\rightarrow\stackrel{{\scriptstyle\text{Primal}}}{{\text{Linear}}}\rightarrow\text{Pre-
activations}\rightarrow\text{Gates}\stackrel{{\scriptstyle\text{lifting}}}{{\rightarrow}}\phi_{\Theta^{\textrm{f}}}(x){\rightarrow}\stackrel{{\scriptstyle\text{Dual}}}{{\text{Linear}}}:\hat{y}(x)=\langle\phi_{\Theta^{\textrm{f}}}(x),v_{{\Theta}^{\text{v}}}\rangle$

The deep linearly gated network (DLGN) has two ‘mathematically’ interpretable
linearities, the ‘primal’ and the ‘dual’ linearities. The primal linearity is
ensured in via construction and needs no theoretical justification. Once the
pre-activations triggers gates, $\phi_{\Theta^{\textrm{f}}}(x)$ gets realised
in the value network by activating the paths. Now, the value network itself is
‘dual’ linear, i.e., it simply computes/learns the inner product
$\hat{y}(x)=\langle\phi_{\Theta^{\textrm{f}}}(x),v_{{\Theta}^{\text{v}}}\rangle$.
Gating _lifts_ the ‘primal’ linear computations in the feature network to
‘dual’ linear computations in the value network. Dual linearity is
characterised by the NPK (for infinite width) which in turn depends on the
input and gates, and the fact that the pre-activations to the gates are primal
linear implies complete disentanglement and interpretability.

Dual linearity is mathematically evident due to the inner product
relationship, however, adopting it has the following conceptual issue: it is a
commonly held view that ‘sophisticated features are learnt in the layers’,
that is, given that the input $x\in\mathbb{R}^{d_{\text{in}}}$ is presented to
the value network (as in Figure 2), it could be argued that the GaLUs and
linear operations are entangled which in turn enable learning of sophisticated
features in the layers. In what follows, we demystify this layer-by-layer view
via theory (infinite width case) in Section 3.1 , and experiments (on finite
width networks) in Section 3.2, and then study the performance of DLGN in
Section 3.2. The layer-by-layer view is demystified by showing that (i) a
constant $\mathbf{1}$ input can be given to the value network, (ii) layer-by-
layer structure can be destroyed. The constant $\mathbf{1}$ input is meant to
show that if the input is not given to the value network then it is not
possible to learn sophisticated structures ‘from the input’ in a layer-by-
layer manner. In terms of the dual linearity, providing a constant
$\mathbf{1}$ input has only a minor impact, in that, the neural path feature
becomes $\phi(x,p)=1\cdot A(x,p)$, i.e., it still encodes the path activity
which is still input dependent. Since $\phi(x)$ depends only on gates, the NPK
will depend only on the overlap matrix; results in Section 3.1 captures this
in theory. Now, it could be argued that, despite a constant $\mathbf{1}$
input, the gates are still arranged layer-by-layer, due to which, the value
network is still able to learn sophisticated structures in its layers. Section
3.1 has theory that points out that as long as the correlation of the gates is
not lost, the layer-by-layer structure can be destroyed.

###  3.1 Dual Linearity: New Insights and New Results

We saw in Section 2.2.3 that dual linearity is characterised by the NPK for
infinite width case. In this section, we: (i) cover standard architectural
choices namely convolutions with global-average-pooling and skip connections
in Theorems 3.2 and 3.3; the prior result Theorem 2.1 is only for the fully
connected case, (ii) present new insights on Theorem 2.1 by restating it
explicitly in terms of the gates in Theorem 3.1, and (iii) discuss how the NPK
structure helps in demystifying the layer-by-layer view. Note: Results in this
section are about the value network and hold for both DGN and DLGN.

####  3.1.1 Fully Connected: Product of LayerWise Base Kernels

######  Theorem 3.1.

Let $G_{l}(x)\in[0,1]^{w}$ denote the gates in layer $l\in\\{1,\ldots,d-1\\}$
for input $x\in\mathbb{R}^{d_{\text{in}}}$. Under 2.1
($\sigma=\frac{c_{\text{scale}}}{\sqrt{w}}$) as $w\rightarrow\infty$, we have
for fully connected DGN/DLGN:

$\displaystyle\text{NTK}^{\texttt{FC}}(x,x^{\prime})\rightarrow
d\cdot\sigma^{2(d-1)}\cdot\text{NPK}^{\texttt{FC}}(x,x^{\prime})=d\cdot
c_{\text{scale}}^{2(d-1)}\cdot\left(\langle
x,x^{\prime}\rangle\cdot\Pi_{l=1}^{d-1}\frac{\langle
G_{l}(x),G_{l}(x^{\prime})\rangle}{w}\right),$

$\bullet$ Product Kernel : Role of Depth and Width. Theorem 3.1 is
mathematically equivalent to Theorem 2.1, which follows from the observation
that $\textbf{overlap}(x,x^{\prime})=\Pi_{l=1}^{(d-1)}\langle
G_{l}(x),G_{l}(x^{\prime})\rangle$. While this observation is very elementary
in itself, it is significant at the same time; Theorem 3.1 provides the most
simplest kernel expression that characterises the information in the gates.
From Theorem 3.1 it is evident that the role of width is _averaging_ (due to
the division by $w$). Each layer therefore corresponds to a _base kernel_
$\frac{\langle G_{l}(x),G_{l}(x^{\prime})\rangle}{w}$ which measures the
_correlation of the gates_. The role of depth is to provide the product of
kernels. To elaborate, the feature network provides the gates $G_{l}(x)$, and
the value network realises the product kernel in Theorem 3.1 by laying out the
GaLUs depth-wise, and connecting them to form a deep network. The depth-wise
layout is important: for instance, if we were to concatenate the gating
features as $\varphi(x)=(G_{l}(x),l=1,\ldots,d-1)\in\\{0,1\\}^{(d-1)w}$, it
would have only resulted in the kernel
$\langle\varphi(x),\varphi(x^{\prime})\rangle=\sum_{l=1}^{d-1}{\langle
G_{l}(x),G_{l}(x^{\prime})\rangle}$, i.e., a _sum (not product)_ of kernels.

$\bullet$ Constant $\mathbf{1}$ Input. This has a minor impact, in that, the
expression on right hand side of Theorem 3.1 becomes $d\cdot
c_{\text{scale}}^{2(d-1)}\cdot d_{\text{in}}\cdot\Pi_{l=1}^{d-1}\frac{\langle
G_{l}(x),G_{l}(x^{\prime})\rangle}{w}$, i.e., the kernel still has information
of the gates.

$\bullet$ Destroying structure by permuting the layers.
$\Pi_{l=1}^{d-1}\frac{\langle G_{l}(x),G_{l}(x^{\prime})\rangle}{w}$ is
permutation invariant, and hence permuting the layers has no effect.

####  3.1.2 Convolution Global Average Pooling: Rotationally Invariant Kernel

We consider networks with circular convolution and global average pooling
(architecture and notations are in the Appendix). In Theorem 3.2, let the
circular rotation of vector $x\in\mathbb{R}^{d_{\text{in}}}$ by ‘$r$’ co-
ordinates be defined as $rot(x,r)(i)=x(i+r)$, if $i+r\leq d_{\text{in}}$ and
$rot(x,r)(i)=x(i+r-d_{\text{in}})$ if $i+r>d_{\text{in}}$.

######  Theorem 3.2.

Under 2.1, for a suitable $\beta_{\text{cv}}$ (see Appendix for expansion of
$\beta_{\text{cv}}$):

$\displaystyle\text{NTK}^{\texttt{CONV}}(x,x^{\prime})\rightarrow\frac{\beta_{\text{cv}}}{{d_{\text{in}}}^{2}}\cdot\sum_{r=0}^{d_{\text{in}}-1}\langle
x,rot(x^{\prime},r)\rangle_{\textbf{overlap}(\cdot,x,rot(x^{\prime},r))},\,\,\text{as}\,\,w\rightarrow\infty\,$

$\bullet$ $\sum_{r=0}^{d_{\text{in}}-1}\langle
x,rot(x^{\prime},r)\rangle_{\textbf{overlap}(\cdot,x,rot(x^{\prime},r))}=\sum_{r=0}^{d_{\text{in}}-1}\sum_{i=1}^{d_{\text{in}}}x(i)rot(x^{\prime},r)(i)\textbf{overlap}(i,x,rot(x^{\prime},r))$,
where the inner ‘$\Sigma$’ is the inner product between $x$ and
$rot(x^{\prime},r)$ weighted by overlap and the outer ‘$\Sigma$’ covers all
possible rotations, which in addition to the fact that all the variables
internal to the network rotate as the input rotates, results in the rotational
invariance. It was observed by Arora et al. (2019) that networks with global-
average-pooling are better than vanilla convolutional networks. The rotational
invariance holds for convolutional architectures only in the presence of
global-pooling. So, this result explains why global-average-pooling helps.
That said, rotational invariance is not a new observation; it was shown by Li
et al. (2019) that prediction using CNTK-GAP is equivalent to prediction using
CNTK without GAP but with full translation data augmentation (same as
rotational invariance) with wrap-around at the boundary (same as circular
convolution). However, Theorem 3.2 is a necessary result, in that, it shows
rotational invariance is recovered in the dual view as well.

$\bullet$ The expression in Theorem 3.2 becomes
$\frac{\beta_{\text{cv}}}{{d_{\text{in}}}^{2}}\cdot\sum_{r=0}^{d_{\text{in}}-1}\sum_{i=1}^{d_{\text{in}}}\textbf{overlap}(i,x,rot(x^{\prime},r))$
for a constant $\mathbf{1}$ input. The key novel insight is that the
rotational invariance is not lost and overlap matrix measures the correlation
of the paths which in turn depends on the correlation of the gates.

$\bullet$ Destroying structure by permuting the layers does not destroy the
rotational invariance in Theorem 3.2. This is because, due to circular
convolutions all the internal variables of the network rotate as the input
rotates. Permuting the layers only affects the ordering of the layers, and
does not affect the fact that the gates rotate if the input rotates, and
correlation in the gates is not lost.

####  3.1.3 Residual Networks With Skip Connections (ResNet): Ensemble Of
Kernels

We consider a ResNet with ‘$(b+2)$’ blocks and ‘$b$’ skip connections between
the blocks. Each block is a fully connected (FC) network of depth
‘$d_{\text{blk}}$’ and width ‘$w$’. There are $2^{b}$ many sub-FCNs within
this ResNet (see Definition 3.1). Note that the blocks being fully connected
is for expository purposes, and the result continue to hold for any kind of
block.

######  Definition 3.1.

[Sub FCNs] Let $2^{[b]}$ denote the power set of $[b]$ and let $\mathcal{J}\in
2^{[b]}$ denote any subset of $[b]$. Define the‘$\mathcal{J}^{th}$’ sub-FCN of
the ResNet to be the fully connected network obtained by (i) including
$\text{block}_{j},\forall j\in\mathcal{J}$ and (ii) ignoring
$\text{block}_{j},\forall j\notin\mathcal{J}$.

######  Theorem 3.3.

Let $\text{NPK}^{\texttt{FC}}_{\mathcal{J}}$ be the NPK of the
$\mathcal{J}^{th}$ sub-FCN, and $\beta_{\text{fc}}^{\mathcal{J}}$ (see
Appendix for expansion of $\beta_{\text{fc}}^{\mathcal{J}}$) be the associated
constant. Under 2.1, we have:

$\displaystyle\text{NTK}^{\texttt{RES}}\rightarrow\sum_{\mathcal{J}\in
2^{[b]}}\beta_{\text{fc}}^{\mathcal{J}}\text{NPK}^{\texttt{FC}}_{\mathcal{J}},\,\,\text{as}\,\,w\rightarrow\infty$

$\bullet$ Ensemble. To the best of our knowledge, this is the first
theoretical result to show that ResNets have an ensemble structure, where each
kernel in the ensemble, i.e., $\text{NPK}^{\texttt{FC}}_{\mathcal{J}}$
corresponds to one of the $2^{b}$ sub-architectures (see Definition 3.1). The
ensemble behaviour of ResNet and presence of $2^{b}$ architectures was
observed by Veit et al. (2016), however without any concrete theoretical
formalism.

$\bullet$ Effect of constant $\mathbf{1}$ input is as before for kernels
$\text{NPK}^{\texttt{FC}}_{\mathcal{J}}$ and translates to the ensemble
$\text{NTK}^{\texttt{RES}}$.

$\bullet$ Destroying structure. The ResNet inherits the invariances of the
block level kernel. In addition, the ensemble structure allows to even remove
layers. Veit et al. (2016) showed empirically that removing single layers from
ResNets at test time does not noticeably affect their performance, and yet
removing a layer from architecture such as VGG leads to a dramatic loss in
performance. Theorem 3.3 can be seen to provide a theoretical justification
for this empirical result. In other words, due to the ensemble structure a
ResNet is capable of dealing with failure of components. While failure of
component itself does not occur unless one makes them fail purposefully as
done in (Veit et al., 2016), the insight is that even if one or many of the
kernels in the ensemble are corrupt and the good ones can compensate.

###  3.2 Numerical Experiments

C4GAP$\hat{y}(x)$$FC$GAPReLU$C_{4}$ReLU$C_{3}$ReLU$C_{2}$ReLU$C_{1}$$x$

C4GAP-
DGN$C^{\text{f}}_{4}$ReLU$C^{\text{f}}_{3}$ReLU$C^{\text{f}}_{2}$ReLU$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{1}$$G_{2}$$G_{3}$$G_{4}$$G_{i_{1}}$$G_{i_{2}}$$G_{i_{3}}$$G_{i_{4}}$Layer
Permutation

C4GAP-
DLGN$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$Layer
Permutation

Table I
---
Dataset | Permute | C4GAP | DGN$(x,x)$ | DGN$(x,\mathbf{1})$ | DLGN$(x,x)$ | DLGN$(x,\mathbf{1})$ | $\frac{\text{DLGN}(x,\mathbf{1})}{\text{DNN}}$
CIFAR10 | No | 80.5$\pm$0.4 | 77.4$\pm$0.3 | 77.5$\pm$0.2 | 75.4$\pm$0.3 | 75.4$\pm$0.2 | $93.66$
Yes | – | 77.3$\pm$0.5 | 77.9$\pm$0.6 | 75.9$\pm$0.5 | 76.0$\pm$0.5 | $94.40$
CIFAR100 | No | 51.8$\pm$0.4 | 47.4$\pm$0.2 | 47.3$\pm$0.3 | 47.4$\pm$0.1 | 48.0$\pm$0.2 | $92.66$
Yes | – | 48.4$\pm$0.8 | 49.2$\pm$0.9 | 47.5$\pm$1.0 | 48.4$\pm$0.9 | $93.43$

Table II
---
Dataset | Model | DNN | DGN$(x,x)$ | DGN$(x,\mathbf{1})$ | DLGN$(x,x)$ | DLGN$(x,\mathbf{1})$ | $\frac{\text{DLGN}(x,\mathbf{1})}{\text{DNN}}$
CIFAR10 | VGG16 | 93.6$\pm$0.2 | 93.0$\pm$0.1 | 93.0$\pm$0.1 | 87.0$\pm$0.1 | 87.0$\pm$0.2 | $92.94$
ResNet110 | 94.0$\pm$0.2 | 93.3$\pm$0.2 | 93.2$\pm$0.1 | 87.9$\pm$0.2 | 87.8$\pm$0.1 | $93.40$
CIFAR100 | VGG16 | 73.4$\pm$0.3 | 70.3$\pm$0.1 | 70.5$\pm$0.2 | 61.5$\pm$0.2 | 61.5$\pm$0.1 | $\mathbf{83.78}$
ResNet110 | 72.7$\pm$0.2 | 70.8$\pm$0.2 | 70.8$\pm$0.4 | 62.3$\pm$0.2 | 62.7$\pm$0.3 | $86.24$

Figure 3: Here the gates $G_{1},G_{2},G_{3},G_{4}$ are generated by the
feature network and are permuted as $G_{i_{1}},G_{i_{2}},G_{i_{3}},G_{i_{4}}$
before applying to the value network. $C_{1},C_{2},C_{3},C_{4}$ have $128$
filters each. Table I and II: All columns (except the last) show the $\%$ test
accuracy on CIFAR-10 and CIFAR-100, and $\%$ of DNN performance recovered by
DLGN is in the last column. Table I: For each dataset, the top row has results
for vanilla models without permutations (the results are averaged over $5$
runs) and the bottom row has results of $4!-1=23$ permutations (except the
identity) for each model (the results are averaged over the $23$
permutations).

Section 3.1 presented theoretical results which demystified the layer-by-layer
view in value network, in this section we will verify these theoretical
results in experiments. We then show that DLGN recovers major part of
performance of state-of-the-art DNNs on CIFAR-10 and CIFAR-100.

Setup Details. We consider $3$ DNN architectures, C4GAP, VGG-16 and
Resnet-110, and their DGN and DLGN counterparts. Here C4GAP is a simple model
(achieves about $80\%$ accuracy on CIFAR-10), mainly used to verify the
theoretical insights in Section 3.1. VGG-16 and Resnet-110 are chosen for
their state-of-the-art performance on CIFAR-10 and CIFAR-100. All models are
trained using off-the-shelf optimisers (for more details, see Appendix C). The
DGN and DLGN are trained from scratch, i.e., both the feature and value
network are initialised at random and trained. In DGN and DLGN, we use soft
gating (see Figure 2) so that gradient flows through the feature network and
the gates are learnt (we chose $\beta=10$). In what follows, we use the
notation DGN$(x^{\text{f}},x^{\text{v}})$ and
DLGN$(x^{\text{f}},x^{\text{v}})$ where $x^{\text{f}}$ and $x^{\text{v}}$
denote the input to the value and feature networks respectively. For instance,
DGN$(x,x)$ will mean that both the value and feature network of the DGN is
provided the image as input, and DLGN$(x,\mathbf{1})$ will mean that the
feature network is given with the image as input and the value network is
given a constant $\mathbf{1}$ as input.

Disentangling Value Network. We show that destroying the layer-by-layer
structure via permutations and providing a constant $\mathbf{1}$ input do not
degrade performance. Since our aim here is not state-of-the-art performance,
we use C4GAP with $4$ convolutional layers which achieves only about $80\%$
test accuracy on CIFAR-10, however, enables us to run all the $4!=24$ layer
permutations. The C4GAP, DGN and DLGN with layer permutations are shown in
Figure 3. Once a permutation is chosen, it is fixed during both training and
testing. The results in Table I of Figure 3 show that there is no significant
difference in performance between DGN$(x,x)$ vs DGN$(x,\mathbf{1})$, and
DLGN$(x,x)$ vs DLGN$(x,\mathbf{1})$, i.e., constant $\mathbf{1}$ input does
not hurt. Also, there is no significant difference between the models without
permutations and the models with permutations. These counter intuitive and
surprising results are difficult to explain using the commonly held
‘sophisticated features are learnt layer-by-layer’ view. However, neither the
permutations or the constant $\mathbf{1}$ input destroys the correlation in
the gates, and are not expected to degrade performance as per the insights in
Section 3.1.

DLGN Performance. For this we choose VGG-16 and Resnet-110. The results in
Table II of Figure 3 show that the DLGN recovers more than $83.5\%$ (i.e.,
$83.78\%$ in the worst case) of the performance of the state-of-the-art DNN.
While entanglement in the DNNs enable their improved performance, the
‘disentangled and interpretable’ computations in the DLGN recovers most part
of the performance.

###  3.3 Is DLGN a Universal Spectral Approximator

Motivated by the success of DLGN, we further break it down into DLGN-_Shallow
Features_ (DLGN-SF), wherein, the feature network is a collection of shallow
single matrix multiplications. We compare a shallow DNN with ReLU called C1GAP
against DLGN-SF of C4GAP (see Figure 4) and VGG-16 (see Appendix). The results
are in Figure 4, based on which we observe the following:

$\bullet$ Power of depth in value network and lifting to dual space. Both
C1GAP and C4GAP-DLGN-SF were trained with identical batch size, optimiser and
learning rate (chosen to be the best for C1GAP). The performance of C1GAP at
$200$ epochs is $\sim 10\%$ lower than that of C4GAP-DLGN-SF. After $2000$
epochs of training and ensembling 16 such C1GAP’s as C1GAP-16-ENS closes the
gap within $\sim 3\%$ on C4GAP-DLGN-SF. Yet, a deeper architecture
VGG-16-DLGN-SF is $\sim 10\%$ better than C1GAP-16-ENS. Note that both
VGG-16-DLGN-SF and C1GAP-16-ENS have gates for $16$ layers produced in a
shallow manner. While in a C1GAP-16-ENS, ‘16’ C1GAPs are ensembled, in
VGG-16-DLGN-SF these gates for 16 layers are used as gating signals to turn
‘on/off’ the GaLUs laid depth-wise as 16 layers of the value network, which
helps to lift the computations to the dual space. Thus, using the gates to
lift (instead of ensembling) the computations to the dual space in the value
network is playing a critical role, investigating which is an important future
work.

$\bullet$ Power of depth in feature network. By comparing CIFAR-100
performance of VGG-16-DLGN-SF in Figure 4 and that of VGG-16-DLGN in Figure 3,
we see $\sim 6\%$ improvement if we have a deep linear network instead of many
shallow linear networks as the feature network. This implies depth helps even
if the feature network is entirely linear, investigating which is an important
future work.

$\bullet$ DGN vs DLGN In Table I and II of Figure 3, the difference between
DGN and DNN is minimal (about $3\%$), however, the difference between DLGN and
DNN is significantly large. Thus, it is important to understand the role of
the ReLUs in the feature network of DGN. It is interesting to know whether
this is simpler than understanding the DNN with ReLUs itself.

C4GAP-DLGN-
SF$x$$C^{\text{f}}_{4}$$x$$C^{\text{f}}_{3}$$x$$C^{\text{f}}_{2}$$x$$C^{\text{f}}_{1}$$\hat{y}(x)$$FC$GAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$\mathbf{1}$GGGGC1GAP$\hat{y}(x)$$FC_{1}$GAPReLU$C_{1}$$x$

Table III
---
Dataset | C1GAP | C1GAP-16-ENS | C1GAP | C1GAP-16-ENS | C4GAP-DLGN-SF | VGG-16-DLGN-SF
(epochs) | (200) | (200) | (2000) | (2000) | (50) | (32)
CIFAR-10 | 62.2$\pm$0.2 | 63.81 | 70.0$\pm$0.2 | 72.2 | 75.1$\pm$0.4 | 84.9$\pm$0.2
CIFAR-100 | 36.3$\pm$0.2 | 38.23 | 42.2$\pm$0.3 | 45.47 | 47.3$\pm$0.6 | 56.3$\pm$0.2

Figure 4: C1GAP and C4GAP have width = 512 to make them comparable to VGG-16
whose maximum width is 512. The ensemble size is 16 to match the 16 layers of
VGG-16. Note that C4GAP in Figure 3 has width=128. The last two columns show
only DLGN-SF$(x,\mathbf{1})$. We observed the performance of DLGN-SF$(x,x)$ to
be $\sim 2\%$ lesser and left it out from Table III for sake brevity. All
results except for ENS are averaged over $5$ runs.

$\bullet$ Is DLGN a Universal Spectral Approximator? The value network
realises the NPK which in general is an ensemble (assuming skip connections).
The NPK is based on the gates whose pre-activations are generated linearly. It
is interesting to ask whether the DLGN via its feature network learns the
right linear transformations to extract the relevant spectral features (to
tigger the gates) and via its value network learns the ensembling of kernels
(based on gates) in a dataset dependent manner.

##  4 Conclusion

Entanglement of the non-linear and the linear operation in each layer of a DNN
makes them uninterpretable. This paper proposed a novel DLGN which
disentangled the computations in a DNN with ReLUs into two mathematically
interpretable linearities, the ‘primal’ linearity from the input to the pre-
activations that trigger the gates, and the ‘dual’ linearity in the path
space. DLGN recovers more than $83.5\%$ of performance of state-of-the-art
DNNs on CIFAR-10 and CIFAR-100. Based on this success of DLGN, the paper
concluded by asking ‘Is DLGN a universal spectral approximator?’.

## References

  * Jacot et al. [2018] 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.
  * Arora et al. [2019] 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–8148, 2019.
  * Cao and Gu [2019] 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.
  * Lakshminarayanan and Singh [2020] Chandrashekar Lakshminarayanan and Amit Vikram Singh.  Neural path features and neural path kernel: Understanding the role of gates in deep learning.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Fiat et al. [2019] Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz.  Decoupling gating from linearity.  _CoRR_ , abs/1906.05032, 2019.  URL http://arxiv.org/abs/1906.05032.
  * Fan and Wang [2020] Zhou Fan and Zhichao Wang.  Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.  _arXiv preprint arXiv:2005.11879_ , 2020.
  * Geifman et al. [2020] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri.  On the similarity between the laplace and neural tangent kernels.  _arXiv preprint arXiv:2007.01580_ , 2020.
  * Liu et al. [2020] Chaoyue Liu, Libin Zhu, and Mikhail Belkin.  On the linearity of large non-linear models: when and why the tangent kernel is constant.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Chen et al. [2020] Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang.  A generalized neural tangent kernel analysis for two-layer neural networks.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Xiao et al. [2020] Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz.  Disentangling trainability and generalization in deep neural networks.  In _International Conference on Machine Learning_ , pages 10462–10472. PMLR, 2020.
  * Novak et al. [2018] Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Bayesian deep convolutional networks with many channels are gaussian processes.  _arXiv preprint arXiv:1810.05148_ , 2018.
  * Lee et al. [2017] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Deep neural networks as gaussian processes.  _arXiv preprint arXiv:1711.00165_ , 2017.
  * Lee et al. [2020a] Jaehoon Lee, Samuel S Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein.  Finite versus infinite neural networks: an empirical study.  _arXiv preprint arXiv:2007.15801_ , 2020a.
  * Balestriero et al. [2018] Randall Balestriero et al.  A spline theory of deep learning.  In _International Conference on Machine Learning_ , pages 374–383, 2018.
  * Balestriero and Baraniuk [2018] Randall Balestriero and Richard G Baraniuk.  From hard to soft: Understanding deep network nonlinearities via vector quantization and statistical inference.  _arXiv preprint arXiv:1810.09274_ , 2018.
  * Srivastava et al. [2015] Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber.  Highway networks.  _arXiv preprint arXiv:1505.00387_ , 2015.
  * Ramachandran et al. [2018] Prajit Ramachandran, Barret Zoph, and Quoc V. Le.  Searching for activation functions, 2018.  URL https://openreview.net/forum?id=SkBYYyZRZ.
  * Lee et al. [2020b] Jaehoon Lee, Samuel S Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein.  Finite versus infinite neural networks: an empirical study.  _arXiv preprint arXiv:2007.15801_ , 2020b.
  * Zhang et al. [2016] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Li et al. [2019] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora.  Enhanced convolutional neural tangent kernels.  _arXiv preprint arXiv:1911.00809_ , 2019.
  * Veit et al. [2016] Andreas Veit, Michael Wilber, and Serge Belongie.  Residual networks behave like ensembles of relatively shallow networks.  _arXiv preprint arXiv:1605.06431_ , 2016.
  * Kingma and Ba [2014] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2014.

##  Appendix A Convolution With Global Average Pooling

In this section, we define NPFs and NPV in the presence of convolution with
pooling. This requires three key steps (i) treating pooling layers like
gates/masks (see Definition A.2) (ii) bundling together the paths that share
the same path value (due to weight sharing in convolutions, see Definition
A.3), and (iii) re-defining the NPF and NPV for bundles (see Definition A.4).
Weight sharing due to convolutions and pooling makes the NPK rotationally
invariant Lemma A.1. We begin by describing the architecture.

Architecture: We consider (for sake of brevity) a $1$-dimensional111The
results follow in a direct manner to any form of circular convolutions.
convolutional neural network with circular convolutions, with $d_{\text{cv}}$
convolutional layers ($l=1,\ldots,d_{\text{cv}}$), followed by a _global-
average-pooling_ layer ($l=d_{\text{cv}}+1$) and $d_{\text{fc}}$
($l=d_{\text{cv}}+2,\ldots,d_{\text{cv}}+d_{\text{fc}}+1$) fully connected
layers. The convolutional window size is $w_{\text{cv}}<d_{\text{in}}$, the
number of filters per convolutional layer as well as the width of the FC is
$w$.

Indexing: Here $i_{\text{in}}/i_{\text{out}}$ are the indices (taking values
in $[w]$) of the input/output filters. $i_{\text{cv}}$ denotes the indices of
the convolutional window taking values in $[w_{\text{cv}}]$. $i_{\text{fout}}$
denotes the indices (taking values in $[d_{\text{in}}]$, the dimension of
input features) of individual nodes in a given output filter. The weights of
layers $l\in[d_{\text{cv}}]$ are denoted by
$\Theta(i_{\text{cv}},i_{\text{in}},i_{\text{out}},l)$ and for layers
$l\in[d_{\text{fc}}]+d_{\text{cv}}$ are denoted by
$\Theta(i_{\text{in}},i_{\text{out}},l)$. The pre-activations, gating and
hidden unit outputs are denoted by
$q_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$,
$G_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$, and
$z_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$ for layers
$l=1,\ldots,d_{\text{cv}}$.

######  Definition A.1 (Circular Convolution).

For $x\in\mathbb{R}^{d_{\text{in}}}$, $i\in[d_{\text{in}}]$ and
$r\in\\{0,\ldots,d_{\text{in}}-1\\}$, define :

(i) $i\oplus r=i+r$, for $i+r\leq d_{\text{in}}$ and $i\oplus
r=i+r-d_{\text{in}}$, for $i+r>d_{\text{in}}$.

(ii) $rot(x,r)(i)=x(i\oplus r),i\in[d_{\text{in}}]$.

(iii)
$q_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)=\sum_{i_{\text{cv}},i_{\text{in}}}\Theta(i_{\text{cv}},i_{\text{in}},i_{\text{out}},l)\cdot
z_{x,\Theta}(i_{\text{fout}}\oplus(i_{\text{cv}}-1),i_{\text{in}},l-1)$.

######  Definition A.2 (Pooling).

Let
$G^{\text{pool}}_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}}+1)$
denote the pooling mask, then we have

$z_{x,\Theta}(i_{\text{out}},d_{\text{cv}}+1)=\sum_{i_{\text{fout}}}z_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}})\cdot
G^{\text{pool}}_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}}+1),$

where in the case of _global-average-pooling_
$G^{\text{pool}}_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}}+1)=\frac{1}{d_{\text{in}}},\forall
i_{\text{out}}\in[w],i_{\text{fout}}\in[d_{\text{in}}]$.

Input Layer | : | $z_{x,\Theta}(\cdot,1,0)$ | $=$ | $x$
---|---|---|---|---
Convolutional Layers, $l\in[d_{\text{cv}}]$
Pre-Activation | : | $q_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$ | $=$ | $\sum_{i_{\text{cv}},i_{\text{in}}}\Theta(i_{\text{cv}},i_{\text{in}},i_{\text{out}},l)\cdot z_{x,\Theta}(i_{\text{fout}}\oplus(i_{\text{cv}}-1),i_{\text{in}},l-1)$
Gating Values | : | $G_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$ | $=$ | $\mathbf{1}_{\\{q_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)>0\\}}$
Hidden Unit Output | : | $z_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$ | $=$ | $q_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)\cdot G_{x,\Theta}(i_{\text{fout}},i_{\text{out}},l)$
GAP Layer, $l=d_{\text{cv}}+1$
Hidden Unit Output | : | $z_{x,\Theta}(i_{\text{out}},d_{\text{cv}}+1)$ | $=$ | $\sum_{i_{\text{fout}}}z_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}})\cdot G^{\text{pool}}_{x,\Theta}(i_{\text{fout}},i_{\text{out}},d_{\text{cv}}+1)$
Fully Connected Layers, $l\in[d_{\text{fc}}]+(d_{\text{cv}}+1)$
Pre-Activation | : | $q_{x,\Theta}(i_{\text{out}},l)$ | $=$ | $\sum_{i_{\text{in}}}\Theta(i_{\text{in}},i_{\text{out}},l)\cdot z_{x,\Theta}(i_{\text{in}},l-1)$
Gating Values | : | $G_{x,\Theta}(i_{\text{out}},l)$ | $=$ | $\mathbf{1}_{\\{(q_{x,\Theta}(i_{\text{out}},l))>0\\}}$
Hidden Unit Output | : | $z_{x,\Theta}(i_{\text{out}},l)$ | $=$ | $q_{x,\Theta}(i_{\text{out}},l)\cdot G_{x,\Theta}(i_{\text{out}},l)$
Final Output | : | $\hat{y}_{\Theta}(x)$ | $=$ | $\sum_{i_{\text{in}}}\Theta(i_{\text{in}},i_{\text{out}},d)\cdot z_{x,\Theta}(i_{\text{in}},d-1)$

Table 1: Shows the information flow in the convolutional architecture
described at the beginning of Appendix A.

###  A.1 Neural Path Features, Neural Path Value

######  Proposition A.1.

The total number of paths in a CNN is given by
$P^{\text{cnn}}=d_{\text{in}}(w_{\text{cv}}w)^{d_{\text{cv}}}w^{(d_{\text{fc}}-1)}$.

######  Notation A.1 (Index Maps).

The ranges of index maps $\mathcal{I}^{\text{f}}_{l}$,
$\mathcal{I}^{\text{cv}}_{l}$, $\mathcal{I}_{l}$ are $[d_{\text{in}}]$,
$[w_{\text{cv}}]$ and $[w]$ respectively.

######  Definition A.3 (Bundle Paths of Sharing Weights).

Let $\hat{P}^{\text{cnn}}=\frac{P^{\text{cnn}}}{d_{\text{in}}}$, and
$\\{B_{1},\ldots,B_{\hat{P}^{\text{cnn}}}\\}$ be a collection of sets such
that $\forall i,j\in[\hat{P}^{\text{cnn}}],i\neq j$ we have $B_{i}\cap
B_{j}=\emptyset$ and
$\cup_{i=1}^{\hat{P}^{\text{cnn}}}B_{i}=[P^{\text{cnn}}]$. Further, if paths
$p,p^{\prime}\in B_{i}$, then
$\mathcal{I}^{\text{cv}}_{l}(p)=\mathcal{I}^{\text{cv}}_{l}(p^{\prime}),\forall
l=1,\ldots,d_{\text{cv}}$ and
$\mathcal{I}_{l}(p)=\mathcal{I}_{l}(p^{\prime}),\forall
l=0,\ldots,d_{\text{cv}}$.

######  Proposition A.2.

There are exactly $d_{\text{in}}$ paths in a bundle.

######  Definition A.4.

Let $x\in\mathbb{R}^{d_{\text{in}}}$ be the input to the CNN. For this input,
$A_{\Theta}(x,p)$ $\stackrel{{\scriptstyle\Delta}}{{=}}$
$\left(\Pi_{l=1}^{d_{\text{cv}}+1}G_{x,\Theta}(\mathcal{I}^{\text{f}}_{l}(p),\mathcal{I}_{l}(p),l)\right)\cdot\left(\Pi_{l=d_{\text{cv}}+2}^{d_{\text{cv}}+d_{\text{fc}}+1}G_{x,\Theta}(\mathcal{I}_{l}(p),l)\right)$
$\phi_{x,\Theta}(\hat{p})$ $\stackrel{{\scriptstyle\Delta}}{{=}}$
$\sum_{\hat{p}\in B_{\hat{p}}}x(\mathcal{I}^{\text{f}}_{0}(p))A_{\Theta}(x,p)$
$v_{\Theta}(B_{\hat{p}})$ $\stackrel{{\scriptstyle\Delta}}{{=}}$
$\left(\Pi_{l=1}^{d_{\text{cv}}}\Theta(\mathcal{I}^{\text{cv}}_{l}(p),\mathcal{I}_{l-1}(p),\mathcal{I}_{l}(p),l)\right)\cdot\left(\Pi_{l=d_{\text{cv}}+2}^{d_{\text{cv}}+d_{\text{fc}}+1}\Theta(\mathcal{I}_{l-1}(p),\mathcal{I}_{l}(p),l)\right)$

NPF | $\phi_{x,\Theta}\stackrel{{\scriptstyle\Delta}}{{=}}(\phi_{x,\Theta}(B_{\hat{p}}),\hat{p}\in[\hat{P}^{\text{cnn}}])\in\mathbb{R}^{\hat{P}^{\text{cnn}}}$
---|---
NPV | $v_{\Theta}\stackrel{{\scriptstyle\Delta}}{{=}}(v_{\Theta}(B_{\hat{p}}),\hat{p}\in[\hat{P}^{\text{cnn}}])\in\mathbb{R}^{\hat{P}^{\text{cnn}}}$

###  A.2 Rotational Invariant Kernel

######  Lemma A.1.

$\displaystyle\text{NPK}^{\texttt{CONV}}_{\Theta}(x,x^{\prime})$
$\displaystyle=\sum_{r=0}^{d_{\text{in}}-1}\langle
x,rot(x^{\prime},r)\rangle_{\textbf{overlap}_{\Theta}(\cdot,x,rot(x^{\prime},r))}$
$\displaystyle=\sum_{r=0}^{d_{\text{in}}-1}\langle
rot(x,r),x^{\prime}\rangle_{\textbf{overlap}_{\Theta}(\cdot,rot(x,r),x^{\prime})}$

###### Proof.

For the CNN architecture considered in this paper, each bundle has exactly
$d_{\text{in}}$ number of paths, each one corresponding to a distinct input
node. For a bundle $b_{\hat{p}}$, let $b_{\hat{p}}(i),i\in[d_{\text{in}}]$
denote the path starting from input node $i$.

$\displaystyle\sum_{\hat{p}\in[\hat{P}]}\Bigg{(}\sum_{i,i^{\prime}\in[d_{\text{in}}]}x(i)x^{\prime}(i^{\prime})A_{\Theta}\left(x,b_{\hat{p}}(i)\right)A_{\Theta}\left(x^{\prime},b_{\hat{p}}(i^{\prime})\right)\Bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{\hat{p}\in[\hat{P}]}\Bigg{(}\sum_{i\in[d_{\text{in}}],i^{\prime}=i\oplus
r,r\in\\{0,\ldots,d_{\text{in}}-1\\}}x(i)x^{\prime}(i\oplus
r)A_{\Theta}\left(x,b_{\hat{p}}(i)\right)A_{\Theta}\left(x^{\prime},b_{\hat{p}}(i\oplus
r)\right)\Bigg{)}$ $\displaystyle=$
$\displaystyle\sum_{\hat{p}\in[\hat{P}]}\Bigg{(}\sum_{i\in[d_{\text{in}}],r\in\\{0,\ldots,d_{\text{in}}-1\\}}x(i)rot(x^{\prime},r)(i)A_{\Theta}\left(x,b_{\hat{p}}(i)\right)A_{\Theta}\left(rot(x^{\prime},r),b_{\hat{p}}(i)\right)\Bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{r=0}^{d_{\text{in}}-1}\Bigg{(}\sum_{i\in[d_{\text{in}}]}x(i)rot(x^{\prime},r)(i)\sum_{\hat{p}\in[\hat{P}]}A_{\Theta}\left(x,b_{\hat{p}}(i)\right)A_{\Theta}\left(rot(x^{\prime},r),b_{\hat{p}}(i)\right)\Bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{r=0}^{d_{\text{in}}-1}\Bigg{(}\sum_{i\in[d_{\text{in}}]}x(i)rot(x^{\prime},r)(i)\textbf{overlap}_{\Theta}(i,x,rot(x^{\prime},r))\Bigg{)}$
$\displaystyle=$ $\displaystyle\sum_{r=0}^{d_{\text{in}}-1}\langle
x,rot(x^{\prime},r)\rangle_{\textbf{overlap}_{\Theta}(\cdot,x,rot(x^{\prime},r))}$

∎

In what follows we re-state Theorem 3.2.

######  Theorem A.1.

Let $\sigma_{\text{cv}}=\frac{c_{\text{scale}}}{\sqrt{ww_{\text{cv}}}}$ for
the convolutional layers and
$\sigma_{\text{fc}}=\frac{c_{\text{scale}}}{\sqrt{w}}$ for FC layers. Under
2.1, as $w\rightarrow\infty$, with $\beta_{\text{cv}}=\
\left(d_{\text{cv}}\sigma_{\text{cv}}^{2(d_{\text{cv}}-1)}\sigma_{\text{fc}}^{2d_{\text{fc}}}+d_{\text{fc}}\sigma_{\text{cv}}^{2d_{\text{cv}}}\sigma_{\text{fc}}^{2(d_{\text{fc}}-1)}\right)$
we have:

$\displaystyle\text{NTK}^{\texttt{CONV}}_{\Theta^{\text{DGN}}_{0}}\rightarrow\quad\frac{\beta_{\text{cv}}}{{d_{\text{in}}}^{2}}\cdot\text{NPK}^{\texttt{CONV}}_{\Theta^{\textrm{f}}_{0}}$

###### Proof.

Follows from Theorem 5.1 in [4]. ∎

##  Appendix B Residual Networks with Skip connections

As a consequence of the skip connections, within the ResNet architecture there
are $2^{b}$ sub-FC networks (see Definition 3.1). The total number of paths
$P^{\text{res}}$ in the ResNet is equal to the summation of the paths in these
$2^{b}$ sub-FC networks (see Proposition B.1). Now, The neural path features
and the neural path value are $P^{\text{res}}$ dimensional quantities,
obtained as the concatenation of the NPFs and NPV of the $2^{b}$ sub-FC
networks.

######  Proposition B.1.

The total number of paths in the ResNet is
$P^{\text{res}}=d_{\text{in}}\cdot\sum_{i=0}^{b}\binom{b}{i}w^{(i+2)d_{\text{blk}}-1}$.

######  Lemma B.1 (Sum of Product Kernel).

Let $\text{NPK}^{\texttt{RES}}_{\Theta}$ be the NPK of the ResNet, and
$\text{NPK}^{\mathcal{J}}_{\Theta}$ be the NPK of the sub-FCNs within the
ResNet obtained by ignoring those skip connections in the set $\mathcal{J}$.
Then,

$\displaystyle\text{NPK}^{\texttt{RES}}_{\Theta}=\sum_{\mathcal{J}\in
2^{[b]}}\text{NPK}^{\mathcal{J}}_{\Theta}$

###### Proof.

Proof is complete by noting that the NPF of the ResNet is a concatenation of
the NPFs of the $2^{b}$ distinct sub-FC-DNNs within the ResNet architecture. ∎

We re-state Theorem 3.3

######  Theorem B.1.

Let $\sigma=\frac{c_{\text{scale}}}{\sqrt{w}}$. Under 2.1, as
$w\rightarrow\infty$, for
$\beta_{\text{res}}^{\mathcal{J}}=(|\mathcal{J}|+2)\cdot
d_{\text{blk}}\cdot\sigma^{2\big{(}(|\mathcal{J}|+2)d_{\text{blk}}-1\big{)}}$,

$\displaystyle\text{NTK}^{\texttt{RES}}_{\Theta^{\text{DGN}}_{0}}\rightarrow\sum_{\mathcal{J}\in
2^{[b]}}\beta_{\text{res}}^{\mathcal{J}}\text{NPK}^{\mathcal{J}}_{\Theta^{\textrm{f}}_{0}}$

###### Proof.

Follows from Theorem 5.1 in [4]. ∎

##  Appendix C Numerical Experiments

We now list the details related to the numerical experiments which have been
left out in the main body of the paper.

$\bullet$ Computational Resource. The numerical experiments were run in
Nvidia-RTX 2080 TI GPUs and Tesla V100 GPUs.

$\bullet$ All the models in Table I of Figure 3 we used Adam [Kingma and Ba,
2014] with learning rate of $3\times 10^{-4}$, and batch size of 32.

$\bullet$ In Section 3.2, the codes for experiments based on VGG-16 and
Resnet-110 were refactored from following repository:
“https://github.com/gahaalt/resnets-in-tensorflow2".

$\bullet$ For VGG-16-DLGN in Figure 3 and DLGN-SF in Figure 4, the
$\max$-pooling were replaced by _average_ pooling so as to ensure that the
feature network is entirely linear. For the comparison to be fair, we replaced
the $\max$ pooling in VGG-16 reported in Figure 3 by _average_ pooling. Batch
normalisation layers were retained in VGG-16, VGG-16-DLGN and VGG-16-DLGN-SF
(all three are shown in Figure 7).

$\bullet$ For VGG-16-DLGN in Figure 3 and DLGN-SF in Figure 4, the
$\max$-pooling were replaced by _average_ pooling so as to ensure that the
feature network is entirely linear. For the comparison to be fair, we replaced
the $\max$ pooling in VGG-16 reported in Figure 3. Batch normalisation layers
were retained in VGG-16, VGG-16-DLGN and VGG-16-DLGN-SF.

$\bullet$ All the VGG-16, Resnet-100 (and their DGN/DLGN) models in Table II
of Figure 3 we used _SGD_ optimiser with momentum $0.9$ and the following
learning rate schedule (as suggested in “https://github.com/gahaalt/resnets-
in-tensorflow2") : for iterations $[0,400)$ learning rate was $0.01$, for
iterations $[400,32000)$ the learning rate was $0.1$, for iterations
$[32000,48000)$ the learning rate was $0.01$, for iterations $[48000,64000)$
the learning rate was $0.001$. The batch size was $128$. The models were
trained till $32$ epochs.

$\bullet$ The VGG-16-DLGN-SF in Table III of Figure 4 uses the same optimiser,
batch size and learning rate schedule as the models in Table II of Figure 3 as
explained in the previous point.

$\bullet$ For C1GAP and C4GAP in Table III of Figure 4, we used Adam [Kingma
and Ba, 2014] with learning rate of $10^{-3}$, and batch size of 32. This
learning rate is best among the set $\\{10^{-1},10^{-2},10^{-3},3\times
10^{-4}\\}$ for C1GAP.

$\bullet$ Models Used in Figure 3 and Figure 4 are shown below.

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

Figure 5: Shows the permutations $1-12$ C4GAP-DLGN in Table I of Figure 3. The
top left is the identity permutation and is the vanilla model.

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

$C^{\text{f}}_{4}$$C^{\text{f}}_{3}$$C^{\text{f}}_{2}$$C^{\text{f}}_{1}$$x^{\text{f}}$$\hat{y}(x)$FCGAPGaLU$C^{\text{v}}_{4}$GaLU$C^{\text{v}}_{3}$GaLU$C^{\text{v}}_{2}$GaLU$C^{\text{v}}_{1}$$x^{\text{v}}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$$G_{i_{4}}$$G_{i_{3}}$$G_{i_{2}}$$G_{i_{1}}$

Figure 6: Shows the permutations $13-24$ C4GAP-DLGN in Table I of Figure 3.

$\hat{y}(x)$$FC$Global Avg. PoolReLU+Avg. Pool (1/2)BN$(3\times
3,512)$$C_{13}$ReLUBN$(3\times 3,512)$$C_{12}$ReLUBN$(3\times
3,512)$$C_{11}$ReLU+ Avg. Pool (1/2)BN$(3\times 3,512)$$C_{10}$ReLUBN$(3\times
3,512)$$C_{9}$ReLUBN$(3\times 3,512)$$C_{8}$ReLU+Avg. Pool (1/2)BN$(3\times
3,256)$$C_{7}$ReLUBN$(3\times 3,256)$$C_{6}$ReLUBN$(3\times
3,256)$$C_{5}$ReLU+Avg. Pool (1/2)BN$(3\times 3,128)$$C_{4}$ReLUBN$(3\times
3,128)$$C_{3}$ReLU+Avg. Pool (1/2)BN$(3\times 3,64)$$C_{2}$ReLUBN$(3\times
3,64)$$C_{1}$$x$

$\hat{y}(x)$$FC$Global Avg. PoolGaLU+Avg.
PoolBN$C_{13}$GaLUBN$C_{12}$GaLUBN$C_{11}$GaLU+ Avg.
PoolBN$C_{10}$GaLUBN$C_{9}$GaLUBN$C_{8}$GaLU+Avg.
PoolBN$C_{7}$GaLUBN$C_{6}$GaLUBN$C_{5}$GaLU+Avg.
PoolBN$C_{4}$GaLUBN$C_{3}$GaLU+Avg.
PoolBN$C_{2}$GaLUBN$C_{1}$$x^{\text{v}}$BN$G_{13}$$C_{13}$BN$G_{12}$$C_{12}$BN$G_{11}$$C_{11}$Avg.
PoolBN$G_{10}$$C_{10}$BN$G_{9}$$C_{9}$BN$G_{8}$$C_{8}$Avg.
PoolBN$G_{7}$$C_{7}$BN$G_{6}$$C_{6}$BN$G_{5}$$C_{5}$Avg.
PoolBN$G_{4}$$C_{4}$BN$G_{3}$$C_{3}$Avg.
PoolBN$G_{2}$$C_{2}$BN$G_{1}$$C_{1}$$x^{\text{f}}$

$\hat{y}(x)$$FC$Global Avg. PoolGaLU+Avg.
PoolBN$C_{13}$GaLUBN$C_{12}$GaLUBN$C_{11}$GaLU+ Avg.
PoolBN$C_{10}$GaLUBN$C_{9}$GaLUBN$C_{8}$GaLU+Avg.
PoolBN$C_{7}$GaLUBN$C_{6}$GaLUBN$C_{5}$GaLU+Avg.
PoolBN$C_{4}$GaLUBN$C_{3}$GaLU+Avg.
PoolBN$C_{2}$GaLUBN$C_{1}$$x^{\text{v}}$BN$G_{13}$$C_{13}$BN$G_{12}$$C_{12}$BN$G_{11}$$C_{11}$BN$G_{10}$$C_{10}$BN$G_{9}$$C_{9}$BN$G_{8}$$C_{8}$BN$G_{7}$$C_{7}$BN$G_{6}$$C_{6}$BN$G_{5}$$C_{5}$BN$G_{4}$$C_{4}$BN$G_{3}$$C_{3}$BN$G_{2}$$C_{2}$BN$G_{1}$$C_{1}$Avg.
PoolAvg. PoolAvg. PoolAvg. Pool$x^{\text{f}}$

Figure 7: Shows VGG-16 (left), VGG-16-DLGN (middle), VGG-16-DLGN-SF(right).