  As the success of deep learning reaches more grounds, one would like to also
envision the potential limits of deep learning. This paper gives a first set of
results proving that certain deep learning algorithms fail at learning certain
efficiently learnable functions. The results put forward a notion of
cross-predictability that characterizes when such failures take place. Parity
functions provide an extreme example with a cross-predictability that decays
exponentially, while a mere super-polynomial decay of the cross-predictability
is shown to be sufficient to obtain failures. Examples in community detection
and arithmetic learning are also discussed.
  Recall that it is known that the class of neural networks (NNs) with
polynomial network size can express any function that can be implemented in
polynomial time, and that their sample complexity scales polynomially with the
network size. The challenge is with the optimization error (the ERM is
NP-hard), and the success behind deep learning is to train deep NNs with
descent algorithms. The failures shown in this paper apply to training
poly-size NNs on function distributions of low cross-predictability with a
descent algorithm that is either run with limited memory per sample or that is
initialized and run with enough randomness. We further claim that such types of
constraints are necessary to obtain failures, in that exact SGD with careful
non-random initialization can be shown to learn parities. The
cross-predictability in our results plays a similar role the statistical
dimension in statistical query (SQ) algorithms, with distinctions explained in
the paper. The proof techniques are based on exhibiting algorithmic constraints
that imply a statistical indistinguishability between the algorithm's output on
the test model v.s.\ a null model, using information measures to bound the
total variation distance.
