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

Abstract

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 \emph{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.

23 pages, 7 figures, work in progress

References in corpus (26)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• Exponential expressivity in deep neural networks through transient chaos
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Real-time Power System State Estimation and Forecasting via Deep Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Generalization in Deep Learning
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Spectrally-normalized margin bounds for neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• Recovery Guarantees for One-hidden-layer Neural Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Optimization Landscape and Expressivity of Deep CNNs
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Adding One Neuron Can Eliminate All Bad Local Minima
• Elimination of All Bad Local Minima in Deep Learning
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• Deep linear neural networks with arbitrary loss: All local minima are global
• Learning ReLU Networks via Alternating Minimization
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Efficiently testing local optimality and escaping saddles for ReLU networks

Cited by in corpus (23)

• Real-time Power System State Estimation and Forecasting via Deep Neural Networks
• Optimization for deep learning: theory and algorithms
• Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
• Graph Multiview Canonical Correlation Analysis
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Piecewise Linear Neural Networks and Deep Learning
• Solving Allen-Cahn and Cahn-Hilliard Equations using the Adaptive Physics Informed Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Modeling Personalized Item Frequency Information for Next-basket Recommendation
• Learning ReLU Networks via Alternating Minimization
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Physics-Guided Memory Network for Building Energy Modeling
• On Connected Sublevel Sets in Deep Learning
• Activated Gradients for Deep Neural Networks
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Microsimulation of Space Time Trellis Code
• Boosting Black-Box Adversarial Attacks with Meta Learning
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization