Learning One-hidden-layer ReLU Networks via Gradient Descent

By Xiao Zhang, Yaodong Yu, Lingxiao Wang, Quanquan Gu. 2018

140 citations recorded by the source corpus.

We study the problem of learning one-hidden-layer neural networks with Rectified Linear Unit (ReLU) activation function, where the inputs are sampled from standard Gaussian distribution and the outputs are generated from a noisy teacher network. We analyze the performance of gradient descent for training such kind of neural networks based on empirical risk minimization, and provide algorithm-dependent guarantees. In particular, we prove that tensor initialization followed by gradient descent can converge to the ground-truth parameters at a linear rate up to some statistical error. To the best of our knowledge, this is the first work characterizing the recovery guarantee for practical learning of one-hidden-layer ReLU networks with multiple neurons. Numerical experiments verify our theoretical findings.

Subfields: Artificial Intelligence, Computational Mathematics, Computer Vision and Pattern Recognition, 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 Computational Mathematics

In Computer Vision and Pattern Recognition

In Optimization & Training

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”
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).”
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).”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…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 generated by a ground…”
Refined Generalization Analysis of Gradient Descent for Over-parameterized Two-layer Neural Networks with Smooth Activations on Classification Problems (2019, background): “[20] Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu.”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, 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. 2017; Zhang et al. 2018) studied a specific class of shallow two-layer (one-hidden-layer) neural networks,whose training data are generated by ”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “A series of work (Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Soltanolkotabi, 2017; Du et al., 2017a,b; Zhong et al., 2017; Zhang et al., 2018) have attempted to study shallow one-hidden-layer neural networks with ground truth parameters, and proved recovery guarantees for gradient-”
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).”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, background): “Recently, scalable approximations to natural gradient descent have shown practical success in a variety of tasks and architectures [Martens and Grosse, 2015, Grosse and Martens, 2016, Wu et al., 2017, Zhang et al., 2018a, Martens et al., 2018].”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, background): “To better understand the training of neural networks, there is a line of research [18, 5, 10, 16, 23, 8, 22, 12] studying two-layer (i.”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, background): “Several other works (Tian, 2017; Du et al., 2017b; Brutzkus & Globerson, 2017; Li & Yuan, 2017; Soltanolkotabi, 2017; Zhong et al., 2017; Zhang et al., 2018) extend this to different settings.”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “…(2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and Soltanolkotabi (2019); Bakshi et al. (2018); Yehudai and Shamir (2019); Zhang et al. (2018); Li and Liang (2017); Li and Dou (2020); Allen-Zhu and Li (2020b).”