Mathematics

Neural networks excel at discovering statistical patterns in high-dimensional datasets. In practice, high-order cumulants, which quantify the non-Gaussian correlations between three or more variables, are particularly importantfor the performance of neural networks. But how hard is it to learn from them? In other words, how many samples from a distribution are needed for a statistician to efficiently learn its high-order cumulants? I will first present our study of this question in the spiked cumulant model, where the task is to recover a privileged direction or 'spike' from the order-p $\ge$ 4 cumulants of d-dimensional inputs. The low-degree method predicts that this task is hard: a quadratic number n of samples (with respect to d) is required to solve the taskusing a polynomial-time algorithm.This result raises the question of how neural networks manage to efficiently extract relevant directions from the higher-order correlations of their inputs. I will show that a possible answer to this question is that neural networks leverage ’side information’ from the Gaussian part of the target distribution. To demonstrate this, we will examine neural networks’ performance on a model with two spikes: an ”easy” spike in the covariance and one ”hard” spike in the high order cumulants. We will see that a positive correlation between the latent variables corresponding to these two different spiked directions can speed up the learning of the hard direction, leading to weak recovery of both directions in linear sample complexity.