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