# Learning Halfspaces and Neural Networks with Random Initialization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2015.

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

- [Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory](https://mlsanity.com/paper/2505.11694/) (2025)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)

## Abstract (arXiv)

We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are L-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk ε>0. The time complexity is polynomial in the input dimension d and the sample size n, but exponential in the quantity (L/ε2)log(L/ε). These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin γ>0, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin Omega(γ). As a consequence, the algorithm achieves arbitrary generalization error ε>0 with rm poly(d,1/ε) sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability η<1/2.