Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning

Bryn Elesedy, Varun Kanade, Yee Whye Teh

Published 2020-07-16Version 1

We analyse the pruning procedure behind the lottery ticket hypothesis arXiv:1803.03635v5 [cs.LG], iterative magnitude pruning (IMP), when applied to linear models trained by gradient flow. We begin by presenting sufficient conditions on the statistical structure of the features, under which IMP prunes those features that have smallest projection onto the data. Following this, we explore IMP as a method for sparse estimation and sparse prediction in noisy settings, with minimal assumptions on the design matrix. The same techniques are then applied to derive corresponding results for threshold pruning. Finally, we present experimental evidence of the regularising effect of IMP. We hope that our work will contribute to a theoretically grounded understanding of lottery tickets and how they emerge from IMP.