Recovery Guarantees for One-hidden-layer Neural Networks

Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon

Abstract

This paper addresses the fundamental challenge of training one-hidden-layer neural networks (1NNs) with provable guarantees. While deep learning is often viewed as a "black box" due to the non-convex nature of its loss landscapes, we identify specific properties of activation functions—including ReLU, sigmoid, and tanh—that induce local strong convexity near ground-truth parameters. We propose a two-stage algorithm combining a novel tensor-based initialization with gradient descent. Our approach achieves recovery of ground-truth weights with sample and computational complexity that scales linearly with the input dimension ($d$) and logarithmically with the target precision ($1/\epsilon$). This represents a significant improvement over previous methods that required cubic complexity or extreme over-parameterization.

Introduction

Training neural networks is inherently difficult because the squared-loss objective is non-convex, typically characterized by numerous local minima and saddle points that can trap standard optimization algorithms. Traditional theoretical approaches to this problem often rely on "over-parameterization"—making the network significantly wider than necessary—to smooth the landscape. However, this can lead to poor generalization and high computational costs. Alternatively, existing methods that guarantee parameter recovery often suffer from computational complexities that scale cubically ($d^3$) with the input dimension, rendering them impractical for high-dimensional tasks.

This research asks whether it is possible to provably recover the exact parameters of a 1-hidden-layer network with complexity that scales linearly with the input dimension. We demonstrate that for a wide class of activation functions, the loss landscape is well-behaved in a neighborhood around the optimal solution, allowing for efficient global convergence when paired with a smart initialization strategy.

Theoretical Framework: The Basin of Attraction

A central contribution of this work is the distillation of mathematical properties—specifically non-negativity, non-linearity, and smoothness—that ensure a neural network's loss landscape becomes locally strongly convex near the ground-truth parameters.

In this "basin of attraction," the Hessian of the loss function is positive definite, meaning the error landscape resembles a simple, convex bowl. We show that most popular nonlinear activation functions satisfy these properties, including:

  • Rectified Linear Units (ReLU)
  • Leaky ReLU
  • Squared ReLU
  • Sigmoid and Tanh

For smooth activations, we prove that gradient descent under a resampling rule achieves local linear convergence, meaning the error decreases exponentially fast as iterations progress.

The Two-Stage Algorithm

To ensure the optimization begins within the basin of attraction, we propose a two-stage recovery process:

1. Tensor Initialization

Instead of random initialization, which often fails to find the global optimum, we utilize higher-order moments of the data to estimate the subspace of the true weights. While standard tensor methods are computationally expensive ($O(d^3)$), we implement an implicit power method. This innovation allows us to estimate the initial parameters without ever explicitly constructing the massive tensors, reducing the initialization complexity to $O(d)$. For homogeneous activations (like ReLU), this step is guaranteed to land the parameters within the locally strongly convex region.

2. Gradient Descent with Resampling

Once initialized, we apply standard gradient descent. To maintain independence between samples across iterations and satisfy theoretical requirements, we utilize a resampling rule. Given the local strong convexity established in our framework, the algorithm converges to the ground-truth parameters $w^*$ and $v^*$ with high probability.

Key Results and Complexity

Our analysis provides the first recovery guarantees for 1NNs that are linear in input dimension and logarithmic in precision:

  • Sample Complexity: $d \cdot \log(1/\epsilon) \cdot \mathrm{poly}(k, \lambda)$, where $k$ is the number of hidden nodes and $\lambda$ represents the conditioning of the ground-truth weight matrix.
  • Computational Complexity: $n \cdot d \cdot \mathrm{poly}(k, \lambda)$, essentially matching the cost of reading the data and performing a few passes of gradient descent.

Experimental validations on synthetic datasets (where $x \sim \mathcal{N}(0, I)$) confirm these bounds. In tests with varying dimensions up to $d=100$, the number of samples required for 100% recovery scaled linearly with $d$, validating the theoretical predictions and outperforming traditional random initialization.

Conclusion and Future Work

This work moves the field closer to a rigorous understanding of neural network optimization. By identifying the conditions for local strong convexity and providing an efficient initialization routine, we demonstrate that exact parameter recovery is computationally feasible even in high-dimensional settings.

Future research directions include extending these guarantees to deep, multi-layer architectures and relaxing the assumption of Gaussian input distributions to accommodate more complex, real-world data structures. Additionally, while our method shows robustness, further formal analysis of recovery under significant label noise remains an open area of study.

Summary updated

Abstract

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to $\mathit{local~strong~convexity}$ in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show $\mathit{local~linear~convergence}$ guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity $ d \cdot \log(1/\epsilon) \cdot \mathrm{poly}(k,\lambda )$ and computational complexity $n\cdot d \cdot \mathrm{poly}(k,\lambda) $ for smooth homogeneous activations with high probability, where $d$ is the dimension of the input, $k$ ($k\leq d$) is the number of hidden nodes, $\lambda$ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, $\epsilon$ is the targeted precision and $n$ is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity $\mathit{linear}$ in the input dimension and $\mathit{logarithmic}$ in the precision.
BibTeX
@inproceedings{zhong2017recovery,
  author = {Kai Zhong and Zhao Song and Prateek Jain and Peter L. Bartlett and Inderjit S. Dhillon},
  title = {{Recovery Guarantees for One-hidden-layer Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
}
Figure