mlsanityData to 7 Oct 2026

ReLU Regression with Massart Noise

arXiv 2109.04623 ↗First posted 10 Sep 2021cs.LG cs.DS stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the realizable setting, but is known to be computationally hard with adversarial label noise. In this work, we focus on ReLU regression in the Massart noise model, a natural and well-studied semi-random noise model. In this model, the label of every point is generated according to a function in the class, but an adversary is allowed to change this value arbitrarily with some probability, which is em at most η < 1/2. We develop an efficient algorithm that achieves exact parameter recovery in this model under mild anti-concentration assumptions on the underlying distribution. Such assumptions are necessary for exact recovery to be information-theoretically possible. We demonstrate that our algorithm significantly outperforms naive applications of ℓ1 and ℓ2 regression on both synthetic and real data.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 35 of its 61 references that are in the map. First posted on arXiv 10 Sep 2021.

Builds on

35 of 61 references.

References · 35

  1. 2017Certified Defenses for Data Poisoning Attackscited by 288
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  5. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  6. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  7. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  8. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  9. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  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. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
23 more
  1. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  2. 2020Learning a Single Neuron with Gradient Methodscited by 50
  3. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  4. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  5. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  6. 2015Robust Regression via Hard Thresholdingcited by 39
  7. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  8. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  9. 2020Approximation Schemes for ReLU Regressioncited by 34
  10. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  11. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  12. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  13. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  14. 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23
  15. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  16. 2020Online Robust Regression via SGD on the l1 losscited by 20
  17. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  18. 2020Point Location and Active Learning: Learning Halfspaces Almost Optimallycited by 13
  19. 2020Consistent regression when oblivious outliers overwhelmcited by 12
  20. 2017Meta-QSAR: a large-scale application of meta-learning to drug design and discoverycited by 10
  21. 2019Fitting ReLUs via SGD and Quantized SGDcited by 10
  22. 2021Boosting in the Presence of Massart Noisecited by 10
  23. 2020On Radial Isotropic Position: Theory and Algorithmscited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

10 papers.

  1. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  2. 2022A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcited by 11
  3. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  4. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
  5. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  6. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  7. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  8. 2025Reweighting Improves Conditional Risk Boundscited by 1
  9. 2024Inferring Change Points in High-Dimensional Regression via Approximate Message Passingcited by 0
  10. 2026Robust Learning of a Group DRO Neuroncited by 0