Optimal Spectral Transitions in High-Dimensional Multi-Index Models
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910997315321856 |
|---|---|
| author | Defilippis, Leonardo Dandi, Yatin Mergny, Pierre Krzakala, Florent Loureiro, Bruno |
| author_facet | Defilippis, Leonardo Dandi, Yatin Mergny, Pierre Krzakala, Florent Loureiro, Bruno |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02545 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Spectral Transitions in High-Dimensional Multi-Index Models Defilippis, Leonardo Dandi, Yatin Mergny, Pierre Krzakala, Florent Loureiro, Bruno Machine Learning Disordered Systems and Neural Networks 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. |
| title | Optimal Spectral Transitions in High-Dimensional Multi-Index Models |
| topic | Machine Learning Disordered Systems and Neural Networks |
| url | https://arxiv.org/abs/2502.02545 |