# Computational-Statistical Gaps in Gaussian Single-Index Models

arXiv: https://arxiv.org/abs/2403.05529 · HTML: https://mlsanity.com/paper/2403.05529/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 47 references that are in the map.
- First posted on arXiv 8 Mar 2024.

## Builds on (most cited first, 6 of 6)

- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)

## Built on by (most cited first, 30 of 44)

- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Progressive distillation induces an implicit curriculum](https://mlsanity.com/paper/2410.05464/) (2024)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations](https://mlsanity.com/paper/2406.11828/) (2024)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networks](https://mlsanity.com/paper/2506.02651/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models](https://mlsanity.com/paper/2502.16849/) (2025)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Specialization after Generalization: Towards Understanding Test-Time Training in Foundation Models](https://mlsanity.com/paper/2509.24510/) (2025)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [A theory of learning data statistics in diffusion models, from easy to hard](https://mlsanity.com/paper/2603.12901/) (2026)
- [Test time training enhances in-context learning of nonlinear functions](https://mlsanity.com/paper/2509.25741/) (2025)
- [Emergent Riemannian geometry over learning discrete computations on continuous manifolds](https://mlsanity.com/paper/2512.00196/) (2025)
- [Universality of high-dimensional scaling limits of stochastic gradient descent](https://mlsanity.com/paper/2512.13634/) (2025)
- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index models](https://mlsanity.com/paper/2602.02855/) (2026)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning](https://mlsanity.com/paper/2607.03347/) (2026)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)

## Abstract (arXiv)

Single-Index Models are high-dimensional regression problems with planted structure, whereby labels depend on an unknown one-dimensional projection of the input via a generic, non-linear, and potentially non-deterministic transformation. As such, they encompass a broad class of statistical inference tasks, and provide a rich template to study statistical and computational trade-offs in the high-dimensional regime. While the information-theoretic sample complexity to recover the hidden direction is linear in the dimension d, we show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require Omega(dk^star/2) samples, where k^star is a "generative" exponent associated with the model that we explicitly characterize. Moreover, we show that this sample complexity is also sufficient, by establishing matching upper bounds using a partial-trace algorithm. Therefore, our results provide evidence of a sharp computational-to-statistical gap (under both the SQ and LDP class) whenever k^star>2. To complete the study, we provide examples of smooth and Lipschitz deterministic target functions with arbitrarily large generative exponents k^star.