Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough

Despite the great success of deep learning, recent works show that large deep\nneural networks are often highly redundant and can be significantly reduced in\nsize. However, the theoretical question of how much we can prune a neural\nnetwork given a specified tolerance of accuracy drop is still open. This paper\nprovides one answer to this question by proposing a greedy optimization based\npruning method. The proposed method has the guarantee that the discrepancy\nbetween the pruned network and the original network decays with exponentially\nfast rate w.r.t. the size of the pruned network, under weak assumptions that\napply for most practical settings. Empirically, our method improves prior arts\non pruning various network architectures including ResNet, MobilenetV2/V3 on\nImageNet.\n