Research map / Learning theory and algorithms / Matrix and tensor methods
Optimal Spectral Transitions in High-Dimensional Multi-Index Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Designs two spectral estimators for Gaussian multi-index models, obtained by linearizing a GAMP-type message passing scheme, and analyzes their weak-recovery threshold, which matches the optimal AMP threshold alpha_c without informed initialization.
Problem
Weak recovery of the relevant index subspace in Gaussian multi-index models: how many samples n ~ alpha d are needed for a computationally efficient method to correlate with the weights, without side information.
Approach
Two spectral methods (asymmetric L-matrix and symmetric T-matrix) derived from linearizing optimal GAMP around the uninformed fixed point; state evolution gives the exact critical threshold alpha_c, and a BBP-like transition is conjectured for the leading eigenvector, proven for a subclass with jointly diagonalizable G(y).
Key results
- Asymmetric and symmetric spectral estimators are shown to attain the optimal weak-recovery threshold alpha_c for link functions with generative exponent 2, without informed initialization.
- For the symmetric method with jointly diagonalizable G(y), the top eigenvalue of T converges to lambda_s = 1 for alpha > alpha_c, and the bulk density is bounded by lambda_b < 1.
- Closed-form overlap expressions are given for examples such as sign(z1 z2), p^{-1}||z||^2 and z1 z2^{-1}; e.g. for sign(z1z2), m^2 = (1 - pi^2/(4 alpha))_+ with alpha_c = pi^2/4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the asymmetric spectral method without informed initialization | Gaussian multi-index models · weak subspace recovery | critical sample complexity | Helped |
| use the symmetric spectral method without informed initialization | Gaussian multi-index models · weak subspace recovery | critical sample complexity | Helped |
Limitations
- Full rigorous proof of the BBP-type conjecture for general multi-index models is missing; relies on random matrix control of spectral norms.
- Rigorous result for the symmetric method holds only when E[zz^T|y] has y-independent orthonormal eigenbasis.
- Restricted to link functions with generative exponent 2; hard cases such as sparse parities are excluded.
Experimental setup
Metrics: overlap m between spectral estimator and W_star critical sample complexity alpha_c top eigenvalue convergence
Baselines: optimal GAMP with side information TAP spectral method LAMP spectral method
Builds on: approximate message passing generalized approximate message passing linear GAMP spectral methods for single-index models (TAP/LAMP) non-backtracking matrix
Closest papers by meaning
- Spectral Phase Transition and Optimal PCA in Block-Structured Spiked Models (ICML 2024 · similarity 0.88)
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.88)
- Random Matrix Theory of Early-Stopped Gradient Flow: A Transient BBP Scenario (NeurIPS 2026 · similarity 0.86)
- Free Decompression with Algebraic Spectral Curves (NeurIPS 2026 · similarity 0.86)
- Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics (ICLR 2025 · similarity 0.86)
- Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.