mlsanityData to 14 Oct 2026

Computational-Statistical Gaps in Gaussian Single-Index Models

arXiv 2403.05529 ↗First posted 8 Mar 2024cs.LG stat.MLcited by 44

Not on the map. Why?

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.

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

6 of 47 references.

References · 6

  1. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  2. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  3. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  4. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  5. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  6. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 21; 2026: 17.

44 papers.

Sort:

By area:

  1. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 36
  2. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 19
  3. 2024Progressive distillation induces an implicit curriculumcited by 15
  4. 2025Survey on Algorithms for multi-index modelscited by 15
  5. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  6. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  7. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  8. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  9. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  10. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 9
  11. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 8
  12. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
32 more
  1. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 7
  2. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  3. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  4. 2025Online Learning of Neural Networkscited by 5
  5. 2025Specialization after Generalization: Towards Understanding Test-Time Training in Foundation Modelscited by 5
  6. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 5
  7. 2026A theory of learning data statistics in diffusion models, from easy to hardcited by 5
  8. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  9. 2025Emergent Riemannian geometry over learning discrete computations on continuous manifoldscited by 3
  10. 2025Universality of high-dimensional scaling limits of stochastic gradient descentcited by 3
  11. 2026Learning Sparse Compositional Functions with Norm-Constrained Neural Networkscited by 3
  12. 2025An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Boundscited by 2
  13. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  14. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 2
  15. 2026When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index modelscited by 2
  16. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  17. 2026The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learningcited by 2
  18. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1
  19. 2025Joint Learning in the Gaussian Single Index Modelcited by 1
  20. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1
  21. 2025Provably Extracting the Features from a General Superpositioncited by 1
  22. 2026Interactive Learning of Single-Index Models via Stochastic Gradient Descentcited by 1
  23. 2026Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networkscited by 1
  24. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  25. 2026Learning with Shallow Neural Networks on Cluster-Structured Featurescited by 1
  26. 2026How does feature learning reshape the function space?cited by 1
  27. 2026A Theoretical Analysis of Generalization Dynamics in Neural Networks under Gradient Descent with Weight Decaycited by 1
  28. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  29. 2026Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networkscited by 0
  30. 2026Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruptioncited by 0
  31. 2026Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Modelcited by 0
  32. 2026Approximate Message Passing with Random Initialization for Phase Retrievalcited by 0