2020/02/03 by Eran Malach, Gilad Yehudai, Malach, Eran +6 · 2 voices · 73 citations
Computer Science · Materials Science · Mathematics · #Algorithm #Artificial intelligence #Bounded function #Combinatorics #Computer network #Computer science #Lottery #Machine Learning and Algorithms #Machine Learning in Materials Science #Mathematics #Parameterized complexity #Pruning #Statistics #Stochastic Gradient Optimization Techniques #Subnetwork #Ticket #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2002.00585
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/02/03 · openalex publication_date 2020/02/03 · arxiv updated 2020/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a randomly-initialized network contains a small subnetwork such that, when trained in isolation, can compete with the performance of the original network. We prove an even stronger hypothesis (as was also conjectured in Ramanujan et al., 2019), showing that for every bounded distribution and every target network with bounded weights, a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, without any further training.