Recovery Guarantees for One-hidden-layer Neural Networks

By Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon. 2017

349 citations recorded by the source corpus.

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to $\mathit{local~strong~convexity}$ in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show $\mathit{local~linear~convergence}$ guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity $ d \cdot \log(1/\epsilon) \cdot \mathrm{poly}(k,\lambda )$ and computational complexity $n\cdot d \cdot \mathrm{poly}(k,\lambda) $ for smooth homogeneous activations with high probability, where $d$ is the dimension of the input, $k$ ($k\leq d$) is the number of hidden nodes, $\lambda$ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, $\epsilon$ is the targeted precision and $n$ is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity $\mathit{linear}$ in the input dimension and $\mathit{logarithmic}$ in the precision.

Subfields: Artificial Intelligence, 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 Statistical Learning Theory

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, methodology): “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): “Moreover, most of the existing works trying to explain these phenomenons in general rely on unrealistic assumptions about the data distribution, such as Gaussian-ness and/or linear separability [32, 25, 10, 17, 7].”
Continual Learning in the Teacher-Student Setup: Impact of Task Similarity (2021, background): “…Broeck, 2001; Zdeborov ´ a & Krzakala, 2016) and has recently experienced a surge of activity in the machine learning community (Zimmer et al., 2014; Zhong et al., 2017; Tian, 2017; Du et al., 2018; Soltanolkotabi et al., 2018; Aubin et al., 2018; Saxe et al., 2018; Baity-Jesi et al., 2018; Goldt…”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “showed that with initialization point found using tensor decomposition, gradient descent could find the ground truth for one hidden layer network [44].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Some local convergence results have also been proved (Zhong et al., 2017; Zhang et al., 2018).”
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): “Some local convergence results have also been proved [Zhong et al., 2017a,b, Zhang et al., 2018].”
On the Convergence Rate of Training Recurrent Neural Networks (2018, methodology): “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].”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “. The papers most closely related to this work analyze algorithms based on gradient descent. Some of these (Andoni et al., 2014; Brutzkus & Globerson, 2017; Ge et al., 2017b; Li & Yuan, 2017; Zhong et al., 2017; Zhang et al., 2018; Brutzkus et al., 2018; Ge et al., 2018) analyze constant-dep”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “(1), a few works have shown that there are no spurious local minima, or that gradient descent will succeed in reaching a global minimum, provided the v i vectors are in general position or orthogonal [Zhong et al., 2017, Soltanolkotabi et al., 2017, Tian, 2017].”
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 .”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “A line of research focused on analyzing gradient descent dynamics for (convolutional) neural networks with one or two unknown layers [Tian, 2017, Brutzkus and Globerson, 2017, Du et al., 2017a,b, Zhong et al., 2017, Li and Yuan, 2017, Ma et al., 2017, Brutzkus et al., 2017].”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “…approximator (Cybenko, 1989; Hornik, 1991)); (Tian, 2017; Soltanolkotabi et al., 2017; Li & Yuan, 2017) assume the weights are initialized very close to those of the teacher generating the labels; and (Janzamin et al., 2015; Zhong et al., 2017) use a non-standard tensor method during training.”