Finding Deep Local Optima Using Network Pruning
Authors: Yangzi Guo
Yiyuan She
Ying Nian Wu
Adrian Barbu
Venue:  (2020)
Keywords: network pruning
non-convex optimization

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 over-parameterized 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.

Under review as a conference paper at ICLR 2020
FINDING DEEP LOCAL OPTIMA USING NETWORK PRUNING
Anonymous authors Paper under double-blind review
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 the large number of parameters. Recent research indicates that these DNNs might be over- parameterized and different solutions have been proposed to reduce the complexity both in the num- ber of parameters and in the training time of the neural networks. Furthermore, some researchers ar- gue 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 always enjoy large number of training samples and research indicates that most local optima 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 em- pirical 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 expo- nentially with the number of irrelevant variables. We also introduce 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 ex- periments sparse datasets can be recovered architecture via connection pruning.
improved by discovering good sub- network
1 INTRODUCTION
Artificial neural networks are very popular nowadays and they can offer good solutions to many vision problems (Dahl et al. 20133 Krizhevsky et al., 2012 Le 2013 He et al. (0166). 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 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 deep local optimum, corresponding training data is limited, the energy landscape could have in some cases so many local minima that it is computationally prohibitive to find deep local minimum with good generalization.
model with good generalization. If the
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 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 fixed problem, the difficulty of finding deep local minimum decreases more training examples are used.

---

Under review as a conference paper at ICLR 2020
Based on these findings, we propose 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 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 purely experimental paper that does not intend to make any theoretical contributions. Through some well- designed 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 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 deep local optimum, where simple SGD or Adam optimization might not be enough.
1.1 RELATED WORK
Local minima. Recent studies/Drxxler 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 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 (216)) 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) Hnd 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. [Lu et aal.(2218) shows that for structured pruning methods, directly training the small target sub-network or pruned model with random initialization can achieve comparable or even better performance than retraining using the remaining parameters after pruning. They also obtain similar results towards to unstructured pruning method Han et al. (2015b) after fine-tuning the pruned sub-network on small-scale datasets. Franklee & Carbin (2019) introduces the Lottery Tickets Hypothesis which claims that random-initialin 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.
dense neural network contains a sub-network that can be
2
AN EMPIRICAL STUDY OF THE NEURAL NETWORK LOCAL MINIMA
To study the local minima of neural networks, we will look at an extreme case, the XOR problem. The k-dimensional XOR a binary classification problem that can be formulated as
y(x) = I x. > Vx R"
Observe that this formulation the XOR data is dimensional but the degree of interaction is k-dimensional, with k I p. We call this data the k-D XOR in p dimensions. In this paper we will work with k E {3, 4, 5), k = 2 is very simple. We assume that x E Rº is sampled uniformly from [|1, 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 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.
2.1 THE ENERGY LANDSCAPE OF THE NN ON THE XOR DATA
To see the difference between the values of the various local minima, we ran the NN starting with 100 random initial- izations and plotted in Figures I and 2 the values of the local minima sorted in increasing order for h = 4 and k = 5. We repeated this process 10 times and also plotted the average of the sorted local minima.
From Figures I 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.
2

---

Under review as a conference paper at ICLR 2020
NN 20 toin
-N 20 trann
MN 20 t:ST
NN. 20 tost
NNN 100 1rain
-NX 100 Itan
NN TOX toed
NO0 100 best
-NN 500 trui)
-0% 500 Iran
0.6
NN 500 leod
14% 500 boat.
A382
0.7
-NN.0 20 bain
0.7
07-
0.0
100 Irann
0.6
06
0.5
0.6
0.5
-NN
NN 20
-NN-20
-NW 103
NN 100
-NV 100
NW 503
NN 500
NN% 500
Lo50
100
20
100
40
sorted local minino
contedtoons
Figure 1: Values of sorted local minima (top) and train and test AUC (bottom) for 4D XOR. Left: 1000, p 4. Middle: n = 3 = 16. Right: n 3000, p = 100.
NN42
NW
NN 20
-NN 100
NN 103
NN 100
-N 600
NW 503
NN E03
Lo55
0
20
20
100
-N Imin
-NN 20 mran
104 text
NN
100 toir
NNN
train
Yoi
luol
500 tncl
40
50
50
100
60
100
20
40
60
80
100
scrlac local meniro
sorted looal mina
sontd mania
Figure 2: Values of sorted local minima(top) and train and test AUC (bottom) for 5D XOR. Left: 3000, 5. Middle: n = 3000, p = 10. Right: n = 3000, p = 100.
The loss values are directly related to the training AUC (area under the ROC curve). In Figures 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 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 deep optimum with good generalization.
2.2 THE TRAINABILITY OF NEURAL NETWORKS
To see the change from an easily trainable NN (such as shown in Figures in Figures and right, for each dimension p train a NN with 500 hidden nodes with 10 random initializations
I and left, to a poorly trained NN such as
3

---

Under review as a conference paper at ICLR 2020
10
n=1000
n=1000
7=10000
59
Test AUC
Tes: AMC
0.7
06
0.
22
90
102
20
30
dimension p
cimarsioe
dimersion
Figure 3: Test AUC of best energy minimum out of 10 random initializations vs, data dimension for a NN with 500 hidden nodes. Left: k = 3. Middle:
4. Right: k: = 5.
and keep the solution with smallest loss. Then we compute the test AUC of the obtained NN. For each we repeat this process times and display in the average test AUC vs
We observe that the test AUC quickly drops from close to 1 to 0.5. The number of variables where the test AUC gets below 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 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 the XOR data), not all local minima equivalent, since in Figures] 1 and2[hher 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 sufficiently large number of hidden nodes will find 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.
training p-30
tteining
training p=10
36
besting pm
66
bevingg pm2c
testing pm13
training p-35
training p-25
training p-15
testing 35
testing 2-25
testing P-15
28
33 61
120
256
264
si2
708 1804
10
32
66
129
256
s13
703
2004 2536 2048
35
32
64
328
254
513 T4o 1004 153e 2008 3332 4006
Figure 4: Training and testing AUC vs number hidden nodes. Left: = 3. {30, 35), middle: = 4,
(20, 25), right k 5,p 150.
3 FINDING BETTER LOCAL MINIMA THROUGH NODE AND CONNECTION PRUNING
As we saw the previous section, the NNs can handle the XOR data if p 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 the average test and train AUC vs the number 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 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 (1 = 1,2, L.., 1) with ReLU activation and one output layer. If the hidden layer has H² neurons, we can represent the weights of the hidden nodes in layer / as matrix W! e p''x"" x the biases vector b' = (b/...., ..., bl.) Denoting the ReLU activation
4

---

Under review as a conference paper at ICLR 2020
hidden layer
hidcen layer
culpul baye:
auiput leyw
pruning
before
wiler
Figure 5: Connection pruning framework for a fully connected NN with one or several hidden layer(s) and one output layer. The input layer is not real layer with parameters, it consists of the data features which feed into the NNs for training or testing purpose.
max(0, x)) we can write the neural network as: a (x)
f(x)
"i....oo.'''' b²) ...) +b + bb
(1)
3.1 CONNECTION PRUNING WITH ANNEALING FOR FEATURE AND NODE SELECTION
The above study showed how important it is to find deep local optima when training neural networks on difficult data with small number of observations. For that will start with 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 al. 2017) and the weight learning for efficient neural networks (Han et al. 2015b), we propose find better local optima by starting with NN with many hidden neurons and then use connection pruning with an annealing schedule to achieve both feature and node selection and obtain 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 determine the minimum number of connections needed to reproduce the performance of the original unpruned network.
Figure S 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 M.,
(Nepoch NNrretrai) 2e
Mr = 1: + (p k)) max (0. 2eju + (Nater NNretrain
(2)
where is the target number of connections desired to be kept at the end, e is the current training iteration number, and u is parameter that controls the annealing rate.
Algorithm 1 Connection Pruning with Normalization and Annealing (CPNA)
Input: Training set T = ((x;, vi) x initial number of hidden neurons H' target number of weight con-
nections m. pre-train iterations Aprettran total training iterations Nottll annealing schedule Me, = 1, N total
Output: Trained NN with m/, weight connections in layer l.
Initialize NN with H hidden neurons with random initialization 2: for e = 1 to Näter do e > Neretroin then
4: for - 1 to L do Normalize hidden node j:
by
w
|| ///
11
(3)
[[
Remove weight connections keep the Me connections with largest [w]
7: end for
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 no longer makes any contribution the NN. If one of the input neuron (i.e data feature) has effective connections any hidden nodes, remove that feature for the feed-in data. After
5

---

Under review as a conference paper at ICLR 2020
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/ I and incorporate the scaling factor into the weight w .j = 1, 1,.....'** 1/-1, as follows. Observe that in Eq.( if we divide w/ and bj by a constant c > and multiply w by the same e we obtain 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]" we can equivalently scale the activation without using training data by normalizing the weight vectors w j 1.... h = 1, ..... L 1. The proposed detailed method for pruning the weight connections with annealing schedule including this normalization step is presented in Algorithm
Observe that similar algorithm can be obtained to directly remove NN hidden nodes instead of connections. We will call this algorithm also CPNA for simplicity.
10
0.
To test the effectiveness of the weight normalization procedure from CPNA, we the experimental results shown in Figure 6 for 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 con- nections 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.
test
0.7
mean
mean NN-
mean NN-CPNA
64
128
256
512
768
1024
1530 2048 2072 4006
number of hidden node
Figure 6: Average test AUC number of hidden nodes. The NN-CPA and NN-CPNA starting with H hidden nodes as the NN, but are reduced to 64 connections at the end of training. Shown are the means, and mtd In this section, we present experiments on 3D, 4D, 5D XOR datasets with 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 = 20. Figure 3 shows that 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.
4 EXPERIMENTS
4.1 XOR RELATED SIMULATED DATASETS
We also train 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-hidder) 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 default Adam optimizer and L2 penalty 0.001 with CPNA are displayed in Table
and leave the
Test AUC(%)
Dataset
NN(best) NN-CPNA(hidden) NN-CPNA(aII) NN-CPNA(random) NN-CPNA(init)
3D-XOR p- = 60
82.53
96.58
99.58
70.47
71.68
4D-XOR p= 40
72.17
95.31
98.31
52.83
69.32
5D-XOR p= = 20
66.24
80.03
96.83
53.21
66.29
Table 1: Comparison between the standard NN, pruned networks on the hidden layer and all layers, and retrained pruned networks with random weights and the initial weights from the beginning of CPNA.
In Table I are also displayed the best test AUC of a standard one hidden layer NN, the best result of a pruned sub- network that was retrained after the pruning stage using a random initialization, and the best result of a pruned sub- network 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 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
6

---

Under review as a conference paper at ICLR 2020
MN-CPAA
MN-CFAA metre
teerng AbC
texting AUC.
N96-77A mendem--entt Unitio ropvii
moran AMC.
Mur y you Myma mmmm
number of trial
nuirber of wrils
number of trials
Figure 7: Testing AUC vs number of trials. Left: 3, 60; Middle: k 4, 40; Right: k 5, 20.
repeat 100 times the process of pretraining 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 /
From Figure 7 we that for these three cases 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 little better than retraining from random initialization, as sometimes the sub-network retrained with initial weights can obtain 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 remove irrelevant features, shown as NN- CN-Cll)() in Table [ 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
XOR are also displayed in Table T. and almost perfectly match the best result we could obtain from training the same XOR data without irrelevant features.
Figure X displays a complete training and test loss obtained during training a NN with CPNA on the 4D XOR data with 40. Also shown is the AUC evolution, which indicates that 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 local optimum with training AUC of 1.0 but 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 comparable performance to the training AUC, which means this is a good deep local optimum. This figure a good illustration 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.
74h
AUC
number of iteration
number of iteration
Figure 8: Loss and AUC evolution for training a pruned sub-network using CPNA for 4, 4,p 40 XOR data.
4.2 REAL DATASETS
In this section, we perform evaluation number of real multi-class datasets compare the performance of fully connected NN and the sparse NN obtained by the CPNA Algorithm [ 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 standard fully connected neural network (with one hidden layer) can have reasonable generalization power on this data. a dataset is large, then the loss landscape is simple and the neural network can find deep local optimum easily, so there is no need for connection pruning escape bad optima. If a dataset is such that neural network can rarely trained on successfully, means that the loss might not have any good local optima, then again connection pruning might not make sense. The details about the datasets displayed in Table 2
7

---

Under review as a conference paper at ICLR 2020
Dataset
Number of classes
Number of features
Number 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- valasdanliitiionn grid search training process to find the best syper--arameter settings of a one hidden layer fully connected neural network. After getting the best 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.
setting from the vols-vaali,,ion,, we use
NN(best)
NN(cquivalent)
NN+CNPA
Car Evaluation Datasel
Number of Connections
21x64=64x4 1600
21x6+6x4 150
120+32 = 152
Test Accuracy
100.0:10.00
98.23:10.06
100.0
Image Segmentation Dataset
Number of Connections
19x256+256x7 6656
19x14+14x7 364
266+98 364
Test Accuracy
96.87:10.72
96.27:10.58
98.40-10.32
Optical Recognition of Handwritten Digits Dataset
Number of Connections
64x5 12x51x0+1 37888
64x27427x10
1998 98.25::0.19
1792+160 1952
Test Accuracy
98.80=00.29
99,01=0.20
Multiple Features Dataset
Number of Connections
216x64464x10== 14464
216x4+4x10
904 95.45
5834320 903
Test Accuracy
97.85++0.80
98.15-
ISOLET Dataset
Number of Connections
617x64+64x226
617x9+9x26 5787 94.311:0.11
4683+1115 18 5801
Test Accuracy
96.73+0.50
96.91=0.54
Table 3: Performance results of NN(best), NN(equivalent) and NN+CNPA for each dataset.
All the experiments were trained with the default Adam optimizer (Kiggma & 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.10,0.1), the batch size was searched in {16, 32, 64). Other NN training techniques like Dropout (Srivastava et al. 2014) and Batch Normalization (Toffe & Szegedy (015)) were not used in our experiments due to the simplicity of the architecture of experimented NNs. The comparison result are listed in Table
We see from Table 3 that using CPNA to guide the search for local optimum leads to NNs with good generalization all these datasets, easily outperforming NN of an equivalent size (with 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 con-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.
5 CONCLUSIONS
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 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 hard to find deep local optima. For these cases we introduce 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 obtain a sparse network trained in a deep minimum. Moreover, the performance of the obtained pruned bub-netwon 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 number of real datasets using the same network pruning technique.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Adrian Barbu, Yiyuan She, Liangjing Ding, and Gary Gramajo. Feature selection with annealing for computer vision and big data learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(2):272- 286, 2017.
George E Dahl, Tara N Sainath, and Geoffrey E. Hinton. Improving deep neural networks for Ivesr using rectified linear units and dropout. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 8609-8613. IEEE, 2013.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht. Essentially no barriers neural network energy landscape. arXiv preprint arXiv: 180p:008330,8 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL URL/ntp:://acciie...s. edu/ m1
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. ICLR, 2019.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pp. 8803-8812, 2018.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 1rXiv:1510.00149, 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceed- ings of the IEEE conference on computer vision and puttern recognition, pp. 770-778, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 4rXiv:1412.6980, 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Quoc Le. Building high-level features using large scale unsupervised learning. In 2013 IEEE International Confer- ence Acoustics, Speech and Signal Processing, pp. 6595-8598 IEEE, 2013.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint arXiv:1810.0527 2018.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint arXiv:1605.0836/ 2016.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-158, 2014.
A
APPENDIX
You may include other additional sections here.
9


Reviews:
[{"review_id": "SkgJL1KqKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe second experiment set is about pruning fully connected neural networks to find deeper and better optima. The proposed pruning method employs a annealing schedule and iteratively pruning connections to reduce features and nodes. For XOR datasets, the pruning seems be effective. For several real datasets, pruned models are better than original or equivalent models. \n\nOne thing concerns me is that there are a lot of experiment settings seem to be arbitrary. For instance, why use 500 hidden nodes, p is 4, 16, then 100, ...It will be better to explain why those setting are representative so the statements derived from those are valid. \n\nFor Figure 1 and 2, why switch sequence? The top 3 subfigures in Figure 1 is AUC, but the top 3 subfigures of Figure 2 is Loss. It is a bit confusing. \n\nThe paper is interesting and the experiments are comprehensive. I think the results and conclusion are specific for FC networks. It will be more interesting to study on CNN, etc.  Overall, I am a bit concerned with the significance of this paper. \n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lOu8zkcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper addresses the very important topic of local minima in Deep Learning. This is one of the central questions in the theory of Deep Learning for the last years, and despite many interesting results the main questions remain wide open.\nThe reviewer really likes the approach proposed in the paper, to use a simple model and an artificially generated data to study a certain phenomenon. The reviewer represents the opinion that more focus on such setups would greatly benefit the community in terms of progressing the theoretical understanding.\nThe claim made in the paper that there is a relationship between the number/suboptimality of local minima  and the scarcity of the data is both convincing and interesting. The result is well motivated and explained.\nWhat the reviewer thinks the paper would greatly benefit from would be improving the Related Work section. There was a lot of valuable work in the field done in the past years that ids very relevant to the results presented that is not mentioned.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1exfgYCYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission studies losses at local minima of a set of neural networks trained on an XOR-like synthetic dataset, finds that local minima are of varying quality, and proposes a network pruning method to find better local minima. The pruning method is evaluated on XOR-like datasets as well as real-world datasets. \n\nThe use of an XOR-like dataset to study loss landscapes is interesting, making for a controlled and analyzable setting to carry out the study. The way the authors set it up, the XOR-like problem involves nuisance variables that naturally introduce suboptimal local minima into the loss landscape (this is my observation as a reviewer -- I am not sure if the authors were aware of this). I am unsure if Section 2 of the paper was intended as a core contribution or as a motivation for the pruning algorithm proposed in Section 3. Given the set-up’s simplicity, a short theoretical argument (maybe even a theorem) about the quality and number of local minima one would expect to find could have been more concise and compelling than the empirical analysis from the paper. The findings from Section 2 may not be surprising enough to warrant two full pages. \n\nSection 3 proposes a network pruning method to find better local minima. The authors cite a paper by Adrian Barbu as the inspiration for their pruning algorithm with annealing, and use it “to improve the capability of NNs to find a deep local minimum even when there are irrelevant variables”. The cited paper by Barbu as well as https://arxiv.org/pdf/1805.01930.pdf (also by Adrian Barbu, not cited, maybe because it appeared) explore feature selection and regularization with (nearly) the same annealed pruning algorithm in some detail. I would be grateful if the authors could highlight the differences between their work and Barbu’s. \n\nI vote to “weak reject” this paper. The paper discusses interesting ideas, but other ICLR submissions present deeper and more novel material, and there appears to be some (unintentional, I believe) overlap with already-published work. I recommend that the authors cite and discuss https://arxiv.org/pdf/1805.01930.pdf , and possibly submit the paper at a less competitive conference. \n\n\nFurther comments / questions / advice\n=================================\n\n- It would be helpful if the authors made more clear what they consider the key contributions of their paper. If contributions build directly on earlier work, it’s helpful to highlight the differences. \n\n- Section 4.2 states that datasets were “carefully selected” in what sounds like a case-by-case basis, probably with the goal of finding data sets on which CPNA outperforms networks trained with vanilla gradient descent methods. This process would have selection bias and surface data sets on which CPNA outperforms. I could be grateful if the authors could clarify if this was indeed the process, or if a less biased criterion was used. For example, one could have chosen data sets on which a 1-layer fully connected neural network achieves between 50% and 90% F-1. \n\n- A reader of the paper might wonder for what data sets they should use CPNA in order to train network that achieves low out-of-sample loss. I could be grateful if the authors could comment on this. Following up on the previous point: it would be great the authors could include data sets where CPNA does not outperform. \n\n- Could the authors include information on how long training takes for the experiments from Table 3? \n\n- https://openreview.net/pdf?id=HkghWScuoQ should probably be cited\n\n- https://arxiv.org/pdf/1805.01930.pdf should definitely be cited", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides empirical evidence on synthetic examples with a focus on understanding the relationship between the number of “good” local minima and number of irrelevant features. The reviewers find the problem discussed to be important. One of the reviewers has pointed out that the paper does not present deep insights and is more suitable for workshops. The authors did not provide a rebuttal, and it appears that the reviewers opinion has not changed.

The current score is clearly not sufficient to accept this paper in its current form. Due to this reason, I recommend to reject this paper. 

Decision: Reject