Generalization Bounds for Neural Networks through Tensor Factorization

By Majid Janzamin, Hanie Sedghi, Anima Anandkumar. 2015

26 citations recorded by the source corpus.

Training neural networks is a challenging non-convex optimization problem, and backpropagation or gradient descent can get stuck in spurious local optima. We propose a novel algorithm based on tensor decomposition for training a two-layer neural network. We prove efficient generalization bounds for our proposed method, with a polynomial sample complexity in the relevant parameters, such as input dimension and number of neurons. While learning arbitrary target functions is NP-hard, we provide transparent conditions on the function and the input for generalizability. Our training method is based on tensor decomposition, which provably converges to the global optimum, under a set of mild non-degeneracy conditions. It consists of simple embarrassingly parallel linear and multi-linear operations, and is competitive with standard stochastic gradient descent (SGD), in terms of computational complexity. Thus, for the first time, we have a computationally efficient method with guaranteed generalization bounds for training neural networks.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “[Janzamin et al., 2015] is another paper that touches on multiple theory components, analyzing the generalization and training of two-layer neural networks through tensor methods.”
ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time (2015, methodology): “It covers the networks that can be learned by the method of Janzamin et al. [12].”
Training Recurrent Neural Networks by Diffusion (2016, methodology): “Using tensor decomposition techniques, [Janzamin et al., 2015] oﬀers new algorithms for deep learning with performance guarantee.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “(Janzamin et al., 2015) show that two layer neural networks can be learned using tensor methods.”
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018, background): “Another line of work investigates classes of such networks that can be learned in polynomial time, notably using tensor methods [17, 22] and polynomial kernels [12, 13] and a combination of tensor initialization followed by gradient descent [26].”
Tensor Regression Networks (2017, methodology): “Other papers investigate tensor methods as tools for devising neural network learning algorithms with theoretical guarantees of convergence (Sedghi and Anandkumar, 2016; Janzamin et al., 2015a,b).”
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 ”
On the Complexity of Learning Neural Networks (2017, background): “[12] to learn a 1-layer network under nondegeneracy assumptions on the weight matrix.”
Learning Halfspaces and Neural Networks with Random Initialization (2015, unknown): “More recently, Janzamin et al. (2015) propose another algorithm relying on the score function that removes the restrictions of Sedghi and Anandkumar (2014).”
Convexified Convolutional Neural Networks (2016, methodology): “od for learning fully-connected neural networks, but their approach handles neither parameter sharing nor the convolutional setting. Other relevant works for learning fully-connected networks include [35,23,29]. Aslan et al. [1,2] propose a method for learning multi-layer latent variable models. The”