The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models

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 = Θ( d 1 ∨ k ⋆ / 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