  (Frankle & Carbin, 2019) shows that there exist winning tickets (small but
critical subnetworks) for dense, randomly initialized networks, that can be
trained alone to achieve comparable accuracies to the latter in a similar
number of iterations. However, the identification of these winning tickets
still requires the costly train-prune-retrain process, limiting their practical
benefits. In this paper, we discover for the first time that the winning
tickets can be identified at the very early training stage, which we term as
early-bird (EB) tickets, via low-cost training schemes (e.g., early stopping
and low-precision training) at large learning rates. Our finding of EB tickets
is consistent with recently reported observations that the key connectivity
patterns of neural networks emerge early. Furthermore, we propose a mask
distance metric that can be used to identify EB tickets with low computational
overhead, without needing to know the true winning tickets that emerge after
the full training. Finally, we leverage the existence of EB tickets and the
proposed mask distance to develop efficient training methods, which are
achieved by first identifying EB tickets via low-cost schemes, and then
continuing to train merely the EB tickets towards the target accuracy.
Experiments based on various deep networks and datasets validate: 1) the
existence of EB tickets, and the effectiveness of mask distance in efficiently
identifying them; and 2) that the proposed efficient training via EB tickets
can achieve up to 4.7x energy savings while maintaining comparable or even
better accuracy, demonstrating a promising and easily adopted method for
tackling cost-prohibitive deep network training. Code available at
https://github.com/RICE-EIC/Early-Bird-Tickets.
