## NEURAL CAPACITANCE: A NEW PERSPECTIVE OF NEURAL NETWORK SELECTION VIA EDGE DYNAMICS

**Anonymous authors**
Paper under double-blind review

ABSTRACT

Efficient model selection for identifying a suitable pre-trained neural network to a
downstream task is a fundamental yet challenging task in deep learning. Current
practice requires expensive computational costs in model training for performance
prediction. In this paper, we propose a novel framework for neural network selection by analyzing the governing dynamics over synaptic connections (edges) during
training. Our framework is built on the fact that back-propagation during neural
network training is equivalent to the dynamical evolution of synaptic connections.
Therefore, a converged neural network is associated with an equilibrium state of a
networked system composed of those edges. To this end, we construct a network
mapping φ, converting a neural network GA to a directed line graph GB that is
defined on those edges in GA. Next, we derive a neural capacitance metric βeff
as a predictive measure universally capturing the generalization capability of GA
on the downstream task using only a handful of early training results. We carried
out extensive experiments using 17 popular pre-trained ImageNet models and five
benchmark datasets, including CIFAR10, CIFAR100, SVHN, Fashion MNIST
and Birds, to evaluate the fine-tuning performance of our framework. Our neural
capacitance metric is shown to be a powerful indicator for model selection based
only on early training results and is more efficient than state-of-the-art methods.

1 INTRODUCTION

Leveraging a pre-trained neural network (i.e., a source model) and fine-tuning it to solve a target
task is a common and effective practice in deep learning, such as transfer learning. Transfer learning
has been widely used to solve complex tasks in text and vision domains. In vision, models trained
on ImageNet are leveraged to solve diverse tasks such as image classification and object detection.
In text, language models that are trained on a large amount of public data comprising of books,
Wikipedia etc are employed to solve tasks such as classification and language generation. Although
such technique can achieve good performance on a target task, a fundamental yet challenging problem
is how to select a suitable pre-trained model from a pool of candidates in an efficient manner. The
naive solution of training each candidate fully with the target data can find the best pre-trained model
but is infeasible due to considerable consumption on time and computation resources. This challenge
motivates the need for an efficient predictive measure to capture the performance of a pre-trained
model on the target task based only on early training results (e.g., predicting final model performance
based on the statistics obtained from first few training epochs).

In order to implement an efficient neural network (NN) model selection, this paper proposes a
novel framework to forecast the predictive ability of a model with its cumulative information in
the early phase of NN training, as practised in learning curve prediction (Domhan et al., 2015;
Chandrashekaran & Lane, 2017; Baker et al., 2017; Wistuba & Pedapati, 2020). Most prior work on
learning curve prediction aims to capture the trajectory of learning curves with a regression function
of models’ validation accuracy. Some of the previous algorithms developed in this field require
training data from additional learning curves to train the predictors (Chandrashekaran & Lane, 2017;
Baker et al., 2017; Wistuba & Pedapati, 2020). On the other hand, our model does not require any
such data. It solely relies on the NN architecture. Ranking models according to their final accuracy
after fine-tuning is a lot more challenging as the learning curves are very similar to each other.


-----

The entire NN training process involves iterative updates of the weights of synaptic connections,
according to one particular optimization algorithm, e.g., gradient descent or stochastic gradient
descent (SGD) (Bottou, 2012; LeCun et al., 2015). In essence, many factors contribute to impact
how weights are updated, including the training data, the neural architecture, the loss function, and
the optimization algorithm. Moreover, weights evolving during NN training in many aspects can
be viewed as a discrete dynamical system. The perspective of viewing NN training as a dynamical
system has been studied by the community (Mei et al., 2018; Chang et al., 2018; Banburski et al.,
2019; Dogra, 2020; Tano et al., 2020; Dogra & Redman, 2020; Feng & Tu, 2021), and many attempted
to make some theoretical explanation of the convergence rate and generalization error bounds. In this
paper, we will provide the first attempt in exploring its power in neural model selection.

One limitation of current approaches is that they concentrated on the macroscopic and collective
behavior of the system, but lacks a dedicated examination of the individual interactions between
the trainable weights or synaptic connections, which are crucial in understanding of the dependency
of these weights, and how they co-evolve during training. To fill the gap, we study the system
from a microscopic perspective, build edge dynamics of synaptic connections from SGD in terms of
differential equations, from which we build an associated network as well. The edge dynamics induced
from SGD is nonlinear and highly coupling. It will be very challenging to solve, considering millions
of weights in many convolutional neural networks (CNNs), e.g., 16M weights in MobileNet (Howard
et al., 2017) and 528M in VGG16 (Simonyan & Zisserman, 2014). Gao et al. (2016) proposed a
universal topological metric for the associated network to decouple the system. The metric will
be used for model selection in our approach, and it is shown to be powerful in search of the best
predictive model. We illustrate our proposed framework in Fig.1.

|P ij|Col2|
|---|---|
|||
|||


**(a)** **Deep Neural Network GA** **Line Graph GB**

Inputsx1 Hiddens Outputsy1 _wi_ _wj_

_x2_ _wi_ _wj_ _y2_ Network Mapping ϕ : GA → _GB_

_x3_ _y3_

**5x** Layer 1 **4x** Layer 2 **7x** Layer 35x Layer 4 **Neural Capacitance
GA** Weight Interactions ℬ

Synaptic Connections **Probe (NCP)** _w·_ _i = f(wi) + ∑_ _Pij g(wi, wj)_

_j_

Output Layer **(c)**

**Randomly Initializing** eff

**(b)** **Freezing Top Layers** New Layers _βTrain_ _βeff = [1]1[T][T][PP]P1[1]_

Output Layer 0

Epoch

Layer K Layer K

**Predicted**

**Fine-tuning**

**Bottom Layers** **Observed**

Layer 1 Layer 1

**Transfer** Validation Accuracy

**Learning** Epoch

Source Data Target Data

**Learning Curve Prediction**


Figure 1: Illustration of our framework. (a) An example multilayer perceptron (MLP) GA is mapped
to a directed line graph GB, which is governed by an edge dynamics . Each node (dichromatic
_B_
square) of GB is associated with a synaptic connection linking two neurons (in different colors) from
different layers of GA. (b) A diagram of transfer learning from the source domain (left stack) to
a target domain (right stack). The pre-trained model is modified by adding additional layers, i.e.
installing a neural capacitance probe (NCP) unit, on top of the bottom layers. The NCP is frozen with
a set of randomly initialized weights, and only the bottom layers are fine-tuned. (c) Observed partial
learning curves (green line segments) of validation accuracy over the early-stage training epochs and
the corresponding neural capacitance metric βeff during fine-tuning. The predicted final accuracy at
weighted adjacency matrixβeff → 0 (red dot) is used to select the best one from a set of models. P, which itself is derived from the reformulation of the training dynamics. The metric βeff relies on GB’s
To predict the performance, a lightweight βeff of the NCP is used instead of the heavyweight one
over the entire network on the right stack of (b).


-----

The main contributions of our framework can be summarized as follows:

-  View NN training as a dynamical system over synaptic connections, and first time investigate
the interactions of synaptic connections in a microscopic perspective.

-  Propose neural capacitance metric βeff for neural network model selection.

-  Empirical results of 17 pre-trained models on five benchmark datasets show that our βeff
based approach outperforms current learning curve prediction approaches.

-  For rank prediction according to the performance of pre-trained models, our approach improves by 9.1/38.3/12.4/65.3/40.1% on CIFAR10/CIFAR100/SVHN/Fashion MNIST/Birds
over the best baseline with observations from learning curves of length only 5 epochs.

2 RELATED WORK

**Learning Curve Prediction. Chandrashekaran & Lane (2017) treated the current learning curve (LC)**
as an affine transformation of previous LCs. They built an ensemble of transformations employing
previous LCs and the first few epochs of the current LC to predict the final accuracy of the current LC.
Baker et al. (2017) proposed an SVM based LC predictor using features extracted from previous LCs,
including the architecture information such as number of layers, parameters, and training technique
such as learning rate and learning rate decay. A separate SVM is used to predict the accuracy of an
LC at a particular epoch. Domhan et al. (2015) trained an ensemble of parametric functions that
observe the first few epochs of an LC and extrapolate it. Klein et al. (2017a) devised a Bayesian NN
to model the functions that Domhan formulated to capture the structure of the LCs more effectively.
Wistuba & Pedapati (2020) developed a transfer learning based predictor that was trained on LCs
generated from other datasets. It is a NN based predictor that leverages architecture and dataset
embeddings to capture the similarities between the architectures of various models and also the other
datasets that it was trained on.

**Dynamical System View of NNs. There are many efforts to study the dynamics of NN training.**
Some prior work on SGD dynamics for NNs generally have a pre-assumption of the input distribution
or how the labels are generated. They obtained global convergence for shallow NNs (Tian, 2017;
Banburski et al., 2019). System identification itself is a complicated task (Haykin, 2010; Lillicrap
et al., 2020). In studying the generalisation phenomenon of deep NNs, Goldt et al. (2019) formulated
SGD with a set of differential equations. But, it is limited to over-parameterised two-layer NNs
under the teacher-student framework. The teacher network determines how the labels are generated.
Also, some interesting phenomena (Frankle et al., 2020) are observed during the early phase of NN
training, such as trainable sparse sub-networks emerge (Frankle et al., 2019), gradient descent moves
into a small subspace (Gur-Ari et al., 2018), and there exists a critical effective connection between
layers (Achille et al., 2019). Bhardwaj et al. (2021) built a nice connection between architectures
(with concatenation-type skip connections) and the performance, and proposed a new topological
metric to identify NNs with similar accuracy. Many of these studies are built on dynamical system
and network science. It will be a promising direction to study deep learning mechanism.

3 PRELIMINARIES

**Dynamical System of a Network. Many real complex systems, e.g., plant-pollinator interac-**
tions (Waser & Ollerton, 2006) and the spread of COVID-19 (Thurner et al., 2020), can be described
with networks (Mitchell, 2006; Barabasi & P´ osfai, 2016). Let´ _G = (V, E) be a network with node_
set V and edge set E. Assuming n = |V |, the interactions between nodes can be formulated as a set
of differential equations
_x˙_ _i = f_ (xi) + _Pijg(xi, xj), ∀i ∈_ _V,_ (1)

_jX∈V_

where xi is the state of node i. In real systems, it could be the abundance of a plant in ecological
network, the infection rate of a person in epidemic network, or the expression level of a gene in
regulatory network. The term P is the adjacency matrix of G, where the entry Pij indicates the
interaction strength between nodes i and j. The functions f (·) and g(·, ·) capture the internal and
external impacts on node i, respectively. Usually, they are nonlinear.


-----

Let x = (x1, x2, . . ., xn). For a small network, given an initial state, one can run a forward simulation
for an equilibrium state x[∗], such that ˙x[∗]i [=][ f] [(][x]i[∗][) +][ P]j _V_ _[P][ij][g][(][x]i[∗][, x]j[∗][) = 0][. However, when the]_

_∈_
size of the system goes up to millions or even billions, it will pose a big challenge to solve the
coupled differential equations. The problem can be efficiently addressed by employing a mean-field
technique (Gao et al., 2016), where a linear operator LP (·) is introduced to decouple the system. In
specific, the operator depends on the adjacency matrix P and is defined as

_P (z) =_ **[1][T][ P]** **_[z]_** (2)
_L_ **1[T]** _P_ **1** _[,]_


where z ∈R[n]. Let δin = P **1 be nodes’ in-degrees and δout = 1[T]** _P be nodes’ out-degrees. For a_
weighted G, the degrees are weighted as well. Applying LP (·) to δin, it gives

out[δ][in]

_βeff =_ _P (δin) =_ **[1][T][ P]** **_[δ][in]_** = **_[δ][T]_** _,_ (3)
_L_ **1[T]** **_δin_** **1[T]** **_δin_**

which proves to be a powerful metric to measure the resilience of networks, and has been applied to
make reliable inferences from incomplete networks (Jiang et al., 2020b;a). We use it to measure the
predictive ability of a NN (see Section 4.3), whose training in essence is a dynamical system. For an
overview of the related technique, the readers are referred to Appendix H.

**NN Training is a Dynamical System. Conventionally, training a NN is a nonlinear optimization**
problem. Because of the hierarchical structure of NNs, the training procedure is implemented by two
alternate procedures: forward-propagation (FP) and back-propagation (BP), as described in Fig.1(a).
During FP, data goes through the input layer, hidden layers, up to the output layer, which produces
the predictions of the input data. The differences between the outputs and the labels of the input data
are used to define an objective function C, a.k.a training error function. BP proceeds to minimize C,
in a reverse way as did in FP, by propagating the error from the output layer down to the input layer.
The trainable weights of synaptic connections are updated accordingly.

Let GA be a NN, w be the flattened weight vector for GA, and z be the set of activation values. As a
whole, the training of GA can be described with two coupled dynamics: A on GA, and B on GB,
where nodes in GA are neurons, and nodes in GB are the synaptic connections. The coupling relation
arises from the strong inter-dependency between z and w: the states z (activation values or activation
gradients) of GA are the parameters of B, and the states w of GB are the trainable parameters of
_GA. If we put the whole training process in the context of networked systems,_ denotes a node
_A_
_dynamics because the states of nodes evolve during FP, and B expresses an edge dynamics because of_
the updates of edge weights during BP (Mei et al., 2018; Poggio et al., 2020a;b). Mathematically, we
formulate the node and edge dynamics based on the gradients of C:

(A) _dz/dt ≈_ _hA(z, t; w) = −∇zC(z(t)),_ (4)

(B) _dw/dt ≈_ _hB(w, t; z) = −∇wC(w(t)),_ (5)

where t denotes the training step. Let a[(]i[ℓ][)] be the pre-activation of node i on layer ℓ, and σℓ( ) be the

_·_
activation function of layer ℓ. Usually, the output activation function is a softmax. The hierarchical
structure of GA exerts some constraints over z for neighboring layers, i.e., zi[(][ℓ][)] = σℓ(a[(]i[ℓ][)][)][,][ 1][ ≤] _[i][ ≤]_
of neurons on layernℓ, ∀1 ≤ _ℓ< L and ℓ z, andk[(][L][)]_ _G= expA has{a L[(]k[L] + 1[)][}][/] layers. It also presents a dependency between[ P]j_ [exp][{][a]j[(][L][)]}, 1 ≤ _k ≤_ _nL, where nℓ_ is the total number z and w. For
example, when GA is an MLP without bias, a[(]i[ℓ][)] = wi[(][ℓ][)][T] **_z[(][ℓ][−][1)], which builds an interconnection_**
from GA to GB. It is obvious, given w, the activation z satisfying all these constraints, is also a fixed
point of . Meanwhile, an equilibrium state of provides a set of optimal weights for GA.
_A_ _B_

4 OUR FRAMEWORK

The metric βeff is a universal metric to characterize different types of networks, including biological
neural networks (Shu et al., 2021) (Section 3). Because of the generality of βeff, we analyze how
it looks on artificial neural networks which are designed to mimic the biological counterparts for
general intelligence. Therefore, we set up an analogue system for the trainable weights. To the end,
we build a line graph for the trainable weights (Section 4.1), and reformulate the training dynamics in
the same form of the general dynamics (Eq. 1) (Section 4.2). The reformulated dynamics reveals


-----

a simple yet powerful property regarding βeff (Section 4.3), which is utilized to predict the final
accuracy of GA with a few observations during the early phase of the training (Section 4.4). For a
detailed description of the core idea of our framework, see Appendix I.

4.1 LINE GRAPH GB

We build a mapping schemetopology of the synaptic connections (edges) is established as a well-defined line graph proposed by φ : GA 7→ _GB, from an NN GA to an associated graph GB. The_
Nepusz & Vicsek (2012), and nodes of GB are the synaptic connections of GA. More precisely, each
node in GB is associated with a trainable parameter in GA. For an MLP, each synaptic connection is
assigned a trainable weight, the edge set of GA is also the set of synaptic connections of GB. For a
CNN, this one-to-one mapping from neurons on layer ℓ to layer ℓ + 1 is replaced by a one-to-more
mapping because of weight-sharing, e.g., a parameter in a convolutional filter is repeatedly used in
FP and associated with multiple pairs of neurons from the two neighboring layers. Since the error
gradients flow in a reversed direction, we reverse the corresponding links of the proposed line graph
for GB. In specific, given any pair of nodes in GB, if they share an associated intersection neuron
in FP propagation routes, a link with a reversed direction will be created for them. In Fig.1(a), we
demonstrate how the mapping is performed on an example MLP. We have the topology of GB in
place, but the weights of links in GB are not yet specified. To make up this missing components, we
reveal the interactions of synaptic connections from SGD, quantify the interaction strengths and then
define the weights of links in GB accordingly. Related technical details are disclosed in next section.

4.2 EDGE DYNAMICS B

In SGD, each time a small batch of samples are chosen to update w, i.e., w **_w_** _α_ **_w_**, where
_←_ _−_ _∇_ _C_
_α > 0 is the learning rate. When desired conditions are met, training is terminated._

We denote the activation gradients as δ[(][ℓ][)] = [∂C/∂z1[(][ℓ][)][,][ · · ·][, ∂][C][/∂z]n[(][ℓ]ℓ[)][]][T][ ∈R][n][ℓ] [1][ and the derivatives]
of activation function σ for layer ℓ as σℓ[′] [= [][σ]ℓ[′] [(][a]1[(][ℓ][)][)][,][ · · ·][, σ]ℓ[′] [(][a][(]n[ℓ]ℓ[)][)]][T][ ∈R][n][ℓ][,][ 1][ ≤] _[ℓ]_ _[≤]_ _[L][. To]_
understand how the weights W [(][ℓ][)] affect each other, we explicitly expand δ[(][ℓ][)]:

**_δ[(][ℓ][)]_** = W [(][ℓ][+1)][T] (W [(][ℓ][+2)][T] ( (W [(][L][−][1)][T] (W [(][L][)][T] (z[(][L][)] **_y))_** **_σL[′]_** 1[)][ · · ·][ )][ ⊙] **_[σ]ℓ[′]+2[)][ ⊙]_** **_[σ]ℓ[′]+1[)][,]_**

_· · ·_ _−_ _⊙_ _−_

where ⊙ is the Hadamard product. We find that parameters W [(][ℓ][)] are associated with all accessible
parameters on downstream layers, and such recursive relation defines a high-order hyper-network interaction (Casadiego et al., 2017) between any W [(][ℓ][)] and the other parameters. The Hadamard product
**_x⊙y has an equivalent matrix multiplication form, i.e. x⊙y = Λ(y)x, where Λ(y) is a diagonal ma-_**
trix consisting of the entries of y on the diagonal. Therefore, we have δ[(][ℓ][)] = W [(][ℓ][+1)][T] Λ(σℓ[′]+1[)][δ][(][ℓ][+1)]

and δ[(][ℓ][)] = W [(][ℓ][+1)][T] Λ(σℓ[′]+1[)][W][ (][ℓ][+2)][T][ Λ(][σ]ℓ[′]+2[)][ · · ·][ W][ (][L][−][1)][T][ Λ(][σ]L[′] 1[)][W][ (][L][)][T][ (][z][(][L][)][ −] **_[y][)][. For a]_**
_−_
ReLU σℓ(·), σℓ[′] [is binary depending on the sign of the input pre-activation values][ a][(][ℓ][)][ of layer][ ℓ][. If]
_a[(]i[ℓ][)]_ _≤_ 0, then σℓ[′] [(][a]i[(][ℓ][)][) = 0][, blocking a BP propagation route of the prediction deviations][ z][(][L][)][ −] **_[y]_**
and giving rise to vanishing gradients.

Our purpose is to build direct interactions between synaptic connections. It can be done by identifying
which units provide direct physical interactions to a given unit and appear on the right hand side of its
differential equation B in Eq. 4, and how much such interactions come into play. There are multiple
routes to build up a direct interaction between any pair of network weights from different layers,
as presented by the product terms in δ[(][ℓ][)]. However, the coupled interaction makes it an impossible
task, which is well known as a credit assignment problem (Whittington & Bogacz, 2019; Lillicrap
et al., 2020). We propose a remedy. The impacts of all the other units on W [(][ℓ][)] is approximated by
direct, local impacts from W [(][ℓ][+1)], and the others’ contribution as a whole is implicitly encoded in
the activation gradient δ[(][ℓ][+1)].

Moreover, we have the weight gradient (see Appendix A for detailed derivation)

_W (ℓ) = Λ(σℓ[′]_ [)][δ][(][ℓ][)][z][(][ℓ][−][1)][T][ = Λ(][σ]ℓ[′] [)][W][ (][ℓ][+1)][T][ Λ(][σ]ℓ[′]+1[)][δ][(][ℓ][+1)][z][(][ℓ][−][1)][T][,] (6)
**_∇_**

1In some literature δ(ℓ) is defined as gradients with respect to a(ℓ), which does not affect our analysis.


-----

which shows the dependency of W [(][ℓ][)] on W [(][ℓ][+1)], and itself can be viewed as an explicit description
of the dynamical system B in Eq. 4. Put it in terms of a differential equation, we have

_dW_ [(][ℓ][)]/dt = −Λ(σℓ[′] [)][W][ (][ℓ][+1)][T][ Λ(][σ]ℓ[′]+1[)][δ][(][ℓ][+1)][z][(][ℓ][−][1)][T][ ≜] _[F]_ [(][W][ (][ℓ][+1)][)][.] (7)

Because of the mutual dependency of the weights and the activation values, it is hard to make an
exact decomposition of the impacts of different parameters on W [(][ℓ][)]. However, in the gradient _W (ℓ)_,
**_∇_**
_W_ [(][ℓ][+1)] presents as an explicit term and contributes the direct impact on W [(][ℓ][)]. To capture such direct
impact and derive the adjacency matrix P for GB, we apply Taylor expansion on _W (ℓ) and have_
**_∇_**

_P_ [(][l,l][+1)] = ∂[2]C/∂W [(][ℓ][)]∂W [(][ℓ][+1)], (8)

which defines the interaction strength between each pair of weights from layer ℓ + 1 to layer ℓ.
See Appendix B for detailed derivation of P on MLP, and Appendix C on general NNs. Let
**_w = (w1, w2, . . .) be a flattened vector of all trainable weights of GA. Given a pair of weights wi_**
and wj, one from layer ℓ1, another from layer ℓ2. If ℓ2 = ℓ1 + 1, the entry Pij is defined according
to Eq. 8, otherwise Pij = 0. Considering the scale of trainable parameters in GA, P is very sparse.

Let W [(][ℓ][+1)][∗] be the equilibrium states (Appendix C), the training dynamics Eq. 7 is reformulated
into the form of Eq. 1 and gives the edge dynamics for GB:
_B_


_Pijg(wi, wj),_ (9)


_w˙_ _i = f_ (wi) +


withis unknown, but it is a constant and does not affect the computing of f (wi) = F (wi[∗][)][ and][ g][(][w][i][, w][j][) =][ w][j][ −] _[w]j[∗][. The value of weights at an equilibrium state] βeff_ . _[ {][w]j[∗][}]_

4.3 NEURAL CAPACITANCE

According to Eq. 8, we have the weighted adjacency matrix P of GB in place. Now we can quantify
the total impact that a trainable parameter (or synaptic connection) receives from itself and the others,
which corresponds to the weighted in-degrees δin = P **1. Applying LP (·) (see Eq. 2) to δin, we get a**
“counterpart” metric βeff = LP (δin) to measure the predictive ability of a neural network GA, as the
resilience metric (see Eq. 3) does to a general network G (see Dynamical System of a Network in
Section 3). If GA is an MLP, we can explicitly write the entries of P, hence a βeff explicitly

_Lℓ=2−2[[][1][T][ z][(][ℓ][−][2)][]][ ×][ 1][T][ [][z][(][ℓ][−][1)][ ⊙]_ **_[σ]ℓ[′]_** 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′]_** []][ ×][ 1][T][ [][δ][(][ℓ][+1)][ ⊙] **_[σ]ℓ[′]+1[]]_**

_βeff =_ _L−1_ _−_ _._ (10)

P _ℓ=2_ [[][1][T][ z][(][ℓ][−][2)][]][ ×][ [][1][T][ σ]ℓ[′] 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′]_** []]

_−_

For details of how to deriveP P and βeff of an MLP, see Appendix B. Moreover, we prove in Theorem
1 below that as GA converges, ∇[(]W[ℓ][)] [vanishes, and][ β][eff][ approaches zero (see Appendix D).]

**Theorem 1. Let ReLU be the activation function of GA. When GA converges, then βeff = 0.**

For an MLP GA, it is possible to derive an **Algorithm 1 Implement NCP and Compute βeff**
analytical form ofextremely complicated for a deep NN with βeff . However, it becomes **Input: A pre-trained model Fs = {Fs[(1)][,][ F]s[(2)][}][ with]**
multiple convolutional layers. To realize βeff bottom layers _s_ and output layer _s_, a target

_F_ [(1)] _F_ [(2)]

for deep NNs in any form, we take advantage dataset Dt, the maximum number of epochs T
of the automatic differentiation implementedin TensorFlowparameters, it is still computationally expen-sive, and prohibitive to calculate a[2]. Considering the number of βeff for the 1:2: Remove Initialize with random weights and freezeNCP unit F Us[(2)] with multiple layers (Fig.1from Fs and add on top ofb F) _Us[(1)]_ an

3: Train _t =_ _s_ _[,][ U}][ by fine-tuning][ F]s[(1)]_ on Dt

entire GA. Because of this, we seek to derive _F_ _{F_ [(1)]

for epochs of T

a surrogate from a partial of GA. As shown 4: Obtain P from according to Eq. 8
in Section 4.4, we insert a neural capacitance _U_

5: Compute βeff with P according to Eq. 3 or Eq. 10

_probe (NCP) unit, i.e., putting additional lay-_
ers on top of the beheaded GA (excluding the original output layer), and estimate the predictive
ability of the entire GA using βeff of the NCP unit. Therefore, in the context of model selection from
a pool of pre-trained models, if no confusion arises, we call βeff a neural capacitance.

2https://www.tensorflow.org/


-----

4.4 MODEL SELECTION WITH βeff

Here we show a novel application of our proposed neural capacitance βeff to model selection. In
specific, we transfer the pre-trained models by (i) removing the output layer, (ii) adding some layers
on top of the remaining layers (Fig.1b), and fine-tune them using a small learning rate. As shown in
Algorithm 1, the newly added layers U on top of the bottom layers of Fs are used as an NCP unit.
The specifics of the NCP unit are detailed in Section 5. The NCP does not involve in fine-tuning, and
is merely used to calculate βeff, then to estimate the performance of GA over the target domain Dt.

According to Theorem 1, when the model converges, βeff 0. In an indirect way, the predictive
ability of the model can be determined by the relation between the training → _βeff and the validation_
accuracy I. Since both βeff and I are available during fine-tuning, we collect a set of data points of
these two in the early phase as the observations, and fit a regularized linear model I = h(βeff ; θ) with
Bayesian ridge regression (Tipping, 2001), where θ are the associated coefficients (see Appendix E
for technical details). The estimated predictor I = h(βeff ; θ[∗]) makes prediction of the final accuracy
of models by setting βeff = 0, i.e., I _[∗]_ = h(0; θ[∗]), see an example in row 3 of Fig.2. For full training
of the best model, one can either retain or remove the NCP and fine-tune the selected model.

5 EXPERIMENTS AND RESULTS

**Pre-trained models and datasets. We evaluate 17 pre-trained ImageNet models implemented in**
Keras[3], including AlexNet, VGGs (VGG16/19), ResNets (ResNet50/50V2/101/101V2/152/152V2),
DenseNets (DenseNet121/169/201), MobileNets (MobileNet and MobileNetV2), Inceptions (InceptionV3, InceptionResNetV2) and Xception, to measure the performance of our approach. Four
benchmark datasets CIFAR10, CIFAR100, SVHN, Fashion MNIST of size 32 × 32 × 3, and one
Kaggle challenge dataset Birds[4] of size 224 × 224 × 3 are used, and their original train/test splits are
adopted. In addition, 15K original training samples are set aside as validation set for each dataset.

**Experimental setup. To get a well-defined βeff**, GA requires at least three hidden layers (see
Appendix C). Also, a batch normalization (Ioffe & Szegedy, 2015) is usually beneficial because it
can stabilize the training by adjusting the magnitude of activations and gradients. To this end, on top
of each pre-trained model, we put a NCP unit composed of (1) a dense layer of size 256, (2) a dense
layer of size 128, each of which follows (3) a batch normalization and is followed by (4) a dropout
layer with a dropout probability of 0.4. Before fine-tuning, we initialize the NCP unit using Kaiming
Normal initialization (He et al., 2015).

We set a batch size of 64 and a learning rate of 0.001, fine-tune each pre-trained model for T = 50
epochs, and repeated it for 20 times. As shown in Fig.2, the pre-trained models are converged after
the fine-tuning on CIFAR10. For each model, we collect the validation accuracy (blue stars in row
1) and βeff on the training set (green squares in row 2) during the early stage of the fine-tuning

as the observations (e.g., green squares in row 3 marked by the green box for 5 epochs), then use
these observations to predict the test accuracy unseen before the fine-tuning terminates. For better
illustration, learning curves are visualized on a log-scale.

**Evaluation. We apply the Bayesian ridge regression on the observations to capture the relation**
between βeff and the validation accuracy, and to estimate a learning curve predictor I = h(βeff ; θ[∗]).
The performance of the model is revealed as I _[∗]_ = h(βeff[∗] [;][ θ][∗][)][ with][ β]eff[∗] [= 0][. As shown in row 3 of]
Fig.2, the blue lines are estimated h(·; θ), the true test accuracy at T and the predicted accuracy are
marked as red triangles and blue stars, respectively. Both the estimates and predictions are accurate.

We aim to select the best one from a pool of candidates. A relative rank of these candidates matters
more than their exact values of predicted accuracy. To evaluate and compare different approaches,
we choose Spearman’s rank correlation coefficient ρ as the metric, and calculate ρ over the true
test accuracy at epoch T and the predicted accuracy I _[∗]_ of all pre-trained models. In Fig.3(a), we
report the true and predicted accuracy for each model on CIFAR10, as well as the overall ranking
performance measured by ρ. It indicates that our β-based model ranking is reliable with ρ > 0.9. For
the results on all five datasets, see Appendix Fig.F.4.

3https://keras.io/api/applications/
4https://www.kaggle.com/gpiosenka/100-bird-species


-----

MobileNet


ResNet


DenseNet


Inception


VGG


1.00

0.75


0.97

0.93

2

0

10[0] 10[1]

Epoch t

0.96


0.95

0.90

2

0

10[0] 10[1]

Epoch t


0.95

0.5


0.95

0.90

2

0

10[0] 10[1]

Epoch t


0.0

10[0] 10[1]

Epoch t

0.94

0.92

0.90


0

10[0] 10[1]

Train
Vali
Test

Epoch t

0.8


0.94

0.92

0.90


0.92

0.90

0.88


0.94

0.92


10[-1] 10[0] 10[1]

Pred. Acc. (w/β)
Test Acc. (t = 50)
Obs@[t0, t0 + 5)

t0 = 2, BIC=3.2

Train β
| |


10[-3] 10[-2] 10[-1] 10[0]

t0 = 3, BIC=3.3

Train β
| |


10[-1] 10[0]

t0 = 3, BIC=3.2

Train β
| |


10[-2] 10[-1] 10[0]

t0 = 2, BIC=3.3

Train β
| |


10[-2] 10[-1] 10[0]

t0 = 4, BIC=4.5

Train β
| |


Figure 2: Learning curves of five representative pre-trained models w.r.t accuracy (row 1) and βeff
(row 2). A regularized linear model h(·; θ) (blue curve in row 3) is estimated with Bayesian ridge
regression using a few of observations of βeff on training set and validation accuracy I during early
fine-tuning. The starting epoch t0 of observations affects the fit of h, and is automatically determined
according to BIC, and the true test accuracy at epoch 50 is predicted with I _[∗]_ = h(0; θ[∗]).

**(a)** Pre-tranied **(b)ρ** 1.0 t0 **(c)ρ** 1.0

0.6

0.92 0.94 0.96 5 10 15 5 10 15

|ρ = 0.92 Spearman Corr.|Inception MobileNet ResNet VGG Xception|
|---|---|


10K
15K
25K
30K

Size of Train Set 35K

t0

1
3
5
7

Starting Epoch 9

Predicted Acc. Length of Learning Curve Length of Learning Curve

Figure 3: (a) Our βeff based prediction of the validation accuracy versus the true test accuracy at
epoch 50 of seven representative pre-trained models. Each shape is associated with one type of
pre-trained models. Distinct models of the same type are marked in different colors. Because the
accuracy of AlexNet is much lower than others, we exclude it for better visualization. Its predicted
accuracy is 0.871, and the true test accuracy is 0.868. If it is included, ρ = 0.93 > 0.92. (b) Impacts
of the starting epoch t0 of the observations and (c) the number of training samples on the ranking
performance of our βeff based approach.

The estimation quality of h determines how well the relation between I and βeff is captured. Besides
the regression method, the starting epoch t0 of the observations also plays a role in the estimation.
As shown in Fig.3(b), we evaluate the impact of t0 on ρ of our approach. It goes as expected, when
the length of learning curves is fixed, a higher t0 usually produces a better ρ. Since our ultimate
goal is to predict with the early observations, t0 should also be constrained to a small value. To
make the comparisons fair, we view t0 as a hyper-parameter, and select it according to the Bayesian
information criterion (BIC) (Friedman et al., 2001), as shown in row 3 of Fig.2.

**Impact of size of training set. CIFAR10 has 50K original training and 10K testing samples.**
Generally, the 50K samples are further split into 35K for training and 15K for validation. In studying
the dynamics of the NN training, it is essential to understand how varying the training size influences
the effectiveness of our approach. We select the first {10,15,20,25,30}K of the original 50K samples
as the training set of reduced size, and the last 10K samples as the validation set to fine-tune the
pre-trained models for 50 epochs. As shown in Fig.3(c), we can use a training set of size as small
as 25K to achieve similar performance to that uses all 35K training samples. It has an important
implication for efficient NN training, because the size of required training set can be greatly reduced
(around 30% in our experiment) while maintaining similar model ranking performance. To be noted
that the true test accuracy used in computing ρ is the same test accuracy for the model trained from
35K training samples and it’s shared by all the five cases {10,15,20,25,30}K in our analysis.

**Ours versus baselines. We select BGRN (Baker et al., 2017) and CL (Chandrashekaran & Lane,**
2017) as the baselines, as well as two heuristic rules of using the last seen value (LSV) (Klein et al.,
2017b) or the best seen value (BSV) of a learning curve for extrapolation.

6https://github.com/tdomhan/pylearningcurvepredictor


-----

Table 1: A comparison between our βeff based approach and the baselines in model ranking. The notation LLC represents the length of the learning curve, and Imprv represents the relative improvement
of our approach to the best baseline. Due to the failure of the supporting package[6] of LC, there is a

|g ρ at LLC of|f 10, which do|oes not affect o|our conclusion|ns.|Col6|
|---|---|---|---|---|---|
|Dataset|CIFAR10|CIFAR100|SVHN|Fashion MNIST|Birds|
|LLC|5 10|5 10|5 10|5 10|5 10|
|Ours BSV LSV BGRN LC|0.93 0.98 0.86 0.89 0.85 0.87 0.74 0.78 0.85 0.85|0.77 0.80 0.55 0.80 0.55 0.80 0.45 0.60 0.50 0.58|0.84 0.88 0.74 0.78 0.73 0.70 0.63 0.65 0.44 0.10|0.95 0.89 0.53 0.60 0.49 0.45 0.57 0.59 0.55 0.61|0.74 0.79 0.52 0.61 0.48 0.45 0.53 0.52 0.50 –|
|Imprv (%)|9.1 10.2|38.3 -0.9|12.4 13.3|65.3 49.2|40.1 30.6|



We compare the performance of ours with the baselines. As shown in Table 1 and Appendix Fig.F.5,
using a few of observations, e.g., only 5 epochs, our approach can achieve 9.1/38.3/12.4/65.3/40.1%
relative improvements over the best baseline on CIFAR10/CIFAR100/SVHN/Fashion MNIST/Birds.

**Running time analysis. Our approach is efficient, especially for large and deep NNs. Different**
from the training task that involves a full FP and BP, i.e. Ttrain = TFP + TBP, computing βeff only
requires to compute the adjacency matrix P according to Eq. 8 on the NCP unit, Tβeff = TNCP.
Although the computation is complicated, the NCP is lightweight. The computing cost per epoch is
comparable to the training time per epoch (see Appendix Fig.G). Let Tβeff = c × Ttrain. If c > 1,
i.e., Tβeff is higher than Ttrain, vice versa. Considering the required epochs, our approach needs k
observations, and takes Tours = k × Tβeff . To obtain the ground-truth final accuracy by running K
epochs, it takes Tfull = K × Ttrain. If Tfull > Tours, our βeff based prediction is cheaper than “just
training longer”. It indicates thatK − _c × k more training epochs._ _K × Ttrain −_ _k × Tβeff = (K −_ _c × k) × Ttrain > 0, saving us_

We perform a running time analysis of the two tasks with 4× NVIDIA Tesla V100 SXM2 32GB, and
visualize the related times in Appendix Fig.G. On average c = Tβeff _/Ttrain_ 1.3, computing βeff
takes 1.3 times of the training per epoch. But the efforts are paying off, as we can predict the final ≈
accuracy by observing only k = 10 of K = 100 full training epochs, Tours is only 13% of Tfull.

When the observations are used for learning curve prediction, the heuristics LSV and BSV directly
take one observation (last or best) as the predicted value, so they are mostly computationally cheap but
have suboptimal model ranking performances. Relatively, BGRN and CL are more time-consuming
because both require to train a predictor with a set of full learning curves from other models. Our
approach also estimates a predictor, but does not need any external learning curves. Here we assume
that each model is observed for only k = 5 epochs, and conduct a running time analysis of these
approaches over learning curve prediction, including estimating a predictor. As shown in Appendix
Table G.2, our approach applies Bayesian ridge regression to efficiently estimate the predictor
_I = h(βeff_ ; θ), taking comparable time as BGRN, significantly less than CL, but performs best in
model ranking. In contrast, the most expensive CL, does not perform well, sometimes even worst.

6 CONCLUSION AND DISCUSSION

We present a new perspective of NN model selection by directly exploring the dynamical evolution of
synaptic connections during NN training. Our framework reformulates the SGD based NN training
dynamics as an edge dynamics B to capture the mutual interaction and dependency of synaptic
connections. Accordingly, a networked system is built by converting an NN GA to a line graph GB
with the governing dynamics, which induces a definition of the link weights in GB. Moreover, a
_B_
topological property of GB named neural capacitance βeff is developed and shown to be an effective
metric in predicting the ranking of a set of pre-trained models based on early training results.

There are several important directions that we intend to explore in the future, including (i) simplify the
adjacency matrix P to capture the dependency and mutual interaction between synaptic connections,
e.g., approximate gradients using local information (Jaderberg et al., 2017), (ii) extend the proposed
framework to NAS benchmarks (Ying et al., 2019; Dong & Yang, 2020; Dong et al., 2021; Zela et al.,
2020; Li et al., 2021) to select the best subnetwork, and (iii) design an efficient algorithm to directly
optimize NN architectures based on βeff .


-----

REFERENCES

Alessandro Achille, Matteo Rovere, and Stefano Soatto. Critical learning periods in deep networks.
In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA,
_May 6-9, 2019. OpenReview.net, 2019._

Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture
search using performance prediction. arXiv preprint arXiv:1705.10823, 2017.

Andrzej Banburski, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Fernanda De La Torre, Jack
Hidary, and Tomaso Poggio. Theory III: Dynamics and generalization in deep networks. arXiv
_preprint arXiv:1903.04991, 2019._

Albert-L´aszl´o Barab´asi and M´arton P´osfai. Network Science. Cambridge University Press, 2016.

Kartikeya Bhardwaj, Guihong Li, and Radu Marculescu. How does topology influence gradient
propagation and model performance of deep networks with densenet-type skip connections?
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
13498–13507, 2021.

Leon Bottou. Stochastic gradient descent tricks. In´ _Neural networks: Tricks of the Trade, pp. 421–436._
Springer, 2012.

Jose Casadiego, Mor Nitzan, Sarah Hallerberg, and Marc Timme. Model-free inference of direct
network interactions from nonlinear collective dynamics. Nature Communications, 8(1):1–10,
2017.

Akshay Chandrashekaran and Ian R Lane. Speeding up hyper-parameter optimization by extrapolation
of learning curves using previous builds. In Joint European Conference on Machine Learning and
_Knowledge Discovery in Databases, pp. 477–492. Springer, 2017._

Bo Chang, Minmin Chen, Eldad Haber, and H Chi. AntisymmetricRNN: A dynamical system view
on recurrent neural networks. In International Conference on Learning Representations, 2018.

Akshunna S Dogra. Dynamical systems and neural networks. arXiv preprint arXiv:2004.11826,
2020.

Akshunna S. Dogra and William Redman. Optimizing neural networks via Koopman operator theory.
In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural
_Information Processing Systems, volume 33, pp. 2087–2097. Curran Associates, Inc., 2020._

Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparameter
optimization of deep neural networks by extrapolation of learning curves. In Twenty-fourth
_International Joint Conference on Artificial Intelligence, 2015._

Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the scope of reproducible neural architecture
search. arXiv preprint arXiv:2001.00326, 2020.

Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. NATS-Bench: Benchmarking nas
algorithms for architecture topology and size. IEEE transactions on pattern analysis and machine
_intelligence, 2021._

Yu Feng and Yuhai Tu. Phases of learning dynamics in artificial neural networks: in the absence or
presence of mislabeled data. Machine Learning: Science and Technology, 2021.

Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the
lottery ticket hypothesis. arXiv preprint arXiv:1903.01611, 2019.

Jonathan Frankle, David J Schwab, and Ari S Morcos. The early phase of neural network training.
_arXiv preprint arXiv:2002.10365, 2020._

Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning,
volume 1. Springer series in statistics New York, 2001.


-----

Jianxi Gao, Baruch Barzel, and Albert-Laszl´ o Barab´ asi. Universal resilience patterns in complex´
networks. Nature, 530(7590):307–312, 2016.

Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborova. Dynamics´
of stochastic gradient descent for two-layer neural networks in the teacher-student setup. In
H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alche-Buc, E. Fox, and R. Garnett (eds.),´ _Advances_
_in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019._

Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv
_preprint arXiv:1812.04754, 2018._

Simon Haykin. Neural Networks and Learning Machines. Pearson Education India, 2010.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing
human-level performance on ImageNet classification. In Proceedings of the IEEE International
_Conference on Computer Vision, pp. 1026–1034, 2015._

Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand,
Marco Andreetto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for
mobile vision applications. arXiv preprint arXiv:1704.04861, 2017.

Sergey Ioffe and Christian Szegedy. Batch Normalization: Accelerating deep network training by
reducing internal covariate shift. In International Conference on Machine Learning, pp. 448–456.
PMLR, 2015.

Max Jaderberg, Wojciech Marian Czarnecki, Simon Osindero, Oriol Vinyals, Alex Graves, David
Silver, and Koray Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In
_International Conference on Machine Learning, pp. 1627–1635. PMLR, 2017._

Chunheng Jiang, Jianxi Gao, and Malik Magdon-Ismail. Inferring degrees from incomplete networks
and nonlinear dynamics. In Proceedings of the Twenty-Ninth International Joint Conference on
_Artificial Intelligence, IJCAI-20, pp. 3307–3313. International Joint Conferences on Artificial_
Intelligence Organization, 2020a.

Chunheng Jiang, Jianxi Gao, and Malik Magdon-Ismail. True nonlinear dynamics from incomplete
networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
131–138, 2020b.

Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian
optimization of machine learning hyperparameters on large datasets. In Artificial Intelligence and
_Statistics, pp. 528–536. PMLR, 2017a._

Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction
with Bayesian neural networks. In 5th International Conference on Learning Representations,
_ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net,_
2017b.

Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436–444,
2015.

Chaojian Li, Zhongzhi Yu, Yonggan Fu, Yongan Zhang, Yang Zhao, Haoran You, Qixuan Yu, Yue
Wang, and Yingyan Lin. HW-NAS-Bench: Hardware-aware neural architecture search benchmark.
_arXiv preprint arXiv:2103.10584, 2021._

Timothy P Lillicrap, Adam Santoro, Luke Marris, Colin J Akerman, and Geoffrey Hinton. Backpropagation and the brain. Nature Reviews Neuroscience, pp. 1–12, 2020.

David JC MacKay. Bayesian interpolation. Neural Computation, 4(3):415–447, 1992.

Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of twolayer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665–E7671,
2018.


-----

Melanie Mitchell. Complex systems: Network thinking. Artificial Intelligence, 170(18):1194–1212,
2006.

Tamas Nepusz and Tam´ as Vicsek. Controlling edge dynamics in complex networks.´ _Nature Physics,_
8(7):568–573, 2012.

Tomaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceed_ings of the National Academy of Sciences, 117(48):30039–30045, 2020a._

Tomaso Poggio, Qianli Liao, and Andrzej Banburski. Complexity control by gradient descent in deep
networks. Nature Communications, 11(1):1–5, 2020b.

Pin Shu, Hong Zhu, Wen Jin, Jie Zhou, Shanbao Tong, and Junfeng Sun. The resilience and
vulnerability of human brain networks across the lifespan. IEEE Transactions on Neural Systems
_and Rehabilitation Engineering, 29:1756–1765, 2021._

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image
recognition. arXiv preprint arXiv:1409.1556, 2014.

Mauricio E Tano, Gavin D Portwood, and Jean C Ragusa. Accelerating training in artificial neural
networks with dynamic mode decomposition. arXiv preprint arXiv:2006.14371, 2020.

Stefan Thurner, Peter Klimek, and Rudolf Hanel. A network-based explanation of why most covid-19
infection curves are linear. Proceedings of the National Academy of Sciences, 117(37):22684–
22689, 2020.

Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its
applications in convergence and critical point analysis. In International Conference on Machine
_Learning, pp. 3404–3413. PMLR, 2017._

Michael E Tipping. Sparse Bayesian learning and the relevance vector machine. Journal of Machine
_Learning Research, 1(Jun):211–244, 2001._

Nickolas M Waser and Jeff Ollerton. Plant-pollinator interactions: from specialization to generaliza_tion. University of Chicago Press, 2006._

James CR Whittington and Rafal Bogacz. Theories of error back-propagation in the brain. Trends in
_Cognitive Sciences, 23(3):235–250, 2019._

Martin Wistuba and Tejaswini Pedapati. Learning to rank learning curves. In International Conference
_on Machine Learning, pp. 10303–10312. PMLR, 2020._

Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NASBench-101: Towards reproducible neural architecture search. In International Conference on
_Machine Learning, pp. 7105–7114. PMLR, 2019._

Arber Zela, Julien Siems, and Frank Hutter. NAS-Bench-1Shot1: Benchmarking and dissecting
one-shot neural architecture search. arXiv preprint arXiv:2001.10422, 2020.


-----

A ERROR GRADIENTS

Let GA be an MLP. To understand the learning mechanism, we take a sample x with label y, and
go through the entire training procedure, including a forward pass FP and a backward pass BP. To
be convenient, we rewrite z[(0)] = x as the inputs, let z[(1)] and z[(][L][−][1)] be the activations of the first
and the last hidden layers, respectively, and let z[(][L][)] be the outputs. The MLP is a parameterized
model ˆy = z[(][L][)] = Fw(x) with w = (W [(1)], W [(2)], . . ., W [(][L][)]), where W [(][ℓ][)] is the weight matrix of
synaptic connections from layer ℓ 1 to layer ℓ, and 1 _ℓ_ _L. Suppose there are nℓ_ neurons on
_−_ _≤_ _≤_
layer ℓ, W [(][ℓ][)] has the size nℓ _× nℓ−1. The inputs x are fed into MLP, after a forward pass from layer_
1 down to layer L − 1 and layer L. Each neuron receives a cumulative input signal from the previous
layer, and sends an activated signal to a downstream layer. Let σℓ be the activation function of layer
_ℓ, a[(]i[ℓ][)]_ = wi[(][ℓ][)][T] **_z[(][ℓ][−][1)]_** be the pre-activation value of neuron i on layer ℓ, we have zi[(][ℓ][)] = σℓ(a[(]i[ℓ][)][)]
with wi[(][ℓ][)] being the ith row of W [(][ℓ][)], 1 _i_ _nℓ. The output activation function σL is generally a_
_≤_ _≤_
softmax function, i.e. zi[(][L][)] = exp{a[(]i[L][)]}/ _j_ [exp][{][a]j[(][L][)]}, and z[(][L][)] is a probability distribution over

_nL classes, i.e. 1[T]_ **_z[(][L][)]_** = 1.

[P]

With the predictions z[(][L][)] and the ground truth y, we can calculate the prediction error C(z[(][L][)], y),
which is often a cross entropy loss, i.e. C(z[(][L][)], y) = − [P]i _[y][i][ log][ z]i[(][L][)]. To minimize C, BP is applied,_

and the weights w are updated backward, from the output layer up to the first hidden layer.

Now we derive the gradients for a close examination. First, we get the derivatives of C w.r.t z[(][L][)] and
_W_ [(][L][)]. Because zi[(][L][)] = exp{a[(]i[L][)]}/ _j_ [exp][{][a]j[(][L][)]}, we get the gradient of the output zk[(][L][)] w.r.t wij[(][L][)][:]

_∂zk[(][L][)]/∂wij[(][L][)]_ = zk[(][L][)](δki _zi[(][L][)])zj[(][L][−][1)],_

[P] _−_

where δki = 1 if k = i, otherwise δki = 0.

On layer L, we get the derivatives of C w.r.t z[(][L][)] and W [(][L][)]:

_∂C_ = ; _∂C_ = _∂C_ _∂zk[(][L][)]_ = (zi[(][L][)] _yi)zj[(][L][−][1)]_ (11)

_∂zi[(][L][)]_ _−_ _z[y]i[(][L][i]_ [)] _∂wij[(][L][)]_ _k_ _∂zk[(][L][)]_ _∂wij[(][L][)]_ _−_

X

Then, we examine layer L − 1. The activation function σL−1 associates to a pair of neurons u[(]i[L][−][1)]
on layer L 1 and u[(]j[L][−][2)] on layer L 2 with a unique connection weight wij[(][L][−][1)]. Since zi[(][L][)] =
_−_ _−_

exp{a[(]i[L][)]}/ _j_ [exp][{][a]j[(][L][)]} and zi[(][L][−][1)] = σL−1(a[(]i[L][−][1)]), we get ∂zk[(][L][)]/∂zi[(][L][−][1)] = zk[(][L][)](wki[(][L][)] _−_

_j_ _[z]j[(][L][)]wji[(][L][)][) =][ z]k[(][L][)](wki[(][L][)]_ _i_ **_z[(][L][)]), and_**
_∗_

[P] _[−]_ _[w][(][L][)][T]_

P _∂zi[(][L][−][1)]/∂wij[(][L][−][1)]_ = zj[(][L][−][2)]σL[′] _−1[(][a][(]i[L][−][1)])._

The derivatives of C are

_∂zi[(]∂[L]C[−][1)]_ = _k_ _∂z∂k[(]C[L][)]_ _∂z∂zi[(][L]k[(][L][−][)][1)]_ = _k_ _[y][k][(][w]∗[(][L]i_ [)][T] **_z[(][L][)]_** _−_ _wki[(][L][)][) =][ w]∗[(][L]i_ [)][T] (z[(][L][)] _−_ **_y),_**

_∂_ _∂_ _∂zi[(][L][−][1)]_

_∂wij[(][L]C[−][1)]_ = P∂zi[(][L]C[−][1)] _∂wij[(][L][−][1)]_ = w[P]∗[(][L]i [)][T] (z[(][L][)] _−_ **_y)zj[(][L][−][2)]σL[′]_** _−1[(][a][(]i[L][−][1)])._


On layer ℓ, where 1 _ℓ_ _L_ 2, we get ∂zk[(][ℓ][+1)]/∂zi[(][ℓ][)] = wki[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)]) and
_≤_ _≤_ _−_

_∂z∂i[(]C[ℓ][)]_ = _k_ _∂z∂k[(][ℓ]C[+1)]_ _∂z∂zk[(][ℓ]i[(][+1)][ℓ][)]_ = _k_ _∂z∂k[(][ℓ]C[+1)]_ _wki[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)]),_

_∂_ _∂_ _∂zi[(][ℓ][)]_ _∂_

_∂wCij[(][ℓ][)]_ = P∂zi[(]C[ℓ][)] _∂wij[(][ℓ][)]_ [=] _∂zi[(]C[ℓ][)]_ _[z]j[(][ℓ][−][P][1)]σℓ[′]_ [(][a]i[(][ℓ][)][)][,]

according to the relations zi[(][ℓ][+1)] = σℓ+1(a[(]i[ℓ][+1)]) and zi[(][ℓ][)] = σℓ(a[(]i[ℓ][)][)][.]


Let δ[(][ℓ][)] = [∂C/∂z1[(][ℓ][)][,][ · · ·][, ∂][C][/∂z]n[(][ℓ]ℓ[)][]][T][ ∈R][n][ℓ][,][ σ]ℓ[′] [= [][σ]ℓ[′] [(][a]1[(][ℓ][)][)][,][ · · ·][, σ]ℓ[′] [(][a][(]n[ℓ]ℓ[)][)]][T][ ∈R][n][ℓ][,][ 1][ ≤] _[ℓ]_ _[≤]_ _[L][.]_
The gradients can be written in a dense form:
_W (L)_ = (z[(][L][)] **_y)z[(][L][−][1)][T]_** _,_
**_∇_** _−_ _∈R[n][L][×][n][L][−][1]_
**_δ[(][L][−][1)]_** = _W_ [(][L][)][T] (z[(][L][)] _−_ **_y) ∈R[n][L][−][1]_** _,_
_W (L−1)_ = (δ[(][L][−][1)] **_σL[′]_** 1[)][z][(][L][−][2)][T][ ∈R][n][L][−][1][×][n][L][−][2] _[,]_ (12)
**_∇_** _⊙_ _−_
**_δ[(][ℓ][)]_** = _W_ [(][ℓ][+1)][T] (δ[(][ℓ][+1)] _⊙_ **_σℓ[′]+1[)][ ∈R][n][ℓ]_** _[,]_
**_∇W (ℓ)_** = (δ[(][ℓ][)] _⊙_ **_σℓ[′]_** [)][z][(][ℓ][−][1)][T][ ∈R][n][ℓ][×][n][ℓ][−][1] _[.]_


-----

B WEIGHTED DEGREES OF GB

We examine three hidden layers {ℓ _−_ 1, ℓ, ℓ + 1} of GA and three neurons on these layers {j, i, k}.
Let wki[(][ℓ][+1)] connects the neuron k on layer ℓ + 1 to the neuron i on layer ℓ, wij[(][ℓ][)] [be the synaptic]

connection weight between the neuron j on layer ℓ and the neuron i on layer ℓ 1, and wjm[(][ℓ][−][1)]
_−_
connects the neuron j on layer ℓ _−_ 1 and the neuron m on layer ℓ _−_ 2.

Now we have a close look at ∂C/∂wij[(][ℓ][)][. According to the chain rule, we have]


_∂zi[(][ℓ][)]_ = δi[(][ℓ][)][z]j[(][ℓ][−][1)]σℓ[′] [(][a][(]i[ℓ][)][) =][ z]j[(][ℓ][−][1)]σℓ[′] [(][a][(]i[ℓ][)][)]

_∂wij[(][ℓ][)]_


_∂_ _∂_
_C_ = _C_

_∂wij[(][ℓ][)]_ _∂zi[(][ℓ][)]_


_δk[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)])wki[(][ℓ][+1)]_


The gradient term δk[(][ℓ][+1)] = ∂ _/∂zk[(][ℓ][+1)]_ is a highly coupled function of all accessible synaptic
_C_
connection weights of wij[(][ℓ][)] on the forward propagation route from zi[(][ℓ][)] to the output neurons.
To ease the analysis, we simplify it with a numerical value or a synthetic one with no synaptic
connection weight included. Therefore, the summation term can be viewed as a simple linear
function of all synaptic connection weights wki[(][ℓ][+1)] associated with neuron i on layer ℓ, and the
associated coefficient is p{wki[(][ℓ][+1)], wij[(][ℓ][)][}][ =][ z]j[(][ℓ][−][1)]σℓ[′] [(][a]i[(][ℓ][)][)][δ]k[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)]), which defines the

edge weights from wki[(][ℓ][+1)] to wij[(][ℓ][)] [on][ G][B][. Similarly, we have the edge weight from][ w]ij[(][ℓ][)] [to][ w]jm[(][ℓ][−][1)],

i.e., p _wij[(][ℓ][)][, w]jm[(][ℓ][−][1)]_ = zm[(][ℓ][−][2)]σℓ[′] 1[(][a][(]j[ℓ][−][1)])δi[(][ℓ][)][σ]ℓ[′] [(][a]i[(][ℓ][)][)][. Therefore, we are able to calculate the in-]
_{_ _}_ _−_

degree and out-degree of wij[(][ℓ][)][, which are defined as the sum of the weights of all in-bound connections]

to wij[(][ℓ][)] [and the sum of the weights of all out-bound connections from][ w]ij[(][ℓ][)][, i.e.]

_δin(wij[(][ℓ][)][) =][z]j[(][ℓ][−][1)]σℓ[′]_ [(][a][(]i[ℓ][)][)] _δk[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)])_ _,_ (13)

_k_

 [X] 

_δout(wij[(][ℓ][)][) =]_ _zm[(][ℓ][−][2)]_ _σℓ[′]_ 1[(][a][(]j[ℓ][−][1)])δi[(][ℓ][)][σ]ℓ[′] [(][a][(]i[ℓ][)][)][.] (14)

_−_
_m_

 [X] 

There are several exceptions, including the first hidden (ℓ = 1), the last hidden (ℓ = L − 1) and the
output (ℓ = L) layers. For the output layer, we have


_∂zk[(][L][)]_ = zj[(][L][−][1)](zi[(][L][)] _yi)._ (15)

_∂wij[(][L][)]_ _−_


_∂C_

_∂wij[(][L][)]_


_∂C_

_∂zk[(][L][)]_


Because σL is softmax, no explicit relation regarding wij[(][L][)] can be built. It implies that no well-defined

in-bound connections to wij[(][L][)][, i.e.,][ δ][in][(][w]ij[(][L][)][) = 0][. But, we can build the connections from][ w]ij[(][L][)] to

_wjm[(][L][−][1)]. It is easy to derive_


_∂w∂zi[(]ij[(][L][L][−][−][1)][1)]_ = zj[(][L][−][2)]σL[′] _−1[(][a][(]i[L][−][1)]_


_∂_ _∂_
_C_ = _C_

_∂wij[(][L][−][1)]_ _∂zi[(][L][−][1)]_


(zk[(][L][)] _−_ _yk)wki[(][L][)][.]_ (16)


From the perspective of wij[(][L][−][1)], we get p _wki[(][L][)][, w]ij[(][L][−][1)]_ = zj[(][L][−][2)]σL[′] 1[(][a][(]i[L][−][1)])(zk[(][L][)] _yk); from_
_{_ _}_ _−_ _−_

the perspective of wij[(][L][)][, we have][ p][{][w]ij[(][L][)][, w]jm[(][L][−][1)] = zm[(][L][−][2)]σL[′] 1[(][a][(]j[L][−][1)])(zi[(][L][)] _yi). So we have_
_}_ _−_ _−_

_δout(wij[(][L][)][)]_ = _m_ _[z]m[(][L][−][2)]_ _σL[′]_ 1[(][a][(]j[L][−][1)])(zi[(][L][)] _yi),_

_−_ _−_
_δin(wij[(][L][−][1)])_ = z Pj[(][L][−][2)]σL[′] _−1[(][a][(]i[L][−][1)])_ _k[(][z]k[(][L][)]_ _−_ _yk) = 0,_

_δout(wij[(][L][−][1)])_ = _m_ _[z]m[(][L][−][3)]_ _σL[′]_ 2[(][a][(]j[L][−][2)])δi[(][L][−][1)]σL[′] 1[(][a][(]i[L][−][1)]).

_−_ _−_

[P]

The softmax σL(·) makes the output values sum up to one, i.e., P  _k_ _[y][k][ = 1][, and][ δ][in][(][w]ij[(][L][−][1)]) = 0._

Now, we examine the first hidden layer. Similar to the output layer, there is no well-defined out-bound
connections for wij[(1)][,][ δ][out][(][w]ij[(1)][) = 0][. Setting][ ℓ] [= 1][ in Eq. 13, we can get the in-degree of][P] _[ w]ij[(1)]_

_δin(wij[(1)][) =][ z]j[(0)][σ]1[′]_ [(][a][(1)]i [)] _δk[(2)][σ]2[′]_ [(][a][(2)]k [)] _._

_k_

 [X] 


-----

Based on our definition of the weights of GB, when the number of layers is small, it is trivial that
_βeff = 0. To get a non-trivial βeff_, we identify the minimum number of hidden layers in GA. First,
we examine a GA with one hidden layer, i.e. L = 2, whose degrees are

_δin(wij[(1)][) =]_ _δout(wij[(1)][) =][ δ][in][(][w]ij[(2)][) = 0][,]_
_δout(wij[(2)][) =]_ _m_ _[z]m[(0)]_ _σ1[′]_ [(][a][(1)]j [)(][z]i[(2)] _−_ _yi)._

Since the degrees sum up to zero, βeff = 0 P, regardless of how many hidden neurons in _GA._


If GA only has two hidden layers, i.e. L = 3, the in-degrees are

_δin(wij[(1)][) =]_ _zj[(0)][σ]1[′]_ [(][a][(1)]i [)] _nk=12_ _[δ]k[(2)][σ]2[′]_ [(][a][(2)]k [)] _,_
_δin(wij[(2)][) =]_ _δin(wij[(3)][) = 0] P[.]_ 

The out-degrees are summarized as follows:

_δout(wij[(1)][)]_ = 0,
_δout(wij[(2)][)]_ = _nm0=1_ _[z]m[(0)]_ _σ1[′]_ [(][a][(1)]j [)][δ]i[(2)]σ2[′] [(][a][(2)]i [)][,]
_δout(wij[(3)][)]_ =  Pnm1=1 _[z]m[(1)]σ2[′]_ [(][a][(2)]j [)(][z]i[(3)] _−_ _yi)._

The total degree may be non-zero, but β Peff = 0 alway holds.


**Therefore, the minimum number of hidden layers required for a well-defined βeff is three, i.e.,**
_L ≥_ 4. We summarize the in-degrees

_δin(wij[(1)][)]_ = zj[(0)][σ]1[′] [(][a][(1)]i [)] _k_ _[δ]k[(2)][σ]2[′]_ [(][a][(2)]k [)] _,_

_δin(wij[(][ℓ][)][)]_ = zj[(][ℓ][−][1)]σℓ[′] [(][a][(]i[ℓ] P[)][)] _k_ _[δ]k[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)])_ _, ∀1 < ℓ< L −_ 1,

_δin(wij[(][L][−][1)])_ = 0,  P 
_δin(wij[(][L][)][)]_ = 0.

and the out-degrees


_δout(wij[(1)][)]_ = 0,
_δout(wij[(][ℓ][)][)]_ = _m_ _[z]m[(][ℓ][−][2)]_ _σℓ[′]_ 1[(][a]j[(][ℓ][−][1)])δi[(][ℓ][)][σ]ℓ[′] [(][a]i[(][ℓ][)][)][,][ ∀][1][ < ℓ< L][ −] [1][,]

_−_
_δout(wij[(][L][−][1)])_ =  Pm _[z]m[(][L][−][3)]_ _σL[′]_ _−2[(][a][(]j[L][−][2)])δi[(][L][−][1)]σL[′]_ _−1[(][a][(]i[L][−][1)]),_

_δout(wij[(][L][)][)]_ =  Pm _[z]m[(][L][−][2)]σL[′]_ _−1[(][a][(]j[L][−][1)])(zi[(][L][)]_ _−_ _yi)._

It is easy to derive  P 

**_δin[T]_** **_[δ][out]_** = _i,j_ 1<ℓ<L 1 _[δ][in][(][w]ij[(][ℓ][)][)][δ][out][(][w]ij[(][ℓ][)][)]_
_−_
= _i,j_ P1<ℓ<L−1 _m_ _[z]m[(][ℓ][−][2)]_ _zj[(][ℓ][−][1)]σℓ[′]−1[(][a][(]j[ℓ][−][1)])[σℓ[′]_ [(][a]i[(][ℓ][)][)]][2][δ]i[(][ℓ][)] _k_ _[δ]k[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)])_ _,_

= [P]1<ℓ<L 1[[][1][T][ z][(][ℓ][−][2)][]][ ×][ 1][T][ [][z][(][ℓ][−][1)][ ⊙] **_[σ]ℓ[′]_** 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′][2][]][ ×][ 1][T][ [][δ][(][ℓ][+1)][ ⊙]_** **_[σ]ℓ[′]+1[]][.]_**

P _−_  P  _−_  P 

[P]

Now, we move forward to compute the total degree

[P]

**1[T]** **_δin_** = _ij_ _[z]j[(0)][σ]1[′]_ [(][a][(1)]i [)] _k_ _[δ]k[(2)][σ]2[′]_ [(][a][(2)]k [)] + _ij_ 1<ℓ<L 1 _[z]j[(][ℓ][−][1)]σℓ[′]_ [(][a]i[(][ℓ][)][)] _k_ _[δ]k[(][ℓ][+1)]σℓ[′]+1[(][a][(]k[ℓ][+1)])_

_−_

= [1[T] **_z[(0)]]_** [1[T] **_σ1[′]_** []][ ×][ 1][T][ [][δ][(2)][ ⊙] **_[σ]2[′]_** [] +][ P]1<ℓ<L 1[[][1][T][ z][(][ℓ][−][1)][]][ ×][ [][1][T][ σ]ℓ[′] []][ ×][ 1][T][ [][δ][(][ℓ][+1)][ ⊙] **_[σ]ℓ[′]+1[]][,]_**
_×_  P  P _−_  P 
= [P]1 _ℓ<L_ 1[[][1][T][ z][(][ℓ][−][1)][]][ ×][ [][1][T][ σ]ℓ[′] []][ ×][ 1][T][ [][P][δ][(][ℓ][+1)][ ⊙] **_[σ]ℓ[′]+1[]][.]_**

_≤_ _−_

The definitions of in-degree and out-degree ensure that 1[T] **_δin = 1[T]_** **_δout must hold. Let’s prove it:_**

[P]

**1[T]** **_δout_** = _i,j_ 1<ℓ _L_ 1 _m_ _[z]m[(][ℓ][−][2)]σℓ[′]_ 1[(][a][(]j[ℓ][−][1)])δi[(][ℓ][)][σ]ℓ[′] [(][a]i[(][ℓ][)][) +][ P]m _[z]m[(][L][−][2)]σL[′]_ 1[(][a][(]j[L][−][1)])(zi[(][L][)] _yi)_

_≤_ _−_ _−_ _−_ _−_

= 1<ℓ _L_ 1[[][1][T][ z][(][ℓ][−][2)][]][ ×][ [][1][T][ σ]ℓ[′] 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′]_** [] =][ 1][T][ δ][in][.]

 P≤ _−_ P _−_

[P]

With the fact that[P] **_σℓ[′][2]_** [=][ σ]ℓ[′] [for ReLU, according to Eq. 3, we have]

_Lℓ=2−2[[][1][T][ z][(][ℓ][−][2)][]][ ×][ 1][T][ [][z][(][ℓ][−][1)][ ⊙]_ **_[σ]ℓ[′]_** 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′]_** []][ ×][ 1][T][ [][δ][(][ℓ][+1)][ ⊙] **_[σ]ℓ[′]+1[]]_**

_βeff =_ _L−1_ _−_ _._

P _ℓ=2_ [[][1][T][ z][(][ℓ][−][2)][]][ ×][ [][1][T][ σ]ℓ[′] 1[]][ ×][ 1][T][ [][δ][(][ℓ][)][ ⊙] **_[σ]ℓ[′]_** []]

_−_
P


-----

DERIVATION OF ADJACENCY MATRIX P OF GB


The right hand side (RHS) of Eq. 6 is a function of W [(][ℓ][+1)], and denoted as F (W [(][ℓ][+1)]).
Here we derive the strength of the impact from W [(][ℓ][+1)] and other weights W [(][−][ℓ][)] =
(W [(0)], W [(1)], . . ., W [(][ℓ][)], W [(][ℓ][+2)], . . ., W [(][L][)]) for building the edge dynamics. Let W =
(W [(][ℓ][+1)], W [(][−][ℓ][)]) and F (W ) = dW [(][ℓ][)]/dt. We denote _W[ˆ]_ [(][−][ℓ][)] as the current states of W [(][−][ℓ][)]),
_W_ _[∗][(][ℓ][+1)]_ as an equilibrium point, and W _[∗]_ = (W _[∗][(][ℓ][+1)],_ _W[ˆ]_ [(][−][ℓ][)]). According to the Taylor expansion,
we linearize F at W _[∗]_ and have

_dW_ [(][ℓ][)]/dt ≈ _F_ (W _[∗]) +_ _[∂F][ (][W]∂W[ ∗][(][ℓ][+1)][(][ℓ][+1)][,][ ˆ]W_ [(][−][ℓ][)]) (W [(][ℓ][+1)] _−_ _W_ _[∗][(][ℓ][+1)]) +_ _[∂F][ (][W][ ∗]∂W[(][ℓ][+1)][(][−][ℓ][,][ ˆ]W[)]_ [(][−][ℓ][)]) (W [(][−][ℓ][)] _−_ _W[ˆ]_ [(][−][ℓ][)]).

The last term on the RHS can be cancelled out when the realizations of W [(][−][ℓ][)] take the current states
of W [(][−][ℓ][)], i.e. _W[ˆ]_ [(][−][ℓ][)]. The gradient is simplified as

_W_ [(][−][ℓ][)])
_dW_ [(][ℓ][)]/dt ≈ _F_ (W _[∗]) +_ _[∂F]_ [(][W]∂W[ ∗][(][ℓ][+1)][(][ℓ][+1)][,][ ˆ] (W [(][ℓ][+1)] _−_ _W_ _[∗][(][ℓ][+1)])._


The term ∂F (W _[∗][(][ℓ][+1)],_ _W[ˆ]_ [(][−][ℓ][)])/∂W [(][ℓ][+1)] = ∂[2]C(W _[∗][(][ℓ][+1)],_ _W[ˆ]_ [(][−][ℓ][)])/∂W [(][ℓ][)]∂W [(][ℓ][+1)] effectively
captures the interaction strengths between W [(][ℓ][)] and W [(][ℓ][+1)], because it measures how much F
is affected by a unit perturbation on W [(][ℓ][+1)]. Usually, W _[∗][(][ℓ][+1)]_ are not available before updating W [(][ℓ][+1)] following the update of W [(][ℓ][)], we use the current states of W [(][ℓ][+1)] instead. The
system can be viewed as a realization of the general Eq. 1, with linear f (W [(][ℓ][)]) = F (W _[∗]) and_
_g(W_ [(][ℓ][)], W [(][ℓ][+1)]) = W _[∗][(][ℓ][+1)]_ _−_ _W_ [(][ℓ][+1)]. Now, we can immediately have the adjacency matrix P of
_GB with P_ [(][l,l][+1)] = ∂[2]C(W [(][ℓ][+1)], _W[ˆ]_ [(][−][ℓ][)])/∂W [(][ℓ][)]∂W [(][ℓ][+1)], ∀1 ≤ _ℓ_ _≤_ _L._

D PROOF OF THEOREM 1

The second order gradient P [(][l,l][+1)] = ∂[2]C/∂W [(][ℓ][)]∂W [(][ℓ][+1)] is proposed to measure the interaction
strength between W [(][ℓ][)] and W [(][ℓ][+1)], ∀1 ≤ _ℓ_ _≤_ _L. Considering an MLP, and assume that each_
activation function σℓ is ReLU for ℓ< L, when GA converges, ∇W[(][ℓ][)] [vanishes, i.e.,][ ∇]W[(][ℓ][)] =
(δ[(][ℓ][)] **_σ[′][ℓ])z[(][ℓ][−][1)][T]_** = 0 (Eq. 12 in Appendix B). It indicates that (δ[(][ℓ][)] **_σ[′][ℓ])izj[(][ℓ][−][1)]_** = 0, i.e., either
_⊙_ _⊙_

(δ[(][ℓ][)] **_σ[′][ℓ])i = 0 or zj[(][ℓ][−][1)]_** = 0, (i, j). According to Eq. 10, the numerator involves the product of
_⊙_ _∀_

terms δ[(][ℓ][)] _⊙_ **_σ[′][ℓ]_** and z[(][ℓ][−][1)], which are zeros[7], so βeff = 0.

E BAYESIAN RIDGE REGRESSION

Ridge regression introduces an ℓ2-regularization to linear regression, and solves the problem

arg minθ (y − _Xθ)[T]_ (y − _Xθ) + λ∥θ∥2[2][,]_ (17)

where X ∈R[n][×][d], y ∈R[n], θ ∈R[d] is the associated set of coefficients, the hyper-parameter λ > 0
controls the impact of the penalty term ∥θ∥2[2][.]

**Bayesian ridge regression introduces uninformative priors over the hyper-parameters of the model,**
and estimates a probabilistic model of the problem in Eq. 17. Usually, the ordinary least squares
method posits the conditional distribution of y to be a Gaussian, i.e., p(y _X, θ) =_ (y _Xθ, σ[2]Id),_
_|_ _N_ _|_
where σ > 0 is a hyper-parameter to be tuned, and Id is a d×d identity matrix. Moreover, if we assume
a spherical Gaussian prior θ, i.e., p(θ) = (θ 0, τ [2]Id), where τ > 0 is another hyper-parameter to
_N_ _|_
be estimated from the data at hand. According to Bayes’ theorem, p(θ|X, y) ∝ _p(θ)p(y|X, θ), the_
estimates of the model are made by maximizing the posterior distribution p(θ|X, y), i.e.,

arg max log p(θ _X, y) = arg max_ log (y _Xθ, σ[2]Id) + log_ (θ **0, τ** [2]Id),
**_θ_** _|_ **_θ_** _N_ _|_ _N_ _|_

which is a maximum-a-posteriori (MAP) estimation of the ridge regression when λ = σ[2]/τ [2]. All θ,
_λ and τ are estimated jointly during the fit of the model, and σ = τ_ _√λ._

7A small constant ε is added to the denominator of βeff to avoid division by zero.


-----

To estimate I = h(βeff ; θ), we use scikit-learn[8], which is built on the algorithm described in Tipping
(2001) updating the regularization parameters λ and τ according to MacKay (1992).

F RANKING PERFORMANCE ON ALL FIVE DATASETS






Birds

0.92 0.96 1.00

|ρ = 0.74 Spearman Corr.|Inception MobileNet ResNet VGG Xception|
|---|---|


ρ = 0.74

Spearman Corr.

Predicted Acc.


1.00

0.96

0.92


AlexNet
DenseNet
Inception
MobileNet
ResNet
VGG
Xception


CIFAR10 CIFAR100 SVHN Fashion MNIST

0.8

0.96

0.96 0.94

0.94

ρ = 0.93 0.7 ρ = 0.77 0.95 ρ = 0.84 0.93 ρ = 0.95

0.92 Spearman Corr. Spearman Corr. Spearman Corr. Spearman Corr.

0.92 0.94 0.96 0.7 0.8 0.95 0.96 0.93 0.94

Predicted Acc. Predicted Acc. Predicted Acc. Predicted Acc.


Figure F.4: Predictions of the validation accuracy of pre-trained models on all five datasets based
on βeff v.s. true test accuracy of these models after fine-tuning for T = 50 epochs. The Spearman’s
ranking correlation ρ is used to quantify the performance in model selection. Each shape is associated
with one type of pre-trained models. Distinct models of the same type are marked in different colors.
To be noted, each includes AlexNet in computing ρs.


CIFAR10

10 15


CIFAR100


SVHN


Fashion MNIST

10 15


Birds

10 15


1.00

0.75

0.50

0.25


10 15 5 10 15

Length of Learning Curve


Ours
BSV
LSV
BGRN
CL


Figure F.5: A comparison between our βeff based approach and the baselines in model ranking.

RUNNING TIME ANALYSIS


500

300

100


Figure G.6: Training time per epoch versus
computing time for βeff per epoch over all 17
pre-trained models and five datasets discussed
in the main text. Each data point is associated
with one pre-trained model over one dataset.
The relative cost of our approach in computing βeff with respect to training more epochs
can be measured by c = Tβeff _/Ttrain. On_
average, it is ¯c ≈ 1.3 (slope of the pink line).


100 300 500

CIFAR10
CIFAR100
SVHN
Fashion MNIST

¯c = 1.332

Birds

Ttrain


Table G.2: Running time
(in seconds) in learning
curve prediction, including the predictor estimation (if necessary, e.g.,
Ours, CL and BGRN).


|ataset|Ours|BGRN|LSV|BSV|CL|
|---|---|---|---|---|---|

|FAR10 FAR100 VHN shion MNIST rds|0.491 0.414 0.506 0.493 0.460|0.610 0.628 0.607 0.625 0.636|0.059 0.051 0.074 0.057 0.071|0.049 0.045 0.044 0.046 0.044|3966.128 5256.478 4690.507 4552.194 4734.992|
|---|---|---|---|---|---|


[8https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.BayesianRidge.html)
[BayesianRidge.html](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.BayesianRidge.html)


-----

H MEAN-FIELD APPROACH

We summarize the main idea of the mean-field approach developed by Gao et al. (2016), and show
how Eq. 3 is obtained (Jiang et al., 2020a;b).

Based on the notations described in Section 3, we consider a vertex i and the interaction term

_j_ _[P][ij][g][(][x][i][, x][j][)][ in Eq. 1, where][ P][ij][ is the influence][ j][ has on][ i][. Similarly,][ i][ influences][ j][ with a]_
weightP _Pji. We define the in-degree δi[in]_ [=][ P]j _[P][ij][ and the out-degree][ δ]i[out]_ = _j_ _[P][ji][. The interaction]_

term can be rewritten as

_j_ _[P][ij][g][(][x][i][, x][j][)]_

_Pijg(xi, xj) = δi[in]_ _._ [P] (18)
_j_ P _k_ _[P][ik]_

X

Here the in-degrees δ[in] captures the idiosyncratic part, and the averageP _g(·, ·) captures the network_
effect. The mean-field approximation is to replace local averaging with global averaging, which
approximates the network impact on a vertex as nearly homogeneous. Specifically, we can get


_ij_ _[P][ij][g][(][x][i][, x][j][)]_

= **[1][T][ Pg][(][x][i][,][ x][)]** _,_ (19)
_ik_ _[P][ik]_ **1[T]** _P_ **1**

P


_j_ _[P][ij][g][(][x][i][, x][j][)]_

_k_ _[P][ik]_

P


where the vector g(xi, x) has the jth component g(xi, xj). A linear operator

_P (z) =_ **[1][T][ P]** (20)
_L_ **1[T]** _P_ **1** **_[z][ =][ δ]δ[out][out][ ·][ z] 1_**

_·_

is defined for a weighted average of the entries in z. The mean-field approximation gives

_x˙_ _i = f_ (xi) + δi[in] [[][g][(][x][i][,][ x][)]][.] (21)

_[L][P]_

In the first order linear approximation, we can take the LP -average inside g. The average of external
interactions is approximately the interaction with its average, i.e. LP [g(xi, x)] ≈ _g(xi, LP (x)) and_

_x˙_ _i = f_ (xi) + δi[in][g][(][x][i][,][ L][P] [(][x][))][,] (22)

where LP (x) is a global state. Let xav ≜ _LP (x). Applying LP to both sides of Eq. 22 gives_

_x˙_ av = LP [f (x)] + LP [δ[in]g(x, xav)]. (23)

According to the extensive discussion and tests in (Gao et al., 2016), the in-degrees δ[in] and the
interaction with the external xav are roughly uncorrelated, so the LP -average of the product is roughly
the product of LP -averages. Therefore, LP [δ[in]g(x, xav)] ≈LP (δ[in])LP [g(x, xav)]. Using the first
order linear approximation, we take the LP -average inside f and g

_x˙_ av = f (LP (x)) + LP (δ[in])g(LP (x), xav). (24)

Therefore, we have
_x˙_ av = f (xav) + βeff _g(xav, xav),_
where βeff = LP (δ[in]) is the resilience metric, and its steady-state is the effective network impact
_xeff_, satisfying ˙xeff = f (xeff ) + βeff _g(xeff_ _, xeff_ ) = 0.


I CORE PROCEDURE

Our framework is built on several different techniques and the related contents are dispersed in
different sections. Here we briefly summarize the core idea of this paper and show how these sections
are organized, see Fig. I.7 for a flowchart of our core procedure.

We view the NN training as a dynamical system, and directly model the evolving of the trainable
weights in the SGD based training as a set of differential equations (Section 3), characterized by a
general dynamics in Eq. 1. Usually, it is convenient to study the dynamics of agents (trainable weights
in our case) on a regular network, where each node represents an agent in the dynamical system and
the interactions of agents are governed by Eq. 1. Many powerful techniques have been developed
in network science and dynamical systems, e.g. the universal metric βeff developed by Gao et al.
(2016) to quantify and categorize various types of networks, including biological neural networks


-----

(Shu et al., 2021). Because of the generality of the metric, we analyze how it looks on artificial neural
networks which are designed to mimic the biological counterpart for general intelligence. Therefore,
an analogue system of the trainable weights under the context of the general dynamics is set up in our
framework. To the end, we build a line graph for the trainable weights (Fig. 1a and Section 4.1) and
“rewrite” (Section 4.2 and Appendix C) the training dynamics in the form of Eq. 1, which includes a
self-driving force f (·), an external driving force g(·, ·) and an adjacency matrix P (Eqs. 8 & 9).

The reformulated training dynamics yields a simple NN Training as A Dynamical System
yet powerful property. It is proved that as the neural
network converges, βeff approaches zero (Theorem **Network** **Dynamics**
1 in Section 4.3, also one of our primary contribu- Neural Network Training Dynamics
tions). As shown in Fig. 1(c) and Section 4.3, we _GA_ **Eqs. 6 & 7**
exploit the property to predict the final accuracy of a **Section 4.1** **Section 4.2**
neural network model with a few observations during Line Graph Edge Dynamics
the early phase of the training, and apply it to select _GB_ **Eqs. 1 & 9**
the pre-trained models (Algorithm 1 in Section 4.4).
Generally speaking, the metric βeff should be calcu- {
lated for the entire neural network. However, because Mean-Field based Approach
many state-of-the-art neural network models havelarge-scale trainable weights. If all layers are consid- _βeff = [1]1[T][T][PP]P1[1]_ relies on the adjacency matrix (P **Eq. 8)**
ered, it will be prohibitive to compute the associated **Sections 4.3 & 4.4**

|Mean-Field based Approach 1TPP1 β = relies on the adjacency matrix P (Eq. 8) eff 1TP1|Col2|
|---|---|
||Sections 4.3 & 4.4|

_βeff_ . We make a compromise, and estimate βeff of Learning Curve Prediction & Model Selection
the entire network using βeff of the NCP unit (i.e.,
a partial part of the entire network, see the second **Option 1** **Option 2**

|Sections 4.3 & 4.4|Col2|
|---|---|
|Learning Curve Prediction & Model Selection||
||Option 1 Option 2|

to the last sentence of Section 4.3). It’s confirmed Full GA → _GB[full]_ → _βeff[full]_ NCP GA → _GB[ncp]_ → _βeff[ncp]_
from our empirical experiments (Section 5) that the

NN Training as A Dynamical System

**Network** **Dynamics**

Neural Network Training Dynamics

_GA_ **Eqs. 6 & 7**

**Section 4.1** **Section 4.2**

Line Graph Edge Dynamics

_GB_ **Eqs. 1 & 9**

# {

Mean-Field based Approach

_βeff = [1]1[T][T][PP]P1[1]_ relies on the adjacency matrix (P **Eq. 8)**

**Sections 4.3 & 4.4**

Learning Curve Prediction & Model Selection

**Option 1** **Option 2**

Full GA → _GB[full]_ → _βeff[full]_ NCP GA → _GB[ncp]_ → _βeff[ncp]_

simplified, lightweight version of βeff is still effective Figure I.7: A flowchart of the core procedure
in predicting the final accuracy of the entire network. of our framework.

The metric βeff developed by Gao et al. (2016) is universal to characterize different types of networks.
Although our framework utilizes the metric, our application to artificial neural network training
dynamics and the related theoretical results as specified by Theorem 1 are novel. Specifically, it
is applied to study the NN training (Section 3) and predict the final accuracy of an NN with a few
observations during the early phase of the training (Fig. 1c). But βeff relies on the adjacency matrix
_P of GA (Eq. 3). To derive P_, we resort to a reformulation (Section 4.2 and Appendix C) of the
training dynamics in the same form of the general dynamics (Eq. 1). One issue in calculating βeff is
the complexity if the entire GA is considered. As a resolution, we propose to use the lightweight βeff
of the NCP unit – a partial of GA – to predict the performance of the entire network (Sections 4.3 &
4.4).


-----

