Research map / Learning theory and algorithms / Sample complexity
Sample and Computationally Efficient Robust Learning of Gaussian 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 sample- and computationally efficient constant-factor agnostic proper learner for Gaussian single-index models under a general Hermite-based link-function assumption, combining tensor-PCA initialization with Riemannian SGD on a truncated L2 loss.
Problem
Agnostically (adversarial label noise) learning single-index models with arbitrary (not necessarily monotone or Lipschitz) link functions under Gaussian marginals with respect to squared loss, with efficient sample and computational complexity.
Approach
Initialize via tensor unfolding (tensor PCA) applied to the empirical k*-Chow tensor E[y He_k(x)] to get a warm start with constant alignment to w*, then run Riemannian minibatch SGD on the sphere for a truncated loss keeping only the first nonzero Hermite term; a sharpness property of the Riemannian gradient ensures geometric convergence despite agnostic noise.
Key results
- Achieves L2^2 error O(C_{k*} OPT) + eps with sample complexity O~(d^{ceil(k*/2)} + d/eps) and poly time, the first such constant-factor agnostic proper learner for this link class.
- Tensor PCA initialization yields w0 with w0·w* >= 1 - min{1/k*, 1/2} using O(d^{ceil(k*/2)}) samples when OPT is below a constant times c_{k*}^2/(64k*)^2.
- Riemannian minibatch SGD on truncated loss converges geometrically, giving O(log(1/eps)) iterations; sample bound nearly matches CSQ lower bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tensor PCA initialization followed by warm-started Riemannian minibatch SGD on the truncated loss | Gaussian SIM learning under agnostic noise · Gaussian SIMs, agnostic | L2^2 error | Helped |
Surprising findings
- Degree-1 Chow vector carries no information about w* when k*>=2 under agnostic noise, so higher-degree Chow tensors are necessary.
- Smoothing-based SGD of prior work fails under agnostic noise because the noise term dominates the signal unless OPT is tiny (~d^{-k*/4}).
Limitations
- Error guarantee is a constant-factor approximation C*OPT + eps rather than OPT + eps, which is argued to be computationally hard.
- Requires a constant lower bound on the first nonzero Hermite coefficient c_{k*} and a bounded fourth moment, and only Gaussian marginals are handled.
Experimental setup
Datasets: synthetic Gaussian-input labeled samples with adversarial label noise
Metrics: L2^2 loss relative to OPT sample complexity iteration complexity
Baselines: Chen and Meka 2020 smoothing-based SGD Goel et al. 2020 bounded activation agnostic learner Damian et al. 2023 / Dudeja and Hsu 2018 partial trace SQ algorithm
Builds on: tensor unfolding (Hopkins et al.) Chow parameters Wedin's theorem Riemannian SGD Soltanolkotabi-type SIM learning under Gaussian inputs
Closest papers by meaning
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.91)
- Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.91)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.88)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.88)
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.87)
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise (NeurIPS 2024 · similarity 0.87)
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.