Standard deep learning relies on a familiar paradigm: initialize a network with random weights, and then iteratively adjust those weights using gradient descent until the model performs a task. But what if the optimization process doesn't actually need to change the weights at all?
A fascinating line of research shows that within a sufficiently large, completely random, untrained neural network, there exists a hidden subnetwork that can match the performance of a fully trained model. Instead of modifying parameters, learning can be achieved entirely by selecting them. This insight is known as the Strong Lottery Ticket Hypothesis.
The Shift from Optimization to Selection
The idea that random networks contain high-performing sub-structures was brought to light empirically by Ramanujan et al. in their paper, What's Hidden in a Randomly Weighted Neural Network?. They demonstrated that by freezing a network's random initialization and learning only a binary mask (a matrix of 0s and 1s) to turn specific connections on or off, they could uncover "hidden networks" that achieved high accuracy on standard image classification tasks.
To understand the intuition, imagine traditional training as sculpting a statue out of clay by continuously reshaping the material. Subnetwork discovery, by contrast, treats the random network as a block of marble. The functional logic is already embedded within the diverse random distribution of the block; the "training" process is simply a matter of chiseling away the unnecessary connections.
This concept was further deconstructed by Zhou et al. in Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask. The authors introduced the concept of a Supermask—a binary mask optimized over frozen, random weights that yields a high-performing circuit without a single step of weight optimization. They discovered that the effectiveness of these untrained subnetworks relies heavily on weight selection aligning with the correct signs of the required operations, effectively embedding complex functional logic directly into the network's topology.
Why It Works: The Subset Sum Intuition
How is it mathematically possible for a collection of completely random numbers to approximate a highly specific, trained target network?
The foundational proof of this phenomenon was provided by Yehudai et al. in Proving the Lottery Ticket Hypothesis: Pruning is All You Need. The underlying mechanism relies on a classic mathematical concept: the Subset Sum Problem.
Suppose you want to represent a specific target weight, say $w^* = 0.5$. If you are given a large enough pool of random numbers—for example, $\{-0.6, 0.1, -0.2, 0.4, 0.9\}$—you can select a specific subset ($\{0.1, 0.4\}$) that sums exactly to your target value.
Target Weight: 0.5
Random Pool: [-0.6, 0.1, -0.2, 0.4, 0.9]
Binary Mask: [ 0, 1, 0, 1, 0 ]
------------------------------
Result: 0.1 + 0.4 = 0.5
By expanding this logic from a single parameter to an entire architecture, a fixed, randomly initialized network can approximate any target weight distribution. As long as the random pool is sufficiently large and diverse, the probability of finding a subset of weights that sums to the desired target value approaches 1.
Initially, theoretical proofs required the random network to be exponentially larger than the target network. However, Orseau et al. closed this gap in Logarithmic Pruning is All You Need. They proved that the random network only needs to be a logarithmic factor larger than the target network to guarantee the existence of a perfect approximation, making untrained subnetwork discovery a highly practical alternative to weight training.
Finding the Mask: Gradient-Based Selection
Because finding the perfect subnetwork out of a combinatorial explosion of possibilities is an NP-hard problem, researchers use gradient descent as a search heuristic. Instead of updating the weights, gradients are used to update continuous importance scores assigned to each weight.
To maintain a discrete binary mask during the forward pass while allowing gradients to flow during the backward pass, practitioners typically use a Straight-Through Estimator (STE). During the forward pass, the continuous scores are thresholded to produce a hard binary mask:
$$m_i = \begin{cases} 1 & \text{if } s_i > \text{threshold} \\ 0 & \text{otherwise} \end{cases}$$
During the backward pass, the thresholding operation is ignored, and the gradients pass directly through to update the continuous scores $s_i$. Over time, the optimization process pushes the scores of useful random weights above the threshold, locking them into the active topology of the subnetwork.
Generality Across Architectures and Weights
The existence of these strong winning tickets is not a quirk of simple fully connected networks; it is a fundamental property of neural architectures.
- Convolutional Networks: da Cunha et al. extended the theoretical guarantees to structured domains in Proving the Lottery Ticket Hypothesis for Convolutional Neural Networks, showing that the structural constraints of weight sharing do not prevent the subset-sum approximation from recreating precise convolutional kernels.
- Activation Functions: Rebekka Burkholz demonstrated in Most Activation Functions Can Win the Lottery Without Excessive Depth that this property holds true for a wide variety of continuous activation functions (such as Sigmoid and Tanh), proving that the hypothesis is a general characteristic of over-parameterized models rather than a phenomenon unique to ReLU networks.
- Binary and Quantized Spaces: Strikingly, the underlying random distribution does not even need to be continuous. Diffenderfer et al. introduced the Multi-Prize Lottery Ticket Hypothesis in Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network, proving that accurate binary subnetworks (where weights are strictly $\pm 1$) can be extracted from random initializations. Jy-yong Sohn solidified this mathematically in Finding Nearly Everything within Random Binary Networks, demonstrating that the sheer scale and connectivity of a random network matter far more than the precision of its initial weight values.
By framing learning as a problem of topological selection rather than parameter optimization, untrained subnetwork discovery opens up new horizons for ultra-low-power edge deployment, hardware-efficient binary networks, and a deeper theoretical understanding of why over-parameterized neural networks generalize so well.
Key Foundational Work
Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask (2019) — contributed 4 concept elements to this direction.
Proving the Lottery Ticket Hypothesis: Pruning is All You Need (2020) — contributed 3 concept elements to this direction.
Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask (2019) — contributed 2 concept elements to this direction.