{'fraction_non_alphanumeric': 0.03692267262334932, 'fraction_numerical': 0.010478943564811773, 'mean_word_length': 4.634462335739404, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Universality of Deep Neural Network Lottery Tickets: A Renormalization Group Perspective

Foundational work on the Lottery Ticket Hypothesis has suggested an exciting corollary: winning tickets found in the context of one task can be transferred to similar tasks, possibly even across different architectures. While this has become of broad practical and theoretical interest, to date, there exists no detailed understanding of why winning ticket universality exists, or any way of knowing a priori whether a given ticket can be transferred to a given task. To address these outstanding open questions, we make use of renormalization group theory, one of the most successful tools in theoretical physics. We find that iterative magnitude pruning, the method used for discovering winning tickets, is a renormalization group scheme. This opens the door to a wealth of existing numerical and theoretical tools, some of which we leverage here to examine winning ticket universality in large scale lottery ticket experiments, as well as sheds new light on the success iterative magnitude pruning has found in the field of sparse machine learning.


Introduction
The lottery ticket hypothesis (LTH) for deep neural networks (DNNs) proposes that DNNs contain sparse subnetworks that can be trained in isolation and can reach performance that is equal to, or better, than that of the full DNN in the same number of training iterations [14,15]. These subnetworks are called winning lottery tickets. The LTH has provided new insight into the success of dense DNNs, suggesting a key role for the emergence of winning tickets with increasing size, reminiscent of the maxim "more is different" [1]. In recent years, researchers have found an intriguing corollary: winning tickets found in the context of one task can be transferred to related tasks [3,4,8,18,28,29,37,39], possibly even across different architectures [7]. In addition to having applications of practical interest, these results imply that winning tickets can be used to study how tasks are "similar" and which features of said tasks are similarly "relevant". While exciting, to date there exists no principled understanding of why winning tickets can be transferred between tasks, nor does there exist a way to know, a priori, which tasks a given winning ticket can be transferred to. Additionally, there is a lack of theoretical work on iterative magnitude pruning (IMP) [11], the most common method used to find winning tickets. This is in striking analogy to the state of statistical physics in the early-to-mid-20 th century. Empirical evidence suggested that disparate systems, governed by seemingly different underlying physics, exhibited the same, universal properties near their phase transitions. While heuristic methods provided insight [25], a full theory from first principle on this universality was not realized until the development of the renormalization group (RG) [41][42][43]. RG theory has not only provided a framework for explaining universal behavior near phase transitions, but also a scheme for grouping systems by that behavior. This classification, introduced via the notion of universality classes, has allowed for a detailed understanding of materials [2,9,40,44], and provides immediate knowledge as to what other classified systems a given material behaves like.
The analogy between universality in RG and LTH theories becomes strengthened under the following consideration. Recently, [35] found that when the density (i.e. the percentage of parameters remaining) of a DNN being pruned via IMP is in a certain range, d L < d < d C , the network's error scales according to the following power law Similarly, when the temperature of a classical spin system, such as the two-dimensional Ising model, is near, but below, the critical temperature, t < t C , the magnetization scales as These similarities hint at a more fundamental connection between the universality present in winning tickets and in physical systems near phase transitions (see Fig. 1 and Table 1). Indeed, we show that IMP is an RG scheme (i.e. IMP satisfies the properties required to be considered an RG operator). By analyzing winning ticket transfer experiments [4], we find that there exists universality in the IMP flow (i.e. the way in which the parameters of the DNN change after each iteration of IMP). We additionally use the RG perspective to interpet and explain the recent results on transfering winning tickets across architectures [7]. Our contributions are the following: • A theoretical basis for understanding the success of IMP and the universality of winning tickets; • Experimental support of the theory in large scale lottery ticket experiments, providing insight into previously known heuristic based results; • A new set of tools for interrogating and classifying combinations of DNN architecture, task, activation function, and optimizer.

The Renormalization Group and Iterative Magnitude Pruning
The RG operator, R, can be viewed as a method for "coarse-graining" 1 . That is, each application of R replaces local degrees of freedom with a composite of their values. An example of this for the Figure 1: The RG and IMP. Both the RG and IMP are applied iteratively to coarse-grain systems, revealing "relevant" features (left columns). Certain observables are known to have regimes where they follow power-law scaling as the RG and IMP are applied (upper right). In the case of the RG, this scaling, and its universality, is associated with properties of the flow it induces in a certain, abstract space (lower right). The nature of the flow IMP induces has not been previously studied, but none-the-less similarly exists (see Sec. 3.1 and Fig. 2). See Table 1 for the analogous quantities in each theory.
two-dimensional Ising model is shown in the left-hand column Fig. 1, where neighborhoods of four spins are replaced by their mode. The formal way to study R is to consider its action on the Hamiltonian (i.e. energy function). For classical spin systems (e.g. the two-dimensional Ising model), H has the general form where the s i are the spins of the system (e.g. s i ∈ {−1, +1}), ·, · represents sites on the lattice that are nearest neighbors, and the k i are the strengths of the different coupling constants (e.g. k 2 is the strength of the nearest neighbor coupling). Due to the fact that coarse-graining amalgamates spins, the coarse-grained spin system can be viewed as equivalent to the original system, but with a new set of coupling constants. The coarse-grained system has a different Hamiltonian, which is given by where k is the new set of couplings determined by the operator T : R K → R K . Here K is the maximum number of couplings considered, usually introduced for convenience to keep the considered operators finite. R can be applied iteratively, defining a flow through the function space of Hamiltonians via Eq. 4, with an associated flow in the space of coupling constants. The latter is commonly referred to as the RG flow. While R is often a complicated, non-linear function, T can be linearized near fixed points of the flow [19]. It will therefore have eigenvalues greater than, less than, and equal to 1. The flow will grow in the direction of the eigenvectors v r with eigenvalues λ r > 1 and will shrink along the v i for λ i < 1. These combinations of coupling constants, or directions, are called relevant and irrelevant, respectively. A schematic example of these directions, and the general RG flow, is presented in Fig. 1. Thus, by examining the R associated with a given system, and its flow in the space of coupling constants, it is possible to find which components of the system are necessary for certain macroscopic behavior, and which are not. Systems belonging to a particular universality class, have the same relevant directions.
Interestingly, many of the properties discussed above can be analogously found in iterative magnitude pruning (IMP). To see this, let θ represent the parameters of a DNN with loss function, L(θ), and let I represent a single application of the IMP process. The parameters of the DNN pruned via an application of I is related to the original model by where the new set of parameters, θ , are given by an operator T . The similarities between Eqs. 4 and 5 are striking. We note here that, in the case of IMP, T is the composition of a masking operator, M, and a refining operator F. That is, T = F • M : R N → R N , where N is the number of parameters of the DNN. M is defined via the pruning procedure implemented (e.g. pruning parameters based on their magnitudes). While we are considering IMP here because of its connection to the Lottery Ticket Hypothesis [14,15], there are many other pruning procedures (such as Hessian based pruning [26]), all of which have their own M. Similarly, F is defined via the refinement procedure used, making it dependent on the choice of optimizer and whether or not the DNN parameters are left alone or "rewound" to their value at a previous point during training [15,33].
For n iterations of I, the resulting network is given by This defines a trajectory in parameter space (i.e. θ (0) → θ (1) → ... → θ (n−1) ), which we will refer to as the IMP flow. A schematic illustration of what the IMP flow might look like is given in Fig.  1 (the axes of which will be explained in Sec. 3.1). Just as in the case of RG theory, the directions of the IMP flow are determined by the eigenfunctions of T , which grow or shrink exponentially by the magnitude of the associated eigenvalues.

Connection Between the RG and Standard LTH Frameworks
Before we formally show that IMP is an RG scheme, we discuss how the standard theory that has emerged from studying the LTH is related to RG theory.
In the familiar picture, the success of winning tickets is attributed to the surviving sparse DNN being able to find a "good" local minima in the loss landscape [14,15]. This may be possible because the training of DNNs via stochastic gradient descent (SGD) appears to be rapidly confined to a low-dimensional subspace [20]. This implies that the DNN only "feels" changes to a small number of parameters (or linear combinations of parameters) during much of training. Parameters that are not in this low-dimensional subspace can, therefore, be removed with minimal impact. If a sparse DNN is initialized in this subspace (as late rewinding aims to do), then it may be possible for training to find the same, or related, local minima as the full DNN [13,27].
In this way, the parameters that do not lie in the low-dimensional subspace are irrelevant, and repeated applications of IMP are expected to remove them. On the other hand, the relevant parameters are those that span this subspace, and their removal changes the local minima the sparse DNN converges to. Therefore, certain observable functions of the DNN, such as error, are expected to be only sensitive to the relevant, but not irrelevant, parameters.
If two models share the same low-dimensional subspace, then they should be able to transfer winning tickets between each other. Note that this transferability is highly non-trivial. Indeed, it was only with the development of the LTH, and then subsequent experimental work, that this was even considered to be a possibility [14,28,29]. It is, in general, difficult to find these subspaces and accurately compare them across experiments. RG theory provides us with tools for finding relevant and irrelevant directions, which do not rely on explicitly constructing the subspace. In particular, RG theory says that if two models have the same eigenfunctions of T that have eigenvalues > 1, then they have the same relevant parameters. Note that this means that, once the eigenvalues are computed, we know a priori whether winning tickets should be able to transfer between the two. Additional experiments showing this should, theoretically, not be necessary. What the minimal sparsity a winning ticket can have and still successfully be transferred is not, however, identified by this.

IMP as an RG Scheme
To make the connection between IMP and RG more precise, we show that IMP fits the definition of an RG scheme. To do this, we consider the projection operator, P, that is associated with the RG operator. In the case of classical spin systems, the projection operator maps the spins, s i , to a coarse-grained spin system, s I , such that it satisfies where Tr {s i } is the trace operator over the values that the s i can take (e.g. ±1) [19]. For the two-dimensional Ising model, it is standard to take where δ is the kronecker delta function and sign(·) is +1 if the argument is positive and −1 if it is negative [19]. Eq. 8 formally defines the mapping from s i → s I as The projection operator is not unique, but must satisfy the following three properties [19]: 2. P(s i , s I ) respects the symmetry of the system; 3.
To find a projection operator associated with I, we will take the opposite approach and see if we can find a mapping between the activations of all the units, a, before and after an application of IMP. Without loss of generality, we can consider the activation of unit j in layer i as being defined by where h is the activation function (e.g. ReLu, sigmoid) and the g k are functions that determine how the different parameters and activations of other units affect a j . For instance, in a feedforward DNN, the impact of the bias of unit j in layer i is given by g 0 = θ (i) j , and the weighted input from the previous layer is given by As discussed above, IMP changes the parameters θ by the operator T , which is defined by a composition of M and F. Therefore, the activation of unit j in layer i, after applying I, is given by and thus, the projection operator associated with I is P a We can easily verify that the projection operator defined by Eq. 12 satisfies all three properties needed for an RG projection operator. First, property #1 is satisfied, as Eq. 12 is a product of delta functions. Property #2 is satisfied, as IMP only removes parameters, so the form of a (i) j given in Eq. 11, and hence, the loss function, will remain intact until layer collapse (i.e. when all the weights from one layer to another are removed). There is often a non-trivial regime of density where this does not occur. Finally, for property #3 to be satisfied, we can fix the test and training sample ordering for each epoch (as is done when the random seed is fixed). In such a case, both the mask and refining operators in Eq. 12 are deterministic and P a (i) j , a j (i) will be unique.
Having shown that these three properties are satisfied by the projection operator associated with IMP, we have found that IMP meets the criteria of being an RG operator, making it what the literature often refers to as an RG scheme. This, to our knowledge, has not been previously identified and provides new insight into why IMP has found success in discovering winning tickets [14,15], as well as has found general success in the study of DNNs [16].

Universality in the IMP Flow
We start by examining the IMP flow of computer vision models. The goal of this analysis is to find the relevant and irrelevant parameters (or more likely, some function of the relevant and irrelevant parameters), so that we can examine whether different pruned models are in the same universality classes.
While winning tickets do not derive their success purely from their topology (random reinitialization, while the pruning mask is maintained, was shown to lead to a significant decrease in performance by [14]), the topology nonetheless plays an important role. For instance, we note that the parameters in the first residual block of a ResNet architecture not only impact the activations in that block, but all subsequent blocks. This is in contrast to the last residual block, whose parameters influence only that block. We therefore expect to see differences in how thoroughly each layer gets pruned [17,21].
We consider how the distribution of remaining non-zero parameters changes in each residual block. That is, we considered the functions where M i (t) describes the percentage of all non-zero parameters that are in residual block i at IMP iteration t. The numerator sums run over all N (i) of the elements of the pruning mask restricted to residual block i, m (i) . Each m (i) j ∈ {0, 1}. The denominator sums the entire pruning mask, making it equivalent to the number of non-pruned parameters in the entire DNN. Because ResNet-50 has four residual blocks, IMP induces a four-dimensional flow in the space of M i . To visualize the trajectory, we examined two-dimensional slices. Examples of these are plotted in Fig. 2, for ResNet-50s pre-trained on ImageNet [23] via supervised learning and via self-supervised learning with simCLR [6] and MoCo [22]. This data comes from experiments done by [3]. Importantly, we find that the behavior of all three trajectories in these projected spaces to be similar.
If the M i are eigenfunctions of the IMP operator, then they will scale exponentially with respect to IMP iteration number. That is, M i (t + 1) = λ i M i (t), where λ i is the eigenvalue governing the exponential growth/decay. To find λ i , all that is needed is a simple inversion, λ i = M i (t + 1)/M i (t). As long as M i (t) = 0, this is well defined and we can estimate λ i by doing these for each pair of data points. Doing this, we find that ImageNet, simCLR, and MoCo have eigenvalues that are within a standard deviation of each other for all residual blocks ( Table 2). In addition, the standard deviation in the computation of each is eigenvalue is < 1%, suggesting that it is indeed reasonable to consider the M i being eigenfunctions of I.
These results suggest that there is universality in the winning tickets of all three pre-training strategies, despite their differences (i.e. supervised vs. self-supervised training). In particular, all three have one irrelevant direction that is captured by M 4 and three relevant directions that are captured by M 1−3 (although M 3 could possibly be a marginal direction, i.e. an eigenfunction 14 ± 0.01 1.08 ± 0.01 1.01 ± 0.004 0.97 ± 0.01 whose eigenvalue is equal to 1). This universality may be due to the fact that the first few residual blocks learn the low level statistics of the data [30], which for natural images scales in specific, non-trivial ways [36,38]. The sensitivity to the first three residual blocks, which are the furthest from the output layer, is in contrast to standard classical spin systems. In the case of the usual two-dimensional Ising model, the RG removes long-range interactions (i.e. couplings between next-nearest neighbors, next next-nearest neighbors, etc.), which are usually assumed, for physical reasons, to be weak. Systems with relevant long-range interactions have been found to have unique properties, such as the existence of a phase transition in one-dimension [10], which is known not to happen for the standard Ising model. The importance of these long-range interactions may therefore be another interpretation for the success of normalized initializations (e.g. He initialization) for convolutional DNNs, which set parameters in the earlier residual blocks to be larger. This, presumably, is part of what sets ResNet-50 to be in the long-range interaction regime.
Lastly, we note that the eigenvalues of the M i 's suggest that, if the first three residual blocks had sparse parameters that were properly set, the final residual block could be removed. Given the size of the last block, this could provide considerable savings in energy and memory bandwidth [21]. This also provides us insight into the function of the last residual block, namely that it acts to "clean-up" and add small corrections to the representations found in the first three blocks.

Elastic Lottery Ticket Hypothesis
Recent work on the "Elastic Lottery Ticket Hypothesis" (E-LTH) has extended the notion of tranferability by finding it possible to transform winning tickets found on one DNN, to another with a slightly different architecture [7]. In particular, it was found that, for architectures in the same family (e.g. ResNets, VGGs), it was possible to either squeeze (by removing residual blocks) or stretch (by replicating residual blocks) winning tickets so that they could transfer.
Three results from this study of the E-LTH are especially noteworthy: 1. The smallest ResNet considered (ResNet-14) had the weakest transferability properties; 2. The more unique residual blocks replicated, the better the performance.
3. Removing the later residual blocks, in the case of shrinking, and replicating the earliest residual blocks, in the case of stretching, lead to the best results; While preliminary hypotheses on the origin of these results were developed by [7], involving dynamical systems and unrolled estimation perspectives, detailed theoretical understanding was left to future work. Given that the RG framework developed above led to insight into the nature of the universality of winning tickets in the case of different tasks, we wondered whether it could similarly help to explain the nature of these E-LTH results. As discussed in Sec. 2, two tasks that have the same IMP flow can transfer winning tickets. Therefore, we expect that transforming a given winning ticket from one architecture (source) to another (target) will be successful if its IMP flow matches that of the target. In particular, we reasoned that the success (or lack-thereof) may rely on whether the number of relevant, irrelevant, and marginal residual blocks in the target architecture is matched by the transformed source ticket.
To test this, we computed the eigenvalues associated with the eigenfunctions M i , as defined by Eq. 13, for each "normal" residual block of ResNet-14, ResNet-20, ResNet-32, ResNet-44, and ResNet-56 (data from [7]). As discussed in the original paper, the down-sampling residual block in each stage was not transformed between winning tickets, so those were not considered. The eigenvalues for the residual blocks in the first stage are presented in Table 3.
We find that, while the smaller ResNets (ResNet-14 and ResNet-20) have only relevant residual blocks, the larger ResNets have at least one non-relevant block. This offers a straightforward explanation to why ResNet-14 had particularly poor transferability: using it as the source ticket necessarily leads to the transformed ticket have only relevant residual blocks, which does not match the source tickets' structure. Having only relevant residual blocks may make the first stage too sensitive as the depth of the ResNet is increased, leading to poorer performance. Relatedly, we find that replicating a few unique residual blocks (i.e. replicating only block 1 or blocks 1 and 2) can lead to an over representation of either relevant or non-relevant blocks. This mismatch is predicted by the theory to lead to worse transferability.
Finally, we find that most of the non-relevant residual blocks are in the early part of the first stage. Therefore, removing the first several blocks when shrinking a winning ticket (e.g. dropping the first four blocks to go from ResNet-56 to ResNet-32), or replicating the last several blocks when stretching a winning ticket (e.g. adding the last two blocks to go from ResNet-32 to ResNet-44), will lead to too many relevant residual blocks. Again, this may make the transformed source ticket have a different structure than the target ticket and thus, lead to worse performance.
Note that for the later two stages (Tables 1 and 2 of Appendix A), the nature of the distribution of eigenvalues is different. In particular, stage 2 has only relevant and marginal directions, and stage 3 has only marginal and non-relevant directions. However, there is consistent evidence for the fact that the number of each type of eigenfunction is related to the three results from the original E-LTH paper [7] we highlighted.

Discussion
Inspired by similarities between the current state of the sparse machine learning community and that of the statistical physics community in the early-to-mid-20 th , we found that iterative magnitude pruning (IMP), the principle method used to discover winning tickets, is directly related to the renormalization group (RG). Given that the development of the RG led to a first principled understanding of the universality in behavior near phase transitions, as well as a way in which to characterize materials by such behavior, we reasoned that viewing the IMP from an RG perspective may lead to new insight on the universality of winning tickets [3,4,8,18,28,29,37,39] and the general success it has found in the study of DNNs [16].
By viewing IMP as inducing a flow in a certain four-dimensional space, we show that different pre-training methods of ResNet-50 on ImageNet have trajectories with the same properties. In addition to suggesting an underlying reason for winning ticket transferability, these results also provide new perspective on the importance of normalized initializations (e.g. He initialization) and the early residual blocks. Taking the RG framework to the "Elastic Lottery Ticket Hypothesis", recent work which extended the notion of winning ticket universality by transforming tickets between different architectures, we again found that the IMP flow allowed interpretation and explanation of experimental results.
A wealth of theory has been developed around RG theory, including a number of numerical and theoretical tools that go beyond what we used here. Given the connection between IMP and the RG proposed in this work, we believe that there is a considerable potential for future collaboration between the two fields. Possible directions of future study include: • Bringing the RG framework to other sparsficiation methods, like RigL [12], which can similarly be viewed as RG schemes; • Bringing the RG framework to study winning tickets beyond computer vision, such as in natural language processing [3,31,45], reinforcement learning [45], and lifelong learning [5]; • Computing and classifying systems by their critical exponents (such as γ in Eq. 1). We attempted to do this and had some promising results. However, we were limited by having only a few independent seeds and a scaling function with multiple free parameters [35], which led to large differences between computed critical exponents of systems that displayed qualitatively similar scaling behavior (see Appendix B for more details). Bringing methods such as finite scaling [19] and increasing the number of independent seeds may alleviate this problem; • Exploring the connection between the RG framework developed here and the work to build effective theory of DNN behavior [34].
Finally, while RG theory provides a way to predict which combinations of task, optimizer, activation function, and architecture can have winning tickets transferred between them, knowing what is the minimal density of a winning ticket that can be transferred remains an open question. In order to address this, finite size effects [19], differences in symmetries, and non-linear corrections to the IMP flow [32] may need to be taken into account. This interesting, and important, question will be the focus of future work.

Author Contributions
W.T.R. conceived the project, performed the analysis, and wrote the manuscript; T.C. provided the experimental data; A.S.D. advised on the mathematical formulation, analysis, and implications of this work; Z.W. advised on the analysis, contextualization, and implications of this work. All authors provided feedback on the manuscript. W.T.R. is supported by a UC Chancellor's Fellowship. T.C. is supported by an IBM PhD fellowship. A.S.D.'s research has been supported by the EPSRC Centre for Doctoral Training in Mathematics of Random Systems: Analysis, Modelling and Simulation (EP/S023925/1). A.S.D. was funded by the President's PhD Scholarships at Imperial College London. Z.W. is supported by a US Army Research Office Young Investigator Award (W911NF2010240).
where i = √ −1. Here np is interpreted as the error associated with not pruning, ↑ as the asymptotic error upon maximal pruning, γ as the sensitivity of the combination of network architecture, task, activation function, and optimizer to pruning, and p as the degree to which the transition from no change in error to power-law scaling takes place. Importantly, γ can be viewed as a critical exponent under the RG framework. Because systems in the same universality class have the same critical exponents, we wondered if we could find evidence of universality in the computed value of γ for various different computer vision models.
We found the fits to be sensitive to np and, in some cases, there was not a clear single value for np . Therefore, we included np as a free parameter (which [35] did not do), but we tightly bounded the value so as to minimize instability in adding another free parameter. To numerically compute the fits, we used scipy's curve fitting function: scipy.optimize.curve_fit [24].
The computed values of γ for ResNet-50 evaluated on CIFAR-10, CIFAR-100, and SVHN are presented in Table 6. The effect of pre-training using various state-of-the-art methods is also given. The γ values vary, sometimes considerably, across tasks and pre-training condition (e.g. CIFAR-10 and SVHN pre-trained via simCLR). However, we note that the data came from only two or three seeds, making the fits susceptible to noise and making the quantification of error in computed γ difficult. In addition, the fitting function of Eq. 14 has multiple free parameters, again making the fit susceptible to noise.
Taking these possible complications into account, we overlaid the different error as a function of density scaling curves (an example of which is given in Fig 3). We found that they qualitatively matched each other more than the computed γ may have made it seem. We imagine that trying different fitting procedures (especially making use of methods developed in the context of statistical physics, such as finite scaling [19]), as well as using more independent random seeds, may enable more accurate and robust approximations of γ. Overlaying the error as a function of density curves for ResNet-50 trained from random initialization on CIFAR-10/100 or SVHN, with 5% rewind, shows very similar, if noisy, behavior.