  An important characteristic of neural networks is their ability to learn
representations of the input data with effective features for prediction, which
is believed to be a key factor to their superior empirical performance. To
better understand the source and benefit of feature learning in neural
networks, we consider learning problems motivated by practical data, where the
labels are determined by a set of class relevant patterns and the inputs are
generated from these along with some background patterns. We prove that neural
networks trained by gradient descent can succeed on these problems. The success
relies on the emergence and improvement of effective features, which are
learned among exponentially many candidates efficiently by exploiting the data
(in particular, the structure of the input distribution). In contrast, no
linear models on data-independent features of polynomial sizes can learn to as
good errors. Furthermore, if the specific input structure is removed, then no
polynomial algorithm in the Statistical Query model can learn even weakly.
These results provide theoretical evidence showing that feature learning in
neural networks depends strongly on the input structure and leads to the
superior performance. Our preliminary experimental results on synthetic and
real data also provide positive support.
