  Deep learning is also known as hierarchical learning, where the learner
_learns_ to represent a complicated target function by decomposing it into a
sequence of simpler functions to reduce sample and time complexity. This paper
formally analyzes how multi-layer neural networks can perform such hierarchical
learning _efficiently_ and _automatically_ by SGD on the training objective.
  On the conceptual side, we present a theoretical characterizations of how
certain types of deep (i.e. super-constant layer) neural networks can still be
sample and time efficiently trained on some hierarchical tasks, when no
existing algorithm (including layerwise training, kernel method, etc) is known
to be efficient. We establish a new principle called "backward feature
correction", where the errors in the lower-level features can be automatically
corrected when training together with the higher-level layers. We believe this
is a key behind how deep learning is performing deep (hierarchical) learning,
as opposed to layerwise learning or simulating some non-hierarchical method.
  On the technical side, we show for every input dimension $d > 0$, there is a
concept class of degree $\omega(1)$ multi-variate polynomials so that, using
$\omega(1)$-layer neural networks as learners, SGD can learn any function from
this class in $\mathsf{poly}(d)$ time to any $\frac{1}{\mathsf{poly}(d)}$
error, through learning to represent it as a composition of $\omega(1)$ layers
of quadratic functions using "backward feature correction." In contrast, we do
not know any other simpler algorithm (including layerwise training, applying
kernel method sequentially, training a two-layer network, etc) that can learn
this concept class in $\mathsf{poly}(d)$ time even to any $d^{-0.01}$ error. As
a side result, we prove $d^{\omega(1)}$ lower bounds for several
non-hierarchical learners, including any kernel methods.
