Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks
This work addresses a fundamental computational bottleneck in learning from non-Gaussian correlations for machine learning practitioners, though it is incremental by deepening existing statistical-to-computational gap analyses.
The paper tackles the efficiency of neural networks at extracting features from higher-order cumulants, showing that they achieve quadratic sample complexity (n ≳ d²) for polynomial-time distinguishability in the spiked cumulant model, while random features fail. It proves statistical distinguishability requires n ≳ d samples, revealing a large gap between neural networks and lazy methods.
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.