Abstract
We consider the problem of how many samples from a Gaussian multi-index modelare required to weakly reconstruct the relevant index subspace. Despite itsincreasing popularity as a testbed for investigating the computationalcomplexity of neural networks, results beyond the single-index setting remainelusive. In this work, we introduce spectral algorithms based on thelinearization of a message passing scheme tailored to this problem. Our maincontribution is to show that the proposed methods achieve the optimalreconstruction threshold. Leveraging a high-dimensional characterization of thealgorithms, we show that above the critical threshold the leading eigenvectorcorrelates with the relevant index subspace, a phenomenon reminiscent of theBaik-Ben Arous-Peche (BBP) transition in spiked models arising in random matrixtheory. Supported by numerical experiments and a rigorous theoreticalframework, our work bridges critical gaps in the computational limits of weaklearnability in multi-index model.