Optimal Spectral Transitions in High-Dimensional Multi-Index Models

Florent Krzakala (Swiss Federal Institute of Technology Lausanne) · Leonardo Defilippis (CNRS, École Normale Supérieure) · Yatin Dandi (Swiss Federal Institute of Technology Lausanne) · Pierre Mergny (EPFL - EPF Lausanne) · Bruno Loureiro (École Normale Supérieure)

baik–ben arous–peche transitioncomputational complexitygaussian multi-index modelhigh-dimensional characterizationindex subspaceleading eigenvectormessage passing schemenumerical experimentsoptimal reconstruction thresholdrandom matrix theoryspectral algorithmsspiked modelsweak learnabilityweak reconstruction

We consider the problem of how many samples from a Gaussian multi-index model are required to weakly reconstruct the relevant index subspace. Despite its increasing popularity as a testbed for investigating the computational complexity of neural networks, results beyond the single-index setting remain elusive. In this work, we introduce spectral algorithms based on the linearization of a message passing scheme tailored to this problem. Our main contribution is to show that the proposed methods achieve the optimal reconstruction threshold. Leveraging a high-dimensional characterization of the algorithms, we show that above the critical threshold the leading eigenvector correlates with the relevant index subspace, a phenomenon reminiscent of the Baik–Ben Arous–Peche (BBP) transition in spiked models arising in random matrix theory. Supported by numerical experiments and a rigorous theoretical framework, our work bridges critical gaps in the computational limits of weak learnability in multi-index model.