Introduction
The "Lottery Ticket Hypothesis" (LTH), proposed in 2019, suggests that dense, randomly initialized neural networks contain sparse subnetworks that can reach the same accuracy as the original network when trained from scratch. The Strong Lottery Ticket Hypothesis (SLTH) goes a step further, positing that these "winning ticket" subnetworks are already performing well at the moment of initialization, requiring no gradient-based training.
This research, synthesized in Emanuele Natale's "Habilitation à Diriger des Recherches" (HDR) thesis, provides a rigorous mathematical foundation for the SLTH, specifically extending it to the structural complexities of Convolutional Neural Networks (CNNs).
The Random Subset Sum Problem (RSSP)
At the heart of this theoretical framework lies the Random Subset Sum Problem (RSSP). The problem asks: given a set of random numbers, can a subset be found that sums to a specific target value?
Natale provides a new, elementary proof demonstrating that with a sufficient pool of random numbers, such a subset almost always exists. In the context of deep learning, the random weights of a large network serve as this pool. By carefully selecting (pruning) specific weights, one can "sum" their contributions to approximate the weights of any target, pre-trained network. This shifts the paradigm of learning from weight adjustment via gradient descent to weight selection via pruning.
Proving the SLTH for CNNs
While previous proofs of the SLTH focused on simple fully connected layers, this work addresses CNNs. The core result, Theorem 31, proves that for any target CNN with $k$ parameters and $\ell$ layers, a random CNN with $O(k \log \frac{k\ell}{\epsilon})$ parameters contains a subnetwork that approximates the target within an error of $\epsilon$ with high probability.
Crucially, the "over-parameterization" required to find these winning tickets is only logarithmic. This suggests that networks do not need to be infinitely large to contain high-performing subnetworks; they only need to be slightly larger than the target architecture by a factor related to the desired precision.
Distributed Dynamics and Global Consensus
Beyond neural networks, the thesis explores how global patterns emerge from local, stochastic interactions in distributed systems. This is particularly relevant to understanding how agents—whether neurons in a brain or robots in a swarm—reach consensus in noisy environments.
The research investigates simple distributed algorithms, such as the 3-Majority dynamics, to model these interactions. A significant challenge in these systems is "stochastic communication," where messages between agents may be corrupted by noise or restricted to a few bits.
The work demonstrates that multi-agent systems can achieve stable consensus even under these constraints, providing theoretical bounds on the time and memory required for such processes.
Applications and Empirical Context
While primarily theoretical, the framework is informed by and applied to various domains:
- Neuroscience: The author utilizes fMRI brain activity graphs and brain atlases to test network alignment algorithms and evaluate functional partitioning.
- Sustainability Modeling: The research includes a Julia re-implementation of the World3 model (WorldDynamics.jl) for integrated assessment of global sustainability.
Conclusion and Future Work
The concept of "learning by selection" draws a compelling parallel to neurodevelopment. Human brains begin with a high density of synapses that are pruned during early life. This thesis provides a theoretical framework for why this "sculpting" process is a computationally powerful learning mechanism.
Future work aims to optimize the universal constants in current proofs to bring the theory closer to practical engineering limits. Additionally, the author suggests extending these RSSP results to spiking neural networks and neuromorphic hardware, where pruning-based learning could thrive over traditional backpropagation.
Summary updated