Learning One-hidden-layer Neural Networks with Landscape Design

By Rong Ge, Jason D. Lee, Tengyu Ma. 2017

267 citations recorded by the source corpus.

We consider the problem of learning a one-hidden-layer neural network: we assume the input $x\in \mathbb{R}^d$ is from Gaussian distribution and the label $y = a^\top \sigma(Bx) + \xi$, where $a$ is a nonnegative vector in $\mathbb{R}^m$ with $m\le d$, $B\in \mathbb{R}^{m\times d}$ is a full-rank weight matrix, and $\xi$ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. Inspired by the formula, we design a non-convex objective function $G(\cdot)$ whose landscape is guaranteed to have the following properties: 1. All local minima of $G$ are also global minima. 2. All global minima of $G$ correspond to the ground truth parameters. 3. The value and gradient of $G$ can be estimated using samples. With these properties, stochastic gradient descent on $G$ provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity result and validate the results by simulations.

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

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].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “Landscape analyses of ReLU activated neural networks for other settings have also been studied in many previous works (Ge et al., 2017; Safran and Shamir, 2016; Zhou and Liang, 2017; Freeman and Bruna, 2016; Hardt and Ma, 2016; Nguyen and Hein, 2018).”
A mean field view of the landscape of two-layer neural networks (2018, neutral): “inf γ∈C(ρ1,ρ2) ∫ ‖θ1−θ2‖(2)2γ(dθ1, dθ2) )1/2 , [9]”
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”
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].”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “Recently, Ge et al. [2017b] showed using a modiﬁed objective function satisfying the two properties above, one-hidden-layer neural network can be learned by noisy perturbed gradient descent.”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “…make use of the following identities, all of which can be directly veriﬁed by plugging in deﬁnitions: We also need the following inequality, which is [Ge et al., 2017a, Lemma 6]: Now we can prove the desired bound as follows: where in the last line we have used Using Claims B.4 and B.5, we obtain…”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, background): “For example, (Ge et al., 2017b) proved convergence of GD on a modified loss; (Shamir, 2018) compared optimization properties of residual networks with respect to linear models; in (Dauphin et al., 2014) it is argued that the issues arising in the optimization of NN architectures are due to the…”
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).”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “Du et al. [2018] further uses a geometric result (all saddle points in the objective function are strict and all local minima are global minima [Ge et al., 2015, 2017b, 2016, Li et al., 2019b]), and then invokes the stable manifold theorem to show the global convergence of gradient ﬂow [Lee et al.,…”
Adversarial Robustness with Semi-Infinite Constrained Learning (2021, background): “[38] Rong Ge, Jason D Lee, and Tengyu Ma.”
Limitations of Lazy Training of Two-layers Neural Networks (2019, unknown): “Further related landscape results include [13, 15, 12].”
Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex (2018, background): “It is reported that for a single-hidden-layer neural network, when the number of hidden units is small, stochastic gradient descent may get easily stuck at the poor local minima [27, 49].”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “The loss landscape of neural networks has attracted great research interests in the deep learning community [9, 10, 32, 12, 15, 43, 36].”