# Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets

arXiv: https://arxiv.org/abs/2311.09858 · HTML: https://mlsanity.com/paper/2311.09858/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 16 Nov 2023.

## Builds on (most cited first, 28 of 28)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Structured Pruning of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1512.08571/) (2015)
- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Pruning from Scratch](https://mlsanity.com/paper/1909.12579/) (2019)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [Learning the Number of Neurons in Deep Networks](https://mlsanity.com/paper/1611.06321/) (2016)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [On the Integrality Gap of Binary Integer Programs with Gaussian Data](https://mlsanity.com/paper/2012.08346/) (2020)
- [Strong Lottery Ticket Hypothesis with varepsilon--perturbation](https://mlsanity.com/paper/2210.16589/) (2022)
- [On the Multidimensional Random Subset Sum Problem](https://mlsanity.com/paper/2207.13944/) (2022)

## Built on by (most cited first, 3 of 3)

- [On the Sparsity of the Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2410.14754/) (2024)
- [The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms](https://mlsanity.com/paper/2511.04217/) (2025)
- [Structured vs. Unstructured Pruning: An Exponential Gap](https://mlsanity.com/paper/2603.02234/) (2026)

## Abstract (arXiv)

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning.