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

A new study resolves a standing theoretical question by showing that two-layer neural networks trained with gradient-based methods can achieve the optimal computational-statistical tradeoff when learning Gaussian single-index models, matching a known statistical query lower bound up to a polylogarithmic factor [1]. The work, posted to arXiv on 13 June 2026, addresses whether neural networks can reach the sample-complexity floor established by the statistical query framework. Prior research had proved that any polynomial-time SQ algorithm requires at least \(\Omega(d^{s^\star/2} \lor d)\) samples, where \(s^\star\) is a generative exponent that captures the intrinsic hardness of the learning problem [1][2]. Until now, no one had demonstrated that a gradient-trained neural network could actually attain that bound [1][3]. The authors propose a unified algorithm that trains a two-layer network in polynomial time. The method draws on earlier techniques such as label transformation and landscape smoothing, but generalizes them so that it works with a variety of loss and activation functions [1][4]. The key result is a sample complexity of \(\widetilde{O}(d^{s^\star/2} \lor d)\), which matches the SQ lower bound for all generative exponents \(s^\star \geq 1\) [1][2]. The algorithm learns a feature representation that strongly aligns with the unknown signal \(\theta^\star\) [1][3]. Single-index models are a classical statistical framework in which the response depends on a one-dimensional projection of the input. They serve as a tractable testbed for studying feature learning in neural networks, a capability that distinguishes deep learning from earlier methods such as Bayesian networks or cluster analysis, which rely on different structural assumptions about data [6][7]. The new paper shows that gradient-based training can extract that projection with near-optimal sample efficiency [1]. The researchers also extend their approach to the sparse setting, where the true signal \(\theta^\star\) has only \(k\) non-zero entries and \(k = o(\sqrt{d})\). They introduce a weight perturbation technique that exploits the sparsity structure, and they derive a corresponding SQ lower bound of order \(\widetilde{\Omega}(k^{s^\star})\) [1][4]. Their method matches that bound up to a polylogarithmic factor as well [1][2]. The weight perturbation technique is of independent interest and, according to the authors, suggests potential gradient-based solutions for other high-dimensional problems such as sparse tensor PCA [1][3]. The findings do not directly involve large language models, which are typically built on transformer architectures and evaluated on benchmarks measuring reasoning and factual accuracy [5]. Instead, the paper operates in the theoretical domain of computational-statistical tradeoffs, providing a precise characterization of when neural networks can be both computationally efficient and statistically optimal [1][2].