“For any given task, a sufficiently large neural network will contain within it a good subnetwork that can be isolated and finetuned to solve the given task”, is how we would recall the Lottery Ticket Hypothesis (LTH) (Frankle and Carbin, 2018)¹, but this statement by itself does not specify how large the parent network must be. So, it may be tempting to conclude that the parent network must be really, really large—even exponentially large—for at least a slim chance that some subnetwork wins the lottery. This belief, which I had long held, which I’ve also seen advocated in many forums, is false. This post is an attempt at diagnosing and fixing this false belief.

The dart-throwing disanalogy

The above conclusion, we will see, stems from a naive mental model of LTH. This can be demonstrated even in the simplest scenario where the target task is a single neuron:

We think, “if a randomly-initialized network must contain within it a target neuron of the form $\sigma(\mathbf{w}^\star \cdot \mathbf{x})$, the network needs to throw many darts (say, $\mathbf{w}_1, \mathbf{w}_2, ….$) into the space of all possible neurons, praying that one of the darts strikes close enough to the target $\mathbf{w}^\star$.”

In viewing each random “subnetwork” in the LTH statement as though it was a dart thrown into some $d$-dimensional space (where $d$ is the dimensionality of $\mathbf{w}^\star$), we find ourselves playing a hopeless game even for the single-neuron target: the unpruned, randomly-initialized network must contain $\exp(d)$ many random neurons for us to be sure that the one neuron we covet has materialized in it. ² Thankfully, reality is brighter than this train of thought makes it out to be.

Strong LTH

What broke my pessimism is the proof for “the strong LTH”, originally stated in Ramanujan et al., 2019³ and later proved in Malach et al., 2020⁴. They prove that

couched within a network of just twice (not exponential) the depth of the target network, and polynomial (not exponential) in width, is the winning ticket almost as is (a good subnetwork that doesn’t require finetuning)!

How is this possible? Winning the lottery without exponential subcomponents? And the weights are just randomly-initialized and untouched? Sounds like sorcery!

That… or our mental model of LTH is awfully wrong.

---

This post will work its way to a fix for our mental model by going over the proof intuition for the strong LTH. The reader has two paths before them:

• Either directly go to the “analogy” section for the fix,
• Or first follow the proof closely, think for themselves as to what’s wrong in our mental model, and then cross-verify the fix.

Proof for single neuron

Consider a single-Relu target function of the form $f^\star(\mathbf{x}) = \sigma(\mathbf{w}^\star \cdot \mathbf{x})$. Malach et al., 2020 prove that a 2-layer, polynomially-wide neural network can be pruned down to what approximates $f^\star$. Let us understand what this pruned network looks like, and why such a pruning is possible with only a polynomially-sized network.

What is the pruned network?

The key trick for pruning is to independently reconstruct each feature’s component ($w_i x_i$) through a set of neurons dedicated solely for that feature.

Our pruning of the parent network is as follows:

• Partition the first-layer neurons into $d$ chunks. Chunk $i$ will comnpute feature component $w_i x_i$.
• In the chunk $i$, preserve only input from the $i$’th dimension and prune all else.
• In chunk $i$, we’ll find two ReLU neurons, one that constructs the “positive” side of $w_i^\star x_i$ and the other negative. For this:
  • Consider all the “positive neurons” of the form $u \sigma(v x_i)$ where the first-layer has positive weight $v > 0$ (and $u$ is the second layer weight).
  • Compute the set of products $u\cdot v$ corresponding to all the positive neurons in this chunk. Find the neuron for which $u \cdot v \approx w_i^\star$. Keep this neuron and prune all the other positive neurons. This reconstructs the positive half of the linear function $w_i^\star x_i$.
  • Repeat this for the “negative neurons”.

Thus, the exact pruning looks more like this:

\[\hat{f}(\mathbf{x}) = \sigma\left(\sum_{i=1}^{d} \underbrace{(u_i \sigma(v_i x_i) - u'_i\sigma(-v_i' x_i))}_{w^\star_i x_i}\right),\]

where $v_i, v_i’ > 0$ and $u_i v_i \approx w_i$ and $u_i’v_i’\approx w_i$.

Why does such a pruned network exist?

The strong LTH says that a mere polynomially small neural network can be chipped away to expose this target network, upto some $\epsilon$ error. We can verify how this is possible with a network of just $2d/\epsilon$ neurons:

• From $2d/\epsilon$ neurons, we can allocate $2/\epsilon$ neurons to each of the $d$ chunks that reconstructs the $d$ feature components.
• From $2/\epsilon$ neurons in a chunk, we will roughly have $1/\epsilon$ neurons for the positive neurons, and $1/\epsilon$ for the negative neurons.
• To be able to find at least one neuron with $u\cdot v$ such that $| w^\star_i - u\cdot v| \approx \epsilon$, we only need an $1/\epsilon$ dense sampling of a one-dimensional space, which we do have with $1/\epsilon$ positive (negative) neurons. Thus, we’re done.

The multiple-dart-game analogy

We gain an important realization from the proof:

Rather than playing one hopeless $d$-dimensional game of darts, we’re playing a much easier set of $d$ separate $1$-dimensional games.

In more words: in our original mental model, we imagined a play of darts in an exponentially voluminous $d$-dimensional space, hoping that one dart somehow finds itself close to the true target simultaneously along all dimensions. The construction shows that we only throw darts along each of $d$ dimensions independently, hoping that each dimension is covered densely enough. When pruning, we have the liberty to eliminate all but the best dart along each dimension and aggregate the chosen $d$ darts to create the pruned network.⁵

The mystery of deeper networks

Something still remains mysterious, and that something is about LTH in deeper networks. Are we saying that to recover a cat vs. dog classifier, we can take a twice-as-large randomly-initialized network, and somehow find a “cat ear”-detecting feature just lying there as is? Doesn’t this contradict intuition about expressive capacity? It seems unacceptable that a complex composition of many specific layers of many specific neurons just appears somewhere, in its full, pristine glory, within a randomly-initialized network of modest size!

A few observations help resolve this. First is an important correction that must be made for deeper-layered targets:

it is not that a cat-ear detecting feature (or neuron) that is guaranteed to exist, but a cat-ear detecting subnetwork.

This subnetwork exists padded with a zillion garbage parameters, as a result of which all neurons (in a polyomially-sized network) indeed compute garbage. Only with careful and intelligent pruning does a multi-layered cat-ear-detecting neuron begin to form.

Second is a mathematical observation: the single-neuron argument extends without protest to a setup of multiple neurons composed on top of each other. This the paper shows inductively. In just the same way as our dart-throwing challenge conveniently decomposed into independent games across multiple input features, it also conveniently decomposes across multiple layers! ⁶

Third is an insight about expressive capacity: how does a $2l$-layered neural network have within it every possible $l$ layer detector under the sun? This is because in a model with $n$ frozen parameters, there are $2^n$ ways to prune. It seems quite acceptable then that one of these $2^n$ must detect the ear of a cat.

---

References

I refer the reader to this other excellent post and discussion on the same confusion. Other cited references below: