Review for NeurIPS paper: Learning Parities with Neural Networks

This is a very nice paper showing that gradient descent on a carefully regularized hinge loss, two layer network can learn certain sparse parity problems with sample complexity in a certain sense exponentially better than linear methods (including RKHS and NTK after converting to finite width). The reviews and discussions were all eventually in favor, and I personally really enjoyed this paper and also its proof, which I studied in some detail, and plan to investigate even more. Personally, to understand things, I chose q k 18 and n k 40, which I think is kindof implied as natural by the upper bound (it makes the bound like 1/k). While these exponents are large, I think it would help the story for many readers. You can even write "poly"... (b) I think you can spend some time/space explaining the distributional assumption, and what breaks down if you remove it.