Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: 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.
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.

heading: 2 RELATED WORK
text: 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.

heading: 3 PRELIMINARIES
text: Dynamical System of a Network. Many real complex systems, e.g., plant-pollinator interactions (Waser & Ollerton, 2006) and the spread of COVID-19 (Thurner et al., 2020), can be described with networks (Mitchell, 2006; Barabási & Pósfai, 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) + ∑ j∈V Pijg(xi, xj),∀i ∈ V, (1)
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 ) + ∑ j∈V Pijg(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
LP (z) = 1TPz
1TP1 , (2)
where z ∈ Rn. Let δin = P1 be nodes’ in-degrees and δout = 1TP be nodes’ out-degrees. For a weighted G, the degrees are weighted as well. Applying LP (·) to δin, it gives
βeff = LP (δin) = 1TPδin 1T δin = δToutδin 1T δin , (3)
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 andw: 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, A denotes a node 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., z (`) i = σ`(a (`) i ), 1 ≤ i ≤ n`,∀1 ≤ ` < L and z(L)k = exp{a (L) k }/ ∑ j exp{a (L) j }, 1 ≤ k ≤ nL, where n` is the total number of neurons on layer `, and GA has L+ 1 layers. It also presents a dependency between z and w. For example, when GA is an MLP without bias, a (`) i = w (`)T i z
(`−1), which builds an interconnection from GA to GB . It is obvious, givenw, the activation z satisfying all these constraints, is also a fixed point of A. Meanwhile, an equilibrium state of B provides a set of optimal weights for GA.

heading: 4 OUR FRAMEWORK
text: 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.

heading: 4.1 LINE GRAPH GB
text: We build a mapping scheme φ : GA 7→ GB , from an NN GA to an associated graph GB . The topology of the synaptic connections (edges) is established as a well-defined line graph proposed by 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.

heading: 4.2 EDGE DYNAMICS B
text: In SGD, each time a small batch of samples are chosen to update w, i.e., w ← w − α∇wC, where α > 0 is the learning rate. When desired conditions are met, training is terminated.
We denote the activation gradients as δ(`) = [∂C/∂z(`)1 , · · · , ∂C/∂z (`) n` ] T ∈ Rn`1 and the derivatives of activation function σ for layer ` as σ′` = [σ ′ `(a (`) 1 ), · · · , σ′`(a (`) n` )]
T ∈ Rn` , 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 anyW (`) 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 matrix 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) = ∂2C/∂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 B for GB :
ẇi = f(wi) + ∑ j Pijg(wi, wj), (9)
with f(wi) = F (w∗i ) and g(wi, wj) = wj − w∗j . The value of weights at an equilibrium state {w∗j } is unknown, but it is a constant and does not affect the computing of βeff .

heading: 4.3 NEURAL CAPACITANCE
text: 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 = P1. 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
βeff =
∑L−2 `=2 [1
Tz(`−2)]× 1T [z(`−1) σ′`−1]× 1T [δ(`) σ′`]× 1T [δ(`+1) σ′`+1]∑L−1 `=2 [1 Tz(`−2)]× [1Tσ′`−1]× 1T [δ(`) σ′`] . (10)
For details of how to derive 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.
Algorithm 1 Implement NCP and Compute βeff Input: A pre-trained model Fs = {F (1)s ,F (2)s } with
bottom layersF (1)s and output layerF (2)s , a target dataset Dt, the maximum number of epochs T 1: Remove F (2)s from Fs and add on top of F (1)s an NCP unit U with multiple layers (Fig.1b) 2: Initialize with random weights and freeze U 3: Train Ft = {F (1)s ,U} by fine-tuning F (1)s on Dt
for epochs of T 4: Obtain P from U according to Eq. 8 5: Compute βeff with P according to Eq. 3 or Eq. 10 For an MLP GA, it is possible to derive an analytical form of βeff . However, it becomes extremely complicated for a deep NN with multiple convolutional layers. To realize βeff for deep NNs in any form, we take advantage of the automatic differentiation implemented in TensorFlow2. Considering the number of parameters, it is still computationally expensive, and prohibitive to calculate a βeff for the entire GA. Because of this, we seek to derive a surrogate from a partial of GA. As shown in Section 4.4, we insert a neural capacitance probe (NCP) unit, i.e., putting additional layers 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.

heading: 5 EXPERIMENTS AND RESULTS
text: Pre-trained models and datasets. We evaluate 17 pre-trained ImageNet models implemented in Keras3, 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 Birds4 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
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
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 that K × Ttrain − k × Tβeff = (K − c × k) × Ttrain > 0, saving us K − c× k more training epochs. 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.

heading: 6 CONCLUSION AND DISCUSSION
text: 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 B, which induces a definition of the link weights in GB . Moreover, a 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 .

heading: A ERROR GRADIENTS
text: 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 = w (`)T i z (`−1) be the pre-activation value of neuron i on layer `, we have z(`)i = σ`(a (`) i ) with w(`)i being the ith row of W (`), 1 ≤ i ≤ n`. The output activation function σL is generally a softmax function, i.e. z(L)i = exp{a (L) i }/ ∑ j exp{a (L) j }, and z(L) is a probability distribution over nL classes, i.e. 1Tz(L) = 1.
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) = − ∑ i yi log z (L) i . 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 z(L)i = exp{a (L) i }/ ∑ j exp{a (L) j }, we get the gradient of the output z (L) k w.r.t w (L) ij :
∂z (L) k /∂w (L) ij = z (L) k (δki − z (L) i )z (L−1) j ,
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 ∂z
(L) i
= − yi z
(L) i
; ∂C
∂w (L) ij = ∑ k ∂C ∂z (L) k ∂z (L) k ∂w (L) ij = (z (L) i − yi)z (L−1) j (11)
Then, we examine layer L− 1. The activation function σL−1 associates to a pair of neurons u(L−1)i on layer L− 1 and u(L−2)j on layer L− 2 with a unique connection weight w (L−1) ij . Since z (L) i =
exp{a(L)i }/ ∑ j exp{a (L) j } and z (L−1) i = σL−1(a (L−1) i ), we get ∂z (L) k /∂z (L−1) i = z (L) k (w
(L) ki −∑
j z (L) j w (L) ji ) = z (L) k (w (L) ki − w (L)T ∗i z (L)), and
∂z (L−1) i /∂w (L−1) ij = z (L−2) j σ ′ L−1(a (L−1) i ).
The derivatives of C are ∂C
∂z (L−1) i
= ∑ k ∂C ∂z
(L) k
∂z (L) k
∂z (L−1) i
= ∑ k yk(w (L)T ∗i z (L) − w(L)ki ) = w (L)T ∗i (z
(L) − y), ∂C
∂w (L−1) ij
= ∂C ∂z
(L−1) i
∂z (L−1) i ∂w (L−1) ij = w (L)T ∗i (z (L) − y)z(L−2)j σ′L−1(a (L−1) i ).
On layer `, where 1 ≤ ` ≤ L− 2, we get ∂z(`+1)k /∂z (`) i = w (`+1) ki σ ′ `+1(a (`+1) k ) and
∂C ∂z
(`) i
= ∑ k ∂C ∂z
(`+1) k
∂z (`+1) k
∂z (`) i
= ∑ k ∂C ∂z
(`+1) k
w (`+1) ki σ ′ `+1(a (`+1) k ),
∂C ∂w
(`) ij
= ∂C ∂z
(`) i
∂z (`) i ∂w (`) ij = ∂C ∂z (`) i z (`−1) j σ ′ `(a (`) i ),
according to the relations z(`+1)i = σ`+1(a (`+1) i ) and z (`) i = σ`(a (`) i ).
Let δ(`) = [∂C/∂z(`)1 , · · · , ∂C/∂z (`) n` ] T ∈ Rn` , σ′` = [σ′`(a (`) 1 ), · · · , σ′`(a (`) n` )] T ∈ Rn` , 1 ≤ ` ≤ L. The gradients can be written in a dense form:
∇W (L) = (z(L) − y)z(L−1)T ∈ RnL×nL−1 , δ(L−1) = W (L)T (z(L) − y) ∈ RnL−1 ,
∇W (L−1) = (δ(L−1) σ′L−1)z(L−2)T ∈ RnL−1×nL−2 , δ(`) = W (`+1)T (δ(`+1) σ′`+1) ∈ Rn` ,
∇W (`) = (δ(`) σ′`)z(`−1)T ∈ Rn`×n`−1 .
(12)

heading: B WEIGHTED DEGREES OF GB
text: We examine three hidden layers {`− 1, `, `+ 1} of GA and three neurons on these layers {j, i, k}. Let w(`+1)ki connects the neuron k on layer ` + 1 to the neuron i on layer `, w (`) ij be the synaptic connection weight between the neuron j on layer ` and the neuron i on layer ` − 1, and w(`−1)jm connects the neuron j on layer `− 1 and the neuron m on layer `− 2.
Now we have a close look at ∂C/∂w(`)ij . According to the chain rule, we have
∂C ∂w
(`) ij
= ∂C ∂z
(`) i
∂z (`) i ∂w (`) ij = δ (`) i z (`−1) j σ ′ `(a (`) i ) = z (`−1) j σ ′ `(a (`) i ) ∑ k δ (`+1) k σ ′ `+1(a (`+1) k )w (`+1) ki .
The gradient term δ(`+1)k = ∂C/∂z (`+1) k is a highly coupled function of all accessible synaptic connection weights of w(`)ij on the forward propagation route from z (`) i 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 w(`+1)ki associated with neuron i on layer `, and the associated coefficient is p{w(`+1)ki , w (`) ij } = z (`−1) j σ ′ `(a (`) i )δ (`+1) k σ ′ `+1(a (`+1) k ), which defines the edge weights from w(`+1)ki to w (`) ij on GB . Similarly, we have the edge weight from w (`) ij to w (`−1) jm , i.e., p{w(`)ij , w (`−1) jm } = z (`−2) m σ′`−1(a (`−1) j )δ (`) i σ ′ `(a (`) i ). Therefore, we are able to calculate the indegree and out-degree ofw(`)ij , which are defined as the sum of the weights of all in-bound connections to w(`)ij and the sum of the weights of all out-bound connections from w (`) ij , i.e.
δin(w (`) ij ) =z (`−1) j σ ′ `(a (`) i ) [∑
k
δ (`+1) k σ ′ `+1(a (`+1) k )
] , (13)
δout(w (`) ij ) = [∑ m z(`−2)m ] σ′`−1(a (`−1) j )δ (`) i σ ′ `(a (`) i ). (14)
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
∂C ∂w
(L) ij = ∑ k ∂C ∂z (L) k ∂z (L) k ∂w (L) ij = z (L−1) j (z (L) i − yi). (15)
Because σL is softmax, no explicit relation regardingw (L) ij can be built. It implies that no well-defined in-bound connections to w(L)ij , i.e., δin(w (L) ij ) = 0. But, we can build the connections from w (L) ij to w (L−1) jm . It is easy to derive
∂C ∂w
(L−1) ij
= ∂C
∂z (L−1) i
∂z (L−1) i ∂w (L−1) ij = z (L−2) j σ ′ L−1(a (L−1) i ) ∑ k (z (L) k − yk)w (L) ki . (16)
From the perspective of w(L−1)ij , we get p{w (L) ki , w (L−1) ij } = z (L−2) j σ ′ L−1(a (L−1) i )(z (L) k − yk); from the perspective of w(L)ij , we have p{w (L) ij , w (L−1) jm } = z (L−2) m σ′L−1(a (L−1) j )(z (L) i − yi). So we have
δout(w (L) ij ) = [∑ m z (L−2) m ] σ′L−1(a (L−1) j )(z (L) i − yi),
δin(w (L−1) ij ) = z (L−2) j σ ′ L−1(a (L−1) i ) ∑ k(z (L) k − yk) = 0,
δout(w (L−1) ij ) = [∑ m z (L−3) m ] σ′L−2(a (L−2) j )δ (L−1) i σ ′ L−1(a (L−1) i ).
The softmax σL(·) makes the output values sum up to one, i.e., ∑ k yk = 1, and δin(w (L−1) ij ) = 0. Now, we examine the first hidden layer. Similar to the output layer, there is no well-defined out-bound connections for w(1)ij , δout(w (1) ij ) = 0. Setting ` = 1 in Eq. 13, we can get the in-degree of w (1) ij
δin(w (1) ij ) = z (0) j σ ′ 1(a (1) i ) [∑
k
δ (2) k σ ′ 2(a (2) k ) ] .
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(w (1) ij ) = δout(w (1) ij ) = δin(w (2) ij ) = 0,
δout(w (2) ij ) = [∑ m z (0) m ] σ′1(a (1) j )(z (2) i − yi).
Since the degrees sum up to zero, βeff = 0, regardless of how many hidden neurons in GA.
If GA only has two hidden layers, i.e. L = 3, the in-degrees are
δin(w (1) ij ) = z (0) j σ ′ 1(a (1) i ) [∑n2 k=1 δ (2) k σ ′ 2(a (2) k ) ] , δin(w (2) ij ) = δin(w (3) ij ) = 0.
The out-degrees are summarized as follows:
δout(w (1) ij ) = 0, δout(w (2) ij ) = [∑n0 m=1 z (0) m ] σ′1(a (1) j )δ (2) i σ ′ 2(a (2) i ), δout(w (3) ij ) = [∑n1 m=1 z (1) m ] σ′2(a (2) j )(z (3) i − yi).
The total degree may be non-zero, but βeff = 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(w (1) ij ) = z (0) j σ ′ 1(a (1) i ) [∑ k δ (2) k σ ′ 2(a (2) k ) ] , δin(w (`) ij ) = z (`−1) j σ ′ `(a (`) i ) [∑ k δ (`+1) k σ ′ `+1(a (`+1) k ) ] ,∀1 < ` < L− 1,
δin(w (L−1) ij ) = 0,
δin(w (L) ij ) = 0.
and the out-degrees
δout(w (1) ij ) = 0, δout(w (`) ij ) = [∑ m z (`−2) m ] σ′`−1(a (`−1) j )δ (`) i σ ′ `(a (`) i ),∀1 < ` < L− 1,
δout(w (L−1) ij ) = [∑ m z (L−3) m ] σ′L−2(a (L−2) j )δ (L−1) i σ ′ L−1(a (L−1) i ),
δout(w (L) ij ) = [∑ m z (L−2) m ] σ′L−1(a (L−1) j )(z (L) i − yi).
It is easy to derive δTinδout = ∑ i,j ∑ 1<`<L−1 δin(w (`) ij )δout(w (`) ij )
= ∑ i,j ∑ 1<`<L−1 [∑ m z (`−2) m ] z (`−1) j σ ′ `−1(a (`−1) j )[σ ′ `(a (`) i )] 2δ (`) i [∑ k δ (`+1) k σ ′ `+1(a (`+1) k ) ] ,
= ∑
1<`<L−1[1 Tz(`−2)]× 1T [z(`−1) σ′`−1]× 1T [δ(`) σ′2` ]× 1T [δ(`+1) σ′`+1].
Now, we move forward to compute the total degree 1T δin = ∑ ij z (0) j σ ′ 1(a (1) i ) [∑ k δ (2) k σ ′ 2(a (2) k ) ] + ∑ ij ∑ 1<`<L−1 z (`−1) j σ ′ `(a (`) i ) [∑ k δ (`+1) k σ ′ `+1(a (`+1) k ) ] ,
= [1Tz(0)]× [1Tσ′1]× 1T [δ(2) σ′2] + ∑ 1<`<L−1[1 Tz(`−1)]× [1Tσ′`]× 1T [δ(`+1) σ′`+1],
= ∑
1≤`<L−1[1 Tz(`−1)]× [1Tσ′`]× 1T [δ(`+1) σ′`+1].
The definitions of in-degree and out-degree ensure that 1T δin = 1T δout must hold. Let’s prove it: 1T δout = ∑ i,j [∑ 1<`≤L−1 ∑ m z (`−2) m σ′`−1(a (`−1) j )δ (`) i σ ′ `(a (`) i ) + ∑ m z (L−2) m σ′L−1(a (L−1) j )(z (L) i − yi) ] ,
= ∑
1<`≤L−1[1 Tz(`−2)]× [1Tσ′`−1]× 1T [δ(`) σ′`] = 1T δin.
With the fact that σ′2` = σ ′ ` for ReLU, according to Eq. 3, we have
βeff =
∑L−2 `=2 [1
Tz(`−2)]× 1T [z(`−1) σ′`−1]× 1T [δ(`) σ′`]× 1T [δ(`+1) σ′`+1]∑L−1 `=2 [1 Tz(`−2)]× [1Tσ′`−1]× 1T [δ(`) σ′`] .

heading: C DERIVATION OF ADJACENCY MATRIX P OF GB
text: 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 ∗(`+1),Ŵ (−`)) ∂W (`+1) (W (`+1) −W ∗(`+1)) + ∂F (W ∗(`+1),Ŵ (−`)) ∂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
dW (`)/dt ≈ F (W ∗) + ∂F (W ∗(`+1), Ŵ (−`))
∂W (`+1) (W (`+1) −W ∗(`+1)).
The term ∂F (W ∗(`+1), Ŵ (−`))/∂W (`+1) = ∂2C(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) = ∂2C(W (`+1), Ŵ (−`))/∂W (`)∂W (`+1), ∀1 ≤ ` ≤ L.

heading: D PROOF OF THEOREM 1
text: The second order gradient P (l,l+1) = ∂2C/∂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 (δ(`) σ′`)iz(`−1)j = 0, i.e., either (δ(`) σ′`)i = 0 or z(`−1)j = 0, ∀(i, j). According to Eq. 10, the numerator involves the product of terms δ(`) σ′` and z(`−1), which are zeros7, so βeff = 0.

heading: E BAYESIAN RIDGE REGRESSION
text: Ridge regression introduces an `2-regularization to linear regression, and solves the problem
arg min θ
(y −Xθ)T (y −Xθ) + λ‖θ‖22, (17)
where X ∈ Rn×d, y ∈ Rn, θ ∈ Rd is the associated set of coefficients, the hyper-parameter λ > 0 controls the impact of the penalty term ‖θ‖22. 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,θ) = N (y|Xθ, σ2Id), 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(θ) = N (θ|0, τ2Id), where τ > 0 is another hyper-parameter to 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 θ logN (y|Xθ, σ2Id) + logN (θ|0, τ2Id),
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-learn8, 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
0.92 0.94 0.96 Predicted Acc.
0.92
0.94
0.96
Tr ue
T est
A cc
.
Spearman Corr. ρ= 0.93
CIFAR10
0.7 0.8 Predicted Acc.
0.7
0.8
Spearman Corr. ρ= 0.77
CIFAR100
0.95 0.96 Predicted Acc.
0.95
0.96
Spearman Corr. ρ= 0.84
SVHN
0.93 0.94 Predicted Acc.
0.93
0.94
Spearman Corr. ρ= 0.95
Fashion MNIST
0.92 0.96 1.00 Predicted Acc.
0.92
0.96
1.00
Spearman Corr. ρ= 0.74 Birds AlexNet DenseNet Inception MobileNet ResNet VGG Xception
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.
5 10 15
0.25 0.50 0.75 1.00
Sp ea
rm an
C orr
. ρ
CIFAR10
Ours BSV LSV BGRN CL
5 10 15
CIFAR100
5 10 15 Length of Learning Curve
SVHN
5 10 15
Fashion MNIST
5 10 15
Birds
Figure F.5: A comparison between our βeff based approach and the baselines in model ranking.

heading: G RUNNING TIME ANALYSIS
text: 100 300 500 Ttrain
100
300
500
T β
ef f
c̄= 1.332
CIFAR10 CIFAR100 SVHN Fashion MNIST Birds 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).
Table G.2: Running time (in seconds) in learning curve prediction, including the predictor estimation (if necessary, e.g., Ours, CL and BGRN).
Dataset Ours BGRN LSV BSV CL CIFAR10 0.491 0.610 0.059 0.049 3966.128 CIFAR100 0.414 0.628 0.051 0.045 5256.478 SVHN 0.506 0.607 0.074 0.044 4690.507 Fashion MNIST 0.493 0.625 0.057 0.046 4552.194 Birds 0.460 0.636 0.071 0.044 4734.992
8https://scikit-learn.org/stable/modules/generated/sklearn.linear_model. BayesianRidge.html

heading: H MEAN-FIELD APPROACH
text: 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 Pijg(xi, xj) in Eq. 1, where Pij is the influence j has on i. Similarly, i influences j with a
weight Pji. We define the in-degree δini = ∑ j Pij and the out-degree δ out i = ∑ j Pji. The interaction term can be rewritten as ∑ j Pijg(xi, xj) = δ in i ∑ j Pijg(xi, xj)∑ k Pik . (18)
Here the in-degrees δin captures the idiosyncratic part, and the average 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∑
j Pijg(xi, xj)∑ k Pik
≈ ∑ ij Pijg(xi, xj)∑
ik Pik =
1TPg(xi,x)
1TP1 , (19)
where the vector g(xi,x) has the jth component g(xi, xj). A linear operator
LP (z) = 1TP
1TP1 z = δout · z δout · 1
(20)
is defined for a weighted average of the entries in z. The mean-field approximation gives
ẋi = f(xi) + δ in i LP [g(xi,x)]. (21)
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) + δ in i g(xi,LP (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 [δing(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 [δing(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) + βeffg(xav, xav),
where βeff = LP (δin) is the resilience metric, and its steady-state is the effective network impact xeff , satisfying ẋeff = f(xeff) + βeffg(xeff , xeff) = 0.

heading: I CORE PROCEDURE
text: 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 yet powerful property. It is proved that as the neural network converges, βeff approaches zero (Theorem 1 in Section 4.3, also one of our primary contributions). As shown in Fig. 1(c) and Section 4.3, we exploit the property to predict the final accuracy of a neural network model with a few observations during the early phase of the training, and apply it to select the pre-trained models (Algorithm 1 in Section 4.4). Generally speaking, the metric βeff should be calculated for the entire neural network. However, because many state-of-the-art neural network models have large-scale trainable weights. If all layers are considered, it will be prohibitive to compute the associated βeff . We make a compromise, and estimate βeff of the entire network using βeff of the NCP unit (i.e., a partial part of the entire network, see the second to the last sentence of Section 4.3). It’s confirmed from our empirical experiments (Section 5) that the simplified, lightweight version of βeff is still effective in predicting the final accuracy of the entire network.
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).

Review summaries:
Accurately predicting the performance at early stage is important for efficient model selection without incurring too much computation. The paper proposes a neural capacitance metric as a predictive measure to capture the performance of a model on the downstream task using only a handful of early training results. The metric is derived from a line graph mapped from a neural network by modeling the dynamical system of the network.

This paper proposes a framework to select the neural networks for downstream tasks. To identify the better generalization model, the authors propose a new metric (Neural Capacitance, NCP) to predict precise learning curves. And the authors provide the theoretical explanations for NCP.  Then the authors have verified the advantages of the proposed method when being applied to different datasets (CIFAR10, CIFAR100, SVHN, Fashion MNIST, Birds) with 17 CNN models.