Sliding down the stairs: how correlated latent variables accelerate
  learning with neural networks
Lorenzo Bardone Sebastian Goldt
Neural networks extract features from data using stochastic gradient descent
(SGD). In particular, higher-order input cumulants (HOCs) are crucial for their
performance. However, extracting information from the $p$th cumulant of
$d$-dimensional inputs is computationally hard: the number of samples required
to recover a single direction from an order-$p$ tensor (tensor PCA) using
online SGD grows as $d^{p-1}$, which is prohibitive for high-dimensional
inputs. This result raises the question of how neural networks extract relevant
directions from the HOCs of their inputs efficiently. Here, we show that
correlations between latent variables along the directions encoded in different
input cumulants speed up learning from higher-order correlations. We show this
effect analytically by deriving nearly sharp thresholds for the number of
samples required by a single neuron to weakly-recover these directions using
online SGD from a random start in high dimensions. Our analytical results are
confirmed in simulations of two-layer neural networks and unveil a new
mechanism for hierarchical learning in neural networks.