Learning ReLU Networks via Alternating Minimization

Abstract

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=\tilde{O}(d{k}^2)$ 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.

References in corpus (7)

• Visualizing the Loss Landscape of Neural Nets
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Recovery Guarantees for One-hidden-layer Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• Learning ReLUs via Gradient Descent
• The Multilinear Structure of ReLU Networks

Cited by in corpus (3)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Subgradient Descent Learns Orthogonal Dictionaries
• DANTE: Deep AlterNations for Training nEural networks