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

2015/06/28 by Majid Janzamin, Hanie Sedghi, Janzamin, Majid +3 · 3 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM #Neural and Evolutionary Computing (cs.NE) #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1506.08473

openalex publication_date 2015/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Training neural networks is a challenging non-convex optimization problem,\nand backpropagation or gradient descent can get stuck in spurious local optima.\nWe propose a novel algorithm based on tensor decomposition for guaranteed\ntraining of two-layer neural networks. We provide risk bounds for our proposed\nmethod, with a polynomial sample complexity in the relevant parameters, such as\ninput dimension and number of neurons. While learning arbitrary target\nfunctions is NP-hard, we provide transparent conditions on the function and the\ninput for learnability. Our training method is based on tensor decomposition,\nwhich provably converges to the global optimum, under a set of mild\nnon-degeneracy conditions. It consists of simple embarrassingly parallel linear\nand multi-linear operations, and is competitive with standard stochastic\ngradient descent (SGD), in terms of computational complexity. Thus, we propose\na computationally efficient method with guaranteed risk bounds for training\nneural networks with one hidden layer.

Citations

• Fast and Guaranteed Tensor Decomposition via Sketching
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Score Function Features for Discriminative Learning: Matrix and Tensor Framework
• Density Estimation in Infinite Dimensional Exponential Families
• What Regularized Auto-Encoders Learn from the Data Generating Distribution
• Improving neural networks by preventing co-adaptation of feature detectors
• Nonparametric Estimation of Multi-View Latent Variable Models
• Smoothed Analysis of Tensor Decompositions

Cited by

• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Train faster, generalize better: Stability of stochastic gradient descent

Related

• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Practical Convex Formulation of Robust One-hidden-layer Neural Network Training
• Tensor-Based Backpropagation in Neural Networks with Non-Sequential Input
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Faster Neural Network Training with Approximate Tensor Operations