  Neural networks excel at discovering statistical patterns in high-dimensional
data sets. In practice, higher-order cumulants, which quantify the non-Gaussian
correlations between three or more variables, are particularly important for
the performance of neural networks. But how efficient are neural networks at
extracting features from higher-order cumulants? We study this question in the
spiked cumulant model, where the statistician needs to recover a privileged
direction or "spike" from the order-$p\ge 4$ cumulants of $d$-dimensional
inputs. Existing literature established the presence of a wide
statistical-to-computational gap in this problem. We deepen this line of work
by finding an exact formula for the likelihood ratio norm which proves that
statistical distinguishability requires $n\gtrsim d$ samples, while
distinguishing the two distributions in polynomial time requires $n \gtrsim
d^2$ samples for a wide class of algorithms, i.e. those covered by the
low-degree conjecture. Numerical experiments show that neural networks do
indeed learn to distinguish the two distributions with quadratic sample
complexity, while "lazy" methods like random features are not better than
random guessing in this regime. Our results show that neural networks extract
information from higher-ordercorrelations in the spiked cumulant model
efficiently, and reveal a large gap in the amount of data required by neural
networks and random features to learn from higher-order cumulants.
