New preprint on learning multi-index models via harmonic analysis

Our new paper Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis (with Theodor Misiakiewicz) is now on arXiv.

We analyze the problem of learning multi-index models, in which the label depends on the input only through an unknown low-dimensional subspace. Using the orthogonal symmetry of the model, we obtain a sharp harmonic-analytic description of learning complexity for spherically symmetric inputs. This yields lower bounds in the Statistical Query and Low-Degree Polynomial frameworks that decompose across spherical harmonics. We also propose spectral algorithms based on harmonic tensor unfolding that nearly achieve these bounds and offer a range of statistical–computational trade-offs.