Learning Two-layer Neural Networks with Symmetric Inputs

By Rong Ge, Rohith Kuditipudi, Zhize Li, Xiang Wang. 2018

62 citations recorded by the source corpus.

We give a new algorithm for learning a two-layer neural network under a general class of input distributions. Assuming there is a ground-truth two-layer network $$ y = A \sigma(Wx) + \xi, $$ where $A,W$ are weight matrices, $\xi$ represents noise, and the number of neurons in the hidden layer is no larger than the input or output, our algorithm is guaranteed to recover the parameters $A,W$ of the ground-truth network. The only requirement on the input $x$ is that it is symmetric, which still allows highly complicated and structured input. Our algorithm is based on the method-of-moments framework and extends several results in tensor decompositions. We use spectral algorithms to avoid the complicated non-convex optimization in learning neural networks. Experiments show that our algorithm can robustly learn the ground-truth neural network with a small number of samples for many symmetric input distributions.

Subfields: Computational Mathematics, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, Model Architectures, 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 Computational Mathematics

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

In Model Architectures

In Statistical Learning Theory

Citations in the corpus

What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, background): “ test data with relatively few training examples. There has been a sequence of research trying to address this question, showing that under certain conditions neural networks can be learned eciently [7{9, 14, 15, 20, 23, 24, 31{34, 36, 39]. These provable guarantees typically come with strong assump”
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”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, unknown): “…(Klivans et al. (2004); Klivans and Meka (2013); Janzamin et al. (2015); Sedghi and Anandkumar (2014); Zhang et al. (2017, 2016); Zhong et al. (2017); Goel and Klivans (2017); Du et al. (2017); Goel et al. (2018); Ge et al. (2017); Soltanolkotabi (2017); Gao et al. (2018); Ge et al. (2018)).”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “For such reason, it is not surprising that most existing theoretical works on the efficient learning regime of neural networks either focus on (1) two-layer networks [9, 10, 12, 22, 23, 36, 41, 41, 42, 46, 50, 51, 53, 54, 56, 58, 61] which do not have any hierarchical structure, or (2) a multi-layer”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, methodology): “Apart from the gradient descent algorithm, the method of moments has also been shown to be an effective strategy with provable guarantees (e.g. (Bakshi et al., 2018; Ge et al., 2018)).”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, background): “Another line of work investigates classes of such networks that can be learned in polynomial time, notably using tensor methods [21, 28] and polynomial kernels [15, 17], more direct methods with assumptions on the structure of the network [16, 13] and a combination of tensor initialization followed ”
Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, background): “Another line of research (Zhong et al., 2017; Soltanolkotabi, 2017; Soltanolkotabi et al., 2017; Fu et al., 2018; Ge et al., 2019) investigated using (stochastic) gradient descent to minimize the empirical loss function of shallow neural networks, and provided theoretical guarantees on sample comple”