  It is argued that deep learning is efficient for data that is generated from
hierarchal generative models. Examples of such generative models include
wavelet scattering networks, functions of compositional structure, and deep
rendering models. Unfortunately so far, for all such models, it is either not
rigorously known that they can be learned efficiently, or it is not known that
"deep algorithms" are required in order to learn them.
  We propose a simple family of "generative hierarchal models" which can be
efficiently learned and where "deep" algorithm are necessary for learning. Our
definition of "deep" algorithms is based on the empirical observation that deep
nets necessarily use correlations between features. More formally, we show that
in a semi-supervised setting, given access to low-order moments of the labeled
data and all of the unlabeled data, it is information theoretically impossible
to perform classification while at the same time there is an efficient
algorithm, that given all labelled and unlabeled data, perfectly labels all
unlabelled data with high probability.
  For the proof, we use and strengthen the fact that Belief Propagation does
not admit a good approximation in terms of linear functions.
