mlsanityData to 7 Oct 2026

Robustly Learning a Single Neuron via Sharpness

arXiv 2306.07892 ↗First posted 13 Jun 2023cs.LG cs.DS math.OCcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning a single neuron with respect to the L22-loss in the presence of adversarial label noise. We give an efficient algorithm that, for a broad family of activations including ReLUs, approximates the optimal L22-error within a constant factor. Our algorithm applies under much milder distributional assumptions compared to prior work. The key ingredient enabling our results is a novel connection to local error bounds from optimization theory.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 17 of its 38 references that are in the map. First posted on arXiv 13 Jun 2023.

Builds on

17 of 38 references.

References · 17

  1. 2016Gaussian Error Linear Units (GELUs)cited by 3,431
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  5. 2017Learning ReLUs via Gradient Descentcited by 54
  6. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  7. 2020Learning a Single Neuron with Gradient Methodscited by 50
  8. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  9. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  10. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
  11. 2020Approximation Schemes for ReLU Regressioncited by 34
  12. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
5 more
  1. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  2. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  3. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  4. 2018Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditionscited by 9
  5. 2020Provable Training of a ReLU Gate with an Iterative Non-Gradient Algorithmcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 3; 2025: 4; 2026: 3.

12 papers.

  1. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  2. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  3. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  4. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  5. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  6. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  7. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  8. 2025Linear Regression under Missing or Corrupted Coordinatescited by 1
  9. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  10. 2026Robust Learning of a Group DRO Neuroncited by 0
  11. 2026Robust Regression of General ReLUs with Queriescited by 0
  12. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0