Draft:Strong Lottery Ticket Hypothesis

The Strong Lottery Ticket Hypothesis (SLTH) is a theoretical framework in deep learning suggesting that sufficiently large random neural networks can contain sparse subnetworks capable of approximating any target neural network of smaller size without requiring additional training. This hypothesis builds upon the foundational Lottery Ticket Hypothesis (LTH), which posits that sparse subnetworks can achieve comparable performance to the full network when trained in isolation from initialization.

Origins and Background

The LTH, introduced by Frankle and Carbin (2018), demonstrated that iterative pruning and weight rewinding could identify sparse subnetworks—referred to as "winning tickets"—that match or exceed the performance of the original network. The SLTH extends this idea, suggesting that certain subnetworks, even without training, can already approximate specific target networks.

The SLTH gained attention due to its implications for efficient deep learning, particularly in identifying "winning tickets" directly from large, randomly initialized networks, eliminating the need for extensive training.

Formalization

The SLTH can be described informally as follows:

With high probability, a random neural network $N_{\Omega }$ with $m$ parameters contains a sparse subnetwork $N_{S}$ that can approximate any target neural network $N_{t}$ of a smaller size, e.g., $O\left({\frac {m}{\log ^{2}(1/\epsilon )}}\right)$, to within a specified error $\epsilon$.

Results

Advancements in this area have focused on improving theoretical guarantees about the size and structure of these sparse subnetworks, often relying on techniques such as the Random Subset Sum (RSS) Problem or its variants. These tools provide insights into how sparsity impacts the overparameterization required to ensure the existence of such subnetworks.

Theoretical Guarantees

1. A random network with $m$-parameters can be pruned to approximate target networks with ${\frac {m}{\log(1/\epsilon )}}$ parameters. 2. SLTH results have been extended to different neural architectures, including dense, convolutional, and more general equivariant networks.

Sparsity Constraints

The authors of Natale et al. provide proofs for the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks.

Challenges and Open Questions

Despite theoretical guarantees, the practical discovery of winning tickets remains algorithmically challenging:

- Efficiency of Identification: There are no formal guarantees for reliably finding winning tickets efficiently. Empirical methods, like "training by pruning," often require computationally expensive operations such as backpropagation.

- Sparse Structure: The relationship between sparsity levels, overparameterization, and network architectures is still not fully understood.

While empirical methods suggest that sparse subnetworks can be found, reliable algorithms for their discovery are still an open research area.

See also

• Lottery_ticket_hypothesis