On the Sparsity of the Strong Lottery Ticket Hypothesis

Summary

The authors propose an existence proof for Strong Lottery Tickets(SLTs) by improving over the existing method which used the Subset Sum approximation to construct source networks, which involved using subsets of variable sizes in order to approximate target parameters. Instead the authors show the existence of SLTs using subsets with fixed sizes (RFSS) and leverage this results to show the existence of SLTs.

Strengths

1. The authors propose the Random Fixed Subset Sum approximation instead of the previously used Subset Sum approximation to prove the existence of Strong Lottery Tickets. This results allows them to use a subset of a fixed size to approximate parameters in a target network. 2. The subsequent existence proof interpolated between the result of Malach et. al. [1] (which uses a single parameter) and Pensia et. al. [2] (which uses a subset of parameters) based on the size of the subset being used. The authors also extend this result to equivariant networks.

Weaknesses

1. Given the theoretical nature of the work, the overall contribution appears limited as it can only connect the existing results established by [1], [2], [3]. 2. The main insight in this paper is that by using a fixed subset size to approximate parameters in the target, one can exactly estimate the number of parameters required in the strong lottery ticket, which was previously not possible due to the variable size of subsets. However, as Burkholz et. al. [3] have shown via numerical simulations, the number of parameters required to satisfy the theoretical conditions for subset sum proofs can be relatively easily approximated. For example, they use a subset of size 15 for their simulations which is sufficient. Given this, the overall contribution of the paper seems incremental The following claims in the paper need to be addressed appropriately. 1. ‘We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks.’ While the existence of SLTs has been shown before in various settings, the sparsity of these networks has also been estimated using numerical simulations by Burkholz et. al. [3]. This is primarily because the size of the subset required to effectively approximate a parameter seems to have a natural upper bound (15 as shown in [3]). Hence, while the authors are able to show this exactly, previous theoretical work did a decent approximation. 2. ‘It is important to note that, to this day, we only have proofs on the existence of such subnetworks, also called winning tickets, but it remains an open question how to find them reliably.’ While the theoretical framework is laid out by the authors to construct the SLTs, the paper lacks numerical constructions of real world examples of neural networks using the proposed framework. Are the networks found by the proposed method sparser than the one's found by [3]? [1] Malach, Eran, et al. "Proving the lottery ticket hypothesis: Pruning is all you need." International Conference on Machine Learning. PMLR, 2020. [2] Pensia, Ankit, et al. "Optimal lottery tickets via subset sum: Logarithmic over-parameterization is sufficient." Advances in neural information processing systems 33 (2020) [3] Burkholz, Rebekka. "Most activation functions can win the lottery without excessive depth." Advances in Neural Information Processing Systems 35 (2022)

Questions

See above

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The work leverages Random Fixed Subset Sum result to adapt a large body of work showing the existence of SLTs. However, in the context of the existing work, this result seems incremental and lacks numerical validation.

Summary

This work focuses on the theoretical side of the Strong Lottery Ticket Hypothesis. It proposes and studies a fixed-size version of the canonically used Random Subset Sum (abbreviated RFSS) problem in previous proofs for this hypothesis. Then it applies the result of RFSS to prove that overparameterized networks can be pruned to approximate target networks with guaranteed sparsity. A corresponding lower bound is provided to show the tightness (up to log factor) of the overparameterization needed.

Strengths

- The proposed fixed-size version of RSS is an interesting problem and is potentially of independent interest. - Based on the literature reviewed here, this work is the first one that provides a (high probability) size guarantee for the pruned subnetwork. - A lower bound on the overparameterization size is also provided, which helps complete the picture and matches the high probability guarantee up to a log factor.

Weaknesses

- Elaboration of Theorem 3 is helpful in the main text. I do not see how it answers the question proposed in Introduction. Namely, for given target network size $m'$, the internal dimensions $d_\ell$, and a desired sparsity $\alpha$, how should we pick the number of parameters (or the number of layers) for our networks? Also, how does it imply the previous results? - More discussion should be given to the results on the hypothesis (e.g. elaborations) in Section 4 and 5. While the RFSS result is key, instead of having the whole proof in Section 3, the authors can leave a sketch of the proof idea and where it distinguishes / extends RSS results.

Questions

- On line 225 Theorem 3, is it $r = \max_i \min\{…\}$ instead of only $\max_i$ (in which case it’s always at least 1)? - What abbreviates to ANN in Theorem 4?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Addressed by the authors.

Summary

The authors consider the strong lottery ticket hypothesis (SLTH), which is roughly a statement that a large random neural network contains a sparse subnetwork whose performance is comparable to the entire network. By analyzing a fixed variant of the random subset sum problem, which is about the size of the sample of i.i.d. random variables to approximate a fixed number, they improved the previous results on the SLTH with the guarantee on the sparsity of the subnetwork.

Strengths

- The idea based on the fixed-size random subset sum problem seems new and works well. - The writing is in general very clean, especially the introduction and the related work.

Weaknesses

- I think the authors should check more about the references for the results in Section 3. (See Questions.) - There are many small errors and typos in the manuscript. (See Questions.)

Questions

- The assumption on the sum-boundedness in Definition 1 must hold for a very general density function $f$, since it is even weaker than the statement of the local limit theorem for density. (See, e.g., Theorem 7 in Section 7.2 of "Sums of Independent Random Variables" by Petrov.) Thus, I think some parts of Section 3, especially Definition 1 and Lemma 1, can be changed. - Below are small errors and typos: 1) In line 136, there is something missing in "we $\Omega$". 2) In line 140, $f_{\Sigma_{[i]}}$ should be $\Sigma_{[i]}$. 3) In line 182, "independent and uniformly at random" sounds weird. 4) In Equation (6) and other places, $X_S$ should be $Z_S$. 5) In line 186, "Eqs. 5 and 8" should be "Eqs. 6 and 8". 6) From Equation (19) to Equation (20), why $H_z(\tilde{S})$ can be dropped? 7) The equation below 204 seems wrong. I guess $(z-y)$ should be $z$ in the second line. 8) In line 219, "Let $F$ to be" should be "Let $F$ be".

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The work does not seem to have potential negative societal impact.

Summary

This paper studies the strong lottery ticket hypothesis from the perspective of pruning sparsity. In particular, the paper noticed that all previous papers about the strong lottery ticket hypothesis fails to characterize the sparsity of the neural network after pruning, and aims at solving this question in the paper. The paper first extends the random subset sum problem to a case where the selected subset has a cardinality constraint. The paper proves a probability bound in terms of the candidate set's size for the random subset sum to achieve a certain accuracy. Then, the paper utilize this bound to the case of the neural networks by utilizing the technique in previous works, and shows the over-parameterization required to achieve a certain accuracy and sparsity after pruning at initialization. The paper also included a lower bound on such over-parameterization requirement.

Strengths

1. The topic considered in the paper is quite interesting and significant. Indeed, one draw-back of the strong lottery ticket hypothesis is that there is no guarantee on the sparsity level after pruning. 2. A major contribution of the paper is that it extended the random subset sum problem to a case that involves a cardinality constraint on the subset. The proof seems quite technical and nontrivial. 3. The paper also included a lower-bound on the over-parameterization requirement.

Weaknesses

1. The statement of Theorem 2 and Corollary 1 seems weird. In particular, it should be noticed that for both Eq.(1) and Eq.(3), $n$ appears in both the left hand side and the right hand side of the inequality. With some simplification, it seems that the dependency on $n$ can be completely eliminated, and the size of $n$ does not contribute to whether the statement holds or not. In this case, it would be greatly necessary to understand how big the constant $c_{hyp}$ is, which is not stated in the theorem. Moreover, if $n$ is really not affecting the approximation error, then a better way to state the theorem would be to change Eq.(1) into a condition on $k$. 2. The proof of Corollary 1 seems problematic. In particular, in Page 15, the first inequality after line 483, the $\geq$ should be $\leq$, since $Pr(\exists z\in[-\sqrt{k},\sqrt{k}],\dots) \geq Pr(\exists z\in\\{-\sqrt{k} + i\epsilon':i\in[\frac{2}{\epsilon'}\sqrt{k}]\\},\dots)$ (because $\\{-\sqrt{k} + i\epsilon':i\in[\frac{2}{\epsilon'}\sqrt{k}]\\}\subseteq [-\sqrt{k},\sqrt{k}]$). This breaks the whole proof. 3. The definition of $\alpha$ (the sparsity) is ambiguous. From the proof it seems that $\alpha$ denotes the fraction of the zero elements. In this case, however, the result in Theorem 3 seems trivial. In particular, the size of the neural network scales inversely with the $\gamma'$ (roughly the fraction of the nonzero elements), because to achieve $\gamma'$ portion of the nonzero elements, one simply need to initialize $\frac{1}{\gamma'}$ independent neural networks and prune completely the rest $\frac{1}{\gamma'} - 1$. Moreover, the definition of $r$ is problematic since it seems that by defining $r = \max\\{\frac{d_i}{d_{i-1}}, \frac{d_{i-1}}{d_i}\\}$, we must have that $r\geq 1$ (instead of $r\leq 1$ as claimed in the paper). 4. This is a minor issue: the upper bound on the over-parameterization does not match the lower bound.

Questions

Why does the paper focus on the exact sparsity constraint $|S| = k$? Would it be more practical to focus on $|S|\leq k$?

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

The paper has a good discussion about its limitation from a practical perspective. However, I believe that the paper needs to add some discussion about the limitation from a theoretical perspective (tightness of the bound, strength of the assumptions etc.)

Response to the Author's Rebuttal

Thank you for your explanations. In particular, I really appreciate your clarification of my confusion related to the mistake in the proof, and, after seeing that the epsilon used here are different, I am convinced that this is not a mistake. Regarding Weakness #1 and #3, I think your answer also makes sense. What I initially did not notice is the non-linear scaling depending on $\frac{k}{n}$ introduced by the cross entropy function. I believe that the paper could benefit more from a more intuitive explanation of the interaction between $n$ and $H_2(\frac{k}{n})$ (maybe giving some examples to showcase the benefit over simply increasing the size by $\frac{1}{\gamma}$ as in the response to Weakness #3 will be helpful). I have adjusted my score accordingly. As a side note, an interesting future direction could be to combine the results with Z. Xiong, F. Liao, A. Kyrillidis, Strong lottery ticket hypothesis with $\epsilon$-perturbation, in: International Conference on Artificial Intelligence and Statistics, PMLR, 2023, pp. 6879–6902, and see how the perturbation affects the sparsity.

Response to rebuttal

I thank the authors for their rebuttal and for providing clarifications. While I still believe that a sufficiently small subset size (of about 15) is enough to practically approximate a network while maintaining a tractable error for the entire network, I do understand the value of a theoretical existence proof of the SLTH for a fixed subset size. I have adjusted my score accordingly.