Survey on Algorithms for multi-index models
This is a survey paper, so it is incremental, summarizing existing work for researchers in statistical learning and high-dimensional data analysis.
The paper reviews algorithms for estimating the index space in multi-index models, focusing on computationally efficient methods in Gaussian space, their consistency assumptions, and sample complexity, noting gaps between efficient methods and information-theoretic limits.
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