Learning ReLUs via Gradient Descent

By M. Soltanolkotabi. 2017

193 citations recorded by the source corpus.

In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form $max(0, )$ with $w$ denoting the weight vector. We study this problem in the high-dimensional regime where the number of observations are fewer than the dimension of the weight vector. We assume that the weight vector belongs to some closed set (convex or nonconvex) which captures known side-information about its structure. We focus on the realizable model where the inputs are chosen i.i.d.~from a Gaussian distribution and the labels are generated according to a planted weight vector. We show that projected gradient descent, when initialization at 0, converges at a linear rate to the planted model with a number of samples that is optimal up to numerical constants. Our results on the dynamics of convergence of these very shallow neural nets may provide some insights towards understanding the dynamics of deeper architectures.

Subfields: Artificial Intelligence, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Many of them focus on the case when the inputs are random Gaussian, and work only for two-layer neural networks [11, 19, 22, 35, 43, 50, 55, 59, 60].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “Here the gradient formula for each weight vector is Though this is only a shallow fully connected neural network, the objective function is still non-smooth and non-convex due to the use of ReLU activation function.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A series of papers made strong assumptions on input distribution as well as realizability of labels, and showed global convergence of (stochastic) gradient descent for some shallow neural networks (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Du et al., 2017a,b; Li & Yuan, 2017).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “For a neural network with zero hidden units and a single output with a monotonic activation function σ , numerous authors [20], [23], [24], [34], [44] have shown that gradientbased methods converge to the global optimum under various assumptions and models.”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Based on these assumptions, one can obtain global convergence of gradient descent for some shallow neural networks (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Du et al., 2018a; Li & Yuan, 2017; Du et al., 2017b).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Many of them focus on two-layer (thus one-hidden-layer) neural networks and assume that the inputs are random Gaussian or sufﬁciently close to Gaussian [7, 15, 18, 32, 37, 50, 55, 60, 61].”
Learning Compact Neural Networks with Regularization (2018, background): “…on the optimization landscape are closely related to the recent works on provably learning shallow neural nets (Zhong et al., 2017b; Tian, 2017; Soltanolkotabi, 2017; Panigrahy et al., 2018; Ge et al., 2017; Oymak & Soltanolkotabi, 2018; Zhong et al., 2017a; Safran & Shamir, 2017; Arora et…”
The loss surface and expressivity of deep convolutional neural networks (2017, unknown): “…(Andoni et al., 2014; Sedghi & Anandkumar, 2015; Janzamin et al., 2016; Haeffele & Vidal, 2015; Gautier et al., 2016; Brutzkus & Globerson, 2017; Soltanolkotabi, 2017; Soudry & Hoffer, 2017; Goel & Klivans, 2017; Du et al., 2017; Zhong et al., 2017; Tian, 2017; Li & Yuan, 2017) in order to…”
Learning One Convolutional Layer with Overlapping Patches (2018, background): “Other related works analyzing gradient descent with respect to the Gaussian distribution (but for non-convolutional networks) include (Soltanolkotabi, 2017; Ge et al., 2017; Zhong et al., 2017b; Tian, 2016; Li & Yuan, 2017; Zhang et al., 2017).”
Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets (2019, background): “Some works consider the empirical risk minimization with finite input samples (Zhong et al., 2017; Soltanolkotabi, 2017), while some others consider the minimization of population loss averaged over the whole data space (Brutzkus & Globerson, 2017; Tian, 2017; Li & Yuan, 2017; Du et al.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “by Zhang et al. (2016) to obtain results for learning sparse neural networks with certain smooth activations, and Goel et al.”
The Loss Surface of Deep and Wide Neural Networks (2017, background): “However, it turns out that these approaches are either not practical (Janzamin et al., 2016; Haeffele & Vidal, 2015; Soltanolkotabi, 2017) as they require e.g. knowledge about the data generating measure, or they modify the neural network structure and objective (Gautier et al., 2016).”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “, [26], [34], also see Section 4 for further details).”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, unknown): “A series of recent papers used trajectory-based methods to analyze gradient descent for shallow neural networks under strong data assumptions (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Li & Yuan, 2017; Zhong et al., 2017; Zhang et al., 2018; Du et al., 2018c;d).”
Refined Generalization Analysis of Gradient Descent for Over-parameterized Two-layer Neural Networks with Smooth Activations on Classification Problems (2019, background): “Other than these, there are many studies [16, 17, 18, 19, 1, 20, 2, 21] that focus on regression problems, but our study focuses on classification problems and demonstrates that the gradient descent for over-parameterized networks has a preferable property by utilizing the problem structure of a bin”
When is a Convolutional Filter Easy To Learn? (2017, methodology): “With the same Gaussian assumption, Soltanolkotabi [2017] used Gaussian width (c.f. Definition 2.2 of [Soltanolkotabi, 2017]) for concentrations to show the true weights can be exactly recovered by empirical projected gradient descent with enough samples in linear time and his approach cannot be…”