Diverse Neural Network Learns True Target Functions

By Bo Xie, Yingyu Liang, Le Song. 2016

147 citations recorded by the source corpus.

Neural networks are a powerful class of functions that can be trained with simple gradient descent to achieve state-of-the-art performance on a variety of applications. Despite their practical success, there is a paucity of results that provide theoretical guarantees on why they are so effective. Lying in the center of the problem is the difficulty of analyzing the non-convex loss function with potentially numerous local minima and saddle points. Can neural networks corresponding to the stationary points of the loss function learn the true target function? If yes, what are the key factors contributing to such nice optimization properties? In this paper, we answer these questions by analyzing one-hidden-layer neural networks with ReLU activation, and show that despite the non-convexity, neural networks with diverse units have no spurious local minima. We bypass the non-convexity issue by directly analyzing the first order optimality condition, and show that the loss can be made arbitrarily small if the minimum singular value of the "extended feature matrix" is large enough. We make novel use of techniques from kernel methods and geometric discrepancy, and identify a new relation linking the smallest singular value to the spectrum of a kernel function associated with the activation function and to the diversity of the units. Our results also suggest a novel regularization function to promote unit diversity for potentially better generalization.

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

Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “Interestingly, various properties of this H ∞ matrix has been thoroughly studied in previous work [Xie et al., 2017, Tsuchida et al., 2017].”
Visualizing the Loss Landscape of Neural Nets (2017, background): “Theoretical results usually make restrictive assumptions about the sample distributions, non-linearity of the architecture, or loss functions [16, 31, 40, 36, 9, 39].”
Improving Neural Language Modeling via Adversarial Training (2019, background): “Direct Diversity Regularization There has been a body of literature on increasing the robustness by directly adding various forms of diversity-enforcing penalty functions (e.g., Elsayed et al., 2018; Xie et al., 2017; Liu et al., 2016; 2017; Chen et al., 2017; Wang et al., 2018).”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “(3) This matrix can be viewed as a Gram matrix from a kernel associated with the ReLU function, and has been studied in (Xie et al., 2017; Tsuchida et al., 2017; Du et al., 2018c).”
Benign overfitting in linear regression (2019, background): “ and the data-dependent bound of [1, Theorem 5.1] becomes vacuous when independent noise is added to the yis.) The eigenvalues of the covariance operator in this case appear to have a heavy tail (see [24], where this kernel was introduced, and [15]), as required for benign overﬁtting. Of course, the”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, neutral): “…although this is a common assumption appeared in the previous papers [Brutzkus and Globerson, 2017, Li and Yuan, 2017, Zhong et al., 2017a,b, Tian, 2017, Choromanska et al., 2015a, Xie et al., 2017, Shalev-Shwartz et al., 2017b] and also considered plausible in [Choromanska et al., 2015b].”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, methodology): “It has been shown that the Gram matrix for inﬁnite width networks has the following form [Xie et al., 2016, Arora et al., 2019b]: We note that any function deﬁned on the unit sphere has a spherical harmonic decomposition: where φ u ( x ) : S d − 1 → R is a spherical harmonic basis.”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “There is a large body of work on learning two-layer neural networks over the last few years, such as Kawaguchi (2016); Soudry and Carmon (2016); Xie et al. (2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and…”
Dynamics of Deep Neural Networks and Neural Tangent Hierarchy (2019, methodology): “For two layer neural networks with random training data, quantitative estimates for λ are obtained in (Ghorbani et al., 2019; Zhang et al., 2019; Xie et al., 2016).”
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019, background): “As is noted in [23], when the training data distributes uniformly on a hypersphere the eigenvectors of H ∞ are the spherical harmonics.”
Orthogonal Over-Parameterized Training (2020, background): “On one hand, [77] proves that once the neurons are hyperspherically diverse enough in a one-hidden-layer network, the training loss is on the order of the square norm of the gradient and the generalization error will have an additional term Õ(1/√m) where m is the number of samples.”
On the Inductive Bias of Neural Tangent Kernels (2019, methodology): “Neural tangent kernels were introduced in [27], and similar ideas were used to obtain more quantitative guarantees on the global convergence of gradient descent for over-parameterized neural networks [2, 3, 16, 20, 21, 30, 50, 54].”
Global optimality conditions for deep neural networks (2017, background): “Another line of recent results [ 13 – 15 ] provides conditions under which a critical point of the empirical risk is a global minimum.”
Frequency Bias in Neural Networks for Input of Non-Uniform Density (2020, methodology): “(Bach, 2017; Basri et al., 2019; Bietti & Mairal, 2019; Cao et al., 2019; Xie et al., 2017) For a deep FC network the NTK is expressed by the following recursion (Arora et al., 2019a; Jacot et al., 2018) Here ˙ σ ( · ) denotes the step function (i.e., the derivative of the ReLU function).”
Learning with Hyperspherical Uniformity (2021, background): “[83] proves that optimizing one-hiddenlayer neural networks with hyperspherically uniform”