Learning Boolean Circuits with Neural Networks
  While on some natural distributions, neural-networks are trained efficiently
using gradient-based algorithms, it is known that learning them is
computationally hard in the worst-case. To separate hard from easy to learn
distributions, we observe the property of local correlation: correlation
between local patterns of the input and the target label. We focus on learning
deep neural-networks using a gradient-based algorithm, when the target function
is a tree-structured Boolean circuit. We show that in this case, the existence
of correlation between the gates of the circuit and the target label determines
whether the optimization succeeds or fails. Using this result, we show that
neural-networks can learn the (log n)-parity problem for most product
distributions. These results hint that local correlation may play an important
role in separating easy/hard to learn distributions. We also obtain a novel
depth separation result, in which we show that a shallow network cannot express
some functions, while there exists an efficient gradient-based algorithm that
can learn the very same functions using a deep network. The negative
expressivity result for shallow networks is obtained by a reduction from
results in communication complexity, that may be of independent interest.
