The Lottery Ticket Hypothesis from Frankle & Carbin (2019) conjectures that, for typically-sized neural networks, it is possible to find small sub-networks which train faster and yield superior performance than their original counterparts. The proposed algorithm to search for such sub-networks (winning tickets), Iterative Magnitude Pruning (IMP), consistently finds sub-networks with 90-95% less parameters which indeed train faster and better than the overparameterized models they were extracted from, creating potential applications to problems such as transfer learning.

 In this paper, we propose a new algorithm to search for winning tickets, Continuous Sparsification, which continuously removes parameters from a network during training, and learns the sub-network's structure with gradient-based methods instead of relying on pruning strategies. We show empirically that our method is capable of finding tickets that outperforms the ones learned by Iterative Magnitude Pruning, and at the same time providing up to 5 times faster search, when measured in number of training epochs. Although deep neural networks have become ubiquitous in fields such as computer vision and natural language processing, extreme overparameterization is typically required to achieve state-ofthe-art results (Xie et al., 2017; Devlin et al., 2018) , causing higher training costs and hindering applications where memory or inference time are constrained. Recent theoretical work suggest that overparameterization plays a key role in both the capacity and generalization of a network (Neyshabur et al., 2018) , and in training dynamics (Allen-Zhu et al., 2019) . However, it remains unclear whether overparameterization is truly necessary to train networks to state-of-the-art performance. At the same time, empirical approaches have been successful in finding less overparameterized neural networks, either by reducing the network after training (Han et al., 2015; or through more efficient architectures that can be trained from scratch (Iandola et al., 2016) . Recently, the combination of these two approaches lead to new methods which discover efficient architectures through optimization instead of design Savarese & Maire, 2019) . Nonetheless, parameter efficiency is typically maximized by pruning an already trained network. The fact that pruned networks are hard to train from scratch (Han et al., 2015; suggests that, while overparameterization is not necessary for a model's capacity, it might be required for successful network training. Recently, this idea has been put into question by , where heavily pruned networks are trained faster than their original counterparts, often yielding superior performance. A key finding is that the same parameter initialization should be used when re-training the pruned network. A winning ticket, defined by a sub-network and a setting of randomly-initialized parameters, is quickly trainable and has already found applications in, for example, transfer learning (Morcos et al., 2019; Mehta, 2019; Soelen & Sheppard, 2019) , making the search for winning tickets a problem of independent interest. Currently, the standard algorithm to find winning tickets is Iterative Magnitude Pruning (IMP) , which consists of a repeating a 2-stage procedure that alternates between parameter optimization and pruning. As a result, IMP relies on a sensible choice for pruning strategy, and is time-consuming: finding a winning ticket with 1% of the original parameters in a 6-layer CNN requires over 20 rounds of training followed by pruning, totalling over 1000 epochs . Choosing a parameter's magnitude as pruning criterion has also shown to be sub-optimal in some settings (Zhou et al., 2019) , leading to the question of whether better winning tickets can be found by different pruning methods. Moreover, at each iteration, IMP resets the parameters of the network back to initialization, hence considerable time is spent on re-training similar networks with different sparsities. With the goal of speeding up the search for winning tickets in deep neural networks, we design a novel method, Continuous Sparsification, which continuously removes weights from a network during training, instead of following a strategy to prune parameters at discrete time intervals. Unlike IMP, our method approaches the search for sparse networks as a 0 -regularized optimization problem (Louizos et al., 2017) , resulting in a method that can be fully described in the optimization framework. To approximate 0 -regularization, we propose a smooth re-parameterization, allowing for the subnetwork's structure to be directly learned with gradient-based methods. Unlike previous works, our re-parameterization is deterministic, proving more convenient for the tasks of pruning and ticket search, while also yielding faster training times. Experimentally, our method offers superior performance when pruning VGG to extreme regimes, and is capable of finding winning tickets in Residual Networks trained on CIFAR-10 at a fraction of time taken by Iterative Magnitude Pruning. In particular, Continuous Sparsification successfully finds tickets in under 5 iterations, compared to 20 iterations required by Iterative Magnitude Pruning in the same setting. To further speed up the search for sub-networks, our method abdicates parameter rewinding, a key ingredient of Iterative Magnitude Pruning. By showing superior results without rewinding, our experiments offer insights on how ticket search should be performed. With , we now realize that sparse sub-networks can indeed be successfully trained from scratch, putting in question the belief that overparameterization is required for proper optimization of neural networks. Such sub-networks, called winning tickets, can be potentially used to significantly decrease the required resources for training deep networks, as they are shown to transfer between different, but similar, tasks (Mehta, 2019; Soelen & Sheppard, 2019) . Currently, the search for winning tickets is a poorly explored problem, where Iterative Magnitude Pruning stands as the only algorithm suited for this task, and it is unclear whether its key ingredients -post-training magnitude pruning and parameter rewinding -are the correct choices for the task. Here, we approach the problem of finding sparse sub-networks as an 0 -regularized optimization problem, which we approximate through a smooth, parameterized relaxation of the step function. Our proposed algorithm for finding winning tickets, Continuous Sparsification, removes parameters automatically and continuously during training, and can be fully described by the optimization framework. We show empirically that, indeed, post-training pruning might not be a sensible choice for finding winning tickets, raising questions on how the search for tickets differs from standard network compression. With this work, we hope to further motivate the problem of quickly finding tickets in overparameterized networks, as recent work suggests that the task might be highly relevant to transfer learning and mobile applications.
We propose a new algorithm that quickly finds winning tickets in neural networks. This paper proposes a novel objective function that can be used to jointly optimize a classification objective while encouraging sparsification in a network that performs with high accuracy. This work propose a new iterative pruning methods named Continuous Sparsification, which continuously prunes the current weight until it reaches the target ratio.