How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective

Thank you for your careful reading and constructive comments.

Weakness 1: The analysis of Figure 4 is unclear to me. I cannot follow the interpretation of the provided plots to infer that iterative pruning can be beneficial. The provided plots suggest that removing a large fraction of parameters i.e. having a small pruning ratio, increases the value of R, which is not desirable according to the theory, for a dense network. However, does this also hold for a partially sparse network which is iteratively pruned like in the case of IMP, how does pruning iteratively mitigate this trend?

In Fig. 4, in fact, we do not assert that iterative pruning itself is inherently beneficial. Instead, our aim is to demonstrate that in Iterative Magnitude Pruning (IMP), the lower bound of the pruning ratio increases after each pruning iteration. When the previously set pruning ratio is less than the theoretical limit, the pruning ratio should be adjusted to avoid incorrect pruning. Consequently, fewer weights need to be pruned in subsequent iterations, leading to an adjustment in the pruning ratio. This forms the basis for the pruning ratio adjustment algorithm.

Weakness 2: The authors have also not confirmed this insight via experiments with L1 regularization if iterative pruning helps over one-shot pruning. I believe the authors need to give a detailed explanation of Section 7.

We did not compare the performance of iterative pruning with one-shot pruning directly. Instead, our objective is to use our theoretical results to elucidate why iterative pruning requires adjustment of the pruning ratio. Additionally, we aim to explain why, in some iterative pruning algorithms, the use of regularization versus no regularization can lead to discrepancies in the final performance of the sparse network.

Weakness 3: In addition, can the authors comment on the connection to the pruning fractions shown in Figure 4 to the observations made by Paul et. al. [2] for IMP (Figure 5 in Paul et. al. makes a similar analysis). Is there an optimal pruning fraction for an iterative method like IMP?

Figure 4 in our paper and Figure 5 in Paul et al. utilize the same theoretical results to illustrate that in Iterative Magnitude Pruning (IMP), the network cannot be pruned to the target sparsity directly, necessitating iterative pruning. In contrast, our paper shows that after each pruning step, the lower bound of the pruning ratio increases, indicating that the pruning proportion must be adjusted in iterative pruning. The determination of the optimal pruning ratio for iterative methods is an intriguing research question, and we are actively exploring this area.

Weankness 4: The use of the terms pruning ratio, pruning threshold and sparsity are interchangeably used without concretely defining them, which makes the paper difficult to follow. I would urge the authors to correct this and clarify that the pruning ratio implies the number of nonzero parameters left in the network after pruning (it seems so from the derivation?). The use of sparsity is incorrect in Table 9, sparsity denotes the number of zero parameters in the network.

Thanks for your suggestion, pruning ratio and sparsity imply the number of nonzero parameters left in the network after pruning and we will correct those in the revised version.

We sincerely thank you for your insightful feedback. Below are our detailed responses to your concerns:

Weakness 1: The derived upper bound and lower bound on the pruning ratio depend on the new weights of the pruned networks. This is strange to me, meaning that the limit of the pruning ratio varies when a different weight is used. This also limits the application of the results.

Good question. In fact, this is the key point in pruning bounds. We aim for the performance of the sparse network to closely match that of the dense network. In other words, the performance of the sparse network is bounded by that of the dense network. If the weights of the dense model change, the performance bound of the sparse network also changes, leading to a different pruning ratio bound.

Weakness 2: The numerical experiments are performed using the L1 regularized loss function. However, this is not considered in the theoretical results. I wonder if the bounds will be different if the loss function is changed.

In fact, we are considering the pruning limit of a well-trained model without special focus on the loss function. Our theoretical results actually apply to all well-trained models, regardless of the loss function.

Weakness 3: The one-shot magnitude pruning ignores the interaction between the weights, which has been shown to be suboptimal in some recent work. However, the authors claim that it is optimal for the lower and upper bounds. I believe this is because the L1 regularization is used as the loss function, which already takes that into account. This should be clarified.

Thank you for your reminder, we will add relevant instructions to the paper: In the absence of L1 regularization, although the theoretical lower bound for magnitude pruning is the lowest, the achievable upper bound for magnitude pruning may not be the lowest. In general, if the optimal algorithm is not clear, magnitude pruning can be considered as a viable choice.

Weakness 4: The authors claim that the upper and lower bounds match each other when the proposed L1 regularized loss function is used for training. This might not hold when the original loss is without L1 regularization. This should also be discussed and not overclaimed in general cases.

Great reminder. In fact, we only claimed that the upper and lower bounds match when the proposed L1 regularized loss function is used for training. This might not hold in other cases, and we will make this point more clear in the revised version.

Weakness 5: The numerical comparison did not consider many state-of-the-art pruning methods (which are also pruning after training) such as [1] R. Benbaki et. al., Fast as CHITA: Neural Network Pruning with Combinatorial Optimization [2] L. You et. al., SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning [3] X. Yu et. al., The combinatorial brain surgeon: Pruning weights that cancel one another in neural networks.

In fact, since we proved that the lower bound of magnitude pruning is smaller than that of other pruning methods, and that the upper bound of magnitude pruning is more likely to match the lower bound, we focused solely on magnitude pruning. We will include a comparison with other algorithms in our revised version.

Weakness 6: Relating to the previous comment, the magnitude pruning method used here minimizes the bounds proposed here, which then is used as a support for their usefulness. However, in many cases, the network is not pruned to its limit.

This is true; in general, the lower bound for magnitude pruning is the lowest among pruning methods. However, not all upper bounds for magnitude pruning match this lower bound. If we consider the lower bound as the limit, many models in practice will not be pruned to this extent. Nonetheless, our theoretical results highlight two key factors that determine network pruning limit: the flatness of the loss landscape and the magnitude of network weights.

Weakness 7: The title is overclaimed. While the bounds proposed here are sometimes useful, they are not fundamental limits since there are approximations and relaxation used along the derivations. Moreover, the upper and lower bounds do not match each other in general.

Thank you for your comments. Although the upper and lower bounds generally do not coincide exactly, their gap is indeed negligibly small. Moreover, our theoretical results identify two key factors that influence network pruning: the flatness of the loss landscape and the magnitude of network weights. By constraining these factors, such as using L1 regularization to control magnitude, the upper and lower bounds are more likely to match. Additionally, despite employing approximations in our derivations, the results we obtain is actually nearly exact asymptotically, which is supported by that our theoretical results closely match the simulation outcomes.

Sincere thanks once again for your feedback. Below is our response:

Weakness 1: I am not so sure about the statement that different initializations will result in nearly the same empirical distribution of the weights. Table 2 doesn't seem to support this statement.

The experiments in Table 2 were conducted using independent initializations (with the same initialization method), and the results indicate that their pruning limits are largely consistent. We also performed a statistical analysis of the weight distributions and calculated the total variation distance between them. Below is a summary of the experimental results, which we will include in the revised version. The experiments suggest that independent initializations do not lead to significant differences in the final weight distributions.

For reasons of time, the table is simplified

task | tv distance of weight distribution Mean (standard deviation)

VGG, CIFAR10 | 0.02(0.02)

AlexNet, CIFAR10 | 0.01(0.008)

ResNet18, CIFAR100 | 0.04(0.04)

ResNet50, CIFAR100 | 0.03(0.02)

ResNet18, TinyImageNet | 0.02(0.03)

ResNet50, TinyImageNet | 0.03(0.02)

Weaknesses 2,3 and 4: The bounds provided in the paper should also work for networks trained with the original loss function. To answer whether L1 regularization would change the pruning ratio limit, it would be helpful to compare the limits and the actual pruning performance for both networks trained with and without the L1 regularization.

You're right and thank you for your suggestion. The bounds provided in the paper indeed also work for networks trained with the original loss function and we will include experiments related to the original loss in the revised version.

Weakness 6: So when $\epsilon$ decreases further, will the pruning limit eventually lead to a dense network? (e.g. with about 30% of the weights pruned) In that case, the performance of magnitude pruning should be quite far away from other optimization-based methods. I wonder what are the implications of the bounds in those regimes.

If $\epsilon$ is significantly reduced, the amount of pruning that can be done will indeed decrease, as our tolerance for performance degradation also becomes smaller. Therefore, $\epsilon$ should not be chosen arbitrarily, as values that are too high or too low are not appropriate. We compute the standard deviation of the loss across different batches of the training set and use it as $\epsilon$.

Weakness 1: One thing that sounds strange to me is that one conclusion is that "The smaller the network flatness (defined as the trace of the Hessian matrix), the more we can prune the network", which is contrary to the previous common belief, i.e., the flatter the network's landscape, the easier to be pruned. https://arxiv.org/pdf/2205.12694. Could the authors clarify these two counterarguments?

Thank you for the insightful question. We should indeed use sharpness (defined as “trace” of the Hessian matrix), where smaller sharpness corresponds to greater pruning. This definition will be adopted in the revised version to avoid confusion.

Weakness 2: While the theoretical proof looks sound, the empirical results in this paper look strange to me. For instance, it is weird to see that the accuracy maintains the same at a 100% pruning ratio, but drops significantly as it goes below 2%. Does the pruning ratio here stand for a different thing than the common definition, i.e., the ratio of weights that are zero?

We define pruning ratio as the proportion of remaining weights, 100% means no pruning is performed.

Weakness 3: Can the authors explain why RN50 achieves worse accuracy than RN18 on TinyImageNet?

I am not sure which data the accuracy refers to in this context. If it refers to the test accuracy of the network, then Table 9 shows that the accuracy of RN50 is higher.

Weakness 4: Which pruning algorithm is used for Figure 3? It is surprising to see that we can preserve the original performance at 2% ratio, for RN50 on TinyImageNet.

We first train the RN50 model with L1 regularization on TinyImageNet. Following the training, we prune the network by removing the smaller weights. Details of the hyperparameters used during training are provided in the appendix. Additionally, a comparison of the pruning algorithms is included in the appendix. Since L1 regularization-based magnitude pruning is not new technique and not the primary focus of this paper, we have placed it in the appendix.

I thank the authors for their response. Defining the pruning ratio as the proportion of remaining weights makes no sense to me. I suggest to change it to the opposite. I am not an expert in the theoretical study of pruning/sparsity. I will keep my original score and defer the assessment of the theoretical analysis to the AC and other reviewers.

Thanks for your constructive feedback! The concerns and questions in the review are addressed as follows.

Weakness 1: Limited technical novelty: applying convex geometry to attain similar results (e.g. bounds dependent on the Gaussian width) has been explored in prior works, some of which are cited in the related work section. However, the paper lacks discussion of how this work differs from or builds upon existing literature.

Although previous work has employed convex geometry tools to derive lower bounds for network pruning, these bounds might be far from the actual pruning limit. In contrast, we employ more powerful tools in convex geometry, i.e., the statistical dimension and approximate kinematic formula, thus enabling us to obtain a sharp threshold of pruning. Moreover, our research tackles the pruning problem in a more systematic way, and through our theoretical results, we explicitly identify two key factors that determine the pruning limit, i.e., the network flatness and the weight magnitude, which is, in our opinion, valuable to better understand the existing pruning algorithms and design new and more efficient algorithms.

Weakness 2: More intuitions on the theoretical results would be helpful. For example, loss flatness is one of the key factors discussed in the paper, and only its formal definition (trace of the Hessian) is given in the paper. Intuitions like smaller flatness (i.e. flatter loss landscape) means the loss function is less sensitive to perturbations in the weights would be helpful.

Thank you for the suggestion. In the revised version, we will include more intuitive explanations to enhance the understanding of the paper.

Weakness 3: Inconsistencies in notations: For example, from equation (17) onwards, the loss sublevel set notation takes in the weights as the argument. Is this the same loss sublevel set defined in equation (2), which takes in epsilon as the argument? And how is the epsilon parameter chosen for the loss sublevel set?

These are, in fact, two sublevel sets. Consequently, epsilon should be included in the sublevel set notation of Equation 17; we will correct this in the revised version. We compute the standard deviation of the loss across different batches of the training set and use it as epsilon.

Weakness 4: I would define "pruning ratio" earlier in the paper. It was not clear until the contributions section that smaller pruning ratios means more pruning of the network.

Thanks for your suggestion, we will define pruning ratio earlier in the revised version.

Weakness 5: The authors have introduced "pruned ratio", which equals to 1 - pruning ratio, for Table 2. This is the only place in the paper where this term is used. This is confusing. Why did the authors not stick to "pruning ratio" throughout the paper?

Good suggestion, we will change it to "pruning ratio" in the revised version.

Weakness 6: Please consider removing adjectives like "powerful" when describing convex geometry and approximate kinematics formula, or "very tight characterization." They are subjective and do not add much to the clarity of the paper.

We will correct this in the revised version.

Weakness 7: Some typos like "Lottery Tickets Hypolothsis" (line 77)

Thanks for pointing out this, we will correct typos in the revised version.

Weakness 8: Some terms like SLQ (line 82) are not defined until later in the paper.

We will define SLQ before using in the revised version.

Question 1: What is novel here in light of prior work showing results connecting Gaussian widths to recovery thresholds [4]?

Ref.[4] and our work share the similarity that they take advantage of convex geometry to characterize the threshold of given inference or learning problems. The main difference between them lies in:

1. Our work extends significantly the application of convex geometry from a specific inference problem to a general learning problem: Ref. [4] addresses in specific the recovery threshold of the linear inverse problem, which is a classical statistical inference problem. On the other hand, our work tackles a statistical learning problem which is of general DNN architecture and arbitrary loss function. The methods and results in Ref. [4] just cannot be simply translated to the problem we address in our work.

2. The threshold in our work is normally sharper than Ref. [4]: Ref. [4] utilizes the Gaussian width to characterize the recovery threshold, which unfortunately can only provide the lower bound (necessary condition) since the key result Ref. [4] relies on, i.e. Gordon's escape through a mesh theorem only provide the necessary condition. In contrast, our work leverage the statistical dimension framework and the accompanying approximate kinematic formula, whose necessary and sufficient condition almost coincides, thus capable of providing sharp thresholds.

Question 2: How sensitive are the theoretical bounds to the choice of loss function? Do the results generalize across different loss functions commonly used in deep learning?

Our theory only concerns the pruning limits of well-trained models and does not address the loss function during the training process. In other words, our theoretical results apply to one-step pruning for all well-trained models.

Question 3: How computationally expensive is the proposed spectrum estimation algorithm compared to existing methods? Is it practical for very large networks?

In fact, our proposed improved algorithm introduces only a modest increase in computational complexity compared to existing methods. For instance, with a fixed sample size of 100, it requires more computation of only 200 derivatives. These computations do not necessitate the use of the entire dataset and can be performed on a subset. Furthermore, for very large networks, the improved algorithm provides a more accurate estimation of the eigen spectrum.