Research map / Learning theory and algorithms / Sample complexity
Learning from higher-order correlations, efficiently: hypothesis tests, random features, and neural networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies learning from higher-order cumulants in a spiked cumulant model, deriving likelihood-ratio and low-degree bounds showing n~d samples are statistically sufficient but n~d^2 needed for polynomial-time methods, and experiments showing two-layer NNs match the quadratic scaling while random features fail.
Problem
How many samples are needed to detect a spike encoded only in higher-order cumulants (order p>=4) of inputs, both statistically and with polynomial-time algorithms, and how do neural networks and random features compare to these limits?
Approach
Uses an exact likelihood-ratio norm formula and a direct low-degree likelihood-ratio computation for the whitened spiked cumulant model to establish a statistical threshold at n~d and a computational threshold at n~d^2, then shows two-layer ReLU networks trained with SGD reach the quadratic regime while random features do not.
Key results
- Statistical analysis: the LR norm diverges for n ~ d^theta with theta>1, and the LDLR norm stays bounded for theta<2 and diverges for theta>2, so the computational threshold for the spiked cumulant model is n ~ d^2.
- Two-layer ReLU networks (m=5d) learn the spiked cumulant task with quadratic sample complexity, while random features fail to learn it even at quadratic sample complexity.
- Replica theory predicts random-features performance tending to random guessing at linear sample complexity in the spiked Wishart setting, matching experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train a two-layer ReLU neural network instead of using random features | Spiked cumulant classification · Spiked cumulant model | sample complexity: n_class\asymp~d^2; random features cannot solve this task even at quadratic sample complexity | Mixed |
| Train a two-layer ReLU neural network instead of using random features | Spiked Wishart classification · Spiked Wishart model | sample complexity: n_{\mathrm{class}} \gtrsim d; n_{\mathrm{class}} \gtrsim d^2 | Helped |
| Increase sample complexity from linear to quadratic | Random features on the spiked Wishart task · Spiked Wishart model | test accuracy: n_\mathrm{class} \asymp d,d^2 | Helped |
| Increase sample complexity from linear to quadratic | Neural networks on the spiked cumulant task · Spiked cumulant model | test accuracy: n_\mathrm{class}\asymp~d,~d^2 | Helped |
| Increase α toward the lazy-learning regime | Two-layer neural networks on NLGP–Gaussian discrimination · NLGP–Gaussian discrimination | test error | Hurt |
| Use α=100, approaching random features | Two-layer neural network on NLGP–Gaussian discrimination · NLGP–Gaussian discrimination | task learning: n=10^3d | Hurt |
| Orthogonalize initial hidden weights to have overlap 1 / \sqrt d with the spike (ablation) | Neural networks on spiked Wishart and spiked cumulant tasks · Spiked Wishart and spiked cumulant models | distinguishability: 1 / \sqrt d | No clear effect |
| Use a feature-learning network (α=1) rather than a lazy network (ablation) | Two-layer neural network on NLGP–Gaussian discrimination · NLGP–Gaussian discrimination | sample complexity | Helped |
Surprising findings
- Random features fail on the spiked cumulant task even at quadratic sample complexity, while neural networks succeed, revealing a large separation.
- The Gaussian equivalence theorem used for random features breaks down at quadratic sample complexity in the spiked Wishart model.
Limitations
- Null hypothesis restricted to isotropic Gaussian inputs.
- Experiments limited to small input dimensions and the exhaustive-search analysis is only feasible at small d.
- Low-degree conjecture is not proved in general; computational bounds rely on it.
Experimental setup
Datasets: synthetic spiked Wishart data synthetic spiked cumulant data non-linear Gaussian process (NLGP) images
Benchmarks: spiked Wishart classification spiked cumulant classification NLGP classification
Metrics: test accuracy early-stopping test error LR norm low-degree likelihood ratio norm maximum neuron-spike overlap inverse participation ratio
Baselines: random features linear regime random features exhaustive search spectral tensor PCA algorithms
Builds on: spiked Wishart model low-degree conjecture online ICA data model Gaussian equivalence theorem
Closest papers by meaning
- Sliding Down the Stairs: How Correlated Latent Variables Accelerate Learning with Neural Networks (ICML 2024 · similarity 0.92)
- Identification of Causal Structure with Latent Variables Based on Higher Order Cumulants (AAAI 2024 · similarity 0.85)
- Neural Networks Learn Statistics of Increasing Complexity (ICML 2024 · similarity 0.85)
- Asymptotics of feature learning in two-layer networks after one gradient-step (ICML 2024 · similarity 0.85)
- LEAPS: A discrete neural sampler via locally equivariant networks (ICML 2025 · similarity 0.84)
- Feature Contamination: Neural Networks Learn Uncorrelated Features and Fail to Generalize (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.