Reviews: On the Complexity of Learning Neural Networks

The paper presents a new information-theoretic lower bound for learning neural networks. In particular, it gives an exponential statistical query lower bound that applies even to neural nets with only one hidden layer using common activation functions and log-concave input distributions. By assuming log-concavity for the input distribution, the paper proves a lower bound for a more realistic setting than previous works with applied to discrete distributions. To prove this SQ lower bound, the paper extends the notion of statistical dimension to regression problems and proves that a family of functions which can be represented by neural nets with one hidden layer has exponentially high statistical dimension with respect to any log-concave distribution. It is not clear to me if there are any novel technical ideas in the proofs, but the idea of studying the SQ complexity of neural networks in order to obtain lower bounds for a more realistic class of nets is (as far as I can tell) novel and clever.