Structured vs. Unstructured Pruning: An Exponential Gap

This paper demonstrates an exponential gap between structured and unstructured pruning within the Strong Lottery Ticket Hypothesis, proving that while unstructured weight pruning requires only logarithmic overparameterization to approximate a target neuron, structured neuron pruning necessitates linear overparameterization.

The Gist

The Big Picture: The "Lottery Ticket" Idea

Imagine you buy a massive, chaotic jigsaw puzzle with 10 million pieces. The Strong Lottery Ticket Hypothesis is the idea that hidden inside this giant, messy puzzle is a tiny, perfect picture (a "winning ticket") that can be formed just by picking out the right pieces and throwing the rest away. You don't need to paint or reshape the pieces; you just need to find the right ones.

In the world of AI, this means we can take a huge, over-sized neural network, randomly initialize it, and then "prune" (cut out) the useless parts to leave behind a small, efficient network that works just as well as the big one.

The paper asks a crucial question: Does it matter how we cut the pieces out?

The Two Ways to Cut: Scissors vs. The Whole Row

The authors compare two methods of pruning:

1. Unstructured Pruning (The "Scissors" Method):

   • How it works: You can cut out any single weight (connection) in the network. It's like using a pair of scissors to snip out individual puzzle pieces from anywhere on the board.
   • The Result: You get a very sparse network, but the holes are scattered randomly. It's like a Swiss cheese with holes all over the place.
   • The Problem: Computers are bad at reading "Swiss cheese." They are built to read big, solid blocks of data. So, even though the network is smaller, it doesn't necessarily run faster on real hardware.

2. Structured Pruning (The "Whole Row" Method / Neuron Pruning):

   • How it works: You remove entire chunks at once. In this paper, they focus on Neuron Pruning, where you remove an entire "neuron" (a whole row of connections). It's like taking out an entire row of puzzle pieces in one go.
   • The Result: You get a smaller, cleaner block. This is great for computers because they can process these neat blocks very quickly.
   • The Hope: Everyone hoped this method would be just as good as the "scissors" method, just more practical.

The Shocking Discovery: A Massive Gap

The paper proves that Neuron Pruning is exponentially worse than Scissors Pruning when it comes to finding that "winning ticket" without training.

Here is the analogy to understand the scale of the difference:

• The Goal: You want to approximate a specific target function (let's say, drawing a perfect curve).
• The Scissors Method (Unstructured): To get a good approximation, you need a starting network that is roughly logarithmic in size.
  • Analogy: If you want to get 10 times more precise, you only need to add a tiny bit more to your starting network. It's like needing just a few extra pages in a book to write a much longer story.
• The Row Method (Structured/Neuron Pruning): To get the same level of precision, you need a starting network that is linear (and much larger) in size.
  • Analogy: If you want to get 10 times more precise, you need a starting network that is 10 times bigger. If you want to get it 1,000 times more precise, you need a network 1,000 times bigger.

The "Exponential Gap":
The authors show that to get the same result, the "Row Method" requires a starting network that is exponentially larger than the "Scissors Method."

• If the Scissors Method needs a network of size 1,000, the Row Method might need a network of size 1,000,000 (or even more, depending on the precision).

Why Does This Happen? (The "Breakpoint" Problem)

The authors explain this using a concept called breakpoints.

Imagine the target function is a line that suddenly bends at a specific point (like a tent pole).

• With Scissors: You can pick individual weights to create a "breakpoint" exactly where you need it. You have fine-grained control. You can build a perfect tent pole by stacking tiny, specific blocks.
• With Rows: You are forced to use whole neurons. Each neuron creates a "breakpoint" at a random location. To get a breakpoint exactly where you need it, you have to hope that one of your random neurons happens to land there.
  • If you need a breakpoint in a very specific, tiny spot, and you are only allowed to pick whole rows, you might need to bring in a huge number of random rows just to get one of them to land in the right spot.
  • The more precise you need to be (the smaller the target spot), the more rows you need to throw at the problem.

The "Bias-Free" Twist

Previous research suggested that neuron pruning was hard because of "bias" (a specific mathematical offset). Some people thought, "Oh, if we just remove the bias, maybe it will work better!"

The authors of this paper said, "Let's test that." They created a scenario with zero bias (the cleanest possible setting).

• The Result: Even without bias, neuron pruning still failed miserably compared to weight pruning. The difficulty isn't just about bias; it's a fundamental limitation of removing whole neurons versus removing individual connections.

The Takeaway for Everyone

1. Pruning isn't just one thing: Cutting out individual weights is mathematically much more powerful than cutting out whole neurons.
2. The Efficiency Trade-off: While cutting whole neurons (Structured Pruning) is better for hardware speed (because it creates neat blocks), it is mathematically much harder to find a good solution. You need a massively larger starting network to have a chance of success.
3. The Future: If we want to use structured pruning effectively, we can't just rely on random luck. We might need smarter ways to find these "winning tickets," or we have to accept that we need to start with networks that are exponentially larger than we thought.

In short: If you want to find a needle in a haystack by picking out whole bales of hay (Neuron Pruning), you need a haystack that is exponentially bigger than if you are allowed to pick out individual strands of hay (Weight Pruning).

Technical Summary

1. Problem Statement

The paper addresses a fundamental question in the theory of the Strong Lottery Ticket Hypothesis (SLTH): What is the minimum level of overparameterization required for a randomly initialized neural network to contain a sparse subnetwork that approximates a target function without training?

Specifically, the authors investigate the theoretical gap between two pruning paradigms:

• Unstructured (Weight) Pruning: Removing individual weights (edges). Existing theory shows that logarithmic overparameterization ($O(\log(1/\varepsilon))$) is sufficient to approximate target functions.
• Structured (Neuron) Pruning: Removing entire hidden units (neurons), which corresponds to deleting rows/columns in weight matrices. This is preferred for hardware efficiency but lacks rigorous theoretical guarantees.

The core problem is to determine the sample complexity (number of hidden neurons $N_h$) required for neuron pruning to $\varepsilon$-approximate a single bias-free ReLU neuron, and to compare this against the known bounds for weight pruning.

2. Methodology

The authors isolate the intrinsic limitations of neuron pruning by analyzing the simplest non-trivial case: approximating a single target bias-free ReLU neuron $f(x) = \sigma(\langle w^*, x \rangle)$ using a larger, randomly initialized two-layer bias-free ReLU network $g(x) = \sum \alpha_i \sigma(\langle w_i, x \rangle)$.

Key Technical Strategies:

• Breakpoint Analysis: The proof restricts the high-dimensional network to specific one-dimensional input paths $x_i(t)$. On these paths, the ReLU network becomes a piecewise-linear function. The "breakpoints" (where the slope changes) are determined by the ratios of the random weights.
• Necessary Conditions for Approximation:
  • To approximate the target, the pruned network must align its breakpoints with the target's breakpoint.
  • Lemma 1 & 2: If a "broken bin" (an interval of length $\varepsilon$ containing a breakpoint) exists away from the target breakpoint, or if the target breakpoint is missing, the approximation error exceeds $\varepsilon$.
  • Successful pruning requires the stochastic process of selecting neurons to result in exactly zero broken bins (after canceling the initial target breakpoint).
• Stochastic Process Modeling:
  • The selection of neurons is modeled as a sequential process tracking the number of "broken bins."
  • Coupling: The authors construct a capped process (limiting the max number of broken bins) and a homogeneous birth-death process that stochastically dominates the original pruning process.
  • These simplified processes allow for the derivation of upper bounds on the probability of successful approximation.
• Dimensional Independence: The authors construct $\lfloor d/2 \rfloor$ disjoint input families. Since the breakpoint processes on these families are independent, the probability of success decays exponentially with the input dimension $d$.

3. Key Contributions

1. Exponential Separation Theorem: The paper proves that while weight pruning requires $O(d \log(1/\varepsilon))$ neurons, neuron pruning requires $\Omega(d/\varepsilon)$ hidden neurons to achieve $\varepsilon$-approximation. This establishes an exponential gap in overparameterization requirements between the two methods.
2. Bias-Free Lower Bound: Unlike previous impossibility results for random features (e.g., Yehudai & Shamir, 2019) which relied on the presence of large biases to prove hardness, this work demonstrates that the inefficiency of neuron pruning is intrinsic and persists even in the clean, bias-free setting.
3. Novel Proof Technique: The authors introduce a method of tracking "breakpoints" via carefully constructed input families and reformulating the pruning problem as a hitting probability problem for stochastic birth-death processes.

4. Main Results

Theorem 1 (Lower Bound for Neuron Pruning):
Let $d \ge 2$ and $\varepsilon \in (0, 1)$. Consider a random network with $N_h$ hidden neurons. If $N_h < \min(c \cdot d/\varepsilon, 2cd)$ for a universal constant $c$, then with probability at least $1 - e^{-\Omega(d)}$, no subset of neurons can $\varepsilon$-approximate the target ReLU neuron.

• Implication: To succeed with non-negligible probability, the initial network width must scale linearly with the dimension $d$ and inversely with the error $\varepsilon$.
• Comparison:
  • Weight Pruning: $O(d \log(1/\varepsilon))$ neurons.
  • Neuron Pruning: $\Omega(d/\varepsilon)$ neurons.
  • As $\varepsilon \to 0$, the ratio of required neurons grows exponentially ($\varepsilon^{-1}$ vs $\log(1/\varepsilon)$).

5. Significance and Implications

• Theoretical Validation of Hardware Constraints: The results explain why structured pruning (neuron pruning) is theoretically harder to justify than unstructured pruning. While structured pruning offers practical speedups on hardware (due to contiguous memory access), it demands significantly larger initial models to guarantee the existence of a "winning ticket."
• Limitations of SLTH for Structured Sparsity: The Strong Lottery Ticket Hypothesis, which holds strongly for unstructured pruning with logarithmic overparameterization, faces a fundamental barrier when applied to structured neuron pruning.
• Future Directions: The authors conjecture that the dependence on $d$ might be even stronger (exponential in $d$) for neuron pruning, suggesting that even retaining a single neuron might be asymptotically optimal in high dimensions. This highlights a critical trade-off: computational efficiency (structured pruning) comes at the cost of massive overparameterization requirements.

In summary, the paper provides rigorous mathematical evidence that neuron pruning is fundamentally less expressive than weight pruning in the context of the Strong Lottery Ticket Hypothesis, requiring an exponential increase in network size to achieve the same approximation accuracy.