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

arXiv: https://arxiv.org/abs/1506.08473 · HTML: https://mlsanity.com/paper/1506.08473/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2015.

## Built on by (most cited first, 5 of 5)

- [An Information-Theoretic Framework for Supervised Learning](https://mlsanity.com/paper/2203.00246/) (2022)
- [Marginalizable Density Models](https://mlsanity.com/paper/2106.04741/) (2021)
- [Is Stochastic Gradient Descent Near Optimal?](https://mlsanity.com/paper/2209.08627/) (2022)
- [The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning](https://mlsanity.com/paper/2607.03347/) (2026)
- [Agnostically Learning Multi-index Models with Queries](https://mlsanity.com/paper/2312.16616/) (2023)

## Abstract (arXiv)

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.