Review for NeurIPS paper: Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient

Summary and Contributions: This paper considers the strong lottery ticket hypothesis -- a conjecture that a randomly initialized neural network can be pruned (i.e. The authors show that when the target function is a fully-connected neural network, such a pruning will exist with high probability whenever the randomly initialized network has twice as many layers and has a width that is a log(d*l/epsilon) factor larger than the target network. Here, d is the width of the target network, l is its depth, and epsilon is the desired accuracy. This is an improvement over the best/only known result (Malach et al. 2020) on this problem that showed that this can be achieved with a width that is a poly(d, l, 1/epsilon) factor larger than the target. The improvement is achieved by essentially reusing the proof of Malach et al., but fixing a key step where polynomial factors were lost by appealing to known results on random subset sum problems.