Research map / Learning theory and algorithms / Sample complexity
Robustly Learning Monotone Single-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 the first polynomial-time constant-factor agnostic learner for single-index models with unknown monotone (Lipschitz or bounded (2+zeta)-moment) activations under Gaussian marginals, using a spectral method on a piecewise-constant vector field and a random-walk optimization.
Problem
Agnostic (adversarial label noise) learning of single-index models with unknown monotone activation under Gaussian marginals with the squared loss, seeking a constant-factor approximation in polynomial time.
Approach
Instead of gradient descent on a smoothed loss (which requires knowing the activation), it identifies a vector field H = E[y x^{perp w} h(w.x)] and approximates it via the top eigenvectors of a matrix M_w built from piecewise-constant conditional label means over small bands; the sign ambiguity is handled by a random-walk step with repeated restarts.
Key results
- First polynomial-time constant-factor (universal constant C) agnostic SIM learner under Gaussian marginals for all monotone Lipschitz activations, with N = d^2 poly(1/eps, W, L) samples.
- Extends guarantee to all monotone activations with bounded (2+zeta) moment, including biased halfspaces, with the algorithm using at most poly(N,d) time.
- Prior SIM learner (isotonic-type) achieved only O(W sqrt(OPT)) + eps under bounded labels, and the gradient-based constant-factor learner covered only a restricted activation family with error poly(b/a) OPT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed spectral-alignment learning algorithm for SIMs with unknown monotone activation | SIM learning under Gaussian inputs and adversarial label noise · Gaussian SIMs with adversarial label noise | squared loss guarantee | Helped |
Surprising findings
- Alternating best-fit activation updates with gradient-style w-updates, as in prior SIM frameworks, cannot resolve the uncontrolled correlation with w*.
Limitations
- Algorithm is theoretical and repeats the optimization a polynomial number of times with large exponents in 1/eps (sample complexity like eps^-10).
- Requires bounded (2+zeta) moment or regularity of the activation; without this moment assumption learning is information-theoretically impossible.
- Result is for Gaussian marginals only; extension to other distributions is open.
Experimental setup
Metrics: squared loss relative to OPT (approximation factor C) sample complexity runtime
Baselines: gradient descent on smoothed squared loss isotonic regression SIM learner (Lipschitz monotone, bounded second moment)
Builds on: gradient alignment for smoothed squared loss (Wang et al. style GLM learning) robust halfspace learning isotonic regression for monotone activations
Closest papers by meaning
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.91)
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.90)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.87)
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise (NeurIPS 2024 · similarity 0.86)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.85)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.85)
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.