FINDING DEEP LOCAL OPTIMA USING NETWORK PRUNING
Year: 2019

Abstract:
Artificial neural networks (ANNs) are very popular nowadays and offer reliable solutions to many classification problems. However, training deep neural networks (DNN) is time-consuming due to the large number of parameters. Recent research indicates that these DNNs might be overparameterized and different solutions have been proposed to reduce the complexity both in the number of parameters and in the training time of the neural networks. Furthermore, some researchers argue that after reducing the neural network complexity via connection pruning, the remaining weights are irrelevant and retraining the sub-network would obtain a comparable accuracy with the original one. This may hold true in most vision problems where we always enjoy a large number of training samples and research indicates that most local optima of the convolutional neural networks may be equivalent. However, in non-vision sparse datasets, especially with many irrelevant features where a standard neural network would overfit, this might not be the case and there might be many non-equivalent local optima. This paper presents empirical evidence for these statements and an empirical study of the learnability of neural networks (NNs) on some challenging non-linear real and simulated data with irrelevant variables. Our simulation experiments indicate that the cross-entropy loss function on XOR-like data has many local optima, and the number of local optima grows exponentially with the number of irrelevant variables. We also introduce a connection pruning method to improve the capability of NNs to find a deep local minimum even when there are irrelevant variables. Furthermore, the performance of the discovered sparse sub-network degrades considerably either by retraining from scratch or the corresponding original initialization, due to the existence of many bad optima around. Finally, we will show that the performance of neural networks for real-world experiments on sparse datasets can be recovered or even improved by discovering a good sub-network architecture via connection pruning.

text: Artificial neural networks (ANNs) are very popular nowadays and offer reliable solutions to many classification problems. However, training deep neural networks (DNN) is time-consuming due to the large number of parameters. Recent research indicates that these DNNs might be overparameterized and different solutions have been proposed to reduce the complexity both in the number of parameters and in the training time of the neural networks. Furthermore, some researchers argue that after reducing the neural network complexity via connection pruning, the remaining weights are irrelevant and retraining the sub-network would obtain a comparable accuracy with the original one. This may hold true in most vision problems where we always enjoy a large number of training samples and research indicates that most local optima of the convolutional neural networks may be equivalent. However, in non-vision sparse datasets, especially with many irrelevant features where a standard neural network would overfit, this might not be the case and there might be many non-equivalent local optima. This paper presents empirical evidence for these statements and an empirical study of the learnability of neural networks (NNs) on some challenging non-linear real and simulated data with irrelevant variables. Our simulation experiments indicate that the cross-entropy loss function on XOR-like data has many local optima, and the number of local optima grows exponentially with the number of irrelevant variables. We also introduce a connection pruning method to improve the capability of NNs to find a deep local minimum even when there are irrelevant variables. Furthermore, the performance of the discovered sparse sub-network degrades considerably either by retraining from scratch or the corresponding original initialization, due to the existence of many bad optima around. Finally, we will show that the performance of neural networks for real-world experiments on sparse datasets can be recovered or even improved by discovering a good sub-network architecture via connection pruning.

heading: 1 INTRODUCTION
text: Artificial neural networks are very popular nowadays and they can offer good solutions to many vision problems (Dahl et al., 2013; Krizhevsky et al., 2012; Le, 2013; He et al., 2016). However, the neural networks usually require massive amounts of training data for good generalization, which limit their applications to non-vision problems where the data is not so abundant.
In this paper, we conduct an empirical investigation of the relationship between the amount of training data and the landscape of the loss function. We will see that when the training data is large, the landscape has fewer local optima, which makes it is easier to find a deep local optimum, corresponding to a model with good generalization. If the training data is limited, the energy landscape could have in some cases so many local minima that it is computationally prohibitive to find a deep local minimum with good generalization.
For this experimental investigation, we will use it as a proxy of a difficult non-linear dataset generalized XOR data with extra irrelevant variables. By adjusting the dimensionality of the XOR relationship and the number of irrelevant variables we can control the degree of difficulty of the problem and see the relationship between the amount of training data and the loss landscape.
For our experimental investigation, we will focus our attention to simple neural networks with one hidden layer and ReLU activation. On the XOR-based classification problems, we will show that the cross-entropy energy landscape has many shallow local minima and some deep minima that are very hard to find. We will also observe that the number of shallow local minima grows prohibitively large as the number of irrelevant variables increase, and the chances of finding a deep minimum decrease quickly with the number of irrelevant variables. This decrease is much faster for harder problems (e.g. 5D XOR) than for easier problems (3D XOR). We also observe that for a fixed problem, the difficulty of finding deep local minimum decreases as more training examples are used.
Based on these findings, we propose a graduate node and connection pruning technique that starts with a dense network with many hidden nodes and gradually prunes connections or nodes to arrive at a sparse network with few hidden nodes. A large number of initially hidden nodes ensure high connectivity between the local minima making them easier to find. The gradual pruning ensures that the local optimum is not lost during the optimization process. We will see in experiments that this technique finds deeper local optima than when starting from a small network with random initialization or retrain the found sparse sub-network from scratch or using corresponding original initial parameters.
This is a purely experimental paper that does not intend to make any theoretical contributions. Through some welldesigned experiments on data of different levels of difficulty it tries to obtain insights about the relationship between data difficulty, the number of training examples and the computational difficulty of finding a deep local optimum with good generalization. This intuition suggests that in some cases a neural network could be trained with fewer training examples at the expense of increased computational complexity in the optimization process of finding a deep local optimum, where a simple SGD or Adam optimization might not be enough.

heading: 1.1 RELATED WORK
text: Local minima. Recent studies Draxler et al. (2018); Garipov et al. (2018) have shown that the local minima of some convolutional neural networks are equivalent in the sense that they have the same loss (energy) value and a path can be found between the local minima along which the energy stays the same. For this reason, we will focus our attention to fully connected neural networks and find examples where the local minima have different loss values. Moreover, Soudry & Carmon (2016) proves that all differentiable local minima are global minima for the one hidden layer NNs with piecewise linear activation and square loss. However, nothing is proved for non-differentiable local minima.
Network pruning. There has been quite a lot of work recently about neural network pruning, either for the purpose of improving speed and reducing complexity or giving insights about explaining the essential capability of the pruning technique. Han et al. (2015b) and Han et al. (2015a) propose the ”Deep Compression”, a three-stage technique, which significantly reduces the storage requirement for training deep neural networks without affecting their accuracy. Liu et al. (2018) shows that for structured pruning methods, directly training the small target sub-network or pruned model with random initialization can achieve a comparable or even better performance than retraining using the remaining parameters after pruning. They also obtain similar results towards to a unstructured pruning method Han et al. (2015b) after fine-tuning the pruned sub-network on small-scale datasets. Frankle & Carbin (2019) introduces the Lottery Tickets Hypothesis which claims that a random-initialized dense neural network contains a sub-network that can be trained in isolation with the corresponding original initialized parameters to obtain the same test accuracy of the original network after training for the same number of iterations.

heading: 2 AN EMPIRICAL STUDY OF THE NEURAL NETWORK LOCAL MINIMA
text: To study the local minima of neural networks, we will look at an extreme case, the XOR problem. The k-dimensional XOR is a binary classification problem that can be formulated as
y(x) = I( k∏ i=1 xi > 0),∀x ∈ Rp
Observe that in this formulation the XOR data is p dimensional but the degree of interaction is k-dimensional, with k ≤ p. We call this data the k-D XOR in p dimensions. In this paper we will work with k ∈ {3, 4, 5}, as k = 2 is very simple. We assume that x ∈ Rp is sampled uniformly from [−1, 1]p. The XOR problem an example of data that can only be modeled by using higher order feature interactions, and for which lower order marginal models have no discrimination power. This makes it very difficult to detect what features are relevant for predicting the response y.
The neural networks (NN) that we will study are two layer neural networks with ReLU activation for the hidden layer. These NNs can model the XOR data in case p = k = {3, 4, 5} very well given sufficiently many hidden nodes.

heading: 2.1 THE ENERGY LANDSCAPE OF THE NN ON THE XOR DATA
text: To see the difference between the values of the various local minima, we ran the NN starting with 100 random initializations and plotted in Figures 1 and 2 the values of the local minima sorted in increasing order for k = 4 and k = 5. We repeated this process 10 times and also plotted the average of the sorted local minima.
From Figures 1 and 2 we observe that the local minima are not equivalent, with the lowest being much smaller than the highest. We also see that for small p, the 500 hidden nodes NN has the lowest loss values, but for p = 100 the 20 hidden nodes NN obtains the lowest loss.
The loss values are directly related to the training AUC (area under the ROC curve). In Figures 1 and 2, bottom, are plotted the mean train and test AUC of the models corresponding to the sorted local minima. Observe that for p = 100 the NN cannot find the global optimum and the test AUCs are all close to 0.5. These experiments indicate that when the number of irrelevant features is small, it is quite easy to find a deep local optimum with good generalization, so the NN is easily trainable. As the number of irrelevant features increases, it becomes harder and harder to find such a deep optimum, and when there are too many irrelevant features it is close to impossible to find a deep optimum with good generalization.

heading: 2.2 THE TRAINABILITY OF NEURAL NETWORKS
text: To see the change from an easily trainable NN (such as shown in Figures 1 and 2, left, to a poorly trained NN such as in Figures 1 and 2, right, for each dimension p we train a NN with 500 hidden nodes with 10 random initializations
and keep the solution with smallest loss. Then we compute the test AUC of the obtained NN. For each p we repeat this process 10 times and display in Figure 3 the average test AUC vs p.
We observe that the test AUC quickly drops from close to 1 to 0.5. The number of variables p where the test AUC gets below a threshold (e.g. 0.8) depends on the number n of training examples. This drop does resemble a phase transition, from an “easy to train” regime where the local minima are easy to find, to the “hard to train” regime.
Our conclusions from this empirical study are the following:
• If the training data is difficult (such as the XOR data), not all local minima are equivalent, since in Figures 1 and 2 there was a large difference between the test AUC of the best local minimum and the worst one.
• For a fixed training size n, the number of shallow local minima quickly blows up as the number of irrelevant variables increases and finding the deep local minima becomes extremely hard.
• If the number of irrelevant variables is not too large (e.g. the middle plot from Figure 2), an NN with a sufficiently large number of hidden nodes will find a deep optimum more often than one with a small number of hidden nodes.
These conclusions form the basis for the proposed connection pruning methodology presented in the next section.

heading: 3 FINDING BETTER LOCAL MINIMA THROUGH NODE AND CONNECTION PRUNING
text: As we saw in the previous section, the NNs can handle the XOR data if p is in a reasonable range. We also observe that increasing the number of hidden node in NNs may not be very helpful for improving the test AUC. To demonstrate this observation, for different number of hidden nodes, we train a NN with 10 random initializations and keep the best test AUC and its associated training AUC among the 10 trials. We repeat this process 10 times and display in Figure 4 the average test and train AUC vs the number of hidden nodes. When the number of hidden node increases, the training AUC becomes better and better and finally reaches 1. But the test AUC quickly reaches the best results when the number of hidden nodes is relatively small, and then no further improvement happens as the number of hidden nodes increases. This tells us that increasing the number of hidden nodes, will add too many irrelevant nodes to the NNs, leading to overfitting.
We will use fully connected neural networks with one input layer, several hidden layers (l = 1, 2, ..., L − 1) with ReLU activation and one output layer. If the hidden layer l has hl neurons, we can represent the weights of the hidden nodes in layer l as a matrix Wl ∈ Rhl×hl−1 , the biases as a vector bl = (bl1, ..., blh). Denoting the ReLU activation as
σ(x) = max(0, x) we can write the neural network as: f(x) = WLσ(Wl−1σ(...σ(W1x+ b1) + ...) + bL−1) + bL (1)

heading: 3.1 CONNECTION PRUNING WITH ANNEALING FOR FEATURE AND NODE SELECTION
text: The above study showed how important it is to find deep local optima when training neural networks on difficult data with a small number of observations. For that we will start with a larger network which has better connectivity between the local optima, and gradually remove the irrelevant hidden nodes and irrelevant features through connection pruning. Inspired by the feature selection with annealing (Barbu et al., 2017) and the weight learning for efficient neural networks (Han et al., 2015b), we propose find better local optima by starting with a NN with many hidden neurons and then use connection pruning with an annealing schedule to achieve both feature and node selection and obtain a well trained NN. The advantage of using a annealing schedule with an iterative pruning approach is that we can control how many connections we want to keep in the end, making it easy to determine the minimum number of connections needed to reproduce the performance of the original unpruned network.
Figure 5 illustrates the pruning framework: we first train a fully connected NN with many hidden nodes to reach a local optimum, then we start connection pruning at that point with an annealing schedule Me,
Me = k + (p− k)max ( 0,
(Nepoch −Npretrain)− 2e 2eµ+ (N iter −Npretrain)
) (2)
where k is the target number of connections desired to be kept at the end, e is the current training iteration number, and µ is a parameter that controls the annealing rate.
Algorithm 1 Connection Pruning with Normalization and Annealing (CPNA) Input: Training set T = {(xi, yi) ∈ Rp×R}ni=1, initial number of hidden neuronsH l, target number of weight connectionsmlh, pre-train iterationsN
pretrain, total training iterationsN total, annealing scheduleMe, e = 1, .., N total. Output: Trained NN with mlh weight connections in layer l.
1: Initialize a NN with H hidden neurons with random initialization 2: for e = 1 to N iter do 3: if e > Npretrain then 4: for l = 1 to L do 5: Normalize hidden node j:
wl+1←‖wlj‖wl+1, blj← blj ‖wlj‖ ,wlj← wlj ‖wlj‖
(3)
6: Remove weight connections to keep the Me connections with largest |w| 7: end for 8: end if 9: Train the NN for the remaining iterations
10: end for
The connection pruning is done layer-wise. The hidden layer(s) and input layer can be pruned in different orders or even at same time, depending on which approach works best. Any connection that has been removed will not be reintroduced. If one of the hidden neurons has no effective connections to the neurons in the next layer left, we could remove it from the network since it no longer makes any contribution to the NN. If one of the input neuron (i.e data feature) has no effective connections to any hidden nodes, we can remove that feature for the feed-in data. After
pruning, the original fully connected neural network will generate a sparse neural network with only a few connections in each layer. We will keep training for a few more epochs so that the resulted sparse NN can eventually fall into a local optimum.
As the connection dropping criterion is based on the absolute magnitude of each weight connection in the NN, the weights need to be considered relative to the average of the activation of the input corresponding to each weight. We normalize the activation in each layer l and incorporate the scaling factor into the weight wl+1j , j = 1, ..., h
l+1, as follows. Observe that in Eq.(1), if we divide wlj and b l j by a constant c > 0 and multiply w l+1 k by the same c we obtain an equivalent NN that has exactly the same output, due to the fact that we use ReLU activation. Since we normalized the data to the range [−1, 1]p, we can equivalently scale the activation without using training data by normalizing the weight vectors wlj , j = 1, ..., h
l, l = 1, ..., L − 1. The proposed detailed method for pruning the weight connections with annealing schedule including this normalization step is presented in Algorithm 1.
Observe that a similar algorithm can be obtained to directly remove
NN hidden nodes instead of connections. We will call this algorithm also CPNA for simplicity.
To test the effectiveness of the weight normalization procedure from CPNA, we run the experimental results shown in Figure 6 for a single hidden layer neural network with 100 random initializations on the 5D XOR data with p = 15, n = 3000. For the CPA (connection pruning without weight normalization) and CPNA (connection pruning with weight normalization), we only perform connection pruning between the hidden layer and the output layer and leave the input layer connections untouched. We see both CPA and CPNA help improve the generalization capability of NNs, but the CPNA not only achieves the highest test AUC, but also is more consistent (the variance is smaller) than CPA in obtaining deeper local optima.

heading: 4 EXPERIMENTS

heading: 4.1 XOR RELATED SIMULATED DATASETS
text: In this section, we present experiments on 3D, 4D, 5D XOR datasets with a 3000 observations training set and 3000 different testing samples. The total number p of features for each dataset will be selected such that the neural network almost lost all its generalization capability. For the 3D XOR dataset, we selected p = 60, for 4D XOR is p = 40 and 5D XOR is p = 20. Figure 3 shows that a one hidden layer NN without regularization can only obtain a test AUC close to 0.5 for these cases, which means it has nearly no generalization power.
We also train a one hidden layer neural network starting from a large number of hidden nodes, then gradually prune the weight connections to some target number, with the purpose of finding a deeper local optimum that can make the NN generalize better. We first perform connection pruning in the hidden layer (NN-CPNA-hidden), and leave the input connections which connect the features to the hidden neurons untouched. After that we prune connections to the input layer, which will be described below. After searching through a number combination of hyper-parameters, we obtained the best initial number of hidden nodes as 1024 for 3D XOR, 2048 for 4D XOR, and 4096 for 5D XOR, and the final number of connections as 12, 16 and 64 respectively. The obtained test AUC (Area Under the ROC curve) results using a default Adam optimizer and L2 penalty 0.001 with CPNA are displayed in Table 1.
In Table 1 are also displayed the best test AUC of a standard one hidden layer NN, the best result of a pruned subnetwork that was retrained after the pruning stage using a random initialization, and the best result of a pruned subnetwork that was retrained after the pruning stage using the initial weights used before pruning. Clearly, we see that our connection pruning technique that preserved the trained weights helps the NN have a far better generalization than the others networks, and the sub-network does not seem to find a good local optimum when retrained.
We further examine whether or not we can recover the performance of the sub-network after the pruned sub-network was obtained, either via retraining from scratch or from the corresponding initial original weights. In each case, we
repeat 100 times the process of pretraining a fully connected neural network, applying CPNA to prune the hidden connections, and retraining the pruned sub-network using random initialization and initial weights, using the best combination of hyper parameters described above. We sorted the runs by the test AUc and displayed the obtained resulting curves in Figure 7.
From Figure 7 we see that for these three cases on the XOR data, neither retraining from scratch nor using the original initial weights can achieve the performance of the corresponding sub-network that was obtained by pruning the fully connected dense neural network. The retraining using initial weights seems works a little better than retraining from a random initialization, as sometimes the sub-network retrained with initial weights can obtain a test AUC beyond 0.6, but still way behind the sub-network obtained form large network pruning.
Besides pruning the connection between the hidden layer and output layer, we also prune connections to the input layer to remove irrelevant features, shown as NN-CPNA(all) in Table 1. This may further improve the performance for the XOR data. The obtained results of further pruning the input connections down to 24 for 3D, 32 FOR 4D, 256 for 5D XOR are also displayed in Table 1, and almost perfectly match the best result we could obtain from training the same XOR data without irrelevant features.
Figure 8 displays a complete training and test loss obtained during training a NN with CPNA on the 4D XOR data with p = 40. Also shown is the AUC evolution, which indicates that a good sub-network was obtained in the end, performing well on both training and testing data The fully connected neural network was first trained for 1200 iterations to reach a local optimum with a training AUC of 1.0 but a bad test AUC. After pruning the connections to the hidden nodes, the training AUC went back to 1 and the test AUC improved considerably. Finally, after pruning the connections to the input layer to remove irrelevant features, the test AUC obtains a comparable performance to the training AUC, which means this is a good deep local optimum. This figure is a good illustration of how the loss and AUC evolve during the training procedure. In most cases the number of training iterations can be reduced to have same final testing performance.

heading: 4.2 REAL DATASETS
text: In this section, we perform an evaluation on a number of real multi-class datasets to compare the performance of a fully connected NN and the sparse NN obtained by the CPNA Algorithm 1. The real datasets were carefully selected from the UCI ML repository (Dua & Graff, 2017) to ensure that the dataset is not large (the number of data samples less than 10000) and that a standard fully connected neural network (with one hidden layer) can have a reasonable generalization power on this data. If a dataset is large, then the loss landscape is simple and the neural network can find a deep local optimum easily, so there is no need for connection pruning to escape bad optima. If a dataset is such that a neural network can rarely be trained on it successfully, it means that the loss might not have any good local optima, then again connection pruning might not make sense. The details about the datasets are displayed in Table 2.
Dataset Number of classes Number of features Number of observations Car Evaluation 4 21 1728 Image Segmentation 7 19 2310 Optical Recognition of Handwritten Digits 10 64 5620 Multiple Features 10 216 2000 ISOLET 26 617 7797
Table 2: Datasets used for evaluating the performance of fully connected NN and sparse NN with CPNA.
Our real dataset experiments are not aimed at comparing the performance with other classification techniques, but to test the effectiveness of CPNA in guiding neural networks to find deeper and better local optima, we will combine all the samples including training, validation and testing data to form a single dataset for each data type first, and then divide them into a training and testing set with a ratio 4 : 1. The obtained training dataset will be used in a 10-run averaged 5-fold cross-validation grid search training process to find the best hyper-parameter settings of a one hidden layer fully connected neural network. After getting the best hyper-parameter setting from the cross-validation, we use them to retrain the fully connected NNs with the entire training dataset 10 different times, and each time we record the best test accuracy. This procedure is used for the fully connected NN, and the NN with CPNA with different sparsity level and record the best sparsity level and testing accuracy. Finally, we will also train a so-called ”equivalent” fully connected neural network with roughly the same number of connections as the best sparse neural network we get from CPNA.
All the experiments were trained with the default Adam optimizer (Kingma & Ba, 2014), the number of hidden nodes was searched in {16, 32, 64, 128, 256, 512}, the L2 regularization coefficient was searched in {0.0001, 0.001, 0.01, 0.1}, the batch size was searched in {16, 32, 64}. Other NN training techniques like Dropout (Srivastava et al., 2014) and Batch Normalization (Ioffe & Szegedy, 2015) were not used in our experiments due to the simplicity of the architecture of experimented NNs. The comparison result are listed in Table 3.
We see from Table 3 that using CPNA to guide the search for a local optimum leads to NNs with good generalization on all these datasets, easily outperforming a NN of an equivalent size (with a similar number of connections) and in most cases even the standard NN with the best generalization to unseen data. The experiments show that the XOR data is indeed an extreme example where deep local optima are be hard to find, but even these datasets exhibit some non-equivalent local optima and the things we learned from the XOR data carry over to these datasets to help us train NNs with better generalization.

heading: 5 CONCLUSIONS
text: This paper presented an empirical study of the trainability of neural networks and the connection between the amount of training data and the loss landscape. We observed that when the training data is large (where ’large” depends on the problem), the loss landscape is simple with a small number of deep local optima. When the training data is small, the number of local optima can become very large, making it hard to find deep local optima. For these cases we introduce a method for training a neural network that avoids many local optima by starting with a model with many hidden neurons and gradually removing weak connections to obtain a sparse network trained in a deep minimum. Moreover, the performance of the obtained pruned sub-network is hard to achieve by retraining using either random initialization or initial weights due to the existence of many shallow local optima around the deep minimum. Experiments also obtain good results on a number of real datasets using the same network pruning technique.

heading: A APPENDIX
text: You may include other additional sections here.

Review summaries:
This paper presents a few sets of experiments related to deep local optima. The first set of experiments are to study the local minima of two layer neural networks with ReLU activation for the hidden layer and specialized for XOR problem. The paper claims that it is quite easy to find a deep local minimum with good generalization when the number of irrelevant features is small, and it becomes harder to find a deep minimum with good generation as the number of irrelevant features increases. It also claims there is a large difference between the test AUC of the best local minimum and the worse one if the training data is difficult.