# Robust Learning of Multi-index Models via Iterative Subspace Approximation

arXiv: https://arxiv.org/abs/2502.09525 · HTML: https://mlsanity.com/paper/2502.09525/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 13 Feb 2025.

## Builds on (most cited first, 24 of 24)

- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Learning from Noisy Labels with Deep Neural Networks: A Survey](https://mlsanity.com/paper/2007.08199/) (2020)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [A Unified View of Label Shift Estimation](https://mlsanity.com/paper/2003.07554/) (2020)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case](https://mlsanity.com/paper/1902.02244/) (2019)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)

## Built on by (most cited first, 9 of 9)

- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise](https://mlsanity.com/paper/2502.11413/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)
- [Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms](https://mlsanity.com/paper/2602.23341/) (2026)
- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)
- [Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals](https://mlsanity.com/paper/2605.21428/) (2026)
- [Approximate Message Passing with Random Initialization for Phase Retrieval](https://mlsanity.com/paper/2608.01654/) (2026)

## Abstract (arXiv)

We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution. A K-MIM is any function f that only depends on a K-dimensional subspace. We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties. Our main contribution is a general robust learner that is qualitatively optimal in the Statistical Query (SQ) model. Our algorithm iteratively constructs better approximations to the defining subspace by computing low-degree moments conditional on the projection to the subspace computed thus far, and adding directions with relatively large empirical moments. This procedure efficiently finds a subspace V so that f(x) is close to a function of the projection of x onto V. Conversely, for functions for which these conditional moments do not help, we prove an SQ lower bound suggesting that no efficient learner exists. As applications, we provide faster robust learners for the following concept classes: * bf Multiclass Linear Classifiers We give a constant-factor approximate agnostic learner with sample complexity N = O(d) 2poly(K/ε) and computational complexity poly(N ,d). This is the first constant-factor agnostic learner for this class whose complexity is a fixed-degree polynomial in d. * bf Intersections of Halfspaces We give an approximate agnostic learner for this class achieving 0-1 error K tildeO(OPT) + ε with sample complexity N=O(d2) 2poly(K/ε) and computational complexity poly(N ,d). This is the first agnostic learner for this class with near-linear error dependence and complexity a fixed-degree polynomial in d. Furthermore, we show that in the presence of random classification noise, the complexity of our algorithm scales polynomially with 1/ε.