An Operator Theoretic View On Pruning Deep Neural Networks
Authors: William T Redman
MARIA FONOBEROVA
Ryan Mohr
Yannis Kevrekidis
Igor Mezic
Venue: ICLR 2022 Poster (2022)
Keywords: deep neural network pruning
Koopman operator theory

Abstract: The discovery of sparse subnetworks that are able to perform as well as full models has found broad applied and theoretical interest. While many pruning methods have been developed to this end, the naïve approach of removing parameters based on their magnitude has been found to be as robust as more complex, state-of-the-art algorithms. The lack of theory behind magnitude pruning's success, especially pre-convergence, and its relation to other pruning methods, such as gradient based pruning, are outstanding open questions in the field that are in need of being addressed. We make use of recent advances in dynamical systems theory, namely Koopman operator theory, to define a new class of theoretically motivated pruning algorithms. We show that these algorithms can be equivalent to magnitude and gradient based pruning, unifying these seemingly disparate methods, and find that they can be used to shed light on magnitude pruning's performance during the early part of training.

Published as a conference paper at ICLR 2022
AN OPERATOR THEORETIC VIEW ON PRUNING DEEP NEURAL NETWORKS
William T. Redman
Maria Fonoberova & Ryan Mohr
AIMdyn Inc. UC Santa Barbara
AIMdyn Inc. {m (mfonoberova, mohrr)eaiimae iiddindn.... com
W wredman@ucsb.. edu
Toannis G. Kevrekidis Johns Hopkins University yannisk sinkikkrr (akkkjjuuu fdu
Igor Mezić AIMdyn Inc. UC Santa Barbara me i cuuccb. edu
ABSTRACT
The discovery of sparse subnetworks that are able to perform as well full mod- els has found broad applied and theoretical interest. While many pruning methods have been developed to this end, the naïve approach of removing parameters based on their magnitude has been found to be robust as more complex, state-of-ther art algorithms. The lack of theory behind magnitude pruning's 's success, especially pre-convereence, and its relation to other pruning methods, such as gradient based pruning, are outstanding open questions in the field that are in need of being ad- dressed. We make of recent advances in dynamical systems theory, namely Koopman operator theory, to define a new class of theoretically motivated prun- ing algorithms. We show that these algorithms can be equivalent to magnitude and gradient based pruning, unifying these seemingly disparate methods, and find that they can be used shed light on magnitude pruning" performance during the early part of training.
INTRODUCTION
surprising, but well-replicated, result in the study of deep neural network (DNN) optimization is that it is often possible to significantly "prune" the number of parameters after training with little effect on performance (Janowsky] 1989 Mozer & Smolensky, 1989a b LeCun et al. 1989 Karnin 1990 Han et al. 2015; Blalock et al. 2020). Because DNNs have become increasingly large and require considerable storage, memory bandwidth, and computational resources (Han et al.) 2015), finding reduced form is desirable and has become an area of major research. In addition to the practical considerations, DNN pruning has become of theoretical interest, as the search for subnet- works that can be pruned with minimal effect on performance led to new insight on the success of large DNNs, via the development of the Lottery Ticket Hypothesis (LTH) (Frankle & Carbin 2019)] Frankle et al., 2020). A considerable body of literature has been devoted expanding. interrogating. and critiquing the LTH, furthering the understanding of sparse DNNs.
While many different methods exist for choosing which parameters to prune, including ones that take into account the gradient and the Hessian of the loss function (LeCun et al.) 1989; Hassibi Stork 1993] Yu et al., 2018: Lee al., 2019 2020), the simple approach of pruning based on a global threshold of parameters' magnitudes has been found to be robust and competitive with more complicated, state-of-the-art methods (Blalock et al. 2020). In addition, early work on the LTH found that magnitude pruning could be successfully performed early during training (although, iteratively pruning based on magnitude was found to yield considerably better results) (Frankle & Carbin 2019). Subsequent research has related the point in training time when iterative magnitude pruning can be successfully applied to a phenomenon known as "linear mode connectivity" (Frankle) et al. 2020 However, why magnitude pruning does not work before the emergence of linear mode

---

Published as a conference paper at ICLR 2022
connectivity, is not well understood. Therefore, there is need develop new, theoretically driven tools for studying magnitude pruning, especially pre-convergence (Frankle et al. 2021).
DNN training can be viewed as discrete dynamical system, evolving the associated parameters along a trajectory. Despite the fact that this perspective is familiar (indeed, it is often taught in intro- ductions to gradient descent), the complex dependence of the trajectory on the choice of optimization algorithm, architecture, activation functions, and data has kept dynamical systems theory from pro- viding much insight into the behavior of DNNs. However, the recent development of Koopman operator theory (Koopman 1931 Koopman & Neumann] 1932 Mezić 2005 BudiSić et al. 2012).
a rigorous, data-driven framework for studying nonlinear dynamical systems, has been successfully applied to DNNs and machine learning, more generally (Dietrich et al. [2200] [Dogra & Redman 2020
Tano et 2020 Manojlović al. 2020; Mohr al. 2021: Naiman Azencot 2021).
This recent success motivated us to ask whether we could leverage Koopman operator theory to pro- vide insight into the pruning of DNNs. We first made use of Koopman methods define a new class of pruning algorithms. One method in this class, which we refer to as Koopman magnitude pruning, shown to be equivalent to magnitude pruning at convergence. Early during training, we again find that the two methods can be equivalent. The dynamical systems perspective afforded by Koopman pruning allows us to gain insight into the parameter dynamics present when the equivalence holds and when it does not. We find that the breaking of the equivalence occurs at similar time that non-trivial structure emerges within the DNN. Finally, we extend our work beyond magnitude based pruning, showing that gradient pruning is equivalent to another form of Koopman pruning. Thus, the Koopman framework unifies magnitude and gradient pruning algorithms. Our contributions are the following:
A new class of theoretically motivated pruning methods;
New insight on how training dynamics may impact the success (or lack thereof) of magni- tude pruning pre-convergence:
A unifying framework for magnitude and gradient based pruning.
2 KOOPMAN OPERATOR THEORY BASED PRUNING
Koopman operator theory is a dynamical systems theory that lifts the nonlinear dynamics present in a finite dimensional state space, to an infinite dimensional function space, where the dynamics are linear (Koopman 1931: Koopman& & Neumann 1932 Mezić 2005). While gaining an infinite number ddimensions would appear to make the problem intractable, numerical methods have been developed over the past two decades to find good finite dimensional approximations of the relevant spectral objects (Mezić & Banaszuk] 2004 Mezić 20055) Rowley et al.] 22099) [Schmid] 2010: Tu et al. 20144] Williams et al.J 2015] Mezic 2020). Given the powerful and interpretable tools that exist for studying linear systems, Koopman operator theory has found success in a number of applied settings. Below we discuss the basics of Koopman mode decomposition. key element of Koopman operator theory, and use it to motivate a new class of pruning algorithms. We broadly refer to these methods Koopman based pruning. For more details Koopman operator theory, refer the interested reader to Budišić et al. (2012).
2.1 KOOPMAN MODE DECOMPOSITION
The central object of interest in Koopman operator theory is the Koopman operator, U, an infinite dimensional linear operator that describes the time evolution of observables (i.e. functions of the underlying state space variables) that live in the function space F. That is, after t > 0 amount of time, which can be continuous or discrete, the value of the observable g F, which can be scalar or vector valued function, is given by
U (p() = (T)]
(1)
Here is the nonlinear dynamical map evolving the system and p is the initial condition or location in state space. In the case of training DNN, T is determined by the choice of optimization algorithm and its associated hyperparameters (c.g. learning rate), architecture, activation functions, and order in which the training data is presented. If the optimizer is (a variant of) stochastic gradient descent,
2

---

Published as a conference paper at ICLR 2022
then each epoch will have its own T, since the dynamic map depends the ordering of the training data (see Sec. 2.3). The DNN parameter values that are set at initialization, (()). are the associated initial condition [i.e. p {()]]. The observable. 9, could be chosen to be the identity function or some other function that might be relevant to a given DNN, such as its loss or gradient. However, note that Eq. 1 must hold for all 9 E F. For the remainder of the paper, it will be assumed that the state space being considered is of finite dimension, and that F is the space of square-integrable functions.
The action of the Koopman operator on the observable can be decomposed as
R
Ug(p) = Σ (poi
i=0
where the d; are eigenfunctions of U. with X; C as their eigenvalues and v; their Koopman
modes (Mezić) 2005). The decomposition of Eq. iis called the Koopman mode decomposition.
The Koopman mode decomposition is powerful because, for discrete dynamical system, the value of g at I E N time steps in the future is given by
B (T' = =U' U'g(p)= = Σ (o)
2=0
From Eq. 3 we see that the dynamics of the system in the directions va, scaled by (p),, are given by the magniude of the corresponding Aς. Assuming that A S for all i, finding the long time behavior of y amounts to considering only the (x());; whose A R 1.
Given that the Koopman operator is linear, and it is known that even simple DNNs can have pa- rameters that exhibit nonlinear dynamics (Saxe et al.] 2014), it may seem that applying Koopman methods to the training of DNNs is an over simplification. However, the Hartman-Grobman The- orem, a foundational result in dynamical systems theory, guarantees local neighborhoods around hyperbolic fixed points where the linearization captures the dynamical properties of the full, nonlin- system (i.e. the two conjugate) (Wiggins 2003). Additional work by Lan & Mezić (2013) extended the neighborhood where this conjugacy holds to the entirety of the basin. Therefore, as long the DNN is in a basin of attraction of some fixed point,
assume that the Koopman mode decomposition will provide an accurate representation to the true, nonlinear dynamics.
There exist number of different methods for computing the Koopman mode decomposition. While they differ in their assumptions on the dynamics of the system, they are all data-driven and re- quire multiple snapshots of some g. In the case of DNN training, we can take y be the identity function, and collect T + 1 column vectors of the values the DNN parameters, 6, each taken at different training step. That is. to compute the Koopman mode decomposition, the data matrix D (0(0), (()), ((r)] E R Nx(++1) must be constructed. For more details the method used in this paper to compute the Koopman modes, and its computational demands, see Appendix A
2.2 KOOPMAN BASED PRUNING
Any combination of DNN optimizer, architecture, activation function, and ordering of training data has an associated Koopman operator, U, which governs the flow of DNN parameters during training. This Koopman operator, turn, has various directions along which the flow exponentially grows and shrinks (i.e. the (())vv))
Previous work has shown that, over non-trioee non-trivial window of training, approximations of the Koop- man operator can well capture weight and bias dynamics (Dogra & Redman 2020 Tano et al.) 2020), suggesting that the Φbs [0(0)] v, may be useful for pruning. If we order the modes by the real part of their cigenvalues, i.c. re(Ai) > re(A2) ... re(AR), and assume that A₁ 1 (a reasonable assumption in the case of stable dynamical systems, which we find corroborated in our experiments below), then &1 [0(0)] corresponds to the predicted fixed point of training. That is, the first mode identifies the parameter values that the DNN would take after training reached convergence. All ad- ditional modes would identify parameters that experienced increasingly larger exponential decays.
If on [0()) is accurate in its approximation of the fixed point, then pruming parameters based on their magnitude in & (0(0)) could prove to be beneficial. We refer this Koopman magnitude
3

---

Published as a conference paper at ICLR 2022
Algorithm 1 General form of Koopman based pruning.
1. Construct the data matrix D (8(0), ((1), (()) from snapshots of the parameter values 0 during training.
2. Compute the Koopman mode decomposition from to obtain R Koopman triplets. (A4, 6s. vz).
3. Use a scoring function, s. that is a function of (As, Φs. vt). to create pruning mask, m, that compresses the network by an amount c. In the case of KMP, s(0, )i, Pi v:)
Φb [ assuming that X = 1.
4. Create the pruned DNN, [(; o m).
pruning (KMP) to denote its similarity to global magnitude pruning (GMP), a popular and robust approach to pruning (Blalock et al., 2020). We make this connection explicit in Section 3.
Alternatively, the exponentially decaying modes, i.e. (2(0( da (o()))....... might be expected to convey information about which parameters are most coherently dynamic. We refer to the strategy that prunes parameters based on their magnitude in these modes as Koopman gradient pruming (KGP) to denote its similarity to gradient pruning. We make this connection explicit in Section 5.
These algorithms, KMP and KGP, are two of many possible realizations of pruning based on the Koopman mode decomposition. For example, KMP can be easily extended layer magnitude pruning, by splitting Φ [6(0)]r into subvectors and pruning each layer based on thresholds com- puted from each subvector. [ggorithm[prrovddeee that we follow standard practice in the pruning literature and denote a DNN by f(x; 0), where x its input and 0 is its N parameters. The goal of pruning is find mask, m E {0, 1) such that the accuracy of f(:; 0 @ m) is comparable to the original DNN. Here @ denotes element-wiss multiplication. To determine which parameters to prune (i.e. which m; 0), a scoring function, s, is used. In the case of GMP, a(0,) = [0.|. The DNN is compressed an amount by keeping only the 100 % of parameters with the largest scores. If 4, then only the parameters with scoring function a
general form for Koopman based pruning. Note
values that are in the top 25% are kept.
2.3 KOOPMAN OPERATOR'S 'S DEPENDENCE ON ORDER OF TRAINING DATA
As noted above, the dynamical map involved in training DNN, T, is dependent on the choice of optimizer, architecture, activation function, and order in which the training data is presented. Given that the action of the Koopman operator is related to T via Eq. 1 the Koopman mode decomposition must also be dependent on these quantities. In the experiments that are performed in the remainder of this paper, optimizer, activation function, and architecture will be fixed ahead of time. However, because we made use of SGD, the ordering of the training data, referred to in some literature as "SGD noise" (Frankle et al. 2020), will vary epoch to epoch.
A consequence of this is that, at each epoch, the dynamical system being considered will change, as the mapping from ((t) (( 1) will depend on which subset of training data is shown training iteration f. Note that it will also depend on the batch size (i.c. what fraction of the training data is shown before updating 0), however this will also fixed in the experiments we perform. While Koopman operator theory has been extended to random and non-autonomous dynamical systems (Maéešić et al., 2018 Čmjarić-Zic et al. 2020). we can view the training over the course of an epoch as deterministic process, by fixing ahead of time the ordering of the training data. For the remainder of this paper, we will be computing the Koopman mode decomposition for each epoch by using only the parameter evolution data from that epoch.
The impact that SGD noise has on DNN has been found to depend on the amount of training (Fran- kle et al., 2020). Near initialization, two copies of the same DNN trained on different orderings of the data lead convergence on different local minima, whose linear path sees "hill" (i.e. increase) of testing error. This suggests that they are in different parts the loss landscape. However, with increased training, SGD noise brings the two copies of the DNN to the same "valley", where their linear path has no significant rise in testing error. This phenomenon called linear mode con- nectivity (Frankle et al. 2020), and it is known be related to the success of being able to find
4

---

Published as a conference paper at ICLR 2022
MinistNet (MNIST)
ResNet-20 (CIFAR-
0.1
Kospren meg faaddrn
Top Accuraty
0.7
Pox: relinng
0.3-
02-
0.1-
2
10
Compression
Figure 1: Equivalence of Koopman and global magnitude pruning convergence. Left, com- pression vs, accuracy of MnistNet trained on MNIST. Right, compression vs. accuracy of ResNet-20 trained on CIFAR-I0. Dashed lines are mean accuracy immediately after pruning and solid lines are mean accuracy after single epoch of refining. Error bars are standard deviation.
winning tickets in the Lottery Ticket Hypothesis framework. However, the cause of its emergence, and whether it is related to other dynamical phenomena, are not currently well known.
3 EQUIVALENCE OF GLOBAL AND KOOPMAN MAGNITUDE PRUNING IN THE LONG TRAINING LIMIT (t + 00)
We start by examining how global and Koopman magnitude pruning compare the long-training time limit. We consider DNN, initialized with parameters (0)) optimized via SGD on training data x, with the order of the Th epoch's s data denoted by z, As the number of epochs goes to co, the DNN will converge to f", local minimum in the loss landscape. This requires that [|@(t) 0 [| O, as t + 00. Therefore, for E IR+ there exists f. E N, such that [|0(t) 8" ll2 < c, for all t > tc-
Here, ||- ll is the 12 norm. Note that this additionally implies that at t. the DNN is in the basin of attraction of 0*.
Previous work on approximating the Koopman operator has found that if a system is sufficiently near a fixed point (and if the trajectory is sufficiently "nice"), then the computed Koopman mode decomposition should well approximate the true dynamics. That is, for E RR+, there exists Koop N. such that 1 0-1 mode corresponding to == 1.
for all Koop Here, O" di Korr))y is the computed Koopman
Assuming that a DNN has trained for at least max(te, t .Ko0p) training steps, then
110 0(t) < 2e,
(4)
E sufficiently small, then m()0),,c) vo m((0(t)), c). and the two methods are thus equivalent.
To test whether this result holds in practice, we used ShrinkBench, recent open source toolkit for standardizing pruning results and avoiding bad practices that have been identified in the pruning literature (Blalock et al. (020). The results of pruning custom ShrinkBench convolutional DNN called "MnistNet" (Blalock et al., 2020), pre-trained on MNIST ! CIFAR-10 are presented in Fig. 1 Each DNN was trained from point near convergence for a single epoch, so that the parameter trajectories could be captured. All hyperparameters of the DNNs were the same the off-the-shelf implementation of ShrinkBench, except that allowed for pruning of the classifier layer. Training experiments were repeated independently three times, each with different random seed. Our code has been made publicly available
and ResNet-20,, pre-trained on
We found that, for both MnistNet and ResNet-20, KMP and GMP produced nearly identical results, both immediately after pruning and after one epoch of refinement (Fig. []. These results support the claim developed above that KMP and GMP are equivalent in the long training time limit.
http:///tthhioommoommmmmooooooee https///sttttlcoooolllll//ccnnnp pruning
5

---

Published as a conference paper at ICLR 2022
MnistNet (MNIST) Epoch
ResNet-20 (CIFAR-10) Epoch
1.0
Too Accuracy
0.-
0.3
6.6-
0.2-
0.1
16
16
Compression
MnistNet (MNIST) Epoch 20
ResNet-20 (CIFAR-10) Epoch 20
1.0
0.6
0.3-
@400 mag
0.2
Layer adarte
Post pruming
0.1
Figure 2: Koopman and global magnitude pruning pre-convergence. Left column, compression vs. accuracy MnistNet trained on MNIST. Right column, compression vs. accuracy ResNet-20 trained on CIFAR-10 10. Top row, results of pruning DNN after epoch of training. Bottom row, results of pruning DNN after 20 epochs of training. In both cases, only data from epoch and epoch 20, respectively, mean accuracy immediately after pruning and solid lines are mean accuracy after a single epoch of refining. Error bars are standard deviation.
used to compute the Koopman mode decomposition. Dashed lines
4 KOOPMAN MAGNITUDE PRUNING PRE-CONVERGENCE
Motivated by the equivalence of Koopman and global magnitude pruning in the long training time limit, we next examined how the two methods compared before training converged. In this regime, might expect KMP outperform GMP, since computing the Koopman mode decomposition quires multiple snapshots of the training data. This provides KMP with considerably more dynamic information than GMP, which is based single snapshot.
As previous work has found that ResNet-20 trained on CIFAR- 10 does not achieve linear mode con- nectivity until at least 5 epochs of training (Frankle et al.) 2020), examined pruning performance at epoch and epoch 20 to capture the effect that linear mode connectivity had. We find that, despite the additional information, KMP performs similarly GMP both epochs (Fig. right column).
There are two possible explanations for this similarity in performance. The first is that KMP and GMP prune the same parameters, making them equivalent methods (even before convergence). The second is that KMP and GMP prune distinct parameters, but those that remain result in a subnetwork with similar accuracy. To test these two hypotheses, we compare the overlap between the parameters not pruned by GMP and KMP at different compressions and different epochs (see Appendix B for more details on this metric). The right column of Fig. shows that the two methods largely prune the same parameters. From epochs 1-10, the mean overlap is roughly > 95%, even for compression of 64. At epoch 20, there is a decrease mean overlap and an increase in standard deviation. This suggests that the two methods are equivalent at the carliest epochs of training, with the equivalence breaking at some subsequent epoch.
Because KMP makes use of dynamical systems theory, the equivalence of KMP and GMP during (at least) the first 10 epochs has a strong implication on the trajectory in parameter space that induced by training: at the end of each epoch, the largest parameters of the DNN must be the same ones that are expected to be the largest at convergence, if the order of training data were to remain the same. In this sense, the expected identity of the largest parameters "static". The overlap between

---

Published as a conference paper at ICLR 2022
MnistNet (MNIST)
Re (CIFAR-10)
1.0
1.0
Percert overlap
0.-
0.9
0.8-
0.9-
0.7-
Epech
Spoch 10
0.-
Spoch
Compression
Figure 3: Overlap between Koopman and global magnitude pruning masks. Left, overlap of surviving parameters found via KMP and GMP on MnistNet training on MNIST. Right, overlap of surviving parameters found via KMP and GMP on ResNet-20 trained on 100. Error bars are minimum and maximum of three seeds.
masks found using KMP from increasingly distant epochs shows a decrease with time (Appendix B Fig. 5), suggesting that SGD slowly re-orders the identity of the largest parameters epoch-to-epoeh, making these initial largest parameters inaccurate.
By epoch 20, KMP and GMP stop being equivalent and, on average, start pruning a larger number of different parameters. This implies that, even if the training data was ordered the exact same way for all the remaining epochs, the identity of (some of) the largest parameters are expected to evolve. To contrast this with the "static" dynamics found during epochs 1-10, we call this regime "active". We speculated that this change from "static" to "active" might be caused by emerging structure in the parameter evolution. To test this, we pruned ResNet-20 at epochs and 20 using layer shuffle pruning (LSP). This method preserves the amount of compression in each layer, but randomly chooses which parameters to remove. Previous work has found that many state-of the-art methods designed to prune at initialization do not do better than LSP (Frankle et al., 2021). We find that after only single epoch of training, both GMP and KMP do no better, and in fact, do worse, than LSP for nearly all compressions tested. However, by epoch 20, both GMP and KMP were better than LSP for compression values of less than 16. These results support the idea that non- trivial structure is emerging in the DNN at a similar time that KMP and GMP stop being equivalent. When this structure not present (e.g. at epoch 1). the two methods prune the same parameters.
We also examined the ability of KMP and GMP to prune MnistNet, trained on MNIST, after epochs and 20. While we found similar results to ResNet-20 (Figs. and 3 left column), there are subtle differences in the behavior of the overlap between pruning masks. For MnistNet, the overlap is smallest at epochs and 5, suggesting that the two methods are not equivalent at the earliest part of training (Fig. left). That this is different to what we found for ResNet-20 may be due to the fact that the two models are at different phases of training at equivalent epochs. Previous work has shown that, shortly after initialization, linear mode connectivity emerges in LeNet, trained on MNIST Franklle et al. 2020). This does not happen for ResNet-20, trained on CIFAR-10. 10, until at least epoch 5. Additionally, compression above 8 as early as epoch 1. These MnistNet results further support the fact that, as structure beyond what LSP can find emerges, the dynamies associated with the identity of the largest parameters goes from being "static" to "active""
find that, for MnistNet, KMP and GMP outperform LSP for
Finding what is driving this "static" to "active" transition, and whether it is related to the emergence of linear mode connectivity and/or other noted transitions during training (Gur-Ari et al. 2018 Achille et al. 2019: Kalimeris al. 2019), will be the focus of future work.
5 "NEAR" EQUIVALENCE OF GLOBAL AND KOOPMAN GRADIENT PRUNING
Thus far, we have focused only on magnitude based pruning. In this section, we extend our work to another method that has found success and is of general interest: gradient based pruning Yu et al, 2018 Lee et al. 2019: 2020 Blalock al. 2020). In practice, this way of pruning is accomplished by scoring based on the gradient of the loss function, V,L, as propagated through the network. For instance, global gradient pruning (GGP) scores using the magnitude of the gradient times the
7

---

Published as a conference paper at ICLR 2022
Spectrum of Koopman operator
ResNet-20 (CIFAR-10)
1.0
Hoogerar Port prannig
04
Im/A]
-
0.2
-1.0
-10
0.0
1.0
Compression
Figure 4: Koopman gradient pruning. Left, real and imaginary parts of the computed Koopman cigenvalues. Red dots denote modes that had norm of greater than 0.85. Here, À = 1.000 and A 0.075. Right, compression vs. accuracy of ResNet-20 trained for 20 epochs CIFAR-IO. Dashed lines are mean accuracy immediately after pruning and solid lines are mean accuracy after single epoch of refining. Error bars are standard deviation.
parameter values, s())
VeL. o()) Blalock et al. 2020p. Given that the gradient is applied to update the parameters of the DNN, VoL directly related to the parameters' dynamies.
From the Koopman mode decomposition, we have that the parameters at training step t, (tt,, are given by
R
((t) = 0- + Σ
(5)
1
where the 0, are the scaled Koopman modes (i.e. 0, (p)v.). As before, we use 0* to denote the scaled Koopman mode that has À = Importantly, Eq. teelss us that the future state of the parame- ters is given by the sum of 0, times their decaying eigenvalues. While there are R - modes in this sum, those with large norms (i.e. 0 >> 0) are expected to make the most substantial contribution. For simplicity,
consider only the largest modes that also have real, positive eigenvalues. These modes have easily interpretable dynamics (i.e. exponential decay) and are directly related to VoL. Pruning using the magnitude of these modes is what call Koopman gradient pruming (KGP).
The Koopman spectrum of a ResNet-20 trained on CIFAR-10 for 20 epochs is shown Fig. In addition to the presence of an eigenvalue close to 1, corresponding to 6", there is also an eigenvalue that satisfies the above criteria. We refer to its corresponding mode as 02.
As expected from the discussion above, pruning ResNet-20 after 20 epochs of training using KGP is very similar to pruning using the scoring function s(t) = VoLl, a method we refer to as just gradient pruning (JGP) (Fig. 4 right). We note that we only expect the two methods be "nearly" equivalent (and not truly equivalent, as in the case of KMP and GMP in the long training time limit) because, KGP finds exponential decaying modes from dynamic data, whereas JGP is the average gradient computed over batch of input data (Blalock et al. 2020).
These results highlight the fact that, while gradient and magnitude based pruning methods have seemingly little to do with each other, they are in fact, related in the Koopman operator frame- work. Whereas magnitude pruning is, at certain phases of training, equivalent to pruning using 10%, gradient pruning equivalent to pruning using the exponentially decaying modes.
6 DISCUSSION
Inspired by the widespread success Koopman operator theory has found in a number of applied fields, and its recent application to problems in machine learning, we extended Koopman tools to study deep neural network pruning (Janowsky) 1989; Mozer & Smolensky 1989a bl LeCun et al.) 1989 Karnin 1990; Han et al. 2015; Blalock et al. 2020). By making use of the Koopman mode decomposition, defined
theoretically motivated and data-drives in implementation. We found that both global magnitude and gradient
class of pruning algorithms (Algorithm I that
pruning (Blalock al. 2020) have equivalent (or nearly equivalent) methods at certain regimes of
8

---

Published as a conference paper at ICLR 2022
training in the Koopman framework (Figs. 4). In this way, Koopman pruning provides unified perspective on these "disparate" methods.
Applying KMP to DNNs in the early part of training revealed that it could be equivalent to GMP (Fig. B). From a dynamical systems perspective, this equivalence implies that the largest parameters, at the end of each epoch, the same ones that are expected to remain the largest, if training continued using the same ordering of the data. We refer to this behavior as "static". Given that we found the identity of the largest parameters evolved with training (Appendix B Fig. 5., pruning too early may confine the sparsified DNN to a subspace where it stays in the static regime and therefore is unable find good local minimum. This is additionally supported by the fact that layer shuffle pruning (LSP) outperforms GMP during this part of training, suggesting that the structure present in the GMP mask is more "harmful" than a randomly structured mask (Fig. 2
However, at a certain subsequent point in training. the masks produced by GMP and KMP stop overlapping as completely (Fig. B This suggests that there some transition in the dynamics, with the largest parameters becoming "active". As this transition seems to occur at a similar time that GMP starts to outperform LSP, and at a similar time that linear mode connectivity has been reported to emerge (Frankle et al. 2020), we speculate that it is related to the sparsified DNN still being able to evolve and find a good local minima in the subspace it is restricted to.
By making of ShrinkBench, our results can be easily replicated and avoid some of the bad practices that have been recently identified as being pervasive in the DNN pruning literature (Blalock et al. 2020). Our custom implementations are integrated into the ShrinkBench framework, allowing for additional investigation into Koopman pruning.
While dynamical systems theory is natural language with which to frame DNN optimization, the complex dependencies on optimizer, architecture, activation function, and training data have historically kept efforts in this direction to minimum. This has led to reliance methods, such as iterative magnitude pruning, whose basis of success is still not clear (Elesedy) al.) 202I). Other groups have attempted more principally examine DNN behavior by studying spectral objects, such as the spectrum of the Hessian matrix (Gur-Ari et al. 2018) and the spectrum of the weight matrices (Martin et al. 2021). This work has been influential and led new insight, however the connection between these metrics and the (future) dynamics of DNN training is not direct. An exception to this is the recent work on using inertial manifold theory to study the Lottery Ticket Hypothesis, which is similar in spirit to our Koopman based pruning methods (Zhang et al.) 2021
heuristic
Given the data-driven tools that have been developed for Koopman operator theory Mezii & Ba-
naszuk 2004 Mezić 2005 Rowley et al. 2009 Tu et al. 2014 Williams et al. 2013 Mezic| 2020)
and the rich theoretical literature that connects Koopman objects the state space geometry Meezi
2003 Arbabi & Mezić 2017 Mauroy et al. 2013; Mezić 2020), recent work has focused on bring
Koopman operator theory the study of DNNs (Dietrich al. (2200] & Redman
2020 Tano
cet al. 2020. Manojlovićć et al. 2020; Mohr et al. 2021 Naiman & Azencot 2021
This work has
shown that Koopman methods can:
Approximate the parameter dynamics during training and lead to speed-ups in wall clock
time when substituted for standard optimizers (Dogra & Redman 2020 Tano al. 2020
Predict the number of layers necessary for a hierarchical support vector machine to achieve given level of performance (Manojlović al. 2020 Mohr al. 2021)
Shed light on the behavior of sequence neural models (Naiman & Azencot 2021
Our current work further illustrates the power that Koopman operator theory can bring. In particular, we found that the Koopman mode decomposition encodes dynamical information about training that could be leveraged to prune DNNs, enables framework that unifies disparate pruning algorithms, and provides insight on how training dynamics impact the success of magnitude pruming. To the best of our knowledge, these could not have been done using any other linearization method (e.g. principal component analysis). We believe that continued exchange between the Koopman and machine learning communities will lead to further advances.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
W.T.R. was partially supported by a UC Chancellor's Fellowship. W.T.R., M.F. R.M and LM were partially supported by the Air Force Office of Scientific Research project FA9550-17-C-0012. I. G. K. was partially supported by U.S. DOE (ASCR) and DARPA ATLAS programs.
REPRODUCIBILITY STATEMENT
Forethought ensure reproducibility taken in both the design and description of methods and results. We made use of ShrinkBench, a recent open-source framework for developing and testing new pruning methods (Blalock al. 2020), implement all our experiments. This not only allowed us to report comparisons between our methods and existing methods across a number of different compressions, but will also enable easy sharing of our algorithms, as they are integrated into the ShrinkBench framework. Additionally, we have provided general pscudo-code for implementing Koopman based pruning (Algorithm [ and description of the method we used to compute the Koopman mode decomposition (Appendix A to make it straightforward for others to understand and implement.
REFERENCES
Alessandro Achille, Matteo Rovere, and Stefano Soatto. Critical learning periods in deep networks. In International Conference on Learning Representations, 2019.
Hassan Arbabi and Igor Mezić. Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the koopman operator. SIAM Journal on Applied Dynamical Systems, 16 (4):2096-213 2126, 2017.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag, What is the state of neural network pruning? arXiv preprint, arXiv:2003.03033. 2020.
Marko Budišić, Ryan Mohr, and Igor Mezić. Applied koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4):047510, 2012.
Nelida Emjaric-Zic, Senka Maćešić, and Igor Mezić. Koopman operator spectrum for random dynamical systems. Journal of Nonlinear Science, 30(5):0007-2566, 2020.
Felix Dietrich, Thomas N. Thiem, and Ioamnis G. Kevrekidis. On the koopman operator of algo- rithms. SIAM Journal Applied Dynamical Systems, 19(2):800-885 2020.
Akshunna S. Dogra and William T. Redman. Optimizing neural networks via koopman operator theory. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2087-2097. Curran Associates, Inc., 2020.
Bryn Elesedy, Varun Kanade, and Yee whye Teh. Lottery tickets in linear models: An analysis of iterative magnitude pruning. arXiv preprint, 2xXi:20077.08243 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3259-3269. PMLR, 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works initialization: Why are missing the mark? In International Conference Learning Representations, 2021.
Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint, arXiv: 812,04754 2018.
10

---

Published as a conference paper at ICLR 2022
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28, pp. 1135-1143. Curran Asso- ciates, Inc., 2015.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. In S. Hanson, J. Cowan, and C. Giles (eds.), Advances in Neural Information Processing Systems, volume 5. Morgan-Kaufmann, 1993.
Steven A. Janowsky. Pruning versus clipping in neural networks. Phys. Rev. A, 99:6600-6603 1989.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiram, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. In H. Wal- lach, H. Larochelle, A. Beygelzimer, d' d'Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
E. D. Karnin. A simple procedure for pruning back- precppppppagtionn trained neural networks. IEEE Transactions on Neural Networks, 1(2):239-422, 1990.
B. O. Koopman. Hamiltonian systems and transformation in hilbert space. Proceedings of the National Academy of Sciences, 17(5)331--318, 1931.
B. O. Koopman and J. Neumann. Dynamical systems of continuous spectra. Proceedings of the National Academy of Sciences, (8(3):255-263 1932.
Yueheng Lan and Igor Mezić. Lincarization the large of nonlinear systems and koopman operator spectrum. Physica D: Nonlinear Phenomena, 242(1))42-53,, 2013.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In David S. Touretzky (ed.), Advances Neural Information Processing Systems 2, [NIPS Conference, Denver, Colorado, USA, November 27-30, 1989]. pp. 598-605. Morgan Kaufmann, 1989.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. Torr. A signal propa- gation perspective for pruning neural networks at initialization. In International Conference Learning Representations, 2020.
D. M. Luchtenburg and C. W. Rowley. Model reduction using snapshot- realizations. Bulletin of American Physical Society, 56, 2011.
Iva Manojlović, Maria Fonoberova, Ryan Mohr, Aleksandr Andrejčuk, Zlatko Drmač, Yannis Kevrekidis, and Igor Mezić. Applications of koopman mode analysis to neural networks. arXiv preprint, arXiv:2006.1 1765, 2020.
Charles H. Martin, Tongsu (Serena) Peng, and Michael W. Mahoney. Predicting trends in the quality of state-of-the-al neural networks without access to training or testing data. Nature Communica- tions, (2(1):4122, 2021.
A. Mauroy; I. Mezić, and J. Moehlis. Isostables, isochrons, and koopman spectrum for the tion-angle representation of stable fixed point dynamics. Physica D: Nonlinear Phenomena, 261: 19-30, 2013.
Senka Maćešić, Nelida Črnjarić Zic, and Igor Mezić. Koopman operator family spectrum for nonau- tonomous systems. SIAM Journal on Applied Dynamical Systems, 17(4):247-2211, 2018.
Igor Mezić. Spectral properties of dynamical systems, model reduction and decompositions, Non- linear Dynamics, 4 1:300-325, 2005.
Igor Mezić. On numerical approximations of the koopman operator. arXiv:2009.05883 2020.
arXiv preprint,
Igor Mezić.
Spectrum of the koopman operator, spectral expansions in functional spaces, and state- space geometry. Journal of Nonlinear Science, 2005):2091-2145, 2020.

---

Published as a conference paper at ICLR 2022
Igor Mezić. Analysis of fluid flows via spectral properties of the koopman operator. Annual Review of Fluid Mechanics, 45(1):357-375 2013.
Igor Mezić and Andrzej Banaszuk. Comparison of systems with complex behavior. Physica D: Nonlinear Phenomena, 197(1):01-113,, 2004.
Ryan Mohr, Maria Fonoberova, Zlatko Drmač, Iva Manojlović, and Igor Mezić. Predicting the critical number of layers for hierarchical support vector regression. Entropy, 23(1), 2021.
Michael C. Mozer and Paul Smolensky. Skeletonization: A Technique for Trimming the Fat from Network via Relevance Assessment, pp. 107-115. Morgan Kaufmann Publishers Inc., San Fran- cisco, CA, USA, 1989a
Michael C. Mozer and Paul Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3-16, 1989b.
Ilan Naiman and Omri Azencot. A koopman approach to understanding sequence neural models. arXiv preprint, ar111.12021.......77272,,, 2021.
Clarence W. Rowley, Igor Mezić, Shervin Bagheri, Philipp Schlatter, and Dan Henningson. Spec- tral analysis of nonlinear flows. 641:115- 127, 2009.
Andrew M. Saxe, James L. Mcclelland, and Surya Ganguli. Exact solutions the nonlinear dy- namics of learning in deep linear neural network. In In International Conference on Learning Representations, 2014.
Peter J. Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of Fluid Mechanics, 656:5-28, 2010.
Lawrence Sirovich. Turbulence and the dynamics of coherent structures part i: Coherent structures. Quarterly of Applied Mathematics, 45(3):561-571, 1987.
Mauricio E. Tano, Gavin D. Portwood, and Jean C. Ragusa. Accelerating training in artificial neural networks with dynamic mode decomposition. arXiv preprint, arXiv:2006. 14371, 2020.
Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, and Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 1(2):391-421, 2014.
Stephen Wiggins, Introduction To Applied Nonlinear Dynamical Systems And Chaos. 2003.
Matthew O. Williams, Joannis G. Kevrekidis, and Clarence W. Rowley. data-driven approxima- tion of the koopman operator: Extending dynamic mode decomposition. Journal of Nonlinear Science, 25(6): 107--1367 2015.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui- Hsin Lai, Vlad I. Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and I.. Davis. Nisp: Pruning networks using neuron importance score propaga- tion. 20/8 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9194-9203, 2018.
Zeru Zhang, Jiayin Jin, Zijie Zhang, Yang Zhou, Xin Zhao, Jiaxiang Ren, Ji Liu, Lingfei Wu, Ruoming Jin, and Dejing Dou. Validating the lottery ticket hypothesis with inertial manifold theory. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
12

---

Published as a conference paper at ICLR 2022
A PERFORMING KOOPMAN MODE DECOMPOSITION
As discussed the main text, many different methods have been developed to perform Koopman mode decomposition. One very popular class of approaches is dynamic mode decomposition (DMD) (Schmid] 2010), and its many related variants. Seminal work by |Rowley et al. (2009) showed that DMD, as originally proposed, could be equivalent Koopman mode decomposition. Because of its popularity and noted connection to Koopman operator theory, we made use of one such DMD) method, called Exact DMD (Tu et al. 2014), in this work.
Let X (0)) T0(O), (()))) DNN's parameters, 0 E TR-N, during all but the last iteration training during an epoch (i.e. there r + iterations during epoch). Here T is the nonlinear dynamical map that evolves the DNN parameters, which is dependent on the choice of optimization algorithm, architecture, activation function, and ordering of training data. Let Y [0(1,, .(2).... ((T)]. Exact DMD does require X and Y to be built from sequential time-series data, but we assumed it here.
[0(0). 8(1)...., 1)] E R be snapshots of
Exact DMD considers the operator A, defined as
YX*
(6)
where + is the Moore-Penrose pseudoinverse. Eq. is the least-squares solution to AX Y, and hence, satisfies
min Y AX
where ||: is the Frobenius norm. If Yc = 0 for all e E TRT such that Xc = 0, then AX Y exactly (Tu et al., 2014).. This property is called linear consistency.
In practice, the DMD modes are found by computing the (reduced) singular value decomposition (SVD) of X (i.e. X = QEV*) and setting A = Q YVE-1 (see Algorithm and Appendix 1 Tu et al. 2014) for more details on how the modes are computed from A). When X and Y are linearly consistent and has a full set of eigenvectors, the DMD modes are equivalent the Koopman
modes (Tu et al. 2014).
All pruning experiments performed and reported in the main text were done on 2014 MacBook Air (1.4 GHz Intel Core i5) running ShrinkBench (Blalock et al. 2020). Computing the largest Koopman mode, 0*, took 44 seconds and 1.1 GB of memory usage for the ResNet-20 experiments, and 210 seconds and 1.1 GB of memory usage for MnistNet experiments. Memory usage was computed using the Python module memory- proofilerrr 0.58.(") A single epoch's 's worth of data (i.e. 391 iterations for ResNet-20 and 469 iterations for MnistNet) were used to construct the Koopman operator. Despite MnistNet having s 1.6x many parameters as ResNet-20, the similar amount of memory usage required for both comes from the fact that we employed reduced SVD, which keeps only many singular values there are snapshots, which is comparable across the two DNNs (391 and 469).
A.1 SCALING UP KOOPMAN PRUNING
Given that Koopman based pruning requires performing decompositions on matrices whose total number of elements scale as the square of the number of parameters present in the DNN, scaling up Koopman pruning to larger DNNs may seem intractable. However, the field of fluid dynamics, where Koopman has been extensively applied (Mezić) 2013). often deals with a similar problem, having the dimensionality of the state space being very large [e.g. 105-9 (Luchtenburg & Rowley. 2011]]. Because of this, numerical methods have been developed, such as the method of snapshots (Sirovich] 1987) to efficiently compute the SVD of large matrices. These can, and have, been eas- ily incorporated into methods used to compute the Koopman mode decomposition. Therefore, expect that leveraging similar approaches should make scaling Koopman pruning to larger DNNs tractable.
13

---

Published as a conference paper at ICLR 2022
MnistNet (MNIST)
ResNet 20 (CIFAR-10)
Epocts 10:20
0.95
Percent overlap
Spodis 1:20
0.85
0.7
0.5
0.75
32
32
64
Compression
Figure 5: Overlap between Koopman masks across epochs. Left, overlap of surviving parameters found via KMP on MnistNet, trained on MNIST, at different epochs. Right, overlap of surviving parameters found via KMP on ResNet-20, trained CIFAR-10, at different epochs. Error bars standard deviation.
B PRUNING MASK OVERLAP
Just because two pruning methods find subnetworks that have the same performance at given compression does not imply that the two methods prune the same parameters. Therefore, to study how similar two approaches, A and B, at the level of individual parameters, we computed the pruning overlap of the two masks, m and m. defined as
Σ (m m)) (N/Cc.
(8)
Note that the denominator is equivalent to the number of non-pruned parameters, and that, since E {0, 1) me m if and only if both masks agree to save parameter i.
While we explored the overlap of Koopman magnitude pruning and global magnitude pruning masks in the main text, method changes when applied at different points during training time. this case, m corresponds to the mask found using given method epoch A (and similarly for B). We did this analysis for KMP masks, finding that for both MnistNet and ResNet-20, there is change in which parameters are kept across training time (Fig.
also the overlap metric compare how masks found using the same
14


Reviews:
[{"review_id": "nCgFtFl9rwi", "reviewer": "Reviewer_zqcK", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper is overall well written. There were several aspects of this paper that I liked a lot: \n\n- I think that the questions asked in the paper, e.g., why has magnitude-based pruning been successful and what is its relationship with gradient-based pruning, are highly sought-after. \n\n- I also appreciate the efforts that the authors made to ensure the reproducibility of the paper as mentioned in the discussion section.\n\nHaving said this, at a few places in the paper, I am slightly confused by the authors' interpretation of their results and feel that they might be somewhat overstated. Two such places a below -- I am happy to be corrected if wrong:\n\n- The first place is Section 3, where the authors state that the global and magnitude pruning in the long training time limit is *equivalent*. Equivalence is a strong claim and seemingly this is unlike to hold without strong assumptions on the dynamics of neural network parameters. Indeed, to my understanding, the Koopman operator approximates the dynamic of neural network parameters using a linear transformation, as in Appendix A. This seems to suggest that (4) only holds in a very special regime of neural network training, where the parameter updates can be modeled by a linear update matrix. The assumption of \"linear dynamics in parameters'', however, seems to be a big constraint -- it is known that even linear neural networks (without any nonlinear activation) have nonlinear dynamics in parameters [(Saxe et al. 2013)](https://arxiv.org/abs/1312.6120). To clarify this point, I suggest the authors either (i) state a theorem on the equivalence with all the necessary assumptions listed or (ii) slightly tone down the equivalence claim. \n\n- The second place that I got a bit confused about is how exactly does Koopman pruning provide \"new insight on the success (or lack thereof) of magnitude pruning pre-convergence,\" which is one of the main contributions listed in the introduction. I believe that Section 4 was designated to explicate this insight, but I feel that there is no strong message in that section that I can take home. I feel that the text and experiments in Section 4 demonstrated that Koopman pruning and magnitude-based pruning are *not* equivalent in pre-convergence (by epoch 20 or so) -- but is that all the authors want to conclude for magnitude pruning at pre-convergence?\n\n**Questions**:\n\n- In Section 2.1, where the authors cast neural network training into Koopman decomposition, it will be great if the authors can explicitly write the interpretation of $\\mathbf{U}$, $g$, and $\\mathbf{T}$ in the context of neural network training. Based on my understanding, in neural network training, $g$ is the identity function, $\\mathbf{T}$ is the parameter-update transformation modeled by a linear operator, and $\\mathbf{U}$ is identical to $\\mathbf{T}$. Is this interpretation correct? If so, perhaps it is worth mentioning already at this point that throughout this paper, we assume that the neural network update dynamics is modeled by a linear operator (a matrix) $\\mathbf{T}$.\n\n- In Section 2.2. and Algorithm 1, the authors assume that $\\lambda_1 = 1$ and refer this to as \"a reasonable assumption in the case of stable dynamical systems\". I am wondering if this assumption is well-corroborated by experiments. That is, when we perform Koopman decomposition on snapshots of parameters, is $\\lambda_1$ close to 1? I am not sure if I would expect it to be the case. I feel that the reason perhaps is not that the dynamical system of parameter evolution is \"unstable'' but rather that it may not be well-approximated by a linear dynamical system.", "summary_of_the_paper": "The authors studied network pruning from the perspective of dynamical system theory. They show that a new type of pruning method, named Koopman pruning, unifies magnitude pruning and gradient-based pruning to a degree. It also clarifies aspects of magnitude-based pruning before convergence in training.", "summary_of_the_review": "To summarize, I feel that the paper can be a meaningful contribution to the field. However, the \"operator theoretic perspective\" of this paper -- to my feeling as a non-expert -- is somehow overstated. I think that Koopman pruning is an interesting and useful pruning heuristic on its own, but I am not sure if it can genuinely explain magnitude-based pruning either before or after training convergence in a realistic setting, where network parameters cannot be modeled by a linear dynamical system. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KgWa5sSoOs", "reviewer": "Reviewer_Q2k5", "summary": "", "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": "Strength:\n1. The paper is clearly written.\n2. The experiments are motivated and executed well.\n3. Provides a theoretical basis for pruning which is an intuitive and successful procedure.\n4. The difference between the static and active regimes is interesting. While why this happens is not answered in the paper, it can be considered as a useful by product.\n\nWeakness:\n\n1. Is the message tautological? As in, DNN training is a hidden procedure and the Koopman operator again projects onto a high dimensional space so as to linearise the dynamics, and once this is done, it is sort of natural to expect that the top eigenvalue will have the most say. Now, the Koopman operator is also sort of hidden and does not provide further insights into the working of the DNN. Would any sort of linearisation of dynamics not lead to similar conclusions.\n\n2. While Algorithm 1 is a \"general form\", it is only conceptual, in that, it does not directly yield a procedure that speeds up \"wall clock time\".\n\n\n\n", "summary_of_the_paper": "The paper uses a Koopman operator to provide a theoretical basis to explain the success of pruning deep neural networks.", "summary_of_the_review": "The paper clearly presents interesting results, the experiments seem sound. However, the novelty/significance is not overwhelming and hence the borderline score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8YmnG4ORtTR", "reviewer": "Reviewer_kuYT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "I guess the main strength of this paper is the perspective the authors use to look at this problem, which to me sounds new. Other merits of this paper is that it is readable and teh authors have made an effort to provide a tutorial on Koopman theory, depspite this subject being quite specialistic.", "summary_of_the_paper": "This paper attempts to explain why magnitude-based and gradient-based pruning is effective only after the network has converged, ie it has learned the given task. The aothors attempt to shed some light on this issue via Koopman theory, borrowing from the field of dynamic systems.", "summary_of_the_review": "While this paper has the merit of the originality of the approach, it is hard for me to provide a string feedback due to the unfamiliarity with this Koopman theory.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-f8uvMT72N5", "reviewer": "Reviewer_Zwfq", "summary": "", "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": "This paper tries to explain the success of magnitude based and gradient based methods in compressing neural network models. Although these methods are naive, both of them are found to be robust and are easy to implement. \n\nstrengths:\n1. This paper is well-written and easy to follow.\n2. The targeting problem of this work is very interesting and fundamental. \n3. The solution proposed in this work is easy to implement and is supported by solid theory. For practitioners who are familiar with eigen-decomposition, the theory part of this work may not be amazing, however this viewpoint on understanding pruning is very interesting and provides valuable insights into the success of pruning based methods.\n\n\nquestions:\n1. This works presents results on GMP. I am wondering if the proposed framework can be applied to layerwise pruning. Although in [1], the layerwise pruning is outperformed by GMP. \n2. What are the  computational  requirements? For example, to compute the Koopman mode decomposition of ResNet-20 on CIFAR10, how much time is needed? How much memory is needed? How many snapshots are needed to obtain the eigenvector associated to the largest eigenvalue? \n3. Is the proposed approach be scalable to large networks? It seems there are some computational challenges since the dimension of the parameter space of a large network can be very high.  \n\n\n\n[1] Blalock, Davis, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. 2020. “What Is the State of Neural Network Pruning?” ArXiv:2003.03033 [Cs, Stat], March. http://arxiv.org/abs/2003.03033.\n", "summary_of_the_paper": "This paper proposes a new class of pruning algorithms based on Koopman operator theory and shows existing magnitude based pruning methods and gradient based pruning methods can be unified under the proposed framework. This is a very interesting approach to justify the success of magnitude based and gradient based methods in compressing neural networks by utilizing eigendecomposion, which has been successfully applied to understand the structure of RKHS and GPs.", "summary_of_the_review": "This paper provides an interesting viewpoint in understanding the success of pruning based compression methods. The method is easy to implement and is very practical  (at least for small-scale networks).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper used the Koopman operator theory to explain and guide the DNN pruning. All the reviewers deemed that such a viewpoint is novel (but at different levels). However, the paper still had some issues, including unclear technical details, vague/overselling statements, being computation and memory expensive, etc. The paper finally got 4 "marginally above threshold" (one being of low confidence), making it on the borderline. The AC read through the paper and agreed that the Koopman operator theory brings new perspective to DNN pruning, with potential for other analysis of DNNs. Although the paper is imperfect and not strong, it does not have severe problems either and the issues pointed out by the reviewers could be easily fixed (except the scalability issue, which can be left as future work). In order to encourage new ideas, the AC recommended acceptance.
Decision: Accept (Poster)