Research map / Learning theory and algorithms / Sample complexity
Algorithms and SQ Lower Bounds for Robustly Learning Real-valued 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.
Gives an iterative subspace-finding PAC learner for real-valued multi-index models under Gaussian marginals (robust to adversarial label noise) with d^{O(m)} complexity, plus a nearly matching SQ lower bound, yielding the first efficient learner for positive-homogeneous Lipschitz MIMs and ReLU networks.
Problem
Learning real-valued multi-index models (MIMs) under the Gaussian distribution with square loss, including under adversarial label noise, and characterizing the computational/SQ complexity as a function of dimension.
Approach
An iterative algorithm that grows a subspace V by detecting distinguishing conditional moments of x given discretized (x projected onto V, y in small interval) cells, using spectral analysis of a weighted influence matrix; paired with an SQ lower bound for relativized NGCA showing the d^{Omega(m)} dependence is necessary.
Key results
- Agnostic learner for well-behaved K-MIMs with complexity d^{O(m)} 2^{poly(K/epsilon)} under adversarial label noise.
- SQ lower bound: if distinguishing moments fail for some subspace, SQ learners need d^{Omega(m)} complexity.
- Positive-homogeneous L-Lipschitz K-MIMs learnable with d^2 2^{O(K^3L^2/epsilon^2)} samples, removing network-size dependence for ReLU networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| remove the exponential dependence on network size S | PAC learning homogeneous Lipschitz ReLU networks · Gaussian inputs | sample complexity | Helped |
Limitations
- Complexity is exponential in K and d^{O(m)} in the moment degree m, so not polynomial in all parameters.
- Requires well-behaved condition (bounded variation, bounded norm) on the target class.
- Lower bound applies only to SQ algorithms and to classes where distinguishing moments fail.
Experimental setup
Baselines: prior homogeneous ReLU network learner (exponential in network size)
Builds on: Non-Gaussian Component Analysis discrete multi-index model classification learner generative exponent for single-index models homogeneous ReLU network learning
Closest papers by meaning
- Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks (NeurIPS 2022 · similarity 0.88)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.88)
- Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · similarity 0.86)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.86)
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.86)
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.86)
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.