mlsanityData to 14 Oct 2026

Approximation Schemes for ReLU Regression

arXiv 2005.12844 ↗First posted 26 May 2020cs.LG cs.DS stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We consider the fundamental problem of ReLU regression, where the goal is to output the best fitting ReLU with respect to square loss given access to draws from some unknown distribution. We give the first efficient, constant-factor approximation algorithm for this problem assuming the underlying distribution satisfies some weak concentration and anti-concentration conditions (and includes, for example, all log-concave distributions). This solves the main open problem of Goel et al., who proved hardness results for any exact algorithm for ReLU regression (up to an additive ε). Using more sophisticated techniques, we can improve our results and obtain a polynomial-time approximation scheme for any subgaussian distribution. Given the aforementioned hardness results, these guarantees can not be substantially improved. Our main insight is a new characterization of surrogate losses for nonconvex activations. While prior work had established the existence of convex surrogates for monotone activations, we show that properties of the underlying distribution actually induce strong convexity for the loss, allowing us to relate the global minimum to the activation's Chow parameters.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 9; 2024: 6; 2025: 3; 2026: 3.

34 papers.

Sort:

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  2. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  3. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  4. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  5. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  6. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  7. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  8. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  9. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  10. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  11. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  12. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
22 more
  1. 2024Masks, Signs, And Learning Rate Rewindingcited by 15
  2. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  3. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  4. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  5. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  6. 2021ReLU Regression with Massart Noisecited by 10
  7. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  8. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  9. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  10. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  11. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  12. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  13. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  14. 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
  15. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  16. 2025Near-optimal Active Regression of Single-Index Modelscited by 2
  17. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  18. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  19. 2021Dynamics of Local Elasticity During Training of Neural Netscited by 0
  20. 2026Robust Learning of a Group DRO Neuroncited by 0
  21. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  22. 2026Robust Regression of General ReLUs with Queriescited by 0