mlsanityData to 7 Oct 2026

Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks

arXiv 2312.14922 ↗First posted 22 Dec 2023stat.ML cond-mat.stat-mech cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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≥ 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 ngtrsim d samples, while distinguishing the two distributions in polynomial time requires n gtrsim d2 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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 56 of its 101 references that are in the map. First posted on arXiv 22 Dec 2023.

Builds on

56 of 101 references.

References · 56

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 748
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  7. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  8. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  9. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  10. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  11. 2017High-dimensional dynamics of generalization error in neural networkscited by 238
  12. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
38 more
  1. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  2. 2019Linearized two-layers neural networks in high dimensioncited by 155
  3. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  4. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  5. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  6. 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
  7. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  8. 2020The Gaussian equivalence of generative models for learning with shallow neural networkscited by 113
  9. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  10. 2016TensorLy: Tensor Learning in Pythoncited by 104
  11. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  12. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  13. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  14. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  15. 2020Learning Parities with Neural Networkscited by 77
  16. 2014A statistical model for tensor PCAcited by 72
  17. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
  18. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  19. 2021Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensionscited by 52
  20. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  21. 2022Neural networks trained with SGD learn distributions of increasing complexitycited by 50
  22. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  23. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  24. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  25. 2022Data-driven emergence of convolutional structure in neural networkscited by 29
  26. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  27. 2020Geometric compression of invariant manifolds in neural netscited by 28
  28. 2016Statistical limits of spiked tensor modelscited by 27
  29. 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
  30. 2015MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channelcited by 22
  31. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  32. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  33. 2023Six Lectures on Linearized Neural Networkscited by 19
  34. 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
  35. 2022Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regimecited by 18
  36. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  37. 2017Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squarescited by 17
  38. 2015Phase Transitions in Sparse PCAcited by 15

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 1.

3 papers.

  1. 2024Sliding down the stairs: how correlated latent variables accelerate learning with neural networkscited by 12
  2. 2024Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depthcited by 4
  3. 2025Feature learning is decoupled from generalization in high capacity neural networkscited by 1