mlsanityData to 7 Oct 2026

Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models

arXiv 2411.05708 ↗First posted 8 Nov 2024cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

A single-index model (SIM) is a function of the form σ(wast · x), where σ: ℝ → ℝ is a known link function and wast is a hidden unit vector. We study the task of learning SIMs in the agnostic (a.k.a. adversarial label noise) model with respect to the L22-loss under the Gaussian distribution. Our main result is a sample and computationally efficient agnostic proper learner that attains L22-error of O(OPT)+ε, where OPT is the optimal loss. The sample complexity of our algorithm is tildeO(d^lceil kast/2rceil+d/ε), where kast is the information-exponent of σ corresponding to the degree of its first non-zero Hermite coefficient. This sample bound nearly matches known CSQ lower bounds, even in the realizable setting. Prior algorithmic work in this setting had focused on learning in the realizable case or in the presence of semi-random noise. Prior computationally efficient robust learners required significantly stronger assumptions on the link function.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 8 Nov 2024.

Builds on

26 of 42 references.

References · 26

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  4. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  5. 2016A Geometric Analysis of Phase Retrievalcited by 92
  6. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  7. 2014A statistical model for tensor PCAcited by 72
  8. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  9. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  10. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  11. 2017Learning ReLUs via Gradient Descentcited by 54
  12. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
14 more
  1. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  2. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  3. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  4. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  5. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  6. 2020Approximation Schemes for ReLU Regressioncited by 34
  7. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  8. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  9. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  10. 2016Homotopy Analysis for Tensor PCAcited by 12
  11. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  12. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  13. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11
  14. 2024Robustly Learning Single-Index Models via Alignment Sharpnesscited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  2. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  3. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  4. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0