Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods

Abstract

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 guaranteed training of two-layer neural networks. We provide risk 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 learnability. 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, we propose a computationally efficient method with guaranteed risk bounds for training neural networks with one hidden layer.

arXiv commentThe tensor decomposition analysis is expanded, and the analysis of ridge regression is added for recovering the parameters of last layer of neural network

References in corpus (14)

• Improving neural networks by preventing co-adaptation of feature detectors
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Latent variable graphical model selection via convex optimization
• Train faster, generalize better: Stability of stochastic gradient descent
• Provable Bounds for Learning Some Deep Representations
• What Regularized Auto-Encoders Learn from the Data Generating Distribution
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-$1$ Updates
• On the Computational Efficiency of Training Neural Networks
• Density Estimation in Infinite Dimensional Exponential Families
• Fast and Guaranteed Tensor Decomposition via Sketching
• Sample Complexity Analysis for Learning Overcomplete Latent Variable Models through Tensor Methods
• Nonparametric Estimation of Multi-View Latent Variable Models
• Smoothed Analysis of Tensor Decompositions

Cited by in corpus (78)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Tensor Methods in Computer Vision and Deep Learning
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Optimization for deep learning: theory and algorithms
• On the Expressive Power of Deep Learning: A Tensor Analysis
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• AdaNet: Adaptive Structural Learning of Artificial Neural Networks
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Mathematics of Deep Learning
• Tensor Regression Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Adding One Neuron Can Eliminate All Bad Local Minima
• On the ability of neural nets to express distributions
• Tensor Train decomposition on TensorFlow (T3F)
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• Learning Deep ResNet Blocks Sequentially using Boosting Theory
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Fourth-order Tensors with Multidimensional Discrete Transforms
• Spectral Learning on Matrices and Tensors
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Greedy Layerwise Learning Can Scale to ImageNet
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Convexified Convolutional Neural Networks
• Learning Halfspaces and Neural Networks with Random Initialization
• Efficient Visual Recognition with Deep Neural Networks: A Survey on Recent Advances and New Directions
• Provable Algorithms for Inference in Topic Models
• On the energy landscape of deep networks
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Training Input-Output Recurrent Neural Networks through Spectral Methods
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Learning a Single Neuron with Gradient Methods
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ${\ell }^1$ and ${\ell }^0$ Controls
• Weight Sharing is Crucial to Succesful Optimization
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Hardness of Learning Neural Networks with Natural Weights
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Symmetry & critical points for a model shallow neural network
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• On Connected Sublevel Sets in Deep Learning
• DANTE: Deep AlterNations for Training nEural networks
• Prediction with a Short Memory
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• On the Learnability of Deep Random Networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Learning Polynomials of Few Relevant Dimensions
• Marginalizable Density Models
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• The Rate of Convergence of Variation-Constrained Deep Neural Networks
• Global Convergence of SGD On Two Layer Neural Nets
• Tensor Switching Networks
• Streaming Coresets for Symmetric Tensor Factorization
• Convolutional Neural Networks with Transformed Input based on Robust Tensor Network Decomposition
• From Local Pseudorandom Generators to Hardness of Learning
• Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• The SWAG Algorithm; a Mathematical Approach that Outperforms Traditional Deep Learning. Theory and Implementation
• Landscape analysis of an improved power method for tensor decomposition
• Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• When Can Neural Networks Learn Connected Decision Regions?
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Learning Graph Neural Networks with Approximate Gradient Descent