- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the gap between structured and unstructured pruning under the Strong Lottery Ticket Hypothesis. The authors consider approximating a single bias-free ReLU neuron by pruning hidden units from a randomly initialized two-layer network. They establish lower bounds showing that neuron pruning requires a width that scales polynomially with , in contrast to the logarithmic dependence achieved by existing unstructured pruning results.
Critical strengths
Pros
The paper addresses a meaningful theoretical question that has received relatively little attention. In particular, establishing a lower bound without relying on large biases is a useful contribution over previous hardness results.
Critical weaknesses
Cons
-
Theorem 1 gives a width lower bound involving . Thus, the claimed dependence does not hold uniformly for arbitrarily small . This qualification should be made clearer in the abstract and conclusion.
-
The exponential separation is an important part of the paper's contribution, but the comparison relies on existing upper bounds obtained under somewhat different network constructions and initialization assumptions. It would help to explain more explicitly how these settings relate and what can be concluded from the comparison. The analysis considers a single target ReLU neuron and a randomly initialized two-layer network, with no modification of the retained weights. While this is a reasonable starting point for a theoretical study, it is unclear whether similar limitations hold for deeper networks or for structured pruning with weight finetuning.
Questions for authors
See weakness
3 comments
I thank the authors for their detailed response and clarification. I re-checked the Theorem 1 and Theorem 2, and I understood the difference on the dimension and precision. Though there is exponential cutoff in Theorem 1, Theorem 2 still gives the bound witout cutoff under fix dimension. Thus, the author has solved my first question.
Regarding the comparison with Pensia et al., the author further explains the relationship between the network structure and initialization assumptions used by two pruning methods, thus making the comparison more clear. About the weight finetuning, the author also clarified that the proof of Theorem 2 also applies to the fitting of the linear output, which partly solves my concern on weight finetuning.
Overall, I think the response my main concen, make the paper more clear. I sugget the auther include the above clarification in the paper. I am willing to maintain my original rating.
Thank you for your follow-up. We have included these clarifications in the revised paper, with changes marked in blue. These cover the scope of the accuracy separation, the comparison with Pensia et al., and the remark on fitting the output weights while keeping the hidden weights fixed.
Thank you for your positive assessment of the paper. We also appreciate your suggestions for clarifying the accuracy range of Theorem 1 and the scope of the comparison.
The cutoff in Theorem 1. You are right that the lower bound in Theorem 1 is capped at 2c1d. The gap stated in the abstract and conclusion concerns the dependence on the accuracy ε at fixed dimension, input radius, and confidence. The lower bound for this comparison comes from Theorem 2, which gives a clean lower bound Ω(1/ε) throughout its stated accuracy range, with no exponential cutoff. We will make this distinction clearer in the contributions section by stating Theorem 1's cutoff alongside its width bound and specifying that the separation in accuracy uses Theorem 2.
Comparison with Pensia et al. and weight finetuning. As detailed in our reply to Reviewer Hntk, Pensia et al.'s scalar construction in Eq. (6) gives a weight-pruning upper bound for the simple target f(x)=σ(x1) using the same base network as Theorem 2. Both pruning methods start with one hidden layer of bias-free ReLUs, a linear readout, and independent Gaussian weights in both layers. At fixed dimension, input radius, and confidence, weight pruning succeeds with width O(log(1/ε)), while the unit-norm form of Theorem 2 gives a lower bound of Ω(1/ε) for neuron pruning.
Theorem 2 also addresses part of your question about fine-tuning. As mentioned in our reply to Reviewer i7LW, its proof gives the same width lower bound when we fit the linear output weights and keep the hidden weights fixed at their Gaussian initialization.
We welcome any additional questions or suggestions and would be glad to clarify the bounds further.