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

Majid Janzamin, Hanie Sedghi, Anima Anandkumar

Abstract

Training neural networks is a challenging non-convex optimization problem where standard methods like backpropagation or gradient descent often stall in spurious local optima. This paper introduces a novel algorithm based on tensor decomposition for the guaranteed training of two-layer neural networks. We provide risk bounds for the proposed method with polynomial sample complexity relative to input dimensions and the number of neurons. While learning arbitrary target functions is generally NP-hard, we establish transparent conditions on the function and input for provable learnability. Our method, which relies on tensor decomposition, converges to the global optimum under mild non-degeneracy conditions. Composed of embarrassingly parallel linear and multi-linear operations, the algorithm is computationally competitive with stochastic gradient descent (SGD), offering a robust theoretical framework for efficient neural network training.

Introduction: The Challenge of Non-Convexity

In contemporary deep learning, the standard approach to training involves backpropagation and Stochastic Gradient Descent (SGD). While these "local search" methods have achieved remarkable empirical success, they lack global convergence guarantees. Because the loss landscape of a neural network is inherently non-convex, these algorithms are susceptible to becoming trapped in sub-optimal local minima or stalling at saddle points.

From a theoretical standpoint, training even a simple neural network is known to be NP-hard in the worst case. This research seeks to bridge the gap between practice and theory by identifying the specific conditions under which a neural network can be guaranteed to reach a global optimum. By focusing on two-layer feedforward networks, the authors propose a shift from "hope-based" optimization toward a framework of guaranteed learning.

The NN-LIFT Algorithm

The authors propose NN-LIFT (Neural Network-LearnIng using Feature Tensors), a "method of moments" approach that avoids iterative weight updates in favor of a three-stage algebraic process:

  1. Tensor Decomposition: The core of the algorithm involves using score functions—normalized derivatives of the input data's probability density. By analyzing the cross-moments between output labels and these score functions, the algorithm constructs a third-order tensor. Decomposing this tensor reveals the weight vectors of the first hidden layer.
  2. Fourier Method: Once the hidden layer weights are identified, a Fourier-based technique is employed to estimate the corresponding bias terms.
  3. Ridge Regression: With the first layer parameters fixed, the task of determining the second-layer weights reduces to a linear problem, which is solved efficiently using standard ridge regression.

Unlike the sequential nature of SGD, NN-LIFT is composed of linear and multi-linear operations that are embarrassingly parallel, making it computationally viable for large-scale datasets.

Theoretical Foundations and Insights

Score Functions as Linearizers

A primary insight of this work is that the expectation of the output multiplied by the input's score function is mathematically equivalent to the derivative of the target function. This allows the algorithm to "see through" non-linear activation functions to identify the underlying weight structure.

The Advantage of Tensors

While matrix-based methods (such as PCA) are limited to identifying orthogonal components, neural network weights are rarely perpendicular. Tensors possess a unique property: their decomposition is identifiable even for non-orthogonal components. This allows NN-LIFT to learn "overcomplete" networks where the number of hidden neurons exceeds the number of input dimensions.

Generative Knowledge for Discriminative Tasks

The method assumes access to the distribution of the input data $p(x)$. By leveraging this generative information, the discriminative task of learning the mapping $y = f(x)$ becomes provably tractable, transforming a non-convex search into a structured decomposition problem.

Results and Complexity

The authors evaluate the algorithm using synthetic "realizable" data, mixtures of Gaussian kernels, and toy classification tasks to visualize the loss surface. Key findings include:

  • Global Convergence: Under mild non-degeneracy conditions, the algorithm is guaranteed to find the global optimum, bypassing the local minima that hinder SGD.
  • Polynomial Complexity: The number of samples required ($n$) scales polynomially with the input dimension ($d$) and the number of neurons ($k$).
  • Provable Risk Bounds: The authors provide mathematical guarantees on the "risk" (expected error on unseen data), demonstrating that error decreases predictably as training samples and neurons are added.
  • Efficiency: The parallel time complexity is logarithmic in the input dimension, ensuring the method remains competitive with parallelized SGD implementations.

Limitations and Future Directions

Despite its theoretical strengths, NN-LIFT faces several hurdles for general application:

  • Architecture Constraints: The current proof is limited to networks with a single hidden layer. While recursive applications to deeper networks are possible, theoretical guarantees for deep architectures remain an open challenge.
  • Input Density Requirements: The method requires knowledge of the input distribution $p(x)$ to calculate score functions, which may necessitate unsupervised density estimation for complex, real-world datasets.
  • Activation Functions: The mathematical framework requires activation functions to have a non-zero third derivative in expectation. While common activations like sigmoids satisfy this, it remains a specific constraint for the tensor decomposition to succeed.

Conclusion

NN-LIFT represents a significant step toward a more rigorous understanding of neural network optimization. By replacing local gradient-based searches with global tensor decompositions, the authors provide a path toward guaranteed training with provable risk bounds, offering a robust alternative to the traditional "black box" approach of deep learning.

Summary updated

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.
BibTeX
@misc{janzamin2015beating,
  author = {Majid Janzamin and Hanie Sedghi and Anima Anandkumar},
  title = {{Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods}},
  year = {2015},
  eprint = {1506.08473},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.08473},
}
Figure