Reproduce “Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks” on OpenResearch

About this paper

Eszter Székely, Lorenzo Bardone, Federica Gerace, Sebastian Goldt

Two-layer ReLU neural networks efficiently extract information from higher-order cumulants in high-dimensional datasets, matching computational lower bounds for polynomial-time algorithms and outperforming random features in tasks dependent on these complex correlations. This work utilizes a spiked cumulant model to isolate the role of non-Gaussian features.

Key insights

• The problem of learning solely from higher-order cumulants exhibits a significant statistical-to-computational gap, implying that while information is present with `n ~ d` samples, polynomial-time algorithms generally require `n ~ d^2`.
• Neural networks in their feature-learning regime are remarkably efficient at extracting higher-order correlations, achieving performance consistent with polynomial-time computational limits.
• Random feature models struggle or fail in tasks where information is exclusively contained in higher-order cumulants, highlighting a fundamental advantage of learned features for non-Gaussian pattern discovery.

Summary by alphaXiv.