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

DOI10.1109/TSP.2019.2904921MaRDI QIDQ5238780zbMATH OpenOpenAlexFDO

Authors Gang Wang, Jie Chen, Georgios B. Giannakis

Publication date 28 October 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.04685

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Applications of mathematical programming (90C90)

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.

Cited in

(13)

• Bias of homotopic gradient descent for the hinge loss
• Generalised latent assimilation in heterogeneous reduced spaces with machine learning surrogate models
• Optimization for deep learning: an overview
• Linear constraints on weight representation for generalized learning of multilayer networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks
• On the benefit of width for neural networks: disappearance of basins
• Solving Allen-Cahn and Cahn-Hilliard Equations using the Adaptive Physics Informed Neural Networks
• A Framework for the Construction of Upper Bounds on the Number of Affine Linear Regions of ReLU Feed-Forward Neural Networks
• Suboptimal Local Minima Exist for Wide Neural Networks with Smooth Activations
• Lagrangian dual theory and stability analysis for fuzzy optimization problems
• Efficient deep data assimilation with sparse observations and time-varying sensors
• When will gradient methods converge to max-margin classifier under ReLU models?

This page was built for publication: Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5238780)