Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

By Alon Brutzkus, Amir Globerson. 2017

319 citations recorded by the source corpus.

Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove that optimization will succeed. Here we provide a strong result of this kind. We consider a neural net with one hidden layer and a convolutional structure with no overlap, and a ReLU activation function. For this architecture we show that learning is NP-complete in the general case, but that when the input distribution is Gaussian, gradient descent converges to the global optimum in polynomial time. To the best of our knowledge, this is the first global optimality guarantee of gradient descent on a convolutional neural network with ReLU activations.

Subfields: Artificial Intelligence, Model Architectures, Optimization & Training

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 Model Architectures

In Optimization & Training

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Most of existing works (1) only focus on the case when the training data is spherical Gaussian [28–43], and some of them require heavy initialization using tensor decomposition, which might fail to capture the specific structure of the input and the property of a random initialization; or (2) only c”
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].”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “There also exists a large body of work that analyzes the optimization landscape of learning neural networks [13, 26, 30, 10, 25, 29, 6, 32, 17, 5].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “Based on these two (unrealistic) conditions, it can be shown that randomly initialized (stochastic) gradient descent can learn a ReLU (Tian, 2017; Soltanolkotabi, 2017), a single convolutional filter (Brutzkus and Globerson, 2017), a convolutional neural network with one filter and one output layer ”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “dels only (e.g. Ge et al. (2016); Du and Lee (2018); Du et al. (2018a)). An alternative to the landscape approach is a direct analysis of the trajectories taken by the optimizer. Various papers (e.g. Brutzkus and Globerson (2017); Li and Yuan (2017); Zhong et al. (2017); Tian (2017); Brutzkus et al.”
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): “the labels are generated from a network with planted weights) [10], [21], [32], [49], [55], [57].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “1 What Can Neural Networks Provably Learn? Most existing works analyzing the learnability of neural networks [9, 12, 13, 20, 21, 28, 33, 34, 42, 43, 47, 49, 50, 56] make unrealistic assumptions about the data distribution (such as being random Gaussian), and/or make strong assumptions about the netw”
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 and Globerson, 2017, Du et al., 2018a, Li and Yuan, 2017, Du et al., 2017b]. Some local convergence results have also been proved [Zhong et a”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “One-hidden-layer neural networks with ground truth parameters Recently a series of work (Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Du et al., 2017a,b; Zhang et al., 2018) study a speciﬁc class of shallow two-layer (one-hidden-layer) neural networks, whose training data are…”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “Recovery guarantees for convolution neural network with Gaussian inputs are provided in (Brutzkus & Globerson, 2017), where they show a globally converging guarantee of gradient descent on a one-hidden-layer no-overlap convolution neural network.”
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 One-hidden-layer Neural Networks with Landscape Design (2017, background): “Brutzkus and Globerson [BG17] and Tian [Tia17] analyze the landscape of the population risk for one-hidden-layer neural networks with Gaussian inputs under the assumption that the weights vector associated to each hidden variable (that is, the ﬁlters) have disjoint supports.”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, methodology): “Using the above representation, Brutzkus and Globerson [2017] compute the gradient of f (w,v) with respect to w, given by”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “Other works have studied generalization of neural networks in a model recovery setting, where assumptions are made on the underlying model and the input distribution (Brutzkus & Globerson, 2017; Zhong et al., 2017; Li & Yuan, 2017; Du et al., 2017; Tian, 2017).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “Following [Zhong et al., 2017a,b, Li and Yuan, 2017, Tian, 2017, Brutzkus and Globerson, 2017, Shalev-Shwartz et al., 2017b], in this paper, we mainly focus on the population loss: Algorithm 1 GD for Learning One-Hidden-Layer CNN with Weight Normalization .”