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.
Description
[2002.00585] Proving the Lottery Ticket Hypothesis: Pruning is All You Need
%0 Journal Article
%1 malach2020proving
%A Malach, Eran
%A Yehudai, Gilad
%A Shalev-Shwartz, Shai
%A Shamir, Ohad
%D 2020
%K compression deep-learning
%T Proving the Lottery Ticket Hypothesis: Pruning is All You Need
%U http://arxiv.org/abs/2002.00585
%X 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.
@article{malach2020proving,
abstract = {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.},
added-at = {2020-02-06T00:58:48.000+0100},
author = {Malach, Eran and Yehudai, Gilad and Shalev-Shwartz, Shai and Shamir, Ohad},
biburl = {https://www.bibsonomy.org/bibtex/245ca9ea05f2eef9bdb0ce247c8ec7cd1/kirk86},
description = {[2002.00585] Proving the Lottery Ticket Hypothesis: Pruning is All You Need},
interhash = {4d037738a7c28ed4ccc8ecf7e02d43db},
intrahash = {45ca9ea05f2eef9bdb0ce247c8ec7cd1},
keywords = {compression deep-learning},
note = {cite arxiv:2002.00585},
timestamp = {2020-02-06T00:58:48.000+0100},
title = {Proving the Lottery Ticket Hypothesis: Pruning is All You Need},
url = {http://arxiv.org/abs/2002.00585},
year = 2020
}