Review for NeurIPS paper: Learning Parities with Neural Networks

Summary and Contributions: This is a theoretical work that gives an example of a class of (distribution,hypothesis)-pairs which: (i) can be learnt efficiently using a 1-layer neural net with random initialization and gradient descent; yet (ii) under any embedding, any linear function obtaining vanishing loss requires exponentially large weights. The construction goes roughly as follows: the hypotheses (parity on a subset A of the coordinates) is quite hard given uniform samples. The distribution has 50% weight on uniform samples, and another 50% on samples that are particularly easy for the given hypothesis (all coordinates in A have identical signs). Since the embedding cannot depend on the distribution, it has no chance of being useful on the hard part for a typical hypothesis. For the learning algorithm, the algorithm first uses the easy half to learn to assign high, positive weights to coordinates in A .