Abstract
This paper establishes the first global convergence guarantees for training one-hidden-layer neural networks under cross-entropy loss, the standard for classification tasks. By demonstrating that the loss surface is locally strongly convex near the ground truth, the authors show that a combination of tensor-based initialization and standard gradient descent can recover underlying network weights with near-optimal sample complexity. This work bridges the gap between the practical success of classification models and their theoretical understanding.
Introduction
While deep learning has achieved massive practical success, a rigorous mathematical explanation for its efficacy remains elusive. A key theoretical challenge is "model recovery": given data generated by a specific ground-truth neural network, can standard optimization tools reliably find those original weights?
Most existing literature focuses on regression with squared loss. However, real-world classification typically employs cross-entropy loss, which is significantly harder to analyze due to the "saturation" effect of sigmoid activations that causes gradients to vanish. Furthermore, many previous proofs relied on the unrealistic "fresh sample" assumption, requiring new data for every gradient descent step. This paper addresses these gaps by providing guarantees for recovery without such constraints.
Methodology
The authors analyze two fundamental architectures: Fully Connected Networks (FCN) and Non-overlapping Convolutional Neural Networks (CNN).
The proposed recovery framework utilizes a two-stage algorithm:
- Tensor Initialization: To avoid the non-convex loss surface's numerous local minima, a "tensor method" based on higher-order data moments identifies a starting point provably close to the ground truth.
- Gradient Descent Refinement: Once initialized in the correct neighborhood, standard gradient descent is applied.
The core contribution is the proof of Uniform Local Strong Convexity. The authors demonstrate that within a specific radius of the ground truth, the empirical loss surface is guaranteed to be smooth and "bowl-shaped," facilitating efficient optimization even without fresh samples at each iteration.
Experimental Setup
As a primarily theoretical study, the paper validates its proofs using synthetic datasets. Inputs ($x$) are drawn from a standard Gaussian distribution ($x \sim \mathcal{N}(0, I_d)$), and labels ($y$) are generated by a ground-truth one-hidden-layer network with sigmoid activations. Simulations track the "Success Rate" of recovery and the "Estimation Error" (Normalized Mean Squared Error, NMSE) as functions of the number of samples ($n$) and input dimension ($d$).
Key Insights and Ideas
- Local Geometry of Cross-Entropy: Despite the vanishing gradient problem, the population loss is smooth and the empirical loss is strongly convex near the solution, making optimization straightforward once properly initialized.
- Structural Advantages of CNNs: Theoretical and empirical evidence suggests that the structured nature of CNNs results in more "benign" loss surfaces than FCNs, often requiring fewer samples for accurate recovery.
- Eliminating the Fresh Sample Requirement: By proving uniform concentration of the Hessian, the authors show that the favorable geometry of the loss surface holds for the entire neighborhood simultaneously, justifying the reuse of data throughout training.
- Generalized Tensor Initialization: The authors provide a version of the tensor method that works for a wider class of functions, including sigmoid and tanh, relaxing previous requirements for homogeneous activations like ReLU.
Key Results
The analysis yields several critical findings regarding the efficiency and accuracy of the recovery process:
- Sample Complexity: Recovery is guaranteed with a sample size scaling as $n = O(d \log^2 d)$, which is considered near-optimal relative to the input dimension $d$.
- Linear Convergence: Following correct initialization, gradient descent converges linearly to a point statistically close to the ground truth.
- Statistical Accuracy: The recovered weights $W_n$ converge to the true weights $W^*$ at a rate of $O(\sqrt{d \log n / n})$.
As shown in the figures above, the success rate increases sharply as the number of samples $n$ grows, while the estimation error (NMSE) decreases consistently, confirming the theoretical convergence rates.
Limitations and Future Work
While this work provides a significant step forward, it relies on the assumption of Gaussian input data. Real-world data structures are far more complex. Additionally, the analysis is currently limited to one-hidden-layer networks. Extending these global convergence guarantees to deep, multi-layer architectures and exploring ReLU-like activations under cross-entropy loss remain important directions for future research.
Summary updated