acceptodds
Under review as a conference paper at ICLR 2027

Structured vs. Unstructured Pruning: An Exponential Gap

Abstract

The Strong Lottery Ticket Hypothesis (SLTH) states that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initialization without training, suggesting that pruning alone is sufficient. Pruning methods are typically classified as unstructured, where individual weights can be removed from the network, and structured, where parameters are removed according to specific patterns, as in neuron pruning. Existing theoretical results supporting the SLTH rely almost exclusively on unstructured pruning, showing that logarithmic overparameterization suffices to approximate simple target networks. In contrast, neuron pruning has received limited theoretical attention, despite its practical appeal for direct hardware speedups. In this work, we consider the problem of approximating a single bias-free ReLU neuron by pruning hidden units of a randomly initialized two-layer ReLU network, effectively isolating the intrinsic limitations of neuron pruning. We show that achieving an -approximation requires a starting network size of for neuron pruning, whereas weight pruning succeeds with only hidden units, revealing an exponential separation between the two approaches.

Primary area:
learning theory
Keywords:
strong lottery ticket hypothesis, structured pruning, neuron pruning, sparse subnetworks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_pPiiOpenReview ↗
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 1/ε1/\varepsilon, 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

  1. Theorem 1 gives a width lower bound involving min⁡{c0d/ε,2c1d}\min\{c_0d/\varepsilon, 2^{c_1d}\}. Thus, the claimed Ω(d/ε)\Omega(d/\varepsilon) dependence does not hold uniformly for arbitrarily small ε\varepsilon. This qualification should be made clearer in the abstract and conclusion.

  2. 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

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 2c1d2^{c_1d}. The gap stated in the abstract and conclusion concerns the dependence on the accuracy ε\varepsilon at fixed dimension, input radius, and confidence. The lower bound for this comparison comes from Theorem 2, which gives a clean lower bound Ω(1/ε)\Omega(1/\varepsilon) 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)f(x)=\sigma(x_1) 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/ε))O(\log(1/\varepsilon)), while the unit-norm form of Theorem 2 gives a lower bound of Ω(1/ε)\Omega(1/\varepsilon) 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.

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.

Reviewer_i7LWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a construction of a simple target (ReLU) where ϵ\epsilon-approximation under the Strong Lottery Ticket Hypothesis (SLTH) requires the initial neural network to have O(1/ϵ)O(1/\epsilon) neurons if we use structured pruning (removing entire neuron). This is contrasted against earlier work on unstructured pruning (aka weights pruning) that showed dependence in log⁡(1/ϵ)\log(1/\epsilon). As such, the paper main contribution is showing the theoretical limits of SLTH using ReLU as a target, and with candidate network that is the linear ensemble of randomly initialized ReLU neurons. The paper can be intimidating to readers unfamiliar with the mathematical tools (birth-death processes, some classical concentration bounds, and a bit of function sketching). There parts where the flow feels broken but that's likely due to space constraints that pushed the authors to squeeze as much information in the main text as possible.

Critical strengths

The paper is based on purely theoretical work and constructs the claims in well organized structure. The claims are clearly stated with all theroems and lemmas proven. The main strength of the result is the simplicity of the target network: establishing a lower bound on the size of the network to be pruning in structured way to approximate a linear layer followed by a ReLU under the strong lottery ticket hypothesis (SLTH). The result points towards the impracticality of the SLTH approach, as the target function increases in complexity, the number of neurons of same level of complexity need to scale linearly in the desired approximation quality. The the core of the paper is lemma 2, which can be stated as : any linear function on [−δ,δ][-\delta, \delta] can not approximate ReLU(ax)ReLU(ax) better than ∣a∣δ/4|a|\delta/4, and the paper builds on this observation to show a lower bound on the number of randomly initialized ReLU layers that can be (randomly) linearly combined to approximate a simple target ReLU.

Critical weaknesses

The main weakness of this work concerns its significance. The paper is relevant within the context of the SLTH literature, but I'm not convinced that it is relevant within the broader context of machine learning. SLTH consists of starting from a randomly initialized network and then fitting it to a target function solely by pruning neurons (or weights), without modifying the retained weights or neurons. The hypothesis itself is an interesting exercise in testing the theoretical tools of statistical learning for understanding neural networks, but it has no significant practical use in training or fine-tuning neural networks (especially the latter). For instance, the potentially most useful case of starting from a larger, pretrained network falls outside the scope of the framework.

Moreover, even backpropagation-based fitting, where we have access to a feedback signal, would not satisfy the uniform ϵ\epsilon-approximation requirement, as it considers the maximum error over a ball of a given radius. If we take into consideration the fact that neural networks have adversarial examples (slightly perturbed inputs yielding drastically different outputs), then even a non-randomly initialized network (supposedly a more favorable setting) would not satisfy the uniform ϵ\epsilon-approximation requirement.

Questions for authors

The proof of lemma 7 seems to neglect the fact that right moves can allow more left moves or the other way around when we're at the boundaries 0,T. I'm not sure if that affects the final result, but it's worth addressing and might affect theorem 1 (Perhaps also theorem 1 could be made simpler by working on the hyperplane orthogonal to w⋆w^\star on which σ(w⋆x)=0\sigma(w^\star x) = 0.)

The main sticking point is the significance of the work as its current setting (target network and class of hypothesis) is restrictive, which makes me put the current version of the paper at weak rejection.

3 comments

Thank you for the constructive review. We appreciate your questions about the scope of the result and the proof of Lemma 7, as well as your comments on the strengths of the paper.

Scope and significance. We agree that pruning at random initialization addresses a different question from pruning a pretrained network or fine-tuning its weights. Pruning at initialization can nevertheless serve as a way to learn from data. The weights stay fixed, and we use the training data to learn a pruning mask that determines which connections to retain. The edge-popup algorithm is one example of such an approach (Ramanujan et al., 2020). Pensia et al. show that, under their assumptions, a weight mask that achieves error ε\varepsilon exists with high probability at a starting width logarithmic in 1/ε1/\varepsilon. We ask whether comparable width suffices when the mask is restricted to whole neurons. Theorem 2 shows that with Gaussian initialization, approximating even a single bias-free ReLU by neuron pruning requires at least a constant times 1/ε1/\varepsilon hidden neurons in the network before pruning. In our work, we follow the standard SLTH formulation by requiring a single pruned network to approximate the target uniformly over a bounded input domain. This is the criterion used by Malach et al. (Theorem 2.1), Pensia et al. (Theorem 1), and Orseau et al. (Theorem 3). These existence guarantees give a theoretical basis for learning by selecting a pruning mask. They identify widths at which an accurate predictor is available, while finding that predictor efficiently from data is a separate question.

The adversarial examples you describe involve a large change in output between two nearby inputs. Uniform approximation compares the network's output with the target's output at the same input, so the approximation can follow a sharp change in the target and still have small error at both inputs. When the weights can be adjusted, as in the training setting you mention, a single ReLU with the target's input weights and an output weight of 11 achieves zero uniform error on the ball, so it would satisfy the uniform approximation requirement. If we can adjust only the weights from the hidden neurons to the output and keep the input-to-hidden weights fixed at their random initialization, the proof of Theorem 2 still gives the same lower bound on the number of hidden neurons; the proof uses a necessary condition for successful approximation that depends only on the locations of the hidden neurons’ breakpoints, which refitting the output weights leaves unchanged. We will add this remark after Theorem 2.

Proof of Lemma 7. We used a more complicated argument than necessary to derive Eq. (10), and, as you point out, the conditioning step can fail because a move away from 00 or TT can enable a later move in the opposite direction. We should have used a direct union bound, thank you for pointing it out. Since Bkbd=1+Rk−LkB_k^{\mathrm{bd}}=1+R_k-L_k, ending at zero requires Lk>RkL_k > R_k. Then either Rk<pk/2R_k < pk/2 or Lk≥pk/2L_k\ge pk/2. Taking probabilities gives Eq. (10).

Pr⁡(Bkbd=0)≤Pr⁡(Rk<pk/2)+Pr⁡(Lk≥pk/2).\Pr(B_k^{\mathrm{bd}}=0) \le \Pr(R_k < pk/2)+\Pr(L_k\ge pk/2).

Please let us know if you have further questions about the proof or would like to discuss the scope of the results.

Reviewer_i7LWOpenReview ↗

Response to authors' rebuttal

I appreciate the authors' clarification, and I stand corrected on my initial criticism conflating adversarial robustness with uniform approximation. Adversarial robustness would be based on $\max_{|x-y|\leq \epsilon} |f(x) - f(y)| \leq R $ while the ϵ\epsilon approximation in the paper is about max⁡∥x∥≤R∣h(x)−f(y)∣≤ϵ\max_{\|x\|\leq R} |h(x) - f(y)| \leq \epsilon for the target network hh, which neither establishes nor rule out existence of adversarial samples.

Also, with the response on the scope, I (currently) understand the main contribution as an approximation-based (pseudo)-negative result concerning the SLTH: once we add structure (removing an entire neuron), even a simple ReLU layer can be practically hard to approximate using the SLTH approach. The impracticality stems from 2 aspects: the size of the initial random candidate required for the structured pruning under SLTH, but also from the unstructured sparsity which limits possibilities of hardware-optimized implementations for the weight pruning.

Based on this, I'm learning towards an accept and updating my score (optimistically). I'm also curious about an actual numeric example for a MNIST-sized network: 784->128->1 (to match the single neuron output), or any other ReLU-based stop score to give a clear picture of what the theorems imply practically about the size of the initial network.

Thank you for the follow-up and for reconsidering your assessment. To give a more concrete picture, we can share two experiments conducted during the development of this work.

First, we studied the single-neuron approximation problem of Theorem 2 in dimension 2. For each starting width up to 28, we considered 300 random initializations and exhaustively checked whether any neuron-pruned subnetwork achieved uniform error at most ε. The smallest starting widths for which at least half of the sampled initializations contained a successful subnetwork were 12, 15, 19, and 25 for ε = 0.9, 0.8, 0.7, and 0.6, respectively. Over this limited range, these thresholds closely follow an affine dependence on 1/ε, illustrating the accuracy dependence studied in the paper.

We also explored neuron pruning in multilayer networks on Fashion-MNIST, which has the same 784-dimensional inputs as MNIST. Inspired by the edge-popup algorithm of Ramanujan et al. (2020), we implemented a neuron-level analogue, “neuron-popup,” which learns one score per neuron, retains the top-scoring half in each layer, and keeps all network weights fixed. Fully connected networks with two or three hidden layers and up to 10,000 neurons per layer did not exceed 55% training accuracy in these trials. A conventionally trained MLP with fewer than 100 hidden neurons exceeds 90%.

These multilayer experiments provide some practical context beyond the single-neuron target. The substantial performance gap despite the large starting widths motivated our investigation of a more fundamental approximation barrier. However, the neuron-popup results leave open whether accurate subnetworks were absent or the algorithm failed to find them.

We chose to keep the paper focused on the existence of accurate subnetworks independently of any search algorithm. The exhaustive study covers a small finite regime as it quickly becomes computationally infeasible, while the multilayer experiments evaluate a particular optimization heuristic. We therefore did not include these experiments in the paper, as we do not consider them conclusive, but we would be happy to provide further details.

Reviewer_HntkOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies approximation of a bias-free ReLU neuron by pruning hidden neurons from a randomly initialized two-layer network. It derives width lower bounds through breakpoint geometry and stochastic-process arguments, and contrasts them with logarithmic weight-pruning guarantees.

Critical strengths
  1. I like that the paper removes the large target-bias assumption from earlier hardness results. Studying a single bias-free neuron makes the source of the approximation barrier easier to identify.

  2. The breakpoint analysis gives a concrete explanation for the limitations of neuron pruning. The separate treatment of Gaussian output weights in Theorem 2 also extends the result beyond fixed output coefficients.

Critical weaknesses
  1. The headline comparison needs an upper bound for the same architecture: Section 3 uses a linear output, whereas the cited [1] construction doubles target depth. I could not find a derivation showing that its logarithmic bound applies to the exact two-layer, linear-output model studied here.

  2. Section 5.3 needs to make the broken-bin reduction precise, including tolerance rescaling and placement of the target kink inside its bin. These details matter for the asserted initial condition B_0 = 1 and the implication from successful approximation to zero broken bins.

[1] Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. “Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient.” NeurIPS 2020.

Questions for authors
  • Can you state and prove the weight-pruning upper bound with the same depth, output activation, initialization, and target as your lower bound?

  • Can you specify the bin placement and constants that justify the approximation-to-hitting-event reduction?

2 comments

Thank you for the helpful comments and for appreciating the main contribution of our work. You are right that the submission did not clearly spell out a comparison with Pensia et al. under the same assumptions. However, such a comparison can easily be made for a simple target in the setting of Theorem 2 (see below), and we will add the argument to the paper.

The reason why we use one hidden ReLU layer with a linear readout is to match the architectural form of Yehudai and Shamir's random-feature lower bound. Our question is whether this kind of approximation is still hard for a bias-free target when pruning selects whole neurons and keeps their initialized coefficients. [Yehudai and Shamir, Theorem 4.2 and Example 4.3]

Comparison with Pensia et al. The weight-pruning upper bound follows from the scalar ReLU construction shown in the top branch of Pensia et al.’s Fig. 1(c) and the approximation guarantee stated in their Eq. (6). The approximating network in that branch has the same form as the base network g(x)g(x) in our Theorem 2, with a single hidden layer of bias-free ReLU units and a linear readout. Consider the simple target neuron f(x)=σ(x1)f(x)=\sigma(x_1). Pruning all the edges from x2,…,xdx_2,\ldots,x_d in our base network leaves only the scalar input x1x_1. Setting w=1w=1 in Eq. (6) then gives an approximation of f(x)f(x) by pruning a network of width O(log⁡(1/ε))O(\log(1/\varepsilon)). Pensia et al., Fig. 1(c) and Eq. (6)

As a side note, Pensia et al. consider weights drawn from a uniform distribution, but the same holds for a standard normal distribution (which we use in our Theorem 2), as noted in their Remark 1. Pensia et al., Remark 1

The unit-norm form of Theorem 2 (which we mention right before its statement) gives a neuron-pruning width lower bound of Ω(log⁡d/ε)\Omega(\log d/\varepsilon) for the same target f(x)f(x), architecture, and initialization, up to a constant rescaling of the tolerance. At fixed dimension, input radius, and confidence, this gives an exponential separation in how the required width depends on ε\varepsilon. We will add this comparison and better state its scope in the abstract and contributions.

Broken bins in Section 5.3. We left the bin placement and the relation between the two constants CC and cbrc_{\mathrm{br}} implicit, thanks for pointing it out; in the final version, we will make this explicit. We will specify that we center a bin of width ε\varepsilon at the target kink t=−1t=-1, extend the grid in both directions, and keep only full bins in the test interval. This is the interval ∣t∣≤R2−1|t|\le\sqrt{R^2-1} along each line xi(t)=te2i−1+e2i\mathbf{x}_i(t)=t\mathbf{e}_{2i-1}+\mathbf{e}_{2i}. We count broken bins for the residual on this line, given by the output of the neurons selected so far at xi(t)\mathbf{x}_i(t) minus the target value σ(t+1)\sigma(t+1). Initially the residual is −σ(t+1)-\sigma(t+1) and is affine on every bin except the one centered at −1-1.

One particular choice of constants that works is cbr=1/64c_{\mathrm{br}}=1/64 and C=1/128C=1/128. The values of the initial residual at the endpoints and midpoint of the centered bin force any affine fit to have error at least ε/8\varepsilon/8, so that bin is broken and B0=1B_0=1. This choice of cbrc_{\mathrm{br}} also satisfies the steep-breakpoint lemma's condition cbr≤γ/32c_{\mathrm{br}}\le\gamma/32 with γ=1\gamma=1. For successful approximation to imply Bk=0B_k=0, it suffices to take C<cbrC < c_{\mathrm{br}}; if the uniform error is at most CεC\varepsilon, the zero affine function fits the final residual on every bin with error at most Cε<cbrεC\varepsilon < c_{\mathrm{br}}\varepsilon, giving 0 broken bins.

We would be happy to provide further details on either point or address any other questions.

As the discussion closes today, we wanted to draw your attention to the revised PDF (changes in blue). It addresses both of your points, as explained in our reply above. The paragraph after Theorem 2 gives the O(log⁡(1/ε))O(\log(1/\varepsilon)) weight-pruning upper bound for σ(x1)\sigma(x_1) with the same architecture and initialization as Theorem 2. Section 5.3 now specifies the bin placement and constants, justifies B0=1B_0=1, and explains why successful approximation implies Bk=0B_k=0. If these revisions resolve your remaining concerns, we would be grateful if you could reconsider your assessment.

Comments on the paper

1 comment

We thank all reviewers for the helpful comments and discussion. We have uploaded an updated version of the paper to address all the points raised in the reviews. Changes are highlighted in blue.

The main updates are:

  • Comparison with weight pruning: We explain how the construction of Pensia et al. applies to the same target, architecture, and initialization, and clarify the comparison in the abstract, contribution section, and conclusion.
  • Broken bins: We make the bin placement and constants explicit in the proof of Theorem 1, and explain why the process starts with one broken bin and successful approximation requires zero broken bins.
  • Fitting output weights: We add a remark explaining that Theorem 2 also applies when the output weights are fitted while the hidden weights stay fixed.
  • Lemma 7: We correct and simplify the argument leading to Eq. (10) using a direct union bound.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.