Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
  We give superpolynomial statistical query (SQ) lower bounds for learning
two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard
(noise-free) model. No general SQ lower bounds were known for learning ReLU
networks of any depth in this setting: previous SQ lower bounds held only for
adversarial noise models (agnostic learning) or restricted models such as
correlational SQ.
  Prior work hinted at the impossibility of our result: Vempala and Wilmes
showed that general SQ lower bounds cannot apply to any real-valued family of
functions that satisfies a simple non-degeneracy condition.
  To circumvent their result, we refine a lifting procedure due to Daniely and
Vardi that reduces Boolean PAC learning problems to Gaussian ones. We show how
to extend their technique to other learning models and, in many well-studied
cases, obtain a more efficient reduction. As such, we also prove new
cryptographic hardness results for PAC learning two-hidden-layer ReLU networks,
as well as new lower bounds for learning constant-depth ReLU networks from
label queries.
