Sliding down the stairs: how correlated latent variables accelerate learning with neural networks
This addresses a computational bottleneck in neural network training for high-dimensional data, offering a new mechanism for hierarchical learning, though it is incremental in nature.
The paper tackles the problem of efficiently extracting relevant directions from higher-order input cumulants in neural networks, showing that correlations between latent variables accelerate learning and reduce the required sample complexity from d^(p-1) to d^(p/2) in certain cases.
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.