# Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2018.

## Built on by (most cited first, 21 of 21)

- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization](https://mlsanity.com/paper/2307.12851/) (2023)
- [Generalised Latent Assimilation in Heterogeneous Reduced Spaces with Machine Learning Surrogate Models](https://mlsanity.com/paper/2204.03497/) (2022)
- [Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning](https://mlsanity.com/paper/2305.05119/) (2023)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Activated Gradients for Deep Neural Networks](https://mlsanity.com/paper/2107.04228/) (2021)
- [Efficient deep data assimilation with sparse observations and time-varying sensors](https://mlsanity.com/paper/2310.16187/) (2023)
- [The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program](https://mlsanity.com/paper/2110.06488/) (2021)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Piecewise Linear Neural Networks and Deep Learning](https://mlsanity.com/paper/2206.09149/) (2022)
- [Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?](https://mlsanity.com/paper/2306.09955/) (2023)
- [When Are Bias-Free ReLU Networks Effectively Linear Networks?](https://mlsanity.com/paper/2406.12615/) (2024)
- [Achieving Small Test Error in Mildly Overparameterized Neural Networks](https://mlsanity.com/paper/2104.11895/) (2021)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [Boosting Black-Box Adversarial Attacks with Meta Learning](https://mlsanity.com/paper/2203.14607/) (2022)
- [Linearization of ReLU Activation Function for Neural Network-Embedded Optimization: Optimal Day-Ahead Energy Scheduling](https://mlsanity.com/paper/2310.01758/) (2023)
- [Physics-Guided Memory Network for Building Energy Modeling](https://mlsanity.com/paper/2508.09161/) (2025)
- [Fundamental Limits of Deep Learning-Based Binary Classifiers Trained with Hinge Loss](https://mlsanity.com/paper/2309.06774/) (2023)
- [BioAutoML-NAS: An End-to-End AutoML Framework for Multimodal Insect Classification via Neural Architecture Search on Large-Scale Biodiversity Data](https://mlsanity.com/paper/2510.05888/) (2025)

## Abstract (arXiv)

Neural networks with REctified Linear Unit (ReLU) activation functions (a.k.a. ReLU networks) have achieved great empirical success in various domains. Nonetheless, existing results for learning ReLU networks either pose assumptions on the underlying data distribution being e.g. Gaussian, or require the network size and/or training size to be sufficiently large. In this context, the problem of learning a two-layer ReLU network is approached in a binary classification setting, where the data are linearly separable and a hinge loss criterion is adopted. Leveraging the power of random noise perturbation, this paper presents a novel stochastic gradient descent (SGD) algorithm, which can provably train any single-hidden-layer ReLU network to attain global optimality, despite the presence of infinitely many bad local minima, maxima, and saddle points in general. This result is the first of its kind, requiring no assumptions on the data distribution, training/network size, or initialization. Convergence of the resultant iterative algorithm to a global minimum is analyzed by establishing both an upper bound and a lower bound on the number of non-zero updates to be performed. Moreover, generalization guarantees are developed for ReLU networks trained with the novel SGD leveraging classic compression bounds. These guarantees highlight a key difference (at least in the worst case) between reliably learning a ReLU network as well as a leaky ReLU network in terms of sample complexity. Numerical tests using both synthetic data and real images validate the effectiveness of the algorithm and the practical merits of the theory.