Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
Preprint
Abstract
We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A $K$-MIM is a function $f:\mathbb{R}^d\to \mathbb{R}$ that depends only on the projection of its input onto a $K$-dimensional subspace. We give a general algorithm for PAC learning a broad class of MIMs with respect to the square loss, even in the presence of adversarial label noise. Moreover, we establish a nearly matching Statistical Query (SQ) lower bound, providing evidence that the complexity of our algorithm is qualitatively optimal as a function of the dimension. Specifically, we consider the class of bounded variation MIMs with the property that degree at most $m$ distinguishing moments exist with respect to projections onto any subspace. In the presence of adversarial label noise, the complexity of our learning algorithm is $d^{O(m)}2^{\mathrm{poly}(K/ε)}$. For the realizable and independent noise settings, our algorithm incurs complexity $d^{O(m)}2^{\mathrm{poly}(K)}(1/ε)^{O(K)}$. To complement our upper bound, we show that if for some subspace degree-$m$ distinguishing moments do not exist, then any SQ learner for the corresponding class of MIMs requires complexity $d^{Ω(m)}$. As an application, we give the first efficient learner for the class of positive-homogeneous $L$-Lipschitz $K$-MIMs. The resulting algorithm has complexity $\mathrm{poly}(d) 2^{\mathrm{poly}(KL/ε)}$. This gives a new PAC learning algorithm for Lipschitz homogeneous ReLU networks with complexity independent of the network size, removing the exponential dependence incurred in prior work.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Robust Learning of Multi-index Models via Iterative Subspace Approximation2025
- Survey on Algorithms for Multi-Index ModelsStatistical Science, 2025
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models2024
- A Multiple-Index Model and Dimension ReductionJournal of the American Statistical Association, 2008
- An Adaptive Estimation of Dimension Reduction SpaceJournal of the Royal Statistical Society Series B: Statistical Methodology, 2002
- Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in ${\Bbb R}^n$Mathematical Research Letters, 2001
- On almost Linearity of Low Dimensional Projections from High Dimensional DataThe Annals of Statistics, 1993
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992
- A theory of the learnableCommunications of the ACM, 1984