Validating the Lottery Ticket Hypothesis with Inertial Manifold Theory
Year: 2021

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.

heading: 1 Introduction
text: Deep learning techniques utilize the architecture of large model size and over-parameterization to achieve state-of-the-art performance in a wide range of applications [17, 18]. The performance improvements can be owed to the availability of large-scale neural networks and massive computational resources to train such complex models. However, large model size and extreme over-parameterization typically lead to high training cost, slow inference speed, and large memory consumption. This hinders the applicability of deep learning models in resource-intensive scenarios with the requirement of low latency and energy consumption, such as Internet of Things [2] and mobile computing [51, 55].
We have witnessed a large number of research advances in neural network pruning for reducing the time and space requirements of deep neural networks both at training and test time, with minimal loss in accuracy [31, 20, 34]. These techniques identify non-essential weights, filters, and other structures
∗Equal contributors †Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
from neural networks that do not contribute significantly to the model performance, and remove them for compressing original dense neural networks [49, 68, 52, 57, 3, 30, 35, 64, 39, 27, 29, 4, 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 to train a pruned network from scratch [20, 62, 34, 23, 41, 67, 49, 68, 52, 57, 3, 30, 74, 24, 25, 63, 35, 64, 39, 27, 29, 4, 40], although there are few pruning before training approaches [32, 61, 33, 56, 16, 21]. Thus, these methods still suffer from the non-trivial training cost on over-parameterized networks. Most importantly, traditional network pruning techniques are based on ad-hoc 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, a 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 subnetwork (i.e., a 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 training iterations [13, 14]. Compared with the original dense networks, the winning tickets are able to save a lot of memory for retraining [13, 73, 14, 15, 70, 42, 53, 11, 8]. The existence of winning tickets indicates that deep learning models can be trained in low-resource environments.
While the LTH techniques exhibit promising practical implications for scaling over large models and datasets, they fail to provide an efficient algorithm to 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 to 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 evidence to verify the LTH [71, 12, 1, 47, 69, 54, 5, 53, 26, 8, 7, 11]. In this case, it is difficult to 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?
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 manifoldsMW contain all local minimum points W ∗ of loss function L regarding W (i.e.,∇L(W ∗) = 0), we reduce the original high-dimensional gradient system ϕ onto inertial manifolds to obtain a low-dimensional system regarding W+, i.e., parameters of the winning ticket subnetwork. We demonstrate that there must exist suchMW 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-based method exhibits two unique advantages: (1) All local minimum points W ∗ lie inMW and thus W+ is theoretically lossless pruning of W . (2) The computation ofMW and W+ is a one-time operation, such that our method is able to 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 in Appendices A.3-A.5.

heading: 2 Background

heading: 2.1 Lottery Ticket Hypothesis
text: The Lottery Ticket Hypothesis (LTH) states that a randomly-initialized, dense neural network contains a subnetwork that is initialized such that, when trained in isolation, it can match the test accuracy of the original network after training for at most the same number of iterations [13, 14].
Given a dense neural network f(x;W ) with randomly-initialized weight parameters W = W0 ∈ Rd, when optimizing with stochastic gradient descent (SGD) on a training set, f reaches minimum loss L at iteration I with test accuracy a. A sparse subnetwork of f is denoted as f(x;M W ) using a binary pruning maskM ∈ {0, 1}d, ‖M‖0 d on its parameters such that its initialization isM Wi, where denotes the Hadamard product and Wi are the generated parameters of the original model f(x;W ) at iteration i. When optimizing with SGD on the same training set, f(x;M W ), where W is initialized with Wi, can be trained from M W to reach minimum loss L at commensurate iteration Ī with commensurate accuracy ā ≥ a to the original model f(x;W ). The LTH techniques often utilize an Iterative Magnitude Pruning (IMP) strategy to find winning tickets by gradually training the network and pruning its smallest-magnitude weights [13–15]. 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(x;W ) with weight parameters W = W0; (2) Train W of f for I iterations, generating updated parameters WI ; (3) Prune p% of the parameters with the smallest magnitude in WI , producing a mask M ; and (4) Reset the remaining weight parameters back to their initial values in W0, creating the winning ticket f(x;M W0).

heading: 2.2 Dynamical Systems Theory
text: In mathematics, an ordinary differential equation (ODE) is a 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(x(t)), x ∈ X (1)
where X is a Banach space and f : X → X is a function of x(t). The unknown function x(t) at time t appears on both sides of the differential equation. Definition 1. [Globally Lipschitz] f(x) is globally Lipschitz in X if there exists a constant K ≥ 0 for all x, y ∈ X , it holds ‖f(x)− f(y)‖X ≤ K‖x− y‖X , where K is the Lipschitz constant of f . Definition 2. [Global Solution of ODE] A solution x(t) : R→ X of the ODE in Eq.(1) is said to be global if x(t) exists for any t ∈ R. Lemma 1. If f(x) is globally Lipschitz in X , then the ODE in Eq.(1) has a unique global solution in X for any initial condition x(0) = x0 [9]. Definition 3. [Flow of ODE] ϕ : R × X → X , defined by ϕ(t, x0) = x(t) is the flow (i.e., solution map) of the ODE in Eq.(1) if ϕ(t, x0) is the unique solution of the ODE with initial condition ϕ(0, x0) = x(0) = x0. For any given initial value x0, the sets {ϕ(t, x0) : t ∈ R}, {ϕ(t, x0) : t ∈ R+}, {ϕ(t, x0) : t ∈ R−} are called the complete orbit, positive orbit, and negative orbit starting from x0, respectively.
In this work, we only consider the case of positive time and use the positive orbit starting from x. The orbit {ϕ(t, x0) : t ∈ {R+ ∪ 0}} of the flow is also called the trajectory of the point x under the flow. Definition 4. [Continuous Dynamical System] If a flow ϕ(t, x0) satisfies the following properties: • ϕ(s+ t, x0) = ϕ(s, x0)ϕ(t, x0) for any s, t ∈ R; • ϕ(t, x0) is continuous in x0 for any t ∈ R; • ϕ(t, x0) is continuous in t for any x0 ∈ X , then the flow ϕ(t, x0) 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 a mathematical concept that is used to describe the time dependence of a point’s position in its ambient space. Dynamical System Theory is a mathematical tool to capture long-time behavior of solutions. Definition 5. [Equilibrium of Dynamical System] A point x∗ is called an equilibrium of a dynamical system if ϕ(t, x∗) = x∗ for all t ∈ R, i.e., f(x∗) = 0.
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 ϕ if ϕ(t, A) ⊂ A for any t ≥ 0. That is, if a is an element of A then so is ϕ(t, a) for all t ≥ 0. A manifold is a 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 ⊂ Rn is an attractor that attracts a set B ⊂ Rn under a dynamical system ϕ if A is an invariant set under ϕ and
lim t→∞ dist(ϕ(t, B), A) = 0 (2)
where B denotes the basin of attraction for A. dist represents the Hausdorff semi-distance defined by
dist(B,A) = sup x∈B inf y∈A ‖x− y‖X (3)
An attractor is a 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, a finite set of points, a curve, a manifold, or even a complicated set with a fractal structure. lim
t→∞ dist(ϕ(t, B), A) = 0 implies that flows starting from
any point b ∈ B enter A in the limit t→∞. Definition 8. [Global Attractor of Dynamical System] A nonempty compact set A ⊂ X is a global attractor under a dynamical system ϕ if A is an invariant set under ϕ and A attracts all bounded sets B ⊂ X . A 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 dynamical system, the stable manifoldMs(x∗) of x∗ is a set of points in phase space if
Ms(x∗) = {x ∈ X : ϕ(t, x)→ x∗ as t→ +∞} (4)
and the unstable manifoldMu(x∗) of x∗ is a set of points in phase space if Mu(x∗) = {x ∈ X : ϕ(t, x)→ x∗ as t→ −∞} (5)

heading: 3 Validating the Lottery Ticket Hypothesis
text: The idea of this work is to reformulate gradient descent optimization of a neural network in Eq.(6) as a gradient system in Eq.(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 Eq.(6)) of the gradient dynamical system and theoretically validate the LTH. The gradient dynamical system has a 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 manifoldsMW 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 ontoMW to obtain a low-dimensional 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, it 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 ∗.

heading: 3.1 Neural Network Pruning
text: Traditional deep learning models often utilize gradient descent techniques to optimize neural networks and reach a local minimum of loss L. The gradient decent procedure is given below.
W (t+ 1) = W (t)− η∇L(W (t)) (6)
where W are the parameters of neural network, t is the iteration time, η is a learning rate, and L is the loss function. By starting from initial parameters W (0), the gradient decent procedure converges to a local minimum point W ∗ of L, i.e., ∇L(W ∗) = 0.
The above gradient decent procedure in Eq.(6) can be viewed as the numerical solution of an ODE system under classical Euler scheme. The sequence of W (0),W (1), · · · ,W ∗ in the gradient descent process in Eq.(6) corresponds to discrete points on the orbit of the following ODE.
W ′(t) = −∇L(W (t)) (7)
W ∗ is an equilibrium (i.e., a time-independent solution) of the ODE system. The ODE in Eq.(7) is a gradient system, since the vector field −∇L(W ) is the gradient of L. The dynamical system derived by (7) is a gradient dynamical system, where the loss is decreasing along the solution of the equation.
d dt L(W (t)) = ∇L · dW (t) dt = −|∇L(W (t))|2 ≤ 0 (8)
This is the reason why the gradient descent method works for the optimization of 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.(6) lie in A of the system by (7). Theorem 1. The global attractor A of the dynamical system derived by Eq.(7) is the union of equilibria W ∗ and their unstable manifoldsMu(W ∗) [19]. Since the equilibria W ∗ are the time-independent solutions of our gradient dynamical system, they correspond to the local minimum points of L of the original neural network in Eq.(6). Theorem 2. The global attractor A of the dynamical system derived by Eq.(7) is unique. Theorem 3. Let A ⊂ W be a compact subset of a Banach spaceW , and W (t) ∈ W be a sequence with limt→∞ dist(W (t), A) = 0, then W (t) has a convergent subsequence, whose limit lies in A. Theorem 4. The global attractor A of the dynamical system derived by Eq.(7) is the maximal compact invariant set, and the minimal set that attracts all bounded sets B ⊂ W . Please refer to Appendix A.2 for detailed proof of Theorems 1-3. In mathematics, inertial manifolds are concerned with the long-term behavior of the solutions of dynamical systems [58]. Inertial manifolds are finite-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 to derive the dynamics of the original gradient system. Definition 10. [Inertial Manifold of Dynamical System] Let W be a Banach space, an inertial manifoldMW for a dynamical system is a smooth manifold such that • MW is of finite dimension; • The flow ϕ(t,MW ) ⊂MW for any t ≥ 0; • There exist two constants C1, C2 > 0, such that for any initial condition W (0) ∈ W , it holds
dist(ϕ(t,W (0)),MW ) ≤ C1e−C2tdist(W (0),MW ) (9)
Since all solutions of Eq.(6) eventually converge to the inertial manifoldMW and all local minimum points W ∗ of L of the original neural network in Eq.(6) locate onMW , it would be sufficient to work on the inertial manifoldsMW directly for discovering W ∗. Theorem 5. LetW be a Banach space with dimension d, given a semi-linear ODE
W ′(t) = AW (t) + f(W (t)), W (t) ∈ W (10)
where A is a d× d matrix and f :W →W . The spectrum of A is denoted as follows. λ1 ≤ λ2 ≤ · · · ≤ λd (11)
Assuming that f(0) = 0, let K be the Lipschitz constant of f(x), that is,
‖f(x)− f(y)‖W ≤ K‖x− y‖W for any x, y ∈ W (12)
If there exits an integer k, such that λk+1 − λk > 4K, letW+ be the generalized eigenspace for λk+1, . . . , λd andW− be the generalized eigenspace for λ1, . . . , λk, then there exists an inertial manifoldMW as follows.
MW = (W+, h(W+)) (13)
where h is a mapping fromW+ toW−. Please refer to Appendix A.2 for detailed proof of Theorem 5.
Theorem 5 demonstrates the whole solution spaceW can be decomposed into two subspacesW+ andW− when the gap between arbitrary two consecutive eigenvalues in the spectrum of A is larger than 4K. An inertial manifoldMW can be constructed as the graph of a mapping h :W+ →W−. Consequently, the dynamics onMW can be described by the projected dynamics inW+ through the mapping h, andW− is redundant. When there are multiple integers k satisfying λk+1 − λk > 4K, we choose the largest k to cutMW , such thatW+ has the smallest dimensions, i.e., the best pruning. In order to utilize the conclusion of Theorem 5 to prune the network parameters W in Eq.(6), we leverage linearization-around-fixed-points technique in dynamical systems theory to transform the gradient system in Eq.(7) into an equivalent semi-linear ODE system as follows.
U(t) = W (t)−W ∗ (14)
For ease of presentation, we use symbols U and W to replace U(t) and W (t). Then we have
U ′ = −H(W ∗)U − ( ∇L(U +W ∗)−H(W ∗)U ) = −H(W ∗)U + F (U) (15)
where H(W ∗) denotes the Hessian matrix of loss function L evaluating at W ∗ and F (U) is equal to − ( ∇L(U +W ∗)−H(W ∗)U ) .
The advantage of such linearization-around-fixed-points technique is to make the nonlinear term F (U) satisfy F (0) = 0 since ∇L(W ∗) = 0. Notice that the assumption for nonlinear term f(W (t)) in Theorem 5 is f(0) = 0. The above linearization-around-fixed-points technique allows to leverage the conclusion of Theorem 5 for lossless neural network pruning.
Compared with the system about original parameters W in Eq.(10), Eq.(15) is a semi-linear ODE system regarding converted parameters U . The corresponding inertial manifoldMU is given below.
{MU = (U+, h(U+)) : U+ ∈ U+} (16)
where U+ is a corresponding subspace.MU is an invariant manifold, that is, for any solution U(t) of the ODE system, if U(0) ∈ MU , then U(t) ∈ MU for any t ≥ 0. Moreover,MU contains all local minimum points. U+ is a lossless pruning of U according to the conclusion of Theorem 5.
Thus, the corresponding inertial manifoldMW for the gradient system in Eq.(7) is given as follows.
MW = W ∗ +MU = {(W+,W−) : U+ ∈ U+} (17)
where W+ = U+ +W ∗+ and W− = h(U+)+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 as a function ofW+: W− = h(U+)+W ∗− = h(W+−W ∗+)+W ∗−. We denote this function as g, i.e., W− = g(W+).
The dynamics of the gradient system in Eq.(7) is governed byMW = (W+, g(W+)). The system in Eq.(7) can be reduced ontoMW . The neural network and the loss function onMW are given below.
f̄(W+) = f ( W+, g(W+) ) = f(W ), L̄(W+) = L ( W+, g(W+) ) = L(W ) (18)
where f and f̄ represent the original and pruned neural networks respectively. The reduced gradient system onMW is given as follows.
dW+
dt = −∇L̄(W+) = −∇W+L
( W+, g(W+) ) −∇W−L ( W+, g(W+) ) ∇g(W+) (19)
As all local minimum points lie inMW , the reduced problem in Eqs.(18) and (19) work equally well as the original one in Eq.(7). This indicates that using the low-dimensional parameters W+ ∈ Rd−k to train f̄ is sufficient to obtain the same performance as training f with the original high-dimensional parameters W ∈ Rd. 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 a scalable Hessian computation method to calculate an approximateH(W ∗) [65, 66]. We prune the original network with parameters W to generate a subnetwork with parameters W+ and train the latter until convergence.

heading: 3.2 Estimation of Lipschitz Constant
text: In order to leverage the conclusion of Theorem 5 to compress the parameters W of neural networks in Eq.(6), we need to verify whether its condition is satisfied and thus we need to estimate the Lipschitz constant of the nonlinear term F (U) in Eq.(15).
Let B be the l∞-upper bound of U , i.e., ‖U‖∞ ≤ B, by utilizing the Mean Value Theorem, we get F (U1)− F (U2) =∇L(U1 +W ∗)−∇L(U2 +W ∗)−H(W ∗)(U1 − U2)
= [ H ( W ∗ + U1 + θ1(U2 − U1) ) −H(W ∗) ] (U1 − U2)
=(U1 − U2)T∇H ( W ∗ + U1 + θ2(U2 − U1) ) (U1 − U2)
(20)
where 0 ≤ θ1, θ2 ≤ 1 are two constants. By employing the Hölder Inequality, we have
‖F (U1)− F (U2)‖p ≤ ‖∇H ( W ∗ + U1 + θ2(U2 − U1) ) ‖p‖U1 − U2‖2∞, 1 ≤ p ≤ +∞ (21)
As ‖U‖∞ ≤ B, ‖U1 − U2‖∞ ≤ 2B. In addition, ‖U1 − U2‖∞ ≤ ‖U1 − U2‖p. Thus, we have ‖F (U1)− F (U2)‖p ≤ 2B‖∇H ( W ∗ + U1 + θ2(U2 − U1) ) ‖p‖U1 − U2‖p (22)
Therefore, the Lipschitz constant of F (U) in lp space is 2B‖∇H ( W ∗ + U1 + θ2(U2 − U1) ) ‖p.
For ease of presentation, we use a symbol V to replace W ∗ + U1 + θ2(U2 − U1). Since 2B is a constant for a given U , we only need to estimate ‖∇H(V )‖p. Based on the Second Derivative Formula, the estimation of ‖∇H(V )‖p is given as follows.
‖∇H(V )‖p ≈ ∥∥∥∥∇L(V + ∆M/‖M‖p)− 2∇L(V ) +∇L(V −∆M/‖M‖p)∆2 ∥∥∥∥ p
(23)
where ∆ refers to corresponding change of V .
In our implementation, we choose p = 2 and ∆ = 0.01. A is a randomly-generated matrix with the same dimension as V . In the current experiments, the estimated Lipschitz constants of all neural networks are very tiny with order 10−12. This implies that our neural network pruning technique has great potential as a general pruning solution to other neural networks, which is desirable in practice.

heading: 3.3 Algorithm
text: 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 f(x;W ) with randomlyinitialized flattened weight parameters W = W0 ∈ Rd, when optimizing W with stochastic gradient descent (SGD) on a training set, we generate an approximate W ∗ in few training iterations (10 iterations in our implementation), where W ∗ is a local minimum point of loss function L regarding W in Eq.(6) (i.e.,∇L(W ∗) = 0). Notice that W ∗ is also an equilibrium of the gradient dynamical system in Eq.(7); (2) Based on the transformation U = W −W ∗ from W to U through the above approximate W ∗ in Eq.(14), we transform the gradient dynamical system in Eq.(7) into a semi-linear ODE system U ′ = −H(W ∗)U + F (U) in Eq.(15), where H(W ∗) denotes the Hessian matrix of loss function L evaluating at W ∗ and F (U) is equal to − ( ∇L(U + W ∗) − H(W ∗)U ) ; (3) We employ a scalable Hessian computation method to calculate an approximate −H(W ∗) [78, 79]. We calculate the spectrum of −H(W ∗) and sort its eigenvalues as λ1 ≤ λ2 ≤ · · · ≤ λd; (4) We estimate the Lipschitz constant K of the nonlinear term F (U) in Eq.(15) based on Eqs.(22) and (23); (5) We check pairwise consecutive eigenvalues in descending order, i.e., λd and λd−1, λd−1 and λd−2, · · · , and λ2 and λ1. When finding the first k satisfying λk+1 − λk > 4K, we partition U ∈ Rd into U+ ∈ Rd−k and U− ∈ Rk and split W ∈ Rd into W+ ∈ Rd−k and W− ∈ Rk; and (6) We prune the original network with high-dimensional parameters W ∈ Rd to generate a subnetwork with low-dimensional parameters W+ ∈ Rd−k, i.e., reduce W to W+, and train W+ until convergence.

heading: 4 Experimental Evaluation
text: In this section, we have evaluated the effectiveness of our IMC model and other baselines for neural network pruning over three standard image classification datasets: CIFAR-10 [28], CIFAR-100 [28],
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, 59, 15, 53, 69, 11].
Baselines. We compare the IMC model with nine state-of-the-art models, including three network pruning and six LTH approaches. Flow&Prune is a 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 a given network once at initialization prior to training [32, 56]. LTH+Reinitialization is the original LTH method, which randomly sample a new initialization for winning tickets’ initialization [13]. LTH+Rewinding rewinds unpruned weights to their values from earlier in training and retrains them from there using the original training schedule [15]. LTH+FineTuning fine-tunes the pruned model to regain the lost performance, instead of training it from scratch [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 whether the architecture of the pruned subnetwork are essential for the final performance [54]. Continuous Sparsification searches for sparse networks based on an approximation of an intractable l0 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 of 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-Reinitialization randomly sample a new initialization for winning tickets’ initialization [13], IMC-Rewinding rewinds unpruned weights to their values from earlier in training and retrains them from there using the original training schedule [15], and IMC-FineTuning fine-tunes the pruned subnetworks to regain the lost performance [38].
Evaluation metrics. We evaluate the 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. A larger sparsity indicates a better pruning.
Accuracy of pruned subnetworks with found sparsity by our IMC method. Tables 1 and 3 exhibit the accuracy of pruned subnetworks obtained by thirteenth network pruning and LTH approaches with found sparsity by our IMC method on 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-10. 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. In this case, we choose the closest sparsity level to prune the networks, say 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 on ImageNet surprisingly.
Sparsity of pruned subnetworks with highest accuracy. Tables 2 and 4 present the sparsity of pruned subnetworks obtained by thirteenth methods with highest accuracy within a 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. In addition, even if three variants of our IMC method have the highest sparsity, the accuracy by them are still better than most comparison methods in most experiments. The promising performance of IMC over CIFAR-10 and ImageNet datasets implies that IMC has great potential as a general network pruning solution to other image datasets, which is desirable in practice.
Ablation study. Tables 1- 4 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 the similar accuracy (94.4-95.1) on CIFAR-10 and (59.2-60.7) over ImageNet. The difference of the accuracy achieved by three versions, on average, is only 2.5% on CIFAR-10 and 5.5% over ImageNet respectively. A reasonable explanation is that our IMC methods utilize the dynamical systems theory and inertial manifold theory to analyze the
Table 5: Accuracy with varying training epochs
Neural Network Accuracy IMC-Reinitialization on CIFAR-10 94.27 94.51 94.57 94.18 94.37 IMC-Rewinding on CIFAR-10 94.15 94.43 94.29 94.69 94.74 IMC-FineTuning on CIFAR-10 94.52 94.56 94.54 94.96 94.51 IMC-Reinitialization on ImageNet 59.22 59.51 59.35 58.70 59.28 IMC-Rewinding on ImageNet 58.90 59.19 58.80 58.72 58.76 IMC-FineTuning on ImageNet 58.67 59.53 59.42 58.74 58.56 IMC-Reinitialization on CIFAR-100 73.26 73.40 73.37 73.56 73.80 IMC-Rewinding on CIFAR-100 73.46 73.35 73.18 73.54 73.53 IMC-FineTuning on CIFAR-100 73.58 73.17 73.43 73.23 74.22
Baseline−20 −10 −5 0 5 10 20
85
90
95
Relative Sparsity
A c c u ra
c y
IMC−Reinitialization IMC−Rewinding IMC−FineTuning
(a) CIFAR10
Baseline−20 −10 −5 0 5 10 20
50
55
60
Relative Sparsity
A c c u ra
c y
IMC−Reinitialization IMC−Rewinding IMC−FineTuning
(b) ImageNet
Baseline−20 −10 −5 0 5 10 20
65
70
75
Relative Sparsity
A c c u ra
c y
IMC−Reinitialization IMC−Rewinding IMC−FineTuning
(c) CIFAR100
Figure 1: Accuracy with varying sparsity levels 5 10 15 20 25
50
60
70
80
90
Training Epoch of Original Neural Networks
A c c u
ra c y
IMC−Reinitialization on CIFAR−10 IMC−Rewinding on CIFAR−10 IMC−FineTuning on CIFAR−10 IMC−Reinitialization on ImageNet IMC−Rewinding on ImageNet IMC−FineTuning on ImageNet IMC−Reinitialization on CIFAR−100 IMC−Rewinding on CIFAR−100 IMC−FineTuning on CIFAR−100
Figure 2: Accuracy with varying training epochs
dynamics and inertial manifold structure of our gradient system, instead of manually-crafted pruning heuristics. The above rigorous mathematical analysis substantially decreases the impact of different initialization and training strategies of pruned subnetworks.
Running time. Tables 1- 4 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 1 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-10. 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-10. Although our IMC method executes a onetime pruning operation with a single found sparsity level, in order to verify whether the found sparsity level is 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-based network pruning for discovering the optimal sparsity level.
Impact of training epochs. Table 5 and Figure 2 evaluates the accuracy impact of training epochs on the original large networks. It is 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 is insensitive to the pre-training of the original networks. Especially, as shown in Table 5, limited training of the original networks is enough to help capture of the dynamics and inertial manifold structure of the gradient system, and thus produce a good network pruning.

heading: 5 Conclusions
text: 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 to a low-dimensional system. Finally, we 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.

Review summaries:
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.  

Summary:   The 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.