Validating the Lottery Ticket Hypothesis with Inertial Manifold Theory
Authors: Zeru Zhang
Jiayin Jin
Zijie Zhang
Yang Zhou
Xin Zhao
Jiaxiang Ren
Ji Liu
Lingfei Wu
Ruoming Jin
Dejing Dou
Venue: NeurIPS 2021 Poster (2021)
Keywords: Lottery Ticket Hypothesis
neural network pruning
dynamical systems
inertial manifold
theoretical evidence

Abstract: Despite achieving remarkable efficiency, traditional network pruning techniques often follow manually-crafted heuristics to generate pruned sparse networks. Such heuristic pruning strategies are hard to guarantee that the pruned networks achieve test accuracy comparable to the original dense ones. Recent works have empirically identified and verified the Lottery Ticket Hypothesis (LTH): a randomly-initialized dense neural network contains an extremely sparse subnetwork, which can be trained to achieve similar accuracy to the former. Due to the lack of theoretical evidence, they often need to run multiple rounds of expensive training and pruning over the original large networks to discover the sparse subnetworks with low accuracy loss. By leveraging dynamical systems theory and inertial manifold theory, this work theoretically verifies the validity of the LTH. We explore the possibility of theoretically lossless pruning as well as one-time pruning, compared with existing neural network pruning and LTH techniques. We reformulate the neural network optimization problem as a gradient dynamical system and reduce this high-dimensional system onto inertial manifolds to obtain a low-dimensional system regarding pruned subnetworks. We demonstrate the precondition and existence of pruned subnetworks and prune the original networks in terms of the gap in their spectrum that make the subnetworks have the smallest dimensions.

Validating the Lottery Ticket Hypothesis with Inertial Manifold Theory
Zeru Zhang!
Jiayin Jin Zijie Zhang' Yang Zhou it
Xin Zhao
Jiaxiang Ren!
Ji Liu"
Lingfei Wu Ruoming Jin Dejing Dou
Auburn University, "Badu Research, $JD.COM Silicon Valley Research Center, *Kent State University, University of Oregon
zzz00546auburn. edu, jzj00420auburn. edu, zzz00920auburn. edu, yangzhou@auburn edu, cmik6684355@gmall com, j2r00650auburn. edu, 1iuji04@baidu com, 1wu@email... wm. edu, rjin1@kent edu, douEcs. woregon. edu, doudejing@ban com
Abstract
Despite achieving remarkable efficiency, traditional network pruning techniques often follow manually-crafied heuristics to generate pruned sparse networks. Such heuristic pruning strategies are hard to guarantee that the pruned networks achieve test accuracy comparable to the original dense ones. Recent works have empirically identified and verified the Lottery Ticket Hypothesis (LTH): randomly-initializ dense neural network contains extremely sparse subnetwork, which can be trained to achieve similar accuracy to the former. Due to the lack of theoretical evidence, they often need run multiple rounds of expensive training and pruning over the original large networks to discover the sparse subnetworks with low accuracy loss. By leveraging dynamical systems theory and inertial manifold theory, this work theoretically verifies the validity of the LTH. We explore the possibility theoretically lossless pruning as well one-time pruning, compared with existing neural network pruning and LTH techniques. We reformulate the neural network optimization problem gradient dynamical system and reduce this nigh-dimensional system onto inertial manifolds to obtain low-dimensional system regarding pruned subnetworks. We demonstrate the precondition and existence of pruned subnetworks and prune the original networks in terms of the gap in their spectrum that make the subnetworks have the smallest dimensions.
Introduction
Deep learning techniques utilize the architecture of large model size and over parameterization to achieve state-of-the-art performance in wide range of applications [17 [8], The performance im- provements can owed to the availability large-scale neural networks and massive computational resources to train such complex models. However, large model size and extreme over-parameterrizaion typically lead to high training cost, slow inference speed, and large memory consumption. This hinders the applicability of deep learning models in resource-intensiv scenarios with the requirement of low latency and energy consumption, such as Internet of Things 2 and mobile computing [5))
We have witnessed large number of research advances in neural network pruning for reducing the time and space requirements of deep neural networks both training and test time, with minimal loss in accuracy 31 20 34). These techniques identify non-essential weights, filters, and other structures
Equual contributors Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

from neural networks that do not contribute significantly to the model performance. and remove them
for compressing original dense neural networks 44 68 52
57
3 30
35
64
39
27
29
40
61
33
56
16
21 The goal of neural network pruning is to reduce computational cost and memory
consumption without a significant accuracy drop, compared with the original dense networks.
However, the majority of neural network pruning methods require to train a dense neural network
to generate a pruned sparse network, as it is difficult train pruned network from scratch [20
62 23
67 68
52 57
30
74 24, 25
63
35
64
39
27
29 40), although there are
few pruning before training approaches [32
33
56
16
Thus, these methods still suffer
from the non-trivial training cost on over- weer-paamtterizedd networks. Most importantly, traditional
network pruning techniques are based on ad-hoe heuristic pruning strategies [20] 74 63 (29), leaving some critical theoretical questions unanswered on how much we can prune a neural network given a specified tolerance of accuracy drop, and how to achieve it with a practical and efficient procedure. Therefore, it is difficult to theoretically guarantee that the pruned networks achieve test accuracy comparable to the original dense ones. In addition, recent literature has demonstrated that traditional neural network pruning often fall-short compared to the Lottery Ticket Hypothesis techniques [33]
A recent report has empirically identified and validated a surprising finding of the Lottery Ticket Hypothesis (LTH): a randomly-initialized dense neural network contains an extremely sparse subnet- work (i.e., winning lottery ticket) such that, when trained from scratch with weights being reset to its initialization, can achieve similar performance to the original dense network within similar [3] 14]. Compared with the original dense networks, the winning tickets are able to save a lot of memory for retraining [
training iterations
The existence of winning tickets indicates that deep learning models can be trained in low-resource environments.
73
14 15 70
42 53
While the LTH techniques exhibit promising practical implications for scaling over large models and datasets, they fail to provide an efficient algorithm search for the winning ticket subnetworks for deep learning models in practice, due to the lack of theoretical evidence and analysis. They often utilize an Iterative Magnitude Pruning (IMP) strategy gradually find winning tickets, which needs multiple rounds of expensive training, pruning, and resetting over large neural networks. Although existing LTH techniques raise very intriguing observations. most of them provide only empirical 8 7 ITI In this case, it is difficult to
evidence to verify the LTH [7] identify the optimal pruning strategy without performance drop, i.e., how and where a neural network should be pruned. Therefore, two fundamental unanswered questions are raised: (1) How to verify the existence of winning lottery tickets, i.e., sparse trainable subnetworks inside a dense neural network, with theoretical evidence and analysis? (2) How to provide efficient algorithms to discover winning lottery tickets, without multiple rounds of expensive training and pruning in the IMP process?
69 54
5
53
26
To our best knowledge, this work is the first to theoretically verify the LTH and the existence of winning lottery tickets by leveraging dynamical systems theory and inertial manifold theory.
We reformulate gradient descent optimization of a neural network as a gradient dynamical system regarding W (i.e., parameters of the neural network) and analyze its dynamics with dynamical systems theory. Since inertial manifolds Mw contain all local minimum points W of loss function L regarding W (i.e., VL(W*)= 0), reduce the original high-dimensional gradient system o onto inertial manifolds to obtain low-dimensional system regarding W+, i.e., parameters of the winning ticket subnetwork. We demonstrate that there must exist such Mw for neural network pruning, when the gradient dynamical system meets a certain condition about its spectrum and Lipschitz constant, for cutting W into W++ and W (i.e., redundant parameters of the original neural network).
In comparison with existing neural network pruning and LTH techniques, our dynamical systems and inertial manifold-basee method exhibits two unique advantage: (1) All local minimum points 4 lic in Mw and thus W+ is theoretically lossless pruning of W. (2) The computation of Mw and W+ a one-time operation, such that our method is able avoid the cost of multiple rounds of expensive training and pruning on large networks in the LTH methods. Due to large size of W in real scenarios, an approximate method is designed to estimate the Lipschitz constant for maintaining the efficiency.
Extensive evaluation on real datasets demonstrates the superior performance of our proposed IMC model against several state-of-the-art neural network pruning and LTH methods. More experiments, implementation details, and hyperparameter setting are presented Appendices A.3 A.5
2

---

2 Background
2.1 Lottery Ticket Hypothesis
The Lottery Ticket Hypothesis (LTHH) states that randomly-initialized dense neural network contains a subnetwork that is initialized such that, when trained isolation, it can match the test accuracy of the original network after training for at most the same number of iterations [13 14].
Given dense neural network f(;; W) with randomly-initaalzzed weight parameters W = Wo E R2, when optimizing with stochastic gradient descent (SGD) on a training set, ff reaches minimum loss L at iteration with test accuracy a. A sparse subnetwork of denoted as f(x; M O W) using a binary pruning mask M (0, 13 |o < d on its parameters such that its initialization is M @ W,, where @ denotes the Hadamard product and W; are the generated parameters of the original model f(;; W) at iteration i. When optimizing with SGD on the same training set, f(x; M @ W). where W is initialized with W, can be trained from M @ W to reach minimum loss L at commensurate iteration I with commensurate accuracy
a the original model (z; W).
The LTH techniques often utilize an Iterative Magnitude Pruning (IMP) strategy to find winning tickets by gradually training the network and pruning its magnitse weights [33 It operates in T rounds of expensive training, pruning. and resetting over large neural networks for guaranteeing the acceptable accuracy drop. Each of multiple rounds in the IMP consists of four steps: (1) Randomly initialize a dense neural network f(;; W) with weight parameters W = Wo: (2) Train W of f for iterations, generating updated parameters Wr; r (3) Prune p% of the parameters with the smallest magnitude in W,, producing a mask M; and (4) Reset the remaining weight parameters back their initial values in Wo. creating the winning ticket f (a; M @ Wo).
2.2 Dynamical Systems Theory
In mathematics, an ordinary differential equation (ODE) is differential equation containing one or more functions of one independent variable and the derivatives of those functions (75.. A system of first-order ODE is defined as follows.
x' (t) = f(((t)) x E
where X is a Banach space and f + X is a function of r(t). The unknown function srt) at time t appears on both sides of the differential equation.
Definition 1. [Globally Lipschitz] fxx) is globally Lipschitz in X if there exists a constant K 2 0 for all x. y E X, holds [[f(x)) f(v)(((l S K 2 vllx, where K is the Lipschitz constant of f. Definition 2. [Global Solution of ODE] A solution xtt) RR X of the ODE in Eq. ( is said be global if oz (t) exists for any t E R.
Lemma 1. If (x) is globally Lipschitz in X, then the ODE in Eq. has a unique global solution in X for any initial condition z=) = zo 19.
xxt) is the flow (i.e., if ptt, 20) is the unique solution of the ODE with initial x00)= Ho. For any given initial value To the sets {tp(t, 20) : E). (set, zo) : t E IR}, (0)(t : E } are called the complete orbit, positive orbit, and negative orbit starting from Tu, respectively.
Definition 3. [Flow of ODE] 9 R x X
X. defined by p(t,
solution map) of the ODE in Eg. 1
condition (0, xo)
In this work, we only consider the case of positive time and use the positive orbit starting from x. The orbit (tt 2o) :t E (IR+ OO}}} of the flow is also called the trajectory of the point x under the flow. Definition 4. /Continuous Dynamical System) If a flow sp(1, zp) satisfies the following properties:
p(s + 4, p0) = s(s, x0), 20) for any 8, E IR; ptt, 2u) is continuous in Zo for any t R. pit, 20) is continuous in t for any 2o E X,
then the flow zo) together with the space X is a continuous dynamical system.
If f(x) is globally Lipschitz, then the flow of the ODE is a continuous dynamical system. Dynamical system is mathematical concept that is used to describe the time dependence of a point's position in its ambient space. Dynamical System Theory is mathematical tool to capture long-time behavior of solutions.
Definition 5. [Equilibrium of Dynamical System] A point x² is called an equilibrium of dynamical system if (((tttt)) = x² for all E IR i.e., f(x*) = O.
3

---

An equilibrium is a solution that does not change with time. This means if the systems starts at an equilibrium. the state will remain at the equilibrium forever.
Definition 6. [Invariant Set/Manifold] A set or manifold A is invariant under a dynamical system yp if (tt, A) C A for any t 2 0. That is, if a is an element of A then so is cp(t, a) for all t 2 0. manifold is topological space that locally resembles Euclidean space near each point. Examples of invariant manifolds include stable manifold, unstable manifold, and inertial manifold.
Definition 7. [Attractor of Dynamical System] A set A C BR is an attractor that attracts a set B C R under a dynamical system yp if A an invariant set under ip and
lim dist dist(pp(,, A) = =0 1-00
(2)
where B denotes the basin of attraction for A. dist represents the Hausdorff semi-distance defined by
dist (B, A) = sup inf | - y|lx
(3)
#EB yEA
An attractor is set of states (i.e., points in the phase space), invariant under the dynamics, towards which neighboring states in a given basin of attraction asymptotically approach in the course of dynamic evolution. An attractor can be a point, finite set of points, curve, a manifold, or even a complicated set with a fractal structure. lim dist(yp(t, B), A) = implies that flows starting from t-xx
any point b B enter A in the limit t Do.
Definition 8. |Globul Attractor of Dynamical System] A nonempty compact set A C X is global attractor under a dynamical system yp if A is an invariant set under ip and A attracts all bounded sets B C X.
global attractor represents the maximal compact invariant set which attracts the orbits of all bounded sets at a uniform rate.
Definition 9. /Stable/Unstable Manifold of Dynamical System] Given an equilibrium x² of a dynam- ical system, the stable manifold MM(x") of x² is a set of points in phase space if
M²(x") {x E X: p((t,)) - x' as t -> +00}
(4)
and the unstable manifold (²"x") x" is a set of points in phase space if
M"(x") = (I X: (l) +x l + -c)
(5)
3 Validating the Lottery Ticket Hypothesis
The idea of this work is to reformulate gradient descent optimization of a neural network in 6 as gradient system in 7 regarding W. By leveraging the dynamical system theory, we analyze the dynamics and equilibria (i.e., local minimum points W* of loss function L in (q.(6) of the gradient dynamical system and theoretically validate the LTH. The gradient dynamical system has global attractor that contains all equilibria. However, the global attractor usually has fractal dimension and its geometry is very complicated. Thus, it is difficult to analyze the dynamics inside it.
Fortunately, inertial manifolds Mw of the gradient system enclose the global attractor and have manifold structure (i.e., regular geometric objects). It is more convenient to analyze the dynamics inside them and reduce the original high-dimensional gradient system regarding W onto MM to obtain www-iimeniional system regarding W i.e., parameters of the winning ticket subnetwork. According to Theorem 5] the new low-dimensional system governs the original high-dimensional one. Most importantly, encloses all equilibria of the original system, i.e., all W lie in the inertial manifold. Thus, it is efficient to directly analyze the low-dimensional system to discover the W*.
3.1 Neural Network Pruning
Traditional deep learning models often utilize gradient descent techniques to optimize neural networks and reach local minimum of loss L. The gradient decent procedure is given below.
W(t + 1) W(t) L))())()))
(6)
where W are the parameters of neural network, is the iteration time, 1) is a learning rate, and I, is the loss function. By starting from initial parameters W(D), the gradient decent procedure converges to local minimum point 4 of L, ie., VL(W*) = 0.

---

The above gradient decent procedure in Eq. can be viewed as the numerical solution of an ODE system under classical Euler scheme. The sequence of W(0). (1). W in the gradient descent process in (6 corresponds to discrete points on the orbit of the following ODE.
(t) (()
W' is equilibrium (i.e., iime-independent solution) of the ODE system. The ODE in Eq. is gradient system, since the vector field -V VV(WW) is the gradient of L. The dynamical system derived by (7) is gradient dynamical system, where the loss is decreasing along the solution of the equation.
di L(W()) = VL dW (t) - (L) S
(8)
di
This is the reason why the gradient descent method works for the optimization neural networks.
The following theorems analyze the existence, uniqueness, and convergence of the global attractor A of the gradient dynamical system derived by 7 Most importantly, they demonstrate that all local minimum points W of L of the original neural network in Eq. lie in A of the system by 7 The global attractor A of the dynamical system derived by 7 is the union of equilibria W* and their unstable manifolds (** [19].
Theorem 1.
Since the equilibria W are the time- -ndeeeddeenndnt solutions of our gradient dynamical system, they correspond to the local minimum points of L of the original neural network in (6.
Theorem 2. The global attractor A of the dynamical system derived by Eq. (7) is unique.
Theorem 3. Let A C W be a compact subset of a Banach space W, and ((t) E W be a sequence with lim dist(W(()) A) = O, then W (t) has a convergent subsequence, whose limit lies in A. Theorem 4. The global attractor A of the dynamical system derived by Eg.(7) is the maximal compact invariant set, and the minimal set that attracts all bounded sets B CBC W.
Please refer to Appendix Anmendix(...fff for detailed proof of Theorems 73
In mathematics, inertial manifolds are concerned with the long-term behavior of the solutions of dynamical systems (58]. Inertial manifolds are Unite-dimensional, smooth, invariant manifolds that contain the global attractor and attract all solutions of the dynamical systems. Since an inertial manifold is lower-dimensional compared with the whole solution space and all important dynamics take place on inertial manifold, studying the dynamics on inertial manifolds only is enough derive the dynamics of the original gradient system.
Definition 10. [Inertial Manifold of Dynamical System] Let W be a Banach space, an inertial manifold Mw for dynamical system is smooth manifold such that
Mw is of finite dimension;
The flow glt, Mw) C. MM for any t 0:
There exist two constants C1, C2 > such that for any initial condition W(0) E W, il holds
dist(y((t, (O)), S Cie Cat
-Ca Cat (O),
Since all solutions of Eq. eventually converge to the inertial manifold My and all local minimum points W of L of the original neural network in Eq. locate on Mw, would be sufficient to work on the inertial manifolds MM directly for discovering W
Theorem 5. Let W be Banach space with dimension d, given a semi-linear ODE
w'(t) = AW + f(W())) W(I) W
(10)
where A a d matrix and f W - W. The spectrum of A is denoted as follows.
A A .... ... ...5. da
(11)
Assuming that f(0) 0, let K be the Lipschitz constant of fz), that is,
llf(z) f(y)llw || vllw for any v, y W
(12)
If there exits an integer k. such that Ac+1 D > 4K, let W be the generalized eigenspace for AktI..... da and W be the generalized eigenspace for A1,..., Ag. then there exists an inertial manifold Mw as follows.
Mw (WT, (WWW))))))
(13)
where bs is mapping from W to W
Please refer to Appendix A.2 detailed proof of Theorem
5

---

Theorem 5 demonstrates the whole solution space W can be decomposed into two subspaces W and W when the gup between arbitrary two consecutive eigenvalues in the spectrum of A is larger than 4K. An inertial manifold Mw can be constructed as the graph of a mapping h W -> W- Consequently, the dynamies on Mw can be described by the projected dynamies W+ through the mapping h, and W is redundant. When there are multiple integers & satisfying A X > 4K, we choose the largest k to cut MW. such that W has the smallest dimensions, i.c., the best pruning.
In order to utilize the conclusion of Theorem to prune the network parameters W in Eq. we leverage linearization arrriiaationaruund--- -round- sounnd-fieed-eee ixed-points technique in dynamical systems theory to transform the gradient system in Eq. into an equivalent semi-lineas ODE system as follows.
U(t) = ((t) W
(14)
For ease of presentation, we use symbols U and W replace (() and W(t). Then we have
U' - (VI(U + + (W)")U (W JU F(U)
(15)
where H(W)) denotes the Hessian matrix of loss functiin L evaluating at W and F(U) is equal to - -(VL(U + W*) (W))
The advantage of such linearization-aarun---iss fixedddoonti---tits technique is to make the nonlinear term since VL(W*) = O. Notice that the assumption for nonlinear term (((()) in Theorem 5 is f() O. The above lincarization-
F(U) satisfy F(0)=
technique allows to leverage
the conclusion of Theorem[5Joor lossless neural network pruning.
Compared with the system about original parameters W in ( 10). ( is semi-linear ODE
15
system regarding converted parameters U. The corresponding inertial manifold My is given below.
MMu (U+,h(U*)) U+ eu²)
(16)
where L1+ a corresponding subspace. My is an invariant manifold, that is, for any solution (t) of the ODE system, if (0) E MMu then (t) E MM for any 2 0. Moreover, Mar contains all
local minimum points. U+ is a lossless pruning of according to the conclusion of Theorem 5
Thus, the corresponding inertial manifold My for the gradient system in Eq. is given as follows.
Mw = W + Mu {(W+, W U E4+}
(17)
where W+ = U + + and W +((+++++++++ + W and W W are the counterparts of W* in terms of the same dimension cutting as U. W is a constant when we are given a trained large neural network. W can be written function of W W h(U+)+++++)) + + h(W + - W + W*
We denote this function as g. i.e., W- = g( (W+).
The dynamics of the gradient system in Eq. ( is governed by MM (W+, . (W+)). The system in Eq. can be reduced onto Mw. The neural network and the loss function on Mw are given below.
f(w+) s(w+ ([W++s(("' :s(*)) s(W), I(w+)= L(W .W(+tg = L(W)
(18)
where f and f represent the original and pruned neural networks respectively. The reduced gradient system on Mw is given as follows.
dw+
dt = V((+)) = -Ww+ .gWW)) V Ww-L(Wt .(W Vg((
(19)
As all local minimum points lie in Mw, the reduced problem in Eqs. and 19 work equally well as the original one in 7). This indicates that using the low-dimensional parameters W e d to train f is sufficient to obtain the same performance training f with the original high-dimensional parameters W E IRd. Therefore, we only need to train a subnetwork with W as parameters.
In order to further improve the pruning efficiency, we train the parameters W of the original networks few iterations (10 epochs in our implementation) to generate an approximate W*, Due to large size of W*, we employ scalable Hessian computation method to calculate an approximate H(W*) 65 66
We prune the original network with parameters W to generate subnetwork with parameters W and train the latter until convergence.

---

3.2 Estimation of Lipschitz Constant
In order leverage the conclusion of Theorem 5 to compress the parameters W of neural networks in
(6. we need to verify whether its condition is satisfied and thus we need to estimate the Lipschitz constant of the nonlinear term FUU) in (55
Let B be the la--uppe bound of U, i.e., ||0|| S B, by utilizing the Mean Value Theorem, we get F(U1) F(U2) =VL(U; Wn) VLLU2 W*) H(W" (U; U2)
= =[ -112 [[ -U2)
(20)
+ - (1) - - -U2)
where 0 0- 81, 02 S 1 are two constants.
By employing the Hölder Inequality, we have
[[F(V)) - P()))l>> s (V UU + 02(U2 U1) 11 U2l 1 p to0
(21)
As ||0||50 & B, ||U1 - 02 - 2B. addition, |U; - U2 & |1 - U2llp. Thus, we have
[[+(()) - >(-))ll, v 2 + U1 + 02(2 - Ue)) - U2llp
(22)
Therefore, the Lipschitz constant of FUU) in 1p space is 2B V H (W* +U +22UU U1)
For case of presentation, we use a symbol V to replace W + U1 + +U2 -U). Since 2B is constant for given U, we only need to estimate [V)I'
Based on the Second Derivative Formula, the estimation of (V) p is given as follows.
[V VL(V + AMM 2VL + VL(V 2M/
(23)
A
where A refers to corresponding change of V.
choose p 2 and A 0.01. A is same dimension as V. the current experiments, the estimated Lipschitz constants of all neural networks are very tiny with order 10-12 This implies that neural network pruning technique has great potential as a general pruning solution to other neural networks, which is desirable in practice.
In our implementation,
matrix with the
3.3 Algorithm
The following are the algorithm descriptions of our Inertial Manifold-based neural network Compression (IMC) method step by step: (1) Given a dense neural network / (ar; W) with randomly-
initialized flattened weight parameters W Wo E Rd when optimizing W with stochastic gradient descent (SGD) on training set, we generate an approximate W in few training iterations (10 iterations our implementation), where W is a local minimum point of loss function L regarding W in (6) (i.e., VL(W*) O). Notice that W* is also an equilibrium of the gradient dynamical system in Eq. Eq. (2) Based on the transformation = W - W' from to through the above approximate W in Eq.() we transform the gradient dynamical system in Eq. 7 into semi-linear ODE system U' = (W"")UU + F(U) in (15), where H(W)) denotes the Hessian matrix of loss function L evaluating W and F(U) is equal to -VVL(U + W*) H(W))U): (3) We employ scalable Hessian computation method calculate an approximate 11 [78, 79]. We calculate the spectrum of (WW")) and sort its eigenvalues as a < X2 < ... < As; (4) We estimate the Lipschitz constant K of the nonlinear term F(U) in (q. based on Eqs.(22) and (23); (5) We check pairwise consecutive eigenvalues in descending order, i.e., Aa and Ad-1, Ad-1 and Ad-2, and A2 and Å1. When finding the first k satisfying d4-1 A 4K, we partition
e Rd into U+ E d and U- E R$ and split W E Rd into W+ E Rd* and W E Rt; and (6) We prune the original network with dibeensiiii parameters W e Ed to generate a subnetwork with low-dimensional parameters W+ E IRd-k i.e., reduce W to W- and train W+ until convergence.
4 Experimental Evaluation
In this section, we have evaluated the effectiveness of our IMC model and other baselines for neural network pruning over three standard image classification datascts: CIFAR-10 288, CIFAR-100 28
7

---

Table I: Accuracy with found sparsity by our IMC method on CIFAR-10
Neural Network
ResNet-20
ResNet-32
Metric
Sparsity
Accuracy
Epoch
Runtime
Sparsity
Accuracy
Epoch
Runtime
Baseline
94.6
160
1,956
95.0
160
4,233
Flow&Prune
0.47
91.6
160
6,120
0,45
92.6
160
8460
SNIP
0.47
92.4
160
2,675
0.45
92.9
160
4,046
SynFlow
0.47
92.5
160
2,664
0.45
90.8
160
4,046
LTII-Reimitialization
0.47
92.9
1,120
24,901
0.47
1,120
100,301
LeW+-Reiind
0.47
92.5
1,120
24,477
0.47
93.6
1,120
100,328
LTII+FineTuning
0.47
91.5
1,120
24,875
0.47
92.8
1,120
100,291
GraSP
0,47
91.1
160
2,966
0.45
91.5
160
4,659
sanity
0.47
93.3
2,185
0.45
93.5
160
3,009
Continuous Sparsification
0.47
92.2
320
5,298
0.44
92.9
320
7,490
IMC- MiC-aeenitillization
0.47
94.5
160
3,215
0.45
94.8
160
4,704
IMC-Rewinding
0.47
94.5
160
3,179
0.45
94.9
160
4,591
MMC-iineTunnin
0.47
94.6
3,205
0.45
95.1
4,607
Table 2: Sparsity with highest accuracy CIFAR-10
Neural Network
ResNet-20
ResNet-32
Metric
Sparsity
Accuracy
Epoch
Runtime (8)
Sparsity
Accuracy
Epoch
Runtime (8)
Baseline
0
94.6
160
1.956
0
95.0
160
4,233
Flow&Prune
0.1
94.1
160
6,124
0.1
94.5
160
8,371
SNIP
0.1
92.9
2,670
0.1
93.4
160
4,075
SynFlow
0.05
93.1
160
2,659
0.15
93.6
160
4,065
LTII-Reinitialization
0.1
94.5
320
6,940
0.19
94.9
480
44,636
LTwn-Rewinding
0.1
94.5
320
7,060
0.19
94.1
480
44,683
LTH+FineTunnig
0.1
94.2
320
7,101
0.1
94.5
320
30,406
GraSP
0.05
92.8
160
3,081
0.05
93.4
160
4,637
sanity-check
0.1
94.2
160
2,124
0.15
94.5
160
3,138
Continuous Sparsification
0.39
92.5
320
5,261
0.25
93.3
320
7,067
AMC-Reinitializattion
0.47
94.5
3,215
0.45
160
4,704
-CC-ewinn
0.47
94.4
160
3,179
0.45
94.9
160
4,591
IMC-FineTuningg
0.47
94.6
160
3,205
0.45
95.1
160
4,607
and ImageNet [10. The experiments exactly follow the same settings described by the original LTH
paper 13 14
and other following works on LTH and network pruning (70] 55
15
53
69
11).
Baselines. We compare the IMC model with nine state-of-the-aa models, including three network pruning and six LTH approaches. Flow&Prune is pruning during training approach that uses gradient flow to determine the relationship between pruning measures and evolution of model parameters 40). SNIP and SynFlow prune given network once at initialization prior to training (32 56). MonnH-eiiitillizattion is the original L.TH method, which randomly sample a new initialization for winning tickets' initialization [13 LTH+Rewinding rewinds unpruned weights their values from earlier in training and retrains them from there using the original training schedule (I5).
LTH+Fine fine-tunes the pruned model to regain the lost performance, instead of training from seratch (38]. GraSP prunes the weights whose removal will result in least decrease in the gradient norm after pruning [59]. sanity-check proposes sanity check methods to identify the pruned subnetwork are essential for the final performance [54].
whether the architecture Continuous Sparsification searches for sparse networks based on approximation of an intractable lo regularization [53). To our best knowledge, this work is the first to theoretically verify the LTH and the existence of winning tickets by leveraging dynamical systems theory and inertial manifold theory.
Variants IMC model. We evaluate three variants of IMC to show the strengths of different subnetwork training strategies. After leveraging dynamical systems theory and inertial manifold theory to generate winning lottery tickets, IMC-Reinitializatton randomly sample a new initialization for winning tickets' initialization [I3), IMC- MMC-Reiidding rewinds unpruned weights to their values from earlier in training and retrains them from there using the original training schedule [15]. and IMC-FineTunine fine-tunes the pruned subnetworks regain the lost performance (8).
Evaluation metrics. We evaluate proposed techniques against the baselines by focusing on two specific tasks: (1) the classification accuracy with the same sparsity level found by our IMC model; and (2) the pruning performance (i.e., sparsity) under the highest classification accuracy. larger sparsity indicates better pruning.

---

Table 3: Accuracy with found sparsity by our IMC method on ImageNet
Neural Network
ResNet-20
ResNet-32
Metric
Sparsity
Accuracy
Epoch
Runtime
Sparsity
Accuracy
Epoch Runtime
Baseline
59.4
160
6hrs
60.0
160
8hrs
Flow&Prune
0.33
57.6
160
23,242
0.28
58,9
160
34,920
SNIP
0.33
55.5
160
18,100
0.28
56.6
160
28,947
SynFlow
0.33
56.6
160
17,990
0.28
56.1
160
25,145
LTTI-Reimitialization
0.34
55.9
198,832
0.27
59.4
640
129,344
LeW+-Rewindng
0.34
56.5
800
100,402
0.27
59.2
640
127,899
LTII+FineTuning
0.34
55.9
800
198.658
0.27
57.9
640
130,146
GraSP
0.33
55.4
160
20,374
0.28
56.0
160
29,287
sanity
0.33
57.4
10,573
0.28
58.8
160
16,288
Continuous Sparsification
0.3
54.1
320
21,285
0.3
55.6
320
18,336
IMC-R MNC-Reenitialization
0.33
59.5
160
14,477
0.28
60.9
160
25,783
IMC-Rew MCC-eewidding
0.33
59.2
160
14,468
0.28
60.6
160
23,655
MCC-FineTuning
0.33
59.2
14,474
0.28
22,264
Table Sparsity with highest accuracy on ImageNet
Neural Network
ResNet-20
ResNet-32
Metric
Sparsity
Accuracy
Epoch
Runtime (s)
Sparsity
Accuracy
Epoch
Runtime (8)
Baseline
0
59.4
160
6hrs
0
60.0
160
8hrs
Flow&Prune
0.1
58.9
160
23,242
0.1
59.3
160
34,920
SNIP
0.1
55.7
160
28,972
0.1
55.7
160
28,972
SynFlow
0.33
56.6
160
17,990
0.1
56.2
160
29,062
L.TH-Reinttializtiinn
0.1
59.1
320
79,479
0.1
60.4
320
66,160
I.TH+Rewinding
0.1
58.7
320
40,219
0.1
320
65,455
LTH++FnnTTniig
0.1
58.0
320
79,661
0.1
60.5
320
65,979
GraSP
0.1
55.8
160
20,503
0.1
56.1
160
32,695
check
0.1
58.9
160
10,422
0.1
59.4
160
16,899
Continuous Sparsification
0.16
54.2
320
22,287
0.1
56.1
320
18,160
IMC-Reinitializatiin
0.33
59.5
160
14,477
0.28
60.9
160
25.783
MCC-ewiinding
0.33
59.2
160
14,468
0.28
60.6
160
23,655
IMC-FincTuning
0.33
59.2
160
14,474
0.28
60.7
160
22,264
Accuracy of pruned subnetworks with found sparsity by our IMC method. Tables D and ex- hibit the accuracy of pruned subnetworks obtained by thirteenth network pruning and LTH approaches with found sparsity by our IMC method two datasets. Baseline represents the accuracy achieved by the original unpruned neural networks. Since our IMC method executes a one-time pruning operation, the sparsity level generated by IMC is unique, e.g., 0.47 for ResNet-20 and 0.45 for ResNet-32 on CIFAR-IO. We compare all methods with the same sparsity level. The LTH approaches prune p% of the parameters in each round and thus may not prune the networks with the exact same sparsity level found by our IMC method. this case, we choose 0.47 for LTH+Rewinding with ResNet-32 on CIFAR- 10. It is observed among thirteenth comparison methods, with the same sparsity level, three variants of our IMC achieve the highest accuracy in all experiments, showing the effectiveness of IMC to the neural network pruning. Compared to the accuracy by the Baseline method, IMC, on average, achieves only 0.1% accuracy loss on CIFAR-10, and even gains 0.3% accuracy improvement ImageNet surprisingly.
closest sparsity level to prune the networks, say
Sparsity of pruned subnetworks with highest accuracy. Tables and present the sparsity of pruned subnetworks obtained by thirteenth methods with highest accuracy within range of sparsity levels on two datasets. Compared to the sparsity by other methods, under highest accuracy by pruned subnetworks, IMC, on average, improves sparsity for 32.5% and 18.6% on CIFAR-10 and ImageNet respectively. addition, even three variants our IMC method have the highest sparsity, the accuracy by them still better than most comparison methods in most experiments. The promising performance IMC over CIFAR-I0 and ImageNet datasets implies that IMC has great potential as general network pruning solution other image datasets, which is desirable in practice.
Ablation study. Tables also compares the accuracy over two datasets with three variants of our IMC model with different initialization and training strategies of pruned subnetworks. We have observed that three versions of IMC achieves similar accuracy (94.4-95.1) on CIFAR-10 and (59. 359.2-60.77 over ImageNet. The difference of the accuracy achieved by three versions, average, only 2.5% on CIFAR-10 and 5.5% over ImageNet respectively. reasonable explanation that IMC methods utilize the dynamical systems theory and inertial manifold theory analyze the

---

Table 5: Accuracy with varying training epochs
Neural Network
Accuracy
Renitiaeitall on CIFAR-I0
94.27 94.51 94.57 94.18 94.37
IMC- Mew-neein on CIFAR-10
94.15 94.43 94.29 94.69 94.74
IMC-Fine' FinciTuning on CIFAR-10
94.52 94.56 94.54 94.96 94.51
IMC-
ACCCReiitiaaliztionnn on ImageNet
59.22 59.51 59.35 58.70 59.28
IMC- MeC-Rewind on ImageNet
58,90 59.19 58.80 58.72 58.76
MMC-FineTTunue on ImageNet
58.67 59.53 59.42 58.74 58.56
IMC- Reinitialization on CIFAR- -
73.26 73.40 73.37 73.56 73.80
IMC- ReCC-enin on CIFAR-100
73.46
73.35 73.18
73.54 73.53
MMC--Fne on CIFAR-100 -00
73.58
73.17
73.43
73.23
74.22
Ascuracy 15
Acormny 72
50
So veattatt OFTR-IE
Arcia 90
Ba: -W Centttttati iragrageee
BMC
wew---eeedddgg inagelle
BMC
Sme Taaiia aniaeelle
So alaatii CIFG--113
85
HeIIC-Rewiiddy
Bal Frw Ci
Basciire
-10
Reiiks Soashr
10
Baseline 20
Rea Spankl
10
23
Esseiio
-10
Rsaave Sparate
Traning Epech af Nauta
25
(a) CIFARIO
(b) ImageNet
(c) CIFARI00
Figure 2: Accuracy with varying training epochs
Figure 1: Accuracy with varying sparsity levels
dynamics and inertial manifold structure of our gradient system, instead of manually-crafie pruning heuristics. The above rigorous mathematical analysis substantially decreases the impact of different initialization and training strategies of pruned subnetworks.
Running time. Tables I report the running time achieved by all comparison methods and three versions of our IMC over two dataset to produce pruned subnetworks respectively. Compared with pruning before training techniques, our IMC methods exchange the cost of reducing W to W+ with better sparsity and accuracy. Except pruning before training techniques, our IMC methods outperform all other types of network pruning and LTH techniques. Especially, our IMC methods show good efficiency for network pruning on ImageNet and only sanity-check presents better efficiency.
Impact of sparsity levels. Figure measures the performance effect of sparsity levels for network pruning by varying relative sparsity from -20 to 20. Relative sparsity 0 corresponds to the absolute sparsity level found by our IMC, say 0.47 on CIFAR-1O. The absolute sparsity is equal to the sum of the relative sparsity and the sparsity level found by our IMC, e.g., the absolute sparsity is equal to 0.15 + 0.47 for the relative sparsity 0.15 on CIFAR-IO. Although our IMC method executes one- time pruning operation with a single found sparsity level, in order to verify whether the found sparsity level the optimal, we measure the performance under different sparsity levels. The performance curves initially keeps stable when the sparsity increases. Later on, the performance curves decreases substantially when the sparsity continuously increases and is beyond the found sparsity level by our IMC. This validates the effectiveness of our inertial manifold-band network pruning for discovering the optimal sparsity level.
Impact of training epochs. Table and and Figure eggureeevallates the accuracy impact of training epochs on the original large networks. It observed that when changing training epochs, the accuracy of pruned subnetworks by the IMC model keeps relatively stable, i.e., the accuracy fluctuates within the range of less than 1% This shows the performance of pruned subnetworks insensitive the pre-training of the original networks. Especially, as shown in Table limited training of the original networks is enough to help capture the dynamics and inertial manifold structure of the gradient system, and thus produce good network pruning.
5 Conclusions
In this work, we have theoretically verified the validity of the LTH. First, we explored the possibility of theoretically lossless pruning as well as one-time pruning. Second, we utilized the inertial manifold theory to reduce the original high-dimensional system
oow-dimensional system. Finally, demonstrated the precondition and existence of pruned subnetworks and prune the original networks in terms of the gap in their spectrum that make the subnetworks have the smallest dimensions.
10

---

References
[1] M. Behnke and K. Heafield. Losing heads in the lottery: Pruning transformer attention in neural machine translation. In B. Webher, T. Cohn, Y. He, and Y. Liu, editors, Proceedings the 2020 Conference on Empirical Methods in Natural Language Processing. EMNLP 2020, Online, November 16-20, 2020, pages 2664-2674, Association for Computational Linguisties, 2020.
[2] H. Cai, Zhu, and S. Han. Proxylessnas: Direct neural architecture search on target task and hardware. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[3] X. Chang, Y. Li, S. Oymak, and C. Thrampoulidis, Provable benefits of overparameterization in model compression: From double descent to pruning neural networks. CoRR, abs/2012.08749, 2020.
[4] S. Chao, Z. Wang, Y. Xing, and G. Cheng. Directional pruning of deep neural networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[5] T. Chen, Frankle, Chang. S. Liu, Y. Zhang, Z. Wang, and M. Carbin. The lottery ticket hypothesis for pre-trained BERT networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[6] T. Chen, Y. Sui, X. Chen, A. Zhang, and Z. Wang. A unified lottery ticket hypothesis for graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[7] T. Chen, Z. Zhang, S. Liu, S. Chang, and Z. Wang. Long live the lottery: The existence of win- ning tickets in lifelong learning. In 9th International Conference Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[8] X. Chen, Z. Zhang, Y. Sui, and T. Chen. Gans can play lottery tickets too. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[9] E. A. Coddington and N. Levinson. Theory of Ordinary Differrntial Equations. McGraw-Hill, 1955.
[10] J. Deng, W. Dong, R. Socher, L. K. Li, and F. Li. Imagenet: A large-scale hierarchical image database. 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 248-255 248-255,77 2009,
[11] Diffenderfer and B. Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning A randomly weighted network. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings. 2021.
[12] U. Evei, Т. Gale, J. Menick, P. S. Castro, and E. Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2943-2952. PMLR, 2020.
[13] J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[14] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. The lottery ticket hypothesis scale. CoRR, abs/1 900./01031.11,,11 2019.
[15] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. Linear mode connectivity and the lottery ticket hypothesis. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 3259-3269, 2020.
11

---

[16] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. Pruning neural networks at initialization: Why are we missing the mark? In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedingss, 2021.
[17] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sandinia, Itlly, May 13-15, 2010, pages 249-256, 2010.
[18] J. Goodfellow, Y. Bengio, and A. C. Courville. Deep Learning. Adaptive computation and machine learning. MIT Press, 2016.
[19] J. K. Hale. Stability and gradient dynamical systems. Revista Matematica Complutense, 17(1): 7-57, 2004.
[20] S. Han, J. Pool, J. Tran, and W. J. Dally. Learning both weights and connections for efficient neural networks. CoRR, abs/1500.002626, 2015.
[21] S. Hayou, J.-F. Ton, A. Doucet, and Y. W. Teh. Robust pruning at initialization. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[22] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 1026-1034, 2015.
[23] Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 1398-1406, 2017.
[24) Y. He, G. Kang, X. Dong, Y. Fu, and Y. Yang. Soft filter pruning for accelerating deep convolutional neural networks. In Proceedings of the Twenty-Sevente International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 2234-2240, 2018
[25] Y. He. P. Liu, Z. Wang, Z. Hu, and Y. Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 4340-4349, 2019.
[26] N. M. Kalibhat, Y. Balaji, and S. Feizi. Winning lottery tickets in deep generative models. In Proceedings of the Thirty-Fifh AAAI Conference on Artificial Intelligence, AAAI 2021, 2021.
[27] M. Kang and B. Han. Operation-awart awwre soft channel pruning using differentiable masks. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, pages 5122-5131, 2020.
[28] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, 2009.
[29] A. Kusupati, V. Ramanujan, R. Somani, M. Wortsman, P. Jain, S. M. Kakade, and A. Farhadi. Soft threshold weight reparameterization for learnable sparsity. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 5544-5555, 2020.
[30] D. H. Le and B. Hua. Network pruning that matters: A case study on retraining variants. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[31] Y. Le Cun, J. S. Denker, and A. Solla. Optimal brain damage. In D. Touretzky, editor, Advances in Neural Information Processing Systems. Morgan Kaufmann, 1990.
[32] N. Lee, T. Ajanthan, and P. H. S. Torr. Snip: single-shot network pruning based on connection sensitivity. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
12

---

[33] N. Lee, T. Ajanthan, S. Gould, and P. H. S. Torr A signal propagation perspective for pruning neural networks at initialization. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[34] H. Li, A. Kadav, L. Durdanovic, H. Samet, and H. P. Graf. Pruning filters for efficient convnets. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[35] T. Lin, S. U. Stich, L. Barba, D. Dmitriev, and M. Jaggi. Dynamic model pruning with feedback. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[36] L. Liu, S. Zhang, Z. Kuang, J.-H. Xue, A. Zhou, X. Wang, Y. Chen, W. Yang. Q. Liao, and W. Zhang, Group fisher pruning for practical network compression. In Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[37] N. Liu, G. Yuan, Z. Che, X. Shen, X. Ma, Q. Jin, Ren, J. Tang, S. Liu, and Y. Wang. Lottery ticket preserves weight correlation: Is it desirable or not? In Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[38] Z. Liu, M. Sun, T. Zhou, G. Huang, and T. Darrell. Rethinking the value of network pruning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[39] X. Lu, H. Huang, W. Dong, X. Li, and G. Shi. Beyond network pruning: joint search- and-training approach. In Proceedings of the Twenty-Ninth International Joint Conference on A Artificial Intelligence, IJCAI 2020, pages 2583-2590, 2020.
[40] E. S. Lubana and P. Dick. A gradient flow framework for analyzing network pruning. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[41] J. Luo, J. Wu, and W. Lin. Thinet: A filter level pruning method for deep neural network compression. In IEEE International Conference on Computer Vision, ICCV 2017, Venice Italy, October 22-29, 2017, pages 5068-5076, 2017.
[42] E. Malach, G. Ychudai, S. Shalev-Shwart, and O. Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6682 6691. PMLR, 2020.
[43] R. Mehta. Sparse transfer learning via winning lottery tickets. CoRR, abs/1905.07785, 2019.
[44] A. S. Morcos, H. Yu, M. Paganini, and Y. Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1933-4943. 2019.
[45] L. Orseau, M. Hutter, and O. Rivasplata. Logarithmic pruning is all you need. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 62, 2020, virtual, 2020.
[46] A. Pensia, S. Rajput, A. Nagle, H. Vishwakarma, and D. S. Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over-parameterization is sufficient. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[47] Prasanna, A. Rogers, and A. Rumshisky. When BERT plays the lottery, all tickets are winning. In B. Webber, T. Cohn, Y. He, and Y. Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 3208 -229.. Association for Computational Linguistics, 2020.
13

---

[48] X. Qian and D. Klabjan. A probabilistic approach to neural network pruning. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[49] A. Renda, J. Frankle, and M. Carbin. Comparing rewinding and fine-tuning in neural network pruning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[50] J. Rosenfeld, J. Frankle, M. Carbin, and N. Shavit. On the predictability of pruning across scales. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, 2021.
[51] M. Sandler, A. G. Howard, M. Zhu, A. Zhmoginov, and L. Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages
2018.
[52] V. Sanh, T. Wolf, and A. M. Rush. Movement pruning: Adaptive sparsity by fine-tuning. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[53] P. Savarese, H. Silva, and M. Maire. Winning the lottery with continuous sparsification. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balean, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[54] J. Su, Y. Chen, T. Cai, T. Wu, R. Gao, L.. Wang, and D. Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[55] M. Tan, B. Chen, R. Pang. Vasudevan, M. Sandler, A. Howard, and Q V. Le. Mnasnet: Platform-aware neural architecture search for mobile. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 2820 2828, 2019.
[56] H. Tanaka, D. Kunin, D. Yamins, and S. Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[57] Y. Tang, Y. Wang, Y. Xu, D. Tao, C. Xu, C. Xu, and C. Xu. SCOP: scientific control for reliable neural network pruning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-1 2020, virtual. 2020.
[58] R. Temam. Inertial manifolds. The Mathematical Intelligencer, 12:68-74, 1990.
[59] C. Wang, G. Zhang, and R. B. Grosse. Picking winning tickets before training by preserving gradient flow. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[60] W. Wang, M. Chen, S. Zhao, L. Chen, J. Hu, H. Liu, D. Cai, X. He, and W. Liu. Accelerate cnns from three dimensions: A comprehensive pruning framework. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[61] Y. Wang, X. Zhang, L. Xie, J. Zhou, H. Su, B. Zhang, and X. Hu. Pruning from scratch. In The Thirty-Fourdy AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secondl Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, FAAI 2020, New York, NY, USA, February 7-12, 2020, pages 12273-12280 2020.
14

---

[62] W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural networks. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2074-2082, 2016.
[63] M. Wortsman, A. Farhadi, and M. Rastegari. Discovering neural wirings. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2680-2690, 2019.
[64] Y. Xu, Y. Li, S. Zhang, W. Wen, B. Wang, Y. Qi, Y. Chen, W. Lin, and H. Xiong- TRP: trained rank pruning for efficient deep neural networks. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 977-983, 2020.
[65] 7. Yao, A. Gholami, Q Lei, K. Keutzer, and M. W. Mahoney. Hessian-based analysis of large batch training and robustness to adversaries. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4954-4964, 2018
[66] 7. Yao, A. Gholami, K. Keutzer, and M. W. Mahoney. Pyhessian: Neural networks through the lens of the hessian, In IEEE International Conference on Big Data, Big Data 2020, Atlanta, GA, USA, December 10- 13, 2020, pages 581-590, 2020.
[67] Ye, X. Lu, Lin, and J. Z. Wang. Rethinking the corllle--oorm----------o in channel pruning of convolution layers. In 6th International Conference on Learning Rep- resentations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
assumption
[68] M. Ye, C. Gong, L. Nie, D. Zhou, A. Klivans, and Q Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 10820-10834 2020.
[69] M. Ye, L. Wu, and Q Liu. Greedy optimization provably wins the lottery: Logarithmic number of winning tickets is enough. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[70] H. You, C. P. Xu, Y. Fu, Y. Wang. X. Chen, Y. Lin, Z. Wang, and R. G. Baraniuk. Drawing early-bird tickets: Towards more efficient training of deep networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[71] H. Yu, S. Edunov, Y. Tian, and A. S. Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[72] Z. Zhang, X. Chen, T. Chen, and Z. Wang. Efficient lottery ticket finding: Less data is more. In Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[73] H. Zhou, J. Lan, R. Liu, and J. Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In H. M. Wallach, H. Larochelle, A. Beygelzimer, d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3592-3602. 2019.
[74] M. Zhu and S. Gupta. To prune, or not to prune: Exploring the efficacy of pruning for model compression. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 Muy 2018, Workshop Truck Proceedings, 2018
[75] D. G. Zill. A First Course in Differential Equations with Modeling Applications. Cengage Learning, 2012.
15


Reviews:
[{"review_id": "tybuQFx3jsp", "reviewer": "Reviewer_LUdR", "summary": "This work aims to theoretically verify the lottery ticket hypothesis and the existence of winning lottery tickets. Dynamical systems and inertial manifold theory are used.  Lots of mathematical proof and definitions are included in the papers, and experiments are conducted to test the performance of the proposed method. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Although the method is not explicitly defined, we can grasp some thoughts from line 267-line 271. The pruning method does not seem to resemble other current score-based pruning methods. They seem to address the problem with sub-space properties. Section 3.2 further shows the condition in Theorem 5 is satisfied and also gives an estimate to the Lipchitz constants. This is a novel and interesting work. \n\nMain questions:\n\n1. I was wondering if the author can provide a formal definition of the IMC method? An algorithm can be of great help for people to understand how IMC works. \n\n2. How to control the sparsity of the neural network with the IMC method or is it possible to control the sparsity level? If I understand the method correctly, the size of the pruned networks seems to be decided by $k$, and then $H(W^*)$. So how is the sparsity level controlled?\n\n3. Is it necessary to recover the complete form of $W$ after one finishes training $W^+$ for inference/test? The training process can be done on $W^+$ solely but I am not sure about the inference process. If yes, can the authors give hints on how to use $W^+$ only for inference?\n\n4. Not sure if it is appropriate to put related work in the supplementary files. \n\n5. Regarding Figure 2, I am curious to see the performance when the training epoch is smaller than 5. For example, is it possible to estimate $W*$ when only train 1 epoch?\n\n6. Can the author provide a visualization of sparsity masks?\n\n\n\nUpdate:\n\nThanks for the great efforts in addressing the questions. After reading all reviews and responses, I tend to accept this work and keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YhoFCY08MSj", "reviewer": "Reviewer_PBQY", "summary": "Summary: \n\nThe paper is dedicated to validating the lottery tickets hypothesis and delivering an effective one-time pruning. The authors investigate dynamical systems theory and inertial manifold theory to offer a theoretical justification. Specifically, they reduce the high-dimensional system of dense networks onto inertial manifolds to obtain a low-dimensional system regarding pruned subnetworks. Experiments on CIFAR and ImageNet with ResNet-18 and ResNet-32 validate the effectiveness of the proposal. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Pros. \n1. The authors provide pioneering works on the theoretical justifications of LTH.\n2. They formulate the problem as a gradient dynamical system. The idea is interesting, although within expectation.\n\nCons.\n1. The paper claim that they validate the LTH. I think it is overclaimed since the classical LTH contains two statements: 1.1 undamaged performance when trained from the same initialization; 1.2 fast convergence. The paper only discusses the first point.\n2. The author uses lots of paragraphs to describe the rationale of the formulation, which is great. However, they only describe the detailed methodology or implementation with a few sentences from lines 267-271. I am totally lost about what exact processes are adopted for pruning. For example, I have the following concerns: 2.1 does it only train 10 iterations to estimate the local optimal W* from W? 2.2 all network parameters are flattened to be the W? 2.3 the \"prune\" in line 270 means reduce W to W+?\n3. Although the author compared with diverse previous pruning methods, the experiments are still insufficient. 3.1 As the superior performance of LTH in extreme sparsity levels is the most surprising point of LTH, the authors do not show any extreme sparsity results such as more than 90%/95% sparsity. Table 1/2/3/4 only presents results with sparsity levels lower than 50%.\n4. No large model experiments like Res50.\n5. What is the detailed platform for report running time results? Since running time is super sensitive to the environment or other uncontrollable factors. Maybe use Meta Flops or Energy.\n6. I am very confused and suspicious of the SNIP/GraSP/SynFlow results in table 2. Based on Jonathan Frankle's paper (https://arxiv.org/abs/2009.08576), SNIP/GraSP/SynFlow pruned model with less than 10% sparsity should have almost undamaged performance compared to dense models. However, Table 2 shows that they suffer 1-2 point performance degradation.\n\nMinors.\n1. The statement in the abstract \"Such heuristic pruning strategies are hard to guarantee that the pruned networks achieve test accuracy comparable to the original dense ones\" can be more accurate. It should contain two conditions: a. extreme sparsity; b. hard to train from scratch not hard to fine-tune.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no limitations and potential negative societal impacts. The authors need to add extra discussion.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hrs"}, "extra_text": {}}, {"review_id": "JcfTT3eW126", "reviewer": "Reviewer_nEbX", "summary": "This theory paper uses Inertial manifolds theory to verify Lottery ticket hypothesis and the existence of winning lottery tickets, providing useful measures for requirements/scenarios for lossless pruning and one-time pruning. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "The paper is written clearly, and the connection between inertial manifolds theory, gradient dynamics and lottery ticket hypothesis appears to be original. I have not checked the analytics in supplementary materials extensively, but the optimal sparsity level found by inertial manifolds theory is empirically demonstrated in Fig 1, which appears to be a strong result. \n\nQuestions to the authors \n- Can you provide a pseudo-code and a sample code for computing the optimal sparsity? In the current text, it is unclear how to go from the dynamical theory to the numerical estimation of the optimal sparsity, which would be of great use to the rest of the community. \n- Are there insights on what determines the optimal sparsity from the theory? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have adequately addressed this issue. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "AHgzGtEOj-x", "reviewer": "Reviewer_3SRS", "summary": "The paper uses dynamical system theory and inertial manifold theory to validate the Lottery Ticket Hypothesis, that is, a randomly initialized dense network contains a sparse subnetwork that when trained from scratch, can achieve similar performance to the original dense network after comparable training epochs. They provided a method that in one iteration can find the smallest such subnetwork. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper first uses dynamical system theory and shows that there exists a unique global attractor $A$ of the gradient dynamical system corresponding to the gradient descent procedure. The global attractor contains all local minimum points of loss $L$. Then they introduce the inertial manifold of the dynamical system. The inertial manifolds enclose the global attracter. If the conditions in Theorem 5 hold, there exists an inertial manifold whose dimension is lower than the original space. The authors claim that the condition holds in the empirical data that they test. While the results and claims are impressive, I would like to see more discussion and theoretical justification.\n\n \nComments:\n\nIn stating the Lottery Ticket Hypothesis in section 2.1 on top of page 3, the notations need to be more clear, e.g. does iteration $i$ correspond to the initial state of $W$?\n\nCan the authors clarify if the $W^+$ is the same as the sparse subnetwork in LTH, in which many weights are set to be zero? $W^+$ may lie in a low-dimensional space, but why is it sparse?\n\nIt seems that there are many ways to convert the gradient flow to a semi-linear ODE. Can the authors clarify why they chose the particular way in equation (15)? \n \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to provide theoretical study and justification to the validity of the lottery ticket hypothesis, which indeed has recently been of great interest to the deep learning community. While one reviewer suggested the results or conclusion here are somewhat overclaimed, the work has generally been favorably received by most of the reviewers. The results provided here are somewhat expected, but nevertheless, it is good to see work done to properly derive and establish them. Further, in their responses the authors have addressed most (if not all) major reviewer concerns, and have subsequently also emphasized their commitment to implementing appropriate revisions in their manuscript. In total, three reviewers have scored above acceptance threshold (one outright accept and two marginally leaning to accept). The remaining reviewer has raised their score from reject to marginally below the threshold, but it is my impression that they would not object to the paper being accepted. Therefore, I agree with the majority of reviewers and also lean towards recommending to accept this paper.
Decision: Accept (Poster)