# Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 52 references that are in the map.
- First posted on arXiv 13 Jun 2026.

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

- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries](https://mlsanity.com/paper/2407.05622/) (2024)
- [Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm](https://mlsanity.com/paper/1711.04952/) (2017)
- [Pruning is Optimal for Learning Sparse Features in High-Dimensions](https://mlsanity.com/paper/2406.08658/) (2024)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)

## Abstract (arXiv)

In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires Omega(ds^star/2lor d) samples, where s^star is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal θ^star, with sample complexity widetildeO (ds^star/2 lor d), matching the SQ lower bound up to a polylogarithmic factor for all generative exponents s^star≥ 1. Furthermore, we extend our approach to the setting where θ^star is k-sparse for k = o(√d) by introducing a novel weight perturbation technique that leverages the sparsity structure. We derive a corresponding SQ lower bound of order widetildeOmega(ks^star), matched by our method up to a polylogarithmic factor. Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.