#
Insights into the Lottery Ticket Hypothesis and Iterative Magnitude Pruning

Tausifa Jan Saleem, Ramanjit Ahuja, Surendra Prasad, Brejesh Lall Tausifa Jan
Saleem (email<EMAIL_ADDRESS>is affiliated with the Bharti School
of Telecommunication Technology and Management, Indian Institute of Technology
Delhi. Ramanjit Ahuja (email<EMAIL_ADDRESS>was affiliated with
the Foundation for Innovation and Technology Transfer, Indian Institute of
Technology Delhi as a Research Associate at the time of accomplishing this
work. He is currently affiliated with On Semiconductors (India) as a Member of
Technical Staff. Surendra Prasad (email<EMAIL_ADDRESS>and Brejesh
Lall (email<EMAIL_ADDRESS>are affiliated with the Department of
Electrical Engg and the Bharti School of Telecommunication Technology and
Management at Indian Institute of Technology Delhi. Acknowledgement: This work
was supported by funding from IIT Delhi, Cadence Design Systems, and the
Indian National Science Academy (INSA). We would like to thank the authors of
the papers [1] and [2] for making their code available on GitHub.

###### Abstract

Lottery ticket hypothesis [1] for deep neural networks emphasizes the
importance of initialization used to re-train the sparser networks obtained
using the iterative magnitude pruning process. An explanation for why the
specific initialization proposed by the lottery ticket hypothesis tends to
work better in terms of generalization (and training) performance has been
lacking. Moreover, the underlying principles in iterative magnitude pruning,
like the pruning of smaller magnitude weights and the role of the iterative
process, lack full understanding and explanation. In this work, we attempt to
provide insights into these phenomena by empirically studying the
volume/geometry and loss landscape characteristics of the solutions obtained
at various stages of the iterative magnitude pruning process.

###### Index Terms:

Lottery Ticket Hypothesis, Iterative Magnitude Pruning, Loss Landscape.

##  I Introduction

Neural network pruning is the process of removing unnecessary weights from a
neural network [3]. This reduces the model size and the energy consumed by the
neural network model, which makes inference efficient. It has been observed
that the pruned models do not perform well without re-training, and re-
training the sparser networks from the start (with random initialization) is
difficult [4, 5]. However, Frankle and Carbin [1] demonstrated that there
exists a subnetwork, which if trained from the start, reaches the accuracy of
the original network. More formally, their hypothesis says that a randomly
initialized dense neural network contains a subnetwork that is initialized
such that—when trained from the start—it can match the test accuracy of the
original network after training for at most the same number of iterations.
This hypothesis has been named the lottery ticket hypothesis. Empirical
corroboration of the lottery ticket hypothesis consists of a procedure called
Iterative Magnitude Pruning (IMP) [1, 6]. IMP consists of the following steps:
1) randomly initialize a dense neural network and pre-train it for some number
of iterations. The weights of this pre-trained network is known as the rewind
point; 2) train the network to convergence; 3) prune a fraction of the
smallest magnitude weights from the trained network; 4) rewind the unpruned
weights to their values at the rewind point; 5) repeat steps 2-4 until a
sufficiently pruned network is obtained; 6) train the final network.

The final network is a winning ticket if it is matching, which means it trains
to the same accuracy as the dense network. IMP has been successful in
producing highly-sparse networks that are matching. But the underlying
principles like the role of specific initialization proposed by the lottery
ticket hypothesis, pruning of smaller magnitude weights, and the role of
iterative process are not fully understood.

Many research works related to the lottery ticket hypothesis have been
published since its advent to demystify the mechanisms and principles
governing it. Frankle et al. [7] studied the relationship between the
percentage of weights remaining and interpretability111Ability to understand
and explain how the network arrived at its decisions. of a network in case of
magnitude pruning. They demonstrated that pruning does not harm
interpretability until very few parameters remain in the network and there is
an accuracy drop. The authors demonstrated that the network parameters
considered superfluous for accuracy by the pruning algorithm are also
superfluous for interpretability. However, pruning does not make the network
more interpretable either. The network dissection technique given by Bau et
al. [8] was used to measure the interpretability of the pruned network. In
another work, Frankle et al. [9] demonstrated that the pruning methods that
prune at initialization (prior to training) perform better than random
pruning, but their accuracy remains smaller than the magnitude pruning after
training. They also demonstrated that randomly shuffling the weights pruned by
these techniques within each layer preserves or improves the accuracy. Frankle
et al. [10] performed instability analysis towards Stochastic Gradient Descent
(SGD) noise to explain the success and failure of IMP. They demonstrated that
IMP finds matching sub-networks only when they are stable to SGD noise (not
affected by different data orders), and this happens at initialization in
simple tasks but only after a few training iterations in complicated tasks.
That is why pre-training the dense network for a few iterations (to obtain the
rewind point) and rewinding the unpruned weights of the pruned network to
their values at the rewind point is required in IMP. However, rewinding alone
does not account for the success of IMP since randomly pruning the network and
then rewinding to the rewind point does not produce matching sub-networks
[10]. Hence, there is some information encoded in the associated pruning
procedure, in addition to the information conveyed by the specific
initialization proposed by the lottery ticket hypothesis, that leads to the
success of IMP. Larsen et al. [11] demonstrated that the number of parameters
required for training a deep neural network decreases as the initial loss
decreases. This explains why rewinding to a later point in training leads to
better accuracy. Zhang et al. [12] demonstrated the structural importance of
winning tickets by showing that pruning enlarges the convex region near a
desirable model. They also showed that the number of training samples required
for achieving zero generalization error is proportional to the number of
unpruned weights.

Rosenfeld et al. [13] formulated a scaling law that estimates the test error
when pruning with IMP. They demonstrated that the test error depends on the
size of the training dataset, depth of the network, width of the network, and
pruning level. Movva et al. [14] analyzed the effect of combining pruning
information across multiple training runs (different data orders) on accuracy-
sparsity trade-off in the case of magnitude pruning. They demonstrated that
the pruning overlap between different copies is small (not more than chance).
However, with pre-training, the overlap increased significantly. Combining the
information using intersection or union of masks performed similar to the one-
shot magnitude pruning baseline. Paul et al. [15] demonstrated that in the
pre-training phase, only a subset of data is needed to get a matching
initialization (initialization that produces a matching sub-network), and the
length of this phase can be reduced if training is carried out using easy-to-
learn examples. Jin et al. [16] demonstrated that two factors essentially
contribute to better generalization in the pruned models (obtained using IMP):
extended model training time and model size reduction. Extended model training
time improves training, and model size reduction adds regularization, which in
turn improves generalization.

The closest work to ours is the recently reported work of Paul et al. [17].
They studied the geometry of the error (test error) landscape to answer
several questions about the lottery ticket hypothesis and IMP. Their
contributions are: 1) they concluded that the pairs of IMP solutions at the
successive iterations are connected linearly with no error barrier between
them if and only if they are matching. This shows that in every IMP iteration,
the mask produced by the pruning procedure conveys information about the axial
subspace that intersects a desired linearly connected mode of a matching
sublevel set; 2) they concluded that the reason of one-shot pruning not
working well compared to iterative pruning is that pruning to higher
sparsities using one-shot is prohibited by the sharpness of the error
landscape; 3) they concluded that retraining reequilibriates the weights of
the network, i.e., finds networks with new small weights ready for further
pruning.

Our independently conducted studies have been in the domain of the loss
(training loss) landscape rather than the error (test error) landscape. We
were interested in the question: are the IMP solutions at the successive
iterations (levels) linearly connected in the loss landscape? If so, then SGD
should converge to the sparser solution by itself rather than converging to a
less sparser solution. Consider two IMP solutions: IMP solution at level
$(L-1)$ and IMP solution at level $L$. If they are linearly connected to each
other in the loss landscape, SGD at level $(L-1)$ should have directly
converged to level $L$ solution instead of converging to $(L-1)$ solution, but
obviously, this does not happen. This is a fundamental question that we
address in our work.

In this work, we attempt to provide insights about the lottery ticket
hypothesis and IMP by studying the loss landscape (not the error landscape)
characteristics and volume/geometry of the IMP solutions at different
iterations. Although training loss and test error are correlated with each
other, studying the loss landscape characteristics instead of the error
landscape makes more sense while developing an understanding of the working of
neural network models because SGD navigates through the loss landscape and not
the error landscape.
Contributions. We perform extensive experimentation on two widely used
networks, ResNet-20 and VGG-16, on a benchmark dataset, CIFAR-10. The
contributions are as follows:

  1. 1.

We demonstrate that there exist special type of minima in the loss landscape,
which generalize well but have a very small volume in the original space, and
the IMP procedure exposes such minima, which otherwise remain hidden.

  2. 2.

We demonstrate that there exists a barrier between the IMP solutions at
successive levels in the loss landscape, implying that they are not strictly
linearly connected in this scenario.

  3. 3.

We demonstrate that IMP solutions obtained using rewinding lie within the same
loss sublevel set (defined in the sequel).

  4. 4.

We provide an insight into the role played by specific initialization proposed
by the lottery ticket hypothesis.

  5. 5.

We demonstrate the role played by the iterative process in IMP, which answers
the question of why one-shot pruning does not work well (comparatively).

  6. 6.

We provide new insight into magnitude-based pruning, which answers the
question of why pruning smaller weights (weights with smaller magnitudes) is
beneficial and not the larger ones.

  7. 7.

We provide insight into why fine-tuning does not work at par with rewinding.

##  II Background Information and Problem Formulation

###  II-A Background Information

This subsection discusses the following preliminaries: lottery ticket
hypothesis, fine-tuning and rewinding, iterative pruning versus one-shot
pruning, loss landscape of a neural network, error landscape of a neural
network, loss sublevel set, and the role of volume in generalization
performance.
Lottery ticket hypothesis. Lottery ticket hypothesis postulates that neural
networks contain subnetworks that when trained from scratch reach the accuracy
of the original network in a commensurate number of epochs. This hypothesis
was proposed by Frankle and Carbin in 2018 [1]. Their assertion is supported
by the observation that IMP consistently discovers such subnetworks on small
vision tasks by rewinding the weights of the subnetwork to the $0^{th}$
iteration of the original dense network. However, IMP fails on deeper
networks. In follow-up work, Frankle et al. [6] demonstrated that in the case
of deeper networks, such subnetworks could be obtained by rewinding to
$k^{th}$ iteration instead of rewinding to $0^{th}$ iteration after pruning,
for a suitably chosen value of $k$.
Fine-tuning and rewinding. IMP consists of a number of pruning and re-training
cycles. Fine-tuning and rewinding are the two retraining strategies in IMP.
Rewinding was introduced by the lottery ticket hypothesis, while
conventionally, IMP operated with fine-tuning or rewinding with random
initialization. Fine-tuning trains the pruned network with a fixed (small)
learning rate, and the starting point for retraining with fine-tuning is the
final values of unpruned weights [4, 18]. Rewinding is of two types; weight
rewinding and learning rate rewinding. In the case of weight rewinding, the
unpruned weights are rewound to their values at the rewind point, and apart
from rewinding the weights, it also rewinds the learning rate schedule.
Learning rate rewinding has the same starting point for retraining as that of
fine-tuning and it follows the same learning rate schedule as followed by the
weight rewinding procedure. So, the difference between fine-tuning and
learning rate rewinding is the difference in their learning rates. And the
difference between learning rate rewinding and weight rewinding is the
difference in their starting points. Renda et al., [19] demonstrated that
fine-tuning does not perform as well as weight rewinding, however, learning
rate rewinding performs at par with weight rewinding or even outperforms it in
some scenarios.
Iterative pruning versus one-shot pruning. One of the crucial facets of IMP is
that the weights are pruned iteratively with intervals of retraining between
them. In contrast to this, one-shot pruning prunes all the weights in one go
to attain the desired sparsity and then retrains. It has been demonstrated in
the literature that iterative pruning always outperforms one-shot pruning [1,
19].
Loss landscape of a neural network. Neural networks are trained using feature
vectors $x_{i}$ and their corresponding labels $y_{i}$. In the training
procedure, loss function $Loss(W)$ is minimized:

$Loss(W)=\frac{1}{n}\Sigma_{i=1}^{n}l(x_{i},y_{i},W)$ (1)

where $W$ represents the network parameters, $n$ represents the number of
input data samples, and $l(x_{i},y_{i},W)$ is a function that measures the
difference between the predicted label and the actual label. The number of
parameters in neural networks is very large; hence, the neural network loss
functions reside in extremely high-dimensional spaces. The plot of training
loss ($Loss(W)$) with respect to the network parameters ($W$) is referred to
as the loss landscape.

Studying the loss landscape of neural networks is important for understanding
their behavior. The loss landscape of under-parameterized models has multiple
isolated local minima [20]. The set of solutions of over-parameterized models,
on the other hand, is generically a manifold of dimension $m-rn$ [21], where
$m$ is the number of parameters, $n$ is the number of input data samples, and
$r$ is the number of output classes. This means that the density of minima in
the loss landscape of over-parameterized models is very high, and the
optimizer converges to one of them irrespective of where it starts at.
Error landscape of a neural network. The variation in the test error of a
neural network with respect to the network parameters is referred to as the
error landscape of a neural network. It provides insights into how well the
network is performing and how sensitive it is to the changes in the network
parameters.
Loss sublevel set. Loss sublevel set $S(\epsilon)$ is the set of all points in
the weight space for which loss $Loss(W)$ is less than or equal to some
desired value $\epsilon$ [11] :

$S(\epsilon):={W\in R^{D}:Loss(W)\leq\epsilon}$ (2)

Role of volume222For our discussion here, volume refers to the volume of
minimum, not the volume of loss sublevel set. in generalization performance.
Flatness is an indicator of network performance sensitivity to parameter
perturbations. The minimum is flat if small changes to the parameters do not
cause misclassifications. On the contrary, the minimum is sharp if small
changes to the parameters cause a number of misclassifications, thereby
increasing the value of the loss function. A number of studies have focused on
establishing the relationship between the flatness/sharpness of minima and
their generalization ability. The following presents a summary of those
studies;

Hochreiter and Schmidhuber [22] explained the relationship between the
flatness of minima and their generalization ability using the Minimum
Description Length (MDL) theory. They defined a flat minimum as a region in
the weight space where the error remains approximately constant. Such a region
requires less information for representation because of its lower complexity
than a region where the error changes drastically (sharp minimum). According
to MDL theory, lower complexity models have higher generalization ability.
Chaudhari et al. [23] have shown that the local minima discovered by the
optimizers have a flat geometry for a range of deep neural network
architectures irrespective of their structures, training strategies, and the
input data. These flat regions are robust to perturbations (both data
perturbations as well as parameter perturbations) and noise in the
activations, which makes them generalize well. Keskar et al. [24] have
demonstrated that the large-batch methods are attracted towards sharp minima.
They have shown that these minima have large positive eigen values of the
Hessian (Hessian of the loss function) and do not have good generalization
ability. In contrast, small-batch methods converge to flat minima, which have
a large number of small eigen values of the Hessian and generalize well. Dinh
et al. [25] argued that the notions of flatness cannot be directly related to
the generalization performance without taking certain precautions. Their
argument is based on the following grounds: the loss function of a neural
network with weights much larger than one may seem to be flat because
parameter perturbations by one unit will have a very small consequence on the
network performance. On the contrary, in a neural network with smaller weights
than one, the same perturbation will drastically affect the network
performance, making the loss function appear sharp. Knowing that neural nets
are scale-invariant, the large-parameter network and the small-parameter
network are the same in that the large-parameter network is a rescaled version
of the small-parameter network. Thus, any discrepancies in the loss function
plots are simply the result of the difference in the scales of the networks.
Hence, it is crucial to apply perturbations in accordance with the scale of
network parameters to have a correct notion of the flatness/sharpness of
minima [2].

Huang et al. [26] demonstrated that two types of minima exist in a neural
network loss landscape. These are referred to as the so-called good minima and
bad minima. Good minima exhibit a small training loss and a small
generalization error. Bad minima, too have a small training loss but exhibit a
high generalization error. They also studied the qualitative difference in the
loss landscape around these minima and observed that the decision boundaries
of good minima have wide margins333Distance between the class boundary and the
data. while the decision boundaries of bad minima have very narrow margins.
Huang et al. [26] also illustrated that the good minima reside in wide
basins444Set of points in the neighborhood of a minimum whose loss value is
smaller than some cutoff value. that exhibit a large volume in the parameter
space, while the bad minima reside in narrow basins that exhibit a much
smaller volume. A larger volume also implies a higher probability of hitting
the minima by SGD. Volumes of the minima are, therefore, good indicators of
their robustness and can provide useful insights [26].

Calculation of the volume of these basins is, however, computationally
intractable because the loss function lies in an extremely high-dimensional
space. Huang et al. [26] used Monte-Carlo integration to approximate the
volume of these basins. Using their method, the $n$-dimensional volume of the
basin ($V$) is calculated as:

$V={\omega_{n}E_{\phi}[r^{n}(\phi)]}$ (3)

where $r(\phi)$ represents the radius of the basin in the direction of the
unit vector $\phi$ and $E$ represents the expected value. This expected value
is estimated by calculating $r(\phi)$ along a large number of random
directions. $\omega_{n}$ is the volume of the unit-$n$ ball and is given as;
$\omega_{n}=(\pi^{n/2})/\Gamma(1+n/2)$, where $\Gamma$ represents the Euler’s
Gamma function. However, this method of volume calculation is computationally
expensive. Another approximation of basin volume was given by Wu et al.[27].
They demonstrated that the product of top-$k$ positive eigen values
($\lambda$) of the Hessian could be used to approximate the inverse volume of
these basins. More specifically, the inverse volume of the basin
($V^{{}^{\prime}}$) can be approximately expressed as:

$V^{{}^{\prime}}(k):={\Sigma_{i=1}^{k}Log(\lambda_{i})}$ (4)

This is because a large basin implies that the valley around the minimum is
flat, which is associated with smaller eigen values, and vice-versa.

###  II-B Definitions and Notations.

Sparse subnetworks: Given a dense network with weights $W$
($W\in\mathbb{R}^{D}$), a sparse subnetwork has weights $m\odot W$, where
$m\in$ {${0,1}\\}^{D}$ is a binary mask and $\odot$ is the element-wise
product. The sparsity of a mask $m$, $S(m)$ is the fraction of zeros in the
mask.
Notation for IMP solution at level $L$: We represent the IMP solution
(minimum) at level $L$ by $W_{(L)}^{(min\\_(L))}$, weights of the dense
network at initialization by $W^{(init)}$ and weights of the dense network at
rewind-point by $W^{(rewind\\_point)}$. Note that all these weights are
$D$-dimensional.
Projection of level $L$ solution on level $(L+1)$: Let
$W^{Pr{(min\\_(L))}}_{(L+1)}$ represent the projection of level $L$ solution
on level $(L+1)$. It is obtained as
$W^{Pr{(min\\_(L))}}_{(L+1)}$=$m_{(L+1)}\odot W_{(L)}^{(min\\_(L))}$, where
$m_{(L+1)}$ represents the pruning mask at level $(L+1)$. For example, the
projection of level $0$ solution on level $1$ will be represented as
$W^{Pr{(min\\_(0))}}_{(1)}$. Note that $S(m_{(L+1)})>S(m_{(L)})$.
Reverse Projection of level $(L+1)$ solution on level $(L)$: Let
$W^{RPr{(min\\_(L+1))}}_{(L)}$ represent the reverse projection of level
$(L+1)$ solution on level $(L)$. It is obtained as;
$W^{RPr{(min\\_(L+1))}}_{(L)}$=$m_{(L)}\odot W_{(L+1)}^{(min\\_(L+1))}$, where
$m_{(L)}$ represents the pruning mask at level $(L)$. For example, the reverse
projection of level $1$ solution on level $0$ will be represented as
$W^{RPr{(min\\_(1))}}_{(0)}$.

###  II-C Problem Statement and Questions of Interest.

The primary objective of this study is to develop a deeper insight into the
nature of the loss landscape, especially regarding the distribution and
characteristics of its minima and the behavior of the SGD and of the solutions
obtained using IMP and rewinding at various levels. The specific questions
that can lead to better insight are as follows:
1) Why are these solutions (at different levels) not discoverable directly?
2) What is the role played by specific initialization proposed by the lottery
ticket hypothesis?
3) What is the role played by the iterative process in IMP?
4) Why is the pruning of smaller weights beneficial and not the larger ones?
5) Why fine-tuning does not work at par with rewinding?
Our experiments reported below have been conducted to elicit accurate answers
to these questions.

##  III Methodology

In this section, we limit ourselves to a top-level description of the
experiments conducted for the study. Some of the finer details are relegated
to Appendix I.

We perform experimentation on two widely used networks, ResNet-20 and VGG-16,
on a benchmark dataset, CIFAR-10. We use iterative magnitude pruning with
weight rewinding (IMP-WR) and run $10$ iterations of IMP in the case of
ResNet-20 and $12$ iterations of IMP in the case of VGG-16. We prune 20% of
the smallest magnitude weights in each iteration. The unpruned weights are
rewound to their values at $2000^{th}$ training step of the original dense
network in each iteration. The main part of the manuscript contains the
results obtained on ResNet-20. The corresponding results for VGG-16 are given
in Appendix II. For an initial and quick appreciation, a plot of training loss
and test accuracy at different levels of IMP-WR in the case of ResNet-20 is
presented in Fig. 1.

Figure 1: Training loss and test accuracy at different levels of IMP-WR. Left:
Training loss. Right: Test accuracy.

It is also useful to compare the performance of IMP-WR with other strategies
that may either produce networks with a similar structure as that produced
with IMP-WR but are initialized differently or produce networks with the same
sparsity but different structures. To this end, we apply techniques like one-
shot pruning, fine-tuning, random initialization of the pruned network, and
random pruning on the aforementioned network. The details of these techniques
are summarized below:
One-shot pruned network is obtained by pruning the weights of the trained
dense network $W_{(0)}^{(min\\_(0))}$ based on magnitude pruning in one go to
attain the desired sparsity555Same sparsity as that of
$W_{(10)}^{(min\\_(10))}$ in case of ResNet-20, and same sparsity as that of
$W_{(12)}^{(min\\_(12))}$ in the case of VGG-16. and then rewinding the
unpruned weights to their values at $W^{(rewind\\_point)}$ and retraining. We
represent the solution obtained using one-shot pruning by $W^{(one\\_shot)}$.
Fine-tuned network is obtained by pruning $20\%$ smallest magnitude weights
from $W_{(9)}^{(min\\_(9))}$ in case of ResNet-20 and by pruning $40\%$
smallest magnitude weights from $W_{(11)}^{(min\\_(11))}$ in the case of
VGG-16 and then re-training the unpruned weights (without rewinding) with a
learning rate of $0.001$ for $40$ epochs. We represent the solution obtained
using fine-tuning by $W^{(FT)}$.
Randomly initialized pruned network is obtained by pruning $20\%$ smallest
magnitude weights from $W_{(9)}^{(min\\_(9))}$ in case of ResNet-20 and by
pruning $40\%$ smallest magnitude weights from $W_{(11)}^{(min\\_(11))}$ in
the case of VGG-16 and then randomly initializing the unpruned weights and
retraining. We call this network Randomly Initialized Pruned Network and
represent the solution by $W^{(RIPN)}$.
Randomly pruned network is obtained by randomly pruning $20\%$ weights from
$W_{(9)}^{(min\\_(9))}$ and then rewinding and retraining in case of
ResNet-20. We call this network Randomly Pruned Network and represent the
solution by $W^{(RPN\\_1)}$. We also consider another randomly pruned network
in the case of ResNet-20 by randomly pruning the weights of
$W_{(0)}^{(min\\_(0))}$ in one go to attain the desired sparsity and then
rewinding and re-training. We represent the solution obtained in this manner
by $W^{(RPN\\_2)}$. Note that the only difference between $W^{(RPN\\_2)}$ and
$W^{(one\\_shot)}$ is that while obtaining $W^{(RPN\\_2)}$, the weights of
$W_{(0)}^{(min\\_(0))}$ are pruned randomly whereas while obtaining
$W^{(one\\_shot)}$, the weights of $W_{(0)}^{(min\\_(0))}$ are pruned using
magnitude based pruning.

In the case of VGG-16, a randomly pruned network has been obtained by randomly
pruning $40\%$ weights from $W_{(11)}^{(min\\_(11))}$ and then rewinding and
retraining. We represent the solution obtained in the aforementioned manner by
$W^{(RPN)}$.

A comparison of training loss and test accuracy between
$W_{(10)}^{(min\\_(10))}$, $W^{(one\\_shot)}$, $W^{(FT)}$, $W^{(RIPN)}$,
$W^{(RPN\\_1)}$ and $W^{(RPN\\_2)}$ in case of ResNet-20 presented in Fig. 2
shows that $W_{(10)}^{(min\\_(10))}$ outperforms the other solutions. To
explain the reason behind this, we study the loss landscape of these networks.

Figure 2: Comparison of training loss and test accuracy between
$W_{(10)}^{(min\\_(10))}$, $W^{(one\\_shot)}$, $W^{(FT)}$, $W^{(RIPN)}$,
$W^{(RPN\\_1)}$ and $W^{(RPN\\_2)}$. Left: Training loss. Right: Test
accuracy.

##  IV Results and Findings

In this section, we summarize our major findings based on extensive
experimentation. We also provide a logical rationale/explanation for the
observed behavior.

###  IV-A Result 1: Good Minima with Small volume exist.

Huang et al. [26] had proposed that there exist two kinds of minima in a
neural network loss landscape. The so-called good minima have a low training
loss and a large volume associated with their basins. These tend to have good
generalization performance. Then there are the bad minima, which too have a
low training loss but have a small volume and do not exhibit good
generalization performance.

We demonstrate that there also exist another kind of minima which have good
generalization performance but have a (relatively) small volume. This implies
that volume is not the only criterion for generalization performance; there is
more to it. A careful experimental study leads us to hypothesize that the
small volume of these minima is due to very sharp curvature in certain
dimensions, but the coefficients in these dimensions are zero. Their volume
measure tends to increase when these inferior dimensions are removed (possibly
via pruning at another point) but is small when considered in the original
space. This makes these minima almost undiscoverable by SGD in the original
space but can be readily discovered in the pruned space. This is the main
result of our study.

Consider the two IMP solutions, that at level $(L-1)$, denoted by
$W_{(L-1)}^{(min\\_(L-1))}$ and that at level $(L)$, $W_{(L)}^{(min\\_(L))}$.
$W_{(L-1)}^{(min\\_(L-1))}$ is a baseline for $W_{(L)}^{(min\\_(L))}$ because
the pruning mask for level $L$ is determined by $W_{(L-1)}^{(min\\_(L-1))}$. A
comparison of the euclidean distance between $W^{Pr{(min\\_(L-1))}}_{(L)}$ and
$W^{Pr{(rewind\\_point)}}_{(L)}$, and the euclidean distance between
$W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(rewind\\_point)}}_{(L)}$ given in Fig. 3
shows that for all $L$ except $2$ and $3$, $W^{Pr{(min\\_(L-1))}}_{(L)}$ is
closer to $W^{Pr{(rewind\\_point)}}_{(L)}$ than $W_{(L)}^{(min\\_(L))}$.

Figure 3: Distance from $W^{Pr{(rewind\\_point)}}_{(L)}$ to
$W^{Pr{(min\\_(L-1))}}_{(L)}$ and to $W_{(L)}^{(min\\_(L))}$ for $L$ ranging
from $1$ to $10$.

Despite this at level $(L)$, SGD converges to $W_{(L)}^{(min\\_(L))}$ and not
to $W^{Pr{(min\\_(L-1))}}_{(L)}$.

In order to find the underlying reason, we plot the trajectory of SGD for
level $L$ and that for level $(L-1)$ projected on level $L$ in Fig. 4.

Figure 4: Comparison of logarithm of training loss versus epoch between level
$(L)$ and level $(L-1)$ projected on level $(L)$.

It is evident from the figure that the trajectory for level $(L)$ is steeper
than for level $(L-1)$ projected on level $L$. This makes SGD converge to
$W_{(L)}^{(min\\_(L))}$ and not to $W^{Pr{(min\\_(L-1))}}_{(L)}$.

Further, if we compare the volume of basins around $W_{(L)}^{(min\\_(L))}$ and
$W^{Pr{(min\\_(L-1))}}_{(L)}$ by calculating the product of top-$100$ positive
eigen values of the Hessian (of the loss function), the volume of basin around
$W_{(L)}^{(min\\_(L))}$ is seen to be larger than the volume of the basin
around $W^{Pr{(min\\_(L-1))}}_{(L)}$. This is demonstrated in Fig. 5 and Table
I.

Figure 5: Comparison of top-100 positive eigen values of the Hessian at $W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(min\\_(L-1))}}_{(L)}$ for $L$ ranging from $1$ to $10$. The figure shows that the eigen values of the Hessian at $W_{(L)}^{(min\\_(L))}$ are smaller than that at $W^{Pr{(min\\_(L-1))}}_{(L)}$. And smaller the eigen values, the smaller their product will be, and the larger would be the volume of the basin around the minimum. TABLE I: Comparison of Maximum eigen value, $\lambda_{max}$ and inverse volume of basin, $V^{{}^{\prime}}(100)$ at $W^{Pr{(min\\_(L-1))}}_{(L)}$ and $W_{(L)}^{(min\\_(L))}$. $L$ |  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---|---
1 |  $W^{Pr{(min\\_(0))}}_{(1)}$ |  1416.091 |  409.242
$W_{(1)}^{(min\\_(1))}$ |  1590.829 |  407.417
2 |  $W^{Pr{(min\\_(1))}}_{(2)}$ |  1512.426 |  402.678
$W_{(2)}^{(min\\_(2))}$ |  1349.951 |  399.680
3 |  $W^{Pr{(min\\_(2))}}_{(3)}$ |  1401.285 |  400.855
$W_{(3)}^{(min\\_(3))}$ |  1194.164 |  386.948
4 |  $W^{Pr{(min\\_(3))}}_{(4)}$ |  1266.607 |  392.829
$W_{(4)}^{(min\\_(4))}$ |  1129.884 |  375.590
5 |  $W^{Pr{(min\\_(4))}}_{(5)}$ |  17779.826 |  417.984
$W_{(5)}^{(min\\_(5))}$ |  1094.078 |  372.753
6 |  $W^{Pr{(min\\_(5))}}_{(6)}$ |  1590.785 |  420.431
$W_{(6)}^{(min\\_(6))}$ |  1065.735 |  373.472
7 |  $W^{Pr{(min\\_(6))}}_{(7)}$ |  2368.243 |  446.758
$W_{(7)}^{(min\\_(7))}$ |  1065.881 |  375.401
8 |  $W^{Pr{(min\\_(7))}}_{(8)}$ |  1882.278 |  432.505
$W_{(8)}^{(min\\_(8))}$ |  1200.277 |  382.051
9 |  $W^{Pr{(min\\_(8))}}_{(9)}$ |  3753.991 |  488.004
$W_{(9)}^{(min\\_(9))}$ |  1334.666 |  394.166
10 |  $W^{Pr{(min\\_(9))}}_{(10)}$ |  5426.848 |  525.621
$W_{(10)}^{(min\\_(10))}$ |  1575.910 |  408.810

We also confirmed this by using the method given by Huang et al. [26] to
calculate the radii of the basin. We calculated the radii of the basin along
$500$ different random directions around $W_{(10)}^{(min\\_(10))}$ and
$W^{Pr{(min\\_(9))}}_{(10)}$. The radius of the basin in each direction is
calculated by choosing a suitable cut-off value in proximity to the loss
values at the minima (cut-off=$2\times max\\{$Loss at
$W_{(10)}^{(min\\_(10))}$, Loss at $W^{Pr{(min\\_(9))}}_{(10)}$$\\}$). This
normalized cut-off value turns out to be $1.0$ in this case. A comparison of
radii of the basin, around $W_{(10)}^{(min\\_(10))}$ and
$W^{Pr{(min\\_(9))}}_{(10)}$ is given in Fig. 6 and the average radii of
basins around $W_{(10)}^{(min\\_(10))}$ and $W^{Pr{(min\\_(9))}}_{(10)}$ are
given in Table II. It is clear from the figure and the table that the average
radius of the basin around $W_{(10)}^{(min\\_(10))}$ is larger than that
around $W^{Pr{(min\\_(9))}}_{(10)}$. Since the neural network loss functions
lie in high-dimensional spaces, even a small difference in the radii of basins
around minima translates to exponentially large disparities in the volume of
their surrounding basins.

Figure 6: Comparison of radii of basin along $500$ random directions around $W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(min\\_(L-1))}}_{(L)}$ for $L=10$. The x-axis in the above histograms represents the radius of the basin, and the y-axis represents the number of random directions. Left: Radii of basin around $W_{(10)}^{(min\\_(10))}$. Right: Radii of basin around $W^{Pr{(min\\_(9))}}_{(10)}$.  TABLE II: Comparison of Average Radius of Basin around $W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(min\\_(L-1))}}_{(L)}$ for $L=10$.  Solution |  Average Radius of Basin
---|---
$W_{(10)}^{(min\\_(10))}$ |  0.232314
$W^{Pr{(min\\_(9))}}_{(10)}$ |  0.183428

Next, if we consider the reverse projection of level $(L)$ solution on level
$(L-1)$, $W^{RPr{(min\\_(L))}}_{(L-1)}$ and the level $(L-1)$ solution,
$W_{(L-1)}^{(min\\_(L-1))}$, the volume of basin around
$W_{(L-1)}^{(min\\_(L-1))}$ is seen to be larger than the volume of basin
around $W^{RPr{(min\\_(L))}}_{(L-1)}$. This is demonstrated in Fig. 7 and
Table III.

Figure 7: Comparison of top-100 positive eigen values of the Hessian at
$W_{(L-1)}^{(min\\_(L-1))}$ and $W^{RPr{(min\\_(L))}}_{(L-1)}$ for $L$ ranging
from $1$ to $10$. The figure shows that the eigen values of the Hessian at
$W_{(L-1)}^{(min\\_(L-1))}$ are smaller than that at
$W^{RPr{(min\\_(L))}}_{(L-1)}$.

And this explains why SGD does not converge to $W^{RPr{(min\\_(L))}}_{(L-1)}$
at level $(L-1)$.

TABLE III: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{RPr{(min\\_(L))}}_{(L-1)}$ and $W_{(L-1)}^{(min\\_(L-1))}$. $L$ |  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---|---
1 |  $W^{RPr{(min\\_(1))}}_{(0)}$ |  1742.268 |  418.034
$W_{(0)}^{(min\\_(0))}$ |  1575.277 |  415.42
2 |  $W^{RPr{(min\\_(2))}}_{(1)}$ |  1572.214 |  415.826
$W_{(1)}^{(min\\_(1))}$ |  1590.829 |  407.417
3 |  $W^{RPr{(min\\_(3))}}_{(2)}$ |  1496.211 |  403.674
$W_{(2)}^{(min\\_(2))}$ |  1349.951 |  399.68
4 |  $W^{RPr{(min\\_(4))}}_{(3)}$ |  1326.676 |  394.347
$W_{(3)}^{(min\\_(3))}$ |  1194.164 |  386.948
5 |  $W^{RPr{(min\\_(5))}}_{(4)}$ |  1291.157 |  391.093
$W_{(4)}^{(min\\_(4))}$ |  1129.884 |  375.59
6 |  $W^{RPr{(min\\_(6))}}_{(5)}$ |  1316.275 |  391.471
$W_{(5)}^{(min\\_(5))}$ |  1094.078 |  372.753
7 |  $W^{RPr{(min\\_(7))}}_{(6)}$ |  1418.483 |  394.086
$W_{(6)}^{(min\\_(6))}$ |  1065.735 |  373.472
8 |  $W^{RPr{(min\\_(8))}}_{(7)}$ |  1464.987 |  398.559
$W_{(7)}^{(min\\_(7))}$ |  1065.881 |  375.401
9 |  $W^{RPr{(min\\_(9))}}_{(8)}$ |  1619.784 |  411.997
$W_{(8)}^{(min\\_(8))}$ |  1200.277 |  382.051
10 |  $W^{RPr{(min\\_(10))}}_{(9)}$ |  1913.214 |  427.475
$W_{(9)}^{(min\\_(9))}$ |  1334.66 |  394.166

This is confirmed by a comparison of radii of the basin around
$W_{(9)}^{(min\\_(9))}$ and $W^{RPr{(min\\_(10))}}_{(9)}$ using the method
given by Huang et al. [26]. Here, the normalized cut-off value for the radii
of the basins turns out to be $0.1$. A comparison of radii of the basin around
$W_{(9)}^{(min\\_(9))}$ and $W^{RPr{(min\\_(10))}}_{(9)}$ is given in Fig. 8,
and the average radii of the two basins are given in Table IV. It is clear
from the figure and the table that the average radius of the basin for
$W_{(9)}^{(min\\_(9))}$ is larger than that for $W^{RPr{(min\\_(10))}}_{(9)}$.

To sum up the discussion above, SGD converges to $W_{(L)}^{(min\\_(L))}$ at
level $(L)$ instead of $W^{Pr{(min\\_(L-1))}}_{(L)}$ because the volume of the
basin around $W_{(L)}^{(min\\_(L))}$ is much larger than the volume of the
basin around $W^{Pr{(min\\_(L-1))}}_{(L)}$, and the path to
$W_{(L)}^{(min\\_(L))}$ is steeper than the path to
$W^{Pr{(min\\_(L-1))}}_{(L)}$. However, in the $(L-1)$ space, the volume of
the basin around $W^{RPr{(min\\_(L))}}_{(L-1)}$ is much smaller than the
volume of basin around $W_{(L-1)}^{(min\\_(L-1))}$.

Figure 8: Comparison of radii of basin along $500$ random directions around $W_{(L-1)}^{(min\\_(L-1))}$ and $W^{RPr{(min\\_(L))}}_{(L-1)}$ for $L=10$. The x-axis in the above histograms represents the radius of the basin, and the y-axis represents the number of random directions. Left: Radii of basin around $W_{(9)}^{(min\\_(9))}$. Right: Radii of basin around $W^{RPr{(min\\_(10))}}_{(9)}$. TABLE IV: Comparison of Average Radii of Basin around $W_{(L-1)}^{(min\\_(L-1))}$ and $W^{RPr{(min\\_(L))}}_{(L-1)}$ for $L=10$. Solution |  Average Radius of Basin
---|---
$W_{(9)}^{(min\\_(9))}$ |  0.091809
$W^{RPr{(min\\_(10))}}_{(9)}$ |  0.074714

###  IV-B Result 2: There exists a barrier between IMP solutions at successive
levels in the loss landscape.

One interpretation of the previous result would clearly be that IMP solutions
at different levels are distinct minima. In order to test this hypothesis more
definitively, we examine whether these are separated by distinct barriers in
the loss landscape. If this was not the case, SGD should converge to a sparser
solution in the first place and would not stop at a less sparse solution.
Evidence for our hypothesis is presented in Fig. 9. It gives the training loss
along a straight line connecting $W^{(min\\_(L-1))}_{(L-1)}$ and
$W^{(min\\_(L))}_{(L)}$. The barriers between successive minima are clearly
visible. Thus, at least in the loss landscape, the IMP solutions at successive
levels are not linearly connected, unlike the corresponding claim by [17] in
the test error landscape. The implication is that these loss barriers are
large enough to prevent SGD from crossing over and small enough to have almost
similar generalization performance all over the region between these
solutions.

Figure 9: Training Loss along a straight line connecting
$W^{(min\\_(L-1))}_{(L-1)}$ and $W^{(min\\_(L))}_{(L)}$. The x-axis represents
the interpolation co-efficient $\alpha$. Each plot depicts the training loss
at $501$ points between $W^{(min\\_(L-1))}_{(L-1)}$ and
$W^{(min\\_(L))}_{(L)}$.

###  IV-C Result 3: IMP solutions obtained using rewinding lie within the same
loss sublevel set.

Any random initialization of a dense neural network makes SGD converge to a
good minimum. This can be ascribed to the well-understood fact [26] that the
density of good minima in such scenarios is very high. However, in sparse
subspaces, the density of such minima is much smaller. If we consider starting
from a random point in such subspaces, the solution would not be as good as we
get with rewinding, as is observed in our experiments.

We also hypothesize that all the IMP solutions obtained using rewinding lie
within the same loss sublevel set as that of the original dense network,
whereas random initialization of the pruned network takes SGD out of that
sublevel set. Fig. 10 presents the evidence for our claim. The figure clearly
shows that all the IMP solutions ($W^{(min\\_(0))}_{(0)}$ to
$W^{(min\\_(10))}_{(10)}$) lie within the same connected loss sublevel set
(dark green region). However, $W^{(RIPN)}$ lies outside the sublevel set.
Similarly, random pruning of a large number of weights also takes SGD outside
the sublevel set. It is interesting to see that $W^{(one\\_shot)}$ also lies
in the same sublevel set as the IMP solutions; however, $W^{(RPN\\_2)}$ lies
outside the sublevel set. In other words, a randomly pruned network obtained
by pruning a large number of parameters does not yield an equally good
solution as that of the network obtained with magnitude based pruning, as it
is not seen to lie in the same sublevel set.

Figure 10: Training loss at and around the neighborhood of the points of
interest. The plot shows multiple loss sublevel sets. However, all the IMP-WR
solutions lie within the same sublevel set.

This can be further confirmed by calculating the euclidean distances and
cosine similarities (angular distances) between different points of interest.
Fig. 11 shows the euclidean distance between different points of interest, and
Fig. 12 gives the cosine similarity between different points of interest.

Figure 11: Euclidean distance between different points of interest. Left:
Euclidean distance between IMP solutions at different levels. Right: Euclidean
distance of $W^{(RIPN)}$, $W^{(RPN\\_1)}$, $W^{(RPN\\_2)}$, $W^{(FT)}$ and
$W^{(one\\_shot)}$ with $W^{(min\\_(0))}_{(0)}$, $W^{(min\\_(9))}_{(9)}$ and
$W^{(min\\_(10))}_{(10)}$ .

Figure 12: Cosine similarity between different points of interest. Left:
Cosine similarity between IMP solutions at different levels. Right: Cosine
similarity of $W^{(RIPN)}$, $W^{(RPN\\_1)}$, $W^{(RPN\\_2)}$, $W^{(FT)}$ and
$W^{(one\\_shot)}$ with $W^{(min\\_(0))}_{(0)}$, $W^{(min\\_(9))}_{(9)}$ and
$W^{(min\\_(10))}_{(10)}$ .

It is apparent from these figures that the euclidean distance between IMP
solutions is smaller than the euclidean distance of $W^{(RIPN)}$ with
$W^{(min\\_(9))}_{(9)}$ and $W^{(min\\_(10))}_{(10)}$. Similarly, the cosine
similarity between IMP solutions is greater than the cosine similarity of
$W^{(RIPN)}$ with $W^{(min\\_(9))}_{(9)}$ and $W^{(min\\_(10))}_{(10)}$. Also
the euclidean distance between $W^{(min\\_(0))}_{(0)}$ and $W^{(one\\_shot)}$
is smaller than the euclidean distance between $W^{(min\\_(0))}_{(0)}$ and
$W^{(RPN\\_2)}$, while the cosine similarity between $W^{(min\\_(0))}_{(0)}$
and $W^{(one\\_shot)}$ is greater than the cosine similarity of
$W^{(min\\_(0))}_{(0)}$ with $W^{(RPN\\_2)}$. This further buttresses the
claim.

###  IV-D Result 4: Why does the initialization proposed by the lottery ticket
hypothesis work well?

The above results also provide a strong clue to the positive role of the
initialization proposed by the lottery ticket hypothesis in finding good
minima in the sparser weight space. As seen so far, pruning out the smaller
weights leads to a new minimum or a saddle point with a slightly larger
training loss value and a smaller volume. Retraining from this point via
learning rate rewinding or from a point in close proximity (via weight
rewinding) leads SGD to converge to a new minimum, which has a larger volume
(compared to the earlier minimum) and a lower training loss. This minimum was
not discoverable earlier since it spanned some dimensions where the loss
function was steeply increasing and therefore, had an overall smaller volume,
and pruning out these dimensions exposed this minimum to the SGD. Hence, the
starting minimum acts as a baseline, avoidance of which leads to a better
minimum. Choosing any other initialization point places the SGD at a point
outside the loss sublevel set and there is no guarantee of finding a better
minimum. Fig. 13 presents the training loss along a straight line connecting
$W^{(min\\_(9))}_{(9)}$ (baseline for $W^{(RIPN)}$) and $W^{(RIPN)}$.

Figure 13: Training loss along a straight line between $W^{(min\\_(9))}_{(9)}$
and $W^{(RIPN)}$.

The figure shows a significant barrier between the two points, demonstrating
clearly that these two points lie in different loss sublevel sets.

Further, a comparison of top-100 positive eigen values of the Hessian at
$W^{(RIPN)}$ and $W^{(min\\_(10))}_{(10)}$ (Fig. 14) shows that $W^{(RIPN)}$
has larger eigen values than $W^{(min\\_(10))}_{(10)}$, which indicates a
smaller volume for the basin around $W^{(RIPN)}$ (Table V).

Figure 14: Comparison of top-100 positive eigen values of the Hessian at $W^{(RIPN)}$ and $W^{(min\\_(10))}_{(10)}$.  TABLE V: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(RIPN)}$ and $W^{(min-(10))}_{(10)}$. Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---
$W^{(RIPN)}$ |  6271.873 |  497.099
$W^{(min\\_(10))}_{(10)}$ |  1575.910 |  408.810

Hence, random initialization of a pruned network takes SGD out of the sublevel
set, and after retraining, converges to a minimum with a smaller volume. The
importance of initialization proposed by the lottery ticket hypothesis,
therefore, becomes quite apparent.

###  IV-E Result 5: Why do we need the Iterative Process, and why does one-
shot pruning not work as well?

At each step in the iterative process via the magnitude pruning, we remove
dimensions with smaller weights. This increases the loss of the minimum
arrived at in the previous step and decreases its volume measure. We then
rewind the weights and start looking for an alternate solution in the vicinity
of this minimum. As explained and shown earlier, the new (potentially better)
minimum that is now exposed to SGD has a larger volume and lower training loss
than the earlier pruned minimum. Thus, the pruned minimum acts as a baseline
for the minimum to be found in the next step. If too many weights are pruned
out in a step, it leads to a bigger increase in the training loss and a bigger
decrease in volume, thus lowering the baseline for the next solution. If too
small a number of weights are pruned out in a step, we risk returning to the
same pruned minimum, thus not offering any improvement. One-shot pruning
removes too many weights and therefore, has inferior performance.

A comparison of top-100 positive eigen values of the Hessian between
$W^{(one\\_shot)}$ and $W^{(min\\_(10))}_{(10)}$ (Fig. 15) shows that
$W^{(one\\_shot)}$ has larger eigen values than $W^{(min\\_(10))}_{(10)}$,
which implies a smaller volume for the basin around $W^{(one\\_shot)}$ (Table
VI). This brings out and confirms the importance of the iterative process in
pruning.

Figure 15: Comparison of top-100 positive eigen values of the Hessian at $W^{(one\\_shot)}$ and $W^{(min\\_(10))}_{(10)}$.  TABLE VI: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(one\\_shot)}$ and $W^{(min\\_(10))}_{(10)}$ Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---
$W^{(one\\_shot)}$ |  2944.881 |  450.409
$W^{(min\\_(10))}_{(10)}$ |  1575.910 |  408.810

###  IV-F Result 6: What happens when you prune the smaller weights?

Finding the weights whose removal causes a minimum increase in the loss
function value is a combinatorial problem, and searching for such weights in a
combinatorial space is impractical due to the massive number of parameters in
a neural network. But somehow, the magnitude based pruning algorithm finds
such weights. Le cun et al. [28] proposed an explanation for this based on
approximating the loss function by a $2nd$ order Taylor series expansion:

$Loss({W_{pruned}})=Loss({W})+{(W_{pruned}-W)^{T}}\frac{\partial
Loss}{\partial{W}}_{{W}={W}}+{(W_{pruned}-W)^{T}}\frac{\partial^{2}Loss}{\partial{W}^{2}}{(W_{pruned}-W)}$
(5)

where $W$ represents the weights of a dense network and $W_{pruned}$
represents the weights of a pruned network. To simplify the explanation, it is
assumed that the loss function is smooth (which may not be true in reality due
to the presence of non-linearity induced by ReLU). It is also assumed that the
Hessian of the loss function is a diagonal matrix. Calculating the actual
Hessian is too complex, and this simplification works well in practice.

Pruning out the smallest components in the weight vector ${W}$ results in only
a small increase in the loss value. Pruning out the larger weights tends to
bring about a bigger increase in the loss value since it makes the vector
${(W_{pruned}-W)}$ have a larger magnitude (norm). This can invalidate the
second-order approximation given in Eq. $5$, since, in general, the loss
function will not be a smooth one, and may have several points of inflection
in the neighborhood.

We hypothesize that pruning larger magnitude weights either takes SGD out of
the sublevel set and/or reduces the quality of the baseline minimum so
drastically that after re-training, it converges to a minimum with inferior
performance. This is corroborated when we compare the pruning of smaller
magnitude weights against slightly larger ones. The volume of minimum in the
latter case is generally reduced by a great deal, as seen in Fig. 16. This
also means that the directions with smaller weights do not have the flattest
profile; otherwise, the volume reduction should have been larger in the
earlier case than the latter one.

Figure 16: Comparison of top-$100$ positive eigen values of the Hessian at the
minimum obtained by pruning smaller magnitude weights and at the minimum
obtained by pruning slightly larger weights. Left: Weights are pruned from
$W^{(min\\_(0))}_{(0)}$. Right: Weights are pruned from
$W^{(min\\_(3))}_{(3)}$.

Randomly pruning a large number of weights also has a similar effect in that
it may lead SGD to a position outside the sublevel set region, so that even
re-training with weight rewinding cannot bring the network back to the
sublevel set. Fig. 17 presents the training loss along a straight line
connecting $W^{(min\\_(0))}_{(0)}$ and $W^{(one\\_shot)}$, and
$W^{(min\\_(0))}_{(0)}$ (baseline for $W^{(RPN\\_2)}$) and $W^{(RPN\\_2)}$.

Figure 17: Left: Training Loss along a straight connecting
$W^{(min\\_(0))}_{(0)}$ and $W^{(one\\_shot)}$. Right: Training Loss along a
straight connecting $W^{(min\\_(0))}_{(0)}$ and $W^{(RPN\\_2)}$.

The figure shows a small barrier between $W^{(min\\_(0))}_{(0)}$ and
$W^{(one\\_shot)}$, and a huge barrier between $W^{(min\\_(0))}_{(0)}$ and
$W^{(RPN\\_2)}$, which again demonstrates that $W^{(min\\_(0))}_{(0)}$ and
$W^{(one\\_shot)}$ lie in the same sublevel set, while $W^{(min\\_(0))}_{(0)}$
and $W^{(RPN\\_2)}$ lie in different sublevel sets.

A comparison of top-100 positive eigen values of Hessians at
$W^{(one\\_shot)}$ and $W^{(RPN\\_2)}$ is given in Fig. 18.

Figure 18: Comparison of top-100 positive eigen values of the Hessian at
$W^{(one\\_shot)}$ and $W^{(RPN\\_2)}$.

It can be observed from the figure that $W^{(RPN\\_2)}$ has larger eigen
values of Hessian than that at $W^{(one\\_shot)}$, which implies a smaller
volume for the basin around $W^{(RPN\\_2)}$ (Table VII).

TABLE VII: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(RPN\\_2)}$ and $W^{(one\\_shot)}$.  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---
$W^{(RPN\\_2)}$ |  5635.883 |  487.644
$W^{(one\\_shot)}$ |  2944.881 |  450.409

This demonstrates our contention that random pruning of a large number of
weights can take the SGD out of the sublevel set, and after retraining,
converge to a minimum with a smaller volume.

Fig. 19 presents a training loss along a straight line joining
$W^{(min\\_(9))}_{(9)}$ and $W^{(RPN\\_1)}$. The figure shows a small barrier
between $W^{(min\\_(9))}_{(9)}$ and $W^{(RPN\\_1)}$, indicating that they lie
in the same sublevel set. However, the volume of the basin around
$W^{(RPN\\_1)}$ is smaller than the volume of the basin around
$W^{(min\\_(10))}_{(10)}$. This is illustrated in Fig. 20 and Table VIII.

Figure 19: Training Loss along a straight line between $W^{(min\\_(9))}_{(9)}$ and $W^{(RPN\\_1)}$.  Figure 20: Comparison of top-100 positive eigen values of the Hessian at $W^{(RPN\\_1)}$ and $W^{(min\\_(10))}_{(10)}$. TABLE VIII: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(RPN\\_1)}$ and $W^{(min\\_(10))}_{(10)}$.  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---
$W^{(RPN\\_1)}$ |  2100.56 |  435.624
$W^{(min\\_(10))}_{(10)}$ |  1575.91 |  408.81

This showcases the importance of pruning strategy in neural network pruning.
In general, given that at each level, IMP finds solutions in the neighborhood
of the dense network minimum, an arbitrary perturbation in the pruning process
can lose us this advantage.

###  IV-G Result 7: Why fine-tuning doesn’t perform at par with rewinding?

Fine-tuning perturbs the pruned baseline by a small amount; hence, SGD more
likely stays near the baseline minimum and does not explore the minima outside
the baseline. However, rewinding takes the SGD out of the baseline minimum and
is more likely to converge to a better minimum in the pruned space (which was
undiscoverable in the original space).

Fig. 21 presents the comparison of top-100 positive eigen values of the
Hessian at $W^{(FT)}$ and $W^{(min\\_(10))}_{(10)}$.

Figure 21: Comparison of top-100 positive eigen values of the Hessian at
$W^{(FT)}$ and $W^{(min\\_(10))}_{(10)}$.

It can be observed from the figure that $W^{(FT)}$ has larger eigen values of
the Hessian than $W^{(min\\_(10))}_{(10)}$, which implies a smaller volume for
the basin around $W^{(FT)}$ (Table IX). This elucidates the importance of
rewinding the learning rate schedule while re-training the pruned network.

TABLE IX: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at
$W^{(FT)}$ and $W^{(min\\_(10))}_{(10)}$

.  Solution $\lambda_{max}$ $V^{{}^{\prime}}(100)$ $W^{(FT)}$ 1667.231 412.686
$W^{(min\\_(10))}_{(10)}$ 1575.910 408.810

##  V Conclusion and Scope for Further Work

In this work, we have studied the loss landscape characteristics and
volume/geometry of the IMP solutions at different levels in order to answer
some important questions about the IMP and the lottery ticket hypothesis. The
study provided the following important insights among others: 1) there exist a
special type of minima in the loss landscape, which perform well but have a
very small volume in the original space, and the IMP procedure uncovers such
minima; 2) there exists a barrier between the IMP solutions at successive
levels in the loss landscape; 3) IMP solutions obtained using rewinding lie
within the same loss sublevel set, and random pruning or random initialization
of a pruned network take the SGD out of that sublevel set. These insights help
better understand the underlying principles behind IMP and the lottery-ticket
hypothesis.

We have shown that there exist minima that have narrow profiles along certain
dimensions and flatter profiles along others; however, the narrow profiles of
these minima are along sparser dimensions. There is a possibility of the
existence of minima that have narrow profiles along certain dimensions and
flatter profiles along others, with narrow profiles along non-sparser
dimensions. These minima are clearly not important from the pruning
perspective. If so, an interesting question is: can such minima serve some
other useful properties? This is a potential future direction that can be
explored.

Another future direction would be to design a computationally efficient
algorithm that makes SGD directly converge to the good sparser solutions
without going through the computationally expensive pruning and re-training
cycles.

## References

  * [1] J. Frankle and M. Carbin, “The lottery ticket hypothesis: Finding sparse, trainable neural networks,” _arXiv preprint arXiv:1803.03635_ , 2018.
  * [2] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein, “Visualizing the loss landscape of neural nets,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [3] D. Blalock, J. J. Gonzalez Ortiz, J. Frankle, and J. Guttag, “What is the state of neural network pruning?” _Proceedings of machine learning and systems_ , vol. 2, pp. 129–146, 2020.
  * [4] S. Han, J. Pool, J. Tran, and W. Dally, “Learning both weights and connections for efficient neural network,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [5] H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf, “Pruning filters for efficient convnets,” _arXiv preprint arXiv:1608.08710_ , 2016.
  * [6] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin, “Stabilizing the lottery ticket hypothesis,” _arXiv preprint arXiv:1903.01611_ , 2019.
  * [7] J. Frankle and D. Bau, “Dissecting pruned neural networks,” _arXiv preprint arXiv:1907.00262_ , 2019.
  * [8] D. Bau, B. Zhou, A. Khosla, A. Oliva, and A. Torralba, “Network dissection: Quantifying interpretability of deep visual representations,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 6541–6549.
  * [9] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin, “Pruning neural networks at initialization: Why are we missing the mark?” _arXiv preprint arXiv:2009.08576_ , 2020.
  * [10] J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin, “Linear mode connectivity and the lottery ticket hypothesis,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 3259–3269.
  * [11] B. W. Larsen, S. Fort, N. Becker, and S. Ganguli, “How many degrees of freedom do we need to train deep networks: a loss landscape perspective,” _arXiv preprint arXiv:2107.05802_ , 2021.
  * [12] S. Zhang, M. Wang, S. Liu, P.-Y. Chen, and J. Xiong, “Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 2707–2720, 2021.
  * [13] J. S. Rosenfeld, J. Frankle, M. Carbin, and N. Shavit, “On the predictability of pruning across scales,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 9075–9083.
  * [14] R. Movva, J. Frankle, and M. Carbin, “Studying the consistency and composability of lottery ticket pruning masks,” _arXiv preprint arXiv:2104.14753_ , 2021.
  * [15] M. Paul, B. Larsen, S. Ganguli, J. Frankle, and G. K. Dziugaite, “Lottery tickets on a data diet: Finding initializations with sparse trainable networks,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 18 916–18 928, 2022.
  * [16] T. Jin, M. Carbin, D. M. Roy, J. Frankle, and G. K. Dziugaite, “Pruning’s effect on generalization through the lens of training and regularization,” _arXiv preprint arXiv:2210.13738_ , 2022.
  * [17] M. Paul, F. Chen, B. W. Larsen, J. Frankle, S. Ganguli, and G. K. Dziugaite, “Unmasking the lottery ticket hypothesis: What’s encoded in a winning ticket’s mask?” _arXiv preprint arXiv:2210.03044_ , 2022.
  * [18] Z. Liu, M. Sun, T. Zhou, G. Huang, and T. Darrell, “Rethinking the value of network pruning,” _arXiv preprint arXiv:1810.05270_ , 2018.
  * [19] A. Renda, J. Frankle, and M. Carbin, “Comparing rewinding and fine-tuning in neural network pruning,” _arXiv preprint arXiv:2003.02389_ , 2020.
  * [20] C. Liu, L. Zhu, and M. Belkin, “Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning,” _arXiv preprint arXiv:2003.00307_ , 2020.
  * [21] Y. Cooper, “The loss landscape of overparameterized neural networks,” _arXiv preprint arXiv:1804.10200_ , 2018.
  * [22] S. Hochreiter and J. Schmidhuber, “Flat minima,” _Neural computation_ , vol. 9, no. 1, pp. 1–42, 1997.
  * [23] P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi, C. Borgs, J. Chayes, L. Sagun, and R. Zecchina, “Entropy-sgd: Biasing gradient descent into wide valleys,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2019, no. 12, p. 124018, 2019.
  * [24] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang, “On large-batch training for deep learning: Generalization gap and sharp minima,” _arXiv preprint arXiv:1609.04836_ , 2016.
  * [25] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio, “Sharp minima can generalize for deep nets,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 1019–1028.
  * [26] W. R. Huang, Z. Emam, M. Goldblum, L. Fowl, J. K. Terry, F. Huang, and T. Goldstein, “Understanding generalization through visualizations,” 2020.
  * [27] L. Wu, Z. Zhu _et al._ , “Towards understanding generalization of deep learning: Perspective of loss landscapes,” _arXiv preprint arXiv:1706.10239_ , 2017.
  * [28] Y. LeCun, J. Denker, and S. Solla, “Optimal brain damage,” _Advances in neural information processing systems_ , vol. 2, 1989.

## Appendix-I: Further Experimental Details

Some finer details of the experiments conducted in this study are mentioned
here for completeness.
ResNet-20 on CIFAR-10. We train ResNet-20 on CIFAR-10 for $160$ epochs with
SGD and a batchsize of $128$. We use learning rate = $0.1$, momentum = $0.9$,
and weight decay = $0.0001$. The learning rate is decayed by a factor of $10$
at $80$ and $120$ epochs. We use iterative magnitude pruning with weight
rewinding (IMP-WR) and run $10$ iterations of IMP. We prune $20\%$ of the
smallest magnitude weights in each iteration. The prunable parameters are the
weights of the convolutional layers and the fully-connected layers.
VGG-16 on CIFAR-10. We train VGG-16 on CIFAR-10 for $160$ epochs with SGD and
a batchsize of $128$. We use learning rate = $0.1$, momentum = $0.9$, and
weight decay = $0.0001$. The learning rate is decayed by a factor of $10$ at
$80$ and $120$ epochs. We use IMP-WR and run $12$ iterations of IMP. We prune
$40\%$ of the smallest magnitude weights at each round. The prunable
parameters are the weights of the convolutional layers and the fully-connected
layers.
Inverse volume of basin. In our experiments, we calculate the logarithm of the
product of top-$100$ positive eigen values of the Hessian of the loss function
to approximate the inverse volume of the basin. And the Hessian of the loss
function is calculated on a randomly chosen subset of the training dataset
($1/5^{th}$ of the size of the full training dataset in the case of ResNet-20
and $1/10^{th}$ of the size of the full training dataset in the case of
VGG-16).
Average radius of basin. In our experiments, we have calculated the average
radius of the basin around a solution by averaging the radii of the basin
along $500$ random directions. These experiments have also been performed on a
randomly chosen subset of the training dataset ($1/5^{th}$ of the size of the
full training dataset).
Training loss along a straight line connecting two solutions. The training
loss along a straight line connecting two solutions, $W^{(P)}$ and $W^{(Q)}$
is calculated as $Loss((1-\alpha)W^{(P)}+\alpha W^{(Q)})$, where
$\alpha\in[0,1]$. In our linear interpolation experiments, we calculate
training loss at $501$ points between the two solutions.
Loss landscape plot. Fig.10 presents the training loss at and around the
neighbourhood of the different points of interest. The plot has been obtained
by calculating training loss at $4200$ points in the high-dimensional space
and then projecting the points on the two-dimensional plane spanned by $3$
points, $W_{(0)}^{(min\\_(0))}$, $W_{(10)}^{(min\\_(10))}$ and $W^{(RIPN)}$.
However, the two axes formed by these points are not orthogonal. Hence,
orthogonalization of these axes is carried out before projecting the points
from the high-dimensional space. The loss is calculated using a randomly
chosen subset of the training dataset ($1/5^{th}$ of the size of the full
training dataset).

## Appendix-II: Experimental Results on VGG-16/CIFAR-10

Here, we present the evidence for our results from the experimentation
conducted on VGG-16/CIFAR-10. Fig. 22 presents the training loss and test
accuracy at different levels of IMP-WR.

Figure 22: Training loss and test accuracy at different levels of IMP-WR in
case of VGG-16. Left: Training loss. Right: Test accuracy.

###  V-A Solution obtained with IMP-WR outperforms the solutions obtained with
the other strategies.

Fig. 23 presents the comparison of training loss and test accuracy between
$W_{(12)}^{(min\\_(12))}$, $W^{(FT)}$, $W^{(RIPN)}$, $W^{(RPN)}$ and
$W^{(one\\_shot)}$. The plots clearly show that the solution obtained with
IMP-WR ($W_{(12)}^{(min\\_(12))}$) outperforms the solutions obtained with the
other strategies like: fine-tuning ($W^{(FT)}$), random initialization of the
pruned network ($W^{(RIPN)}$), random pruning ($W^{(RPN)}$) and one-shot
pruning ($W^{(one\\_shot)}$).

Figure 23: Comparison of training loss and test accuracy between
$W_{(12)}^{(min\\_(12))}$, $W^{(FT)}$, $W^{(RIPN)}$, $W^{(RPN)}$ and
$W^{(one\\_shot)}$ in case of VGG-16. Left: Training loss. Right: Test
accuracy.

###  V-B Path leading to $W_{(L)}^{(min\\_(L))}$ is steeper than the path
leading to $W^{Pr{(min\\_(L-1))}}_{(L)}$.

Fig. 24 presents the comparison of the logarithm of training loss versus epoch
between level $(L)$ and level $(L-1)$ projected on level $(L)$. The plots
clearly show that the path leading to $W_{(L)}^{(min\\_(L))}$ is steeper than
the path leading to $W^{Pr{(min\\_(L-1))}}_{(L)}$.

Figure 24: Comparison of the logarithm of training loss versus epoch between
level ($L$) and level $(L-1)$ projected on level ($L$) in case of VGG-16.

###  V-C Volume of the basin surrounding $W_{(L)}^{(min\\_(L))}$ is larger
than the volume of the basin surrounding $W^{Pr{(min\\_(L-1))}}_{(L)}$.

Fig. 25 presents the comparison of top-100 positive eigen values of the
Hessian at $W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(min\\_(L-1))}}_{(L)}$ for $L=$
{$1,6,11$}. As before, the figure shows that the eigen values of the Hessian
at $W_{(L)}^{(min\\_(L))}$ are smaller than that at
$W^{Pr{(min\\_(L-1))}}_{(L)}$, which means larger volume for the basin around
$W_{(L)}^{(min\\_(L))}$ than the volume of the basin around
$W^{Pr{(min\\_(L-1))}}_{(L)}$. This is also depicted in Table X.

Figure 25: Comparison of top-100 positive eigen values of the Hessian at $W_{(L)}^{(min\\_(L))}$ and $W^{Pr{(min\\_(L-1))}}_{(L)}$ for $L=$ {$1,6,11$} in case of VGG-16. TABLE X: Comparison of Maximum eigen value, $\lambda_{max}$ and inverse volume of basin, $V^{{}^{\prime}}(100)$ at $W^{Pr{(min\\_(L-1))}}_{(L)}$ and $W_{(L)}^{(min\\_(L))}$ for $L=$ {$1,6,11$}. $L$ |  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---|---
1 |  $W^{Pr{(min\\_(0))}}_{(1)}$ |  70.099 |  212.779
$W_{(1)}^{(min\\_(1))}$ |  50.77 |  203.681
6 |  $W^{Pr{(min\\_(5))}}_{(6)}$ |  86.27 |  198.106
$W_{(6)}^{(min\\_(6))}$ |  37.08 |  177.233
11 |  $W^{Pr{(min\\_(10))}}_{(11)}$ |  1413.523 |  414.844
$W_{(11)}^{(min\\_(11))}$ |  1326.092 |  352.86

###  V-D Volume of the basin surrounding $W_{(L-1)}^{(min\\_(L-1))}$ is larger
than the volume of the basin surrounding $W^{RPr{(min\\_(L))}}_{(L-1)}$.

Fig. 26 presents the comparison of top-100 positive eigen values of the
Hessian at $W_{(L-1)}^{(min\\_(L-1))}$ and $W^{RPr{(min\\_(L))}}_{(L-1)}$ for
$L=$ {$1,6,11$}. The figure shows that the eigen values of the Hessian at
$W_{(L-1)}^{(min\\_(L-1))}$ are smaller than that at
$W^{RPr{(min\\_(L))}}_{(L-1)}$, which means larger volume for the basin around
$W_{(L-1)}^{(min\\_(L-1))}$ than that of the basin around
$W^{RPr{(min\\_(L))}}_{(L-1)}$. This is also depicted in table XI.

Figure 26: Comparison of top-100 positive eigen values of the Hessian at $W_{(L-1)}^{(min\\_(L-1))}$ and $W^{RPr{(min\\_(L))}}_{(L-1)}$ for $L=$ {$1,6,12$} in case of VGG-16. TABLE XI: Comparison of $\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{RPr{(min\\_(L))}}_{(L-1)}$ and $W_{(L-1)}^{(min\\_(L-1))}$ for $L=$ {$1,6,12$} in case of VGG-16. $L$ |  Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---|---
1 |  $W^{RPr{(min\\_(1))}}_{(0)}$ |  43.777 |  219.996
$W_{(0)}^{(min\\_(0))}$ |  67.929 |  220.915
6 |  $W^{RPr{(min\\_(6))}}_{(5)}$ |  46.733 |  201.835
$W_{(5)}^{(min\\_(5))}$ |  77.396 |  189.044
12 |  $W^{RPr{(min\\_(12))}}_{(11)}$ |  4379.201 |  426.294
$W_{(11)}^{(min\\_(11))}$ |  1326.092 |  352.86

###  V-E There exists a barrier between the IMP solutions at successive levels
in the loss landscape.

Fig.27 presents the training loss along a straight line connecting
$W^{(min\\_(L-1))}_{(L-1)}$ and $W^{(min\\_(L))}_{(L)}$. The x-axis represents
the interpolation co-efficient $\alpha$. Each plot depicts the training loss
at $501$ points between $W^{(min\\_(L-1))}_{(L-1)}$ and
$W^{(min\\_(L))}_{(L)}$. The barriers between successive minima are clearly
visible.

Figure 27: Training Loss along a straight line connecting
$W^{(min\\_(L-1))}_{(L-1)}$ and $W^{(min\\_(L))}_{(L)}$ in case of VGG-16.

###  V-F Random initialization of a pruned network takes SGD out of the loss
sublevel set and converges to a minimum with inferior performance (than that
of the minimum obtained with rewinding).

Fig. 28 presents the training loss along a straight line connecting
$W^{(min\\_(11))}_{(11)}$ (baseline for $W^{(RIPN)}$) and $W^{(RIPN)}$. The
figure shows a huge barrier between the two points, which demonstrates that
these two points lie in different loss sublevel sets.

Figure 28: Training Loss along a straight line between
$W^{(min\\_(11))}_{(11)}$ and $W^{(RIPN)}$.

A comparison of top-100 positive eigen values of the Hessian at $W^{(RIPN)}$
and $W^{(min\\_(12))}_{(12)}$ is given in Fig. 29. It can be observed from the
figure that the Hessian at $W^{(RIPN)}$ has larger eigen values than that at
$W^{(min\\_(12))}_{(12)}$, which indicates a smaller volume for the basin
around $W^{(RIPN)}$ (Table XII).

Figure 29: Comparison of top-100 positive eigen values of the Hessian at
$W^{(RIPN)}$ and $W^{(min\\_(12))}_{(12)}$. TABLE XII: Comparison of
$\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(RIPN)}$ and
$W^{(min\\_(12))}_{(12)}$

.  Solution $\lambda_{max}$ $V^{{}^{\prime}}(100)$ $W^{(RIPN)}$ 25526.326
442.242 $W^{(min\\_(12))}_{(12)}$ 3992.4783 389.957

###  V-G Random pruning takes SGD out of the loss sublevel set and converges
to a minimum with inferior performance (than that of the minimum obtained with
magnitude based pruning).

Fig. 30 presents the training loss along a straight line connecting
$W^{(min\\_(11))}_{(11)}$ (baseline for $W^{(RPN)}$) and $W^{(RPN)}$. The
figure shows a huge barrier between the two points, which demonstrates that
these two points lie in different loss sublevel sets.

Figure 30: Training Loss along a straight line between
$W^{(min\\_(11))}_{(11)}$ and $W^{(RPN)}$.

A comparison of top-100 positive eigen values of the Hessian at $W^{(RPN)}$
and $W^{(min\\_(12))}_{(12)}$ is given in Fig. 31. It can be observed from the
figure that the Hessian at $W^{(RPN)}$ has larger eigen values than that at
$W^{(min\\_(12))}_{(12)}$, which indicates a smaller volume for the basin
around $W^{(RIPN)}$ (Table XIII).

Figure 31: Comparison of top-100 positive eigen values of the Hessian at
$W^{(RPN)}$ and $W^{(min\\_(12))}_{(12)}$. TABLE XIII: Comparison of
$\lambda_{max}$ and $V^{{}^{\prime}}(100)$ at $W^{(RPN)}$ and
$W^{(min\\_(12))}_{(12)}$

.

Solution |  $\lambda_{max}$ |  $V^{{}^{\prime}}(100)$
---|---|---
$W^{(RPN)}$ |  51190.094 |  451.384
$W^{(min\\_(12))}_{(12)}$ |  3992.4783 |  389.957