Survey on Algorithms for multi-index models

2025/04/07 by Joan Bruna, Bruna, Joan, Daniel Hsu +1 · 1 voice · 5 citations
Computer Science · #Neural Networks and Applications #Bayesian Modeling and Causal Inference #Gaussian Processes and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.2504.05426

Abstract

We review the literature on algorithms for estimating the index space in a multi-index model. The primary focus is on computationally efficient (polynomial-time) algorithms in Gaussian space, the assumptions under which consistency is guaranteed by these methods, and their sample complexity. In many cases, a gap is observed between the sample complexity of the best known computationally efficient methods and the information-theoretical minimum. We also review algorithms based on estimating the span of gradients using nonparametric methods, and algorithms based on fitting neural networks using gradient descent

Cited by

• Provably Extracting the Features from a General Superposition
• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
• Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval
• On the Neural Feature Ansatz for Deep Neural Networks
• Learning Multi-Index Models with Hyper-Kernel Ridge Regression

Discussions

• I worked on multi-index models 10-12 years ago, but didn't return despite having some fondness for the topic. Breezed through this new survey in ~1 hr. Lots of good applications here distilling the ge [bsky, 8 points, 1 comments]

Related

• Estimating multi-index models with response-conditional least squares
• Robust Learning of Multi-index Models via Iterative Subspace Approximation
• Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence
• Estimation of Monotone Multi-Index Models
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models