# Learning ReLU Networks via Alternating Minimization

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

## Key facts

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

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

- [How much pre-training is enough to discover a good subnetwork?](https://mlsanity.com/paper/2108.00259/) (2021)
- [Convergence Rates of Training Deep Neural Networks via Alternating Minimization Methods](https://mlsanity.com/paper/2208.14318/) (2022)

## Abstract (arXiv)

We propose and analyze a new family of algorithms for training neural networks with ReLU activations. Our algorithms are based on the technique of alternating minimization: estimating the activation patterns of each ReLU for all given samples, interleaved with weight updates via a least-squares step. The main focus of our paper are 1-hidden layer networks with k hidden neurons and ReLU activation. We show that under standard distributional assumptions on the d-dimensional input data, our algorithm provably recovers the true `ground truth' parameters in a linearly convergent fashion. This holds as long as the weights are sufficiently well initialized; furthermore, our method requires only n=widetildeO(dk2) samples. We also analyze the special case of 1-hidden layer networks with skipped connections, commonly used in ResNet-type architectures, and propose a novel initialization strategy for the same. For ReLU based ResNet type networks, we provide the first linear convergence guarantee with an end-to-end algorithm. We also extend this framework to deeper networks and empirically demonstrate its convergence to a global minimum.