# Reliably Learning the ReLU in Polynomial Time

arXiv: https://arxiv.org/abs/1611.10258 · HTML: https://mlsanity.com/paper/1611.10258/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2016.

## Built on by (most cited first, 30 of 36)

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [Exponentially Many Local Minima in Quantum Neural Networks](https://mlsanity.com/paper/2110.02479/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Efficient Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2102.07802/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time](https://mlsanity.com/paper/2101.02429/) (2021)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Agnostic Learning of General ReLU Activation Using Gradient Descent](https://mlsanity.com/paper/2208.02711/) (2022)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Leveraging KANs for Expedient Training of Multichannel MLPs via Preconditioning and Geometric Refinement](https://mlsanity.com/paper/2505.18131/) (2025)

## Abstract (arXiv)

We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form x mapsto max(0, w · x) with w ∈ mathbbSn-1. Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution calD on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by calD, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in n) with respect to any distribution on mathbbSn-1 (the unit sphere in n dimensions) and for any error parameter ε = Omega(1/log n) (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where ε must be Omega(1) and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a "dual-loss" approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for "convex piecewise-linear fitting" and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere.