The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
Abstract
In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the *generative leap* exponent, a natural extension of the generative exponent from Damian et al. 2024 to the multi-index setting. We show that a sample complexity of $n=\Theta(d^{1 \vee k^\star/2})$ is necessary in the class of algorithms captured by the Low-Degree-Polynomial framework; and also sufficient, by giving a sequential estimation procedure based on a spectral U-statistic over appropriate Hermite tensors.
Cite
Text
Damian et al. "The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models." Advances in Neural Information Processing Systems, 2025.Markdown
[Damian et al. "The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/damian2025neurips-generative/)BibTeX
@inproceedings{damian2025neurips-generative,
title = {{The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models}},
author = {Damian, Alex and Lee, Jason D. and Bruna, Joan},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/damian2025neurips-generative/}
}