# Learning single-index models via harmonic decomposition

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2025.

## Built on by (most cited first, 7 of 7)

- [A general technique for approximating high-dimensional empirical kernel matrices](https://mlsanity.com/paper/2511.03892/) (2025)
- [Emergent Riemannian geometry over learning discrete computations on continuous manifolds](https://mlsanity.com/paper/2512.00196/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption](https://mlsanity.com/paper/2605.29497/) (2026)

## Abstract (arXiv)

We study the problem of learning single-index models, where the label y ∈ ℝ depends on the input boldsymbolx ∈ ℝd only through an unknown one-dimensional projection langle boldsymbolw_*,boldsymbolxrangle. Prior work has shown that under Gaussian inputs, the statistical and computational complexity of recovering boldsymbolw_* is governed by the Hermite expansion of the link function. In this paper, we propose a new perspective: we argue that spherical harmonics -- rather than Hermite polynomials -- provide the natural basis for this problem, as they capture its intrinsic rotational symmetry. Building on this insight, we characterize the complexity of learning single-index models under arbitrary spherically symmetric input distributions. We introduce two families of estimators -- based on tensor unfolding and online SGD -- that respectively achieve either optimal sample complexity or optimal runtime, and argue that estimators achieving both may not exist in general. When specialized to Gaussian inputs, our theory not only recovers and clarifies existing results but also reveals new phenomena that had previously been overlooked.