Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis

We study the problem of learning multi-index models (MIMs), where the label depends on the input boldsymbolx ∈ ℝd only through an unknown mathsfs-dimensional projection boldsymbolW_*^mathsfT boldsymbolx ∈ ℝ^mathsfs. Exploiting the equivariance of this problem under the orthogonal group Od, we obtain a sharp harmonic-analytic characterization of the learning complexity for MIMs with spherically symmetric inputs -- which refines and generalizes previous Gaussian-specific analyses. Specifically, we derive statistical and computational complexity lower bounds within the Statistical Query (SQ) and Low-Degree Polynomial (LDP) frameworks. These bounds decompose naturally across spherical harmonic subspaces. Guided by this decomposition, we construct a family of spectral algorithms based on harmonic tensor unfolding that sequentially recover the latent directions and (nearly) achieve these SQ and LDP lower bounds. Depending on the choice of harmonic degree sequence, these estimators can realize a broad range of trade-offs between sample and runtime complexity. From a technical standpoint, our results build on the semisimple decomposition of the Od-action on L2 (mathbbSd-1) and the intertwining isomorphism between spherical harmonics and traceless symmetric tensors.