Convergence Analysis of Two-layer Neural Networks with ReLU Activation

The evolution of deep learning has been marked by breakthroughs in architecture design, such as residual networks, which alleviate training difficulties in very deep models. Prior work like the loss surface analysis by Choromanska et al. and the expressivity results by Cybenko established the power of neural networks. However, theoretical guarantees for training convergence, especially for nonlinear activations like ReLU, remain limited. Existing analyses often assume independence of activations or linearity, which do not reflect real networks. The challenge of understanding how SGD escapes saddle points and converges efficiently in high-dimensional, non-convex landscapes persists. This paper situates itself within this context, proposing a structural modification to facilitate analysis and convergence guarantees.

Despite empirical success, the theoretical understanding of neural network training via SGD is incomplete. Non-convex loss surfaces contain numerous saddle points and local minima, complicating convergence analysis. Existing theories often rely on restrictive assumptions, such as activation independence or linearity, which are unrealistic. The core problem is to rigorously prove that SGD can efficiently reach the global minimum in realistic, nonlinear settings, especially for networks with ReLU activations. The difficulty lies in the complex geometry of the loss landscape and the dynamics of high-dimensional stochastic optimization. Addressing this requires novel structural insights and analytical tools to characterize the optimization path and convergence conditions.

The key innovation is the incorporation of an identity mapping into the two-layer network, inspired by residual connections, which introduces asymmetry and ensures a unique global minimum. The analysis employs a potential function g to track the deviation from the true weights, combined with Taylor expansion and geometric bounds to analyze the gradient directions. The two-phase framework—initial potential reduction followed by convergence in a convex region—provides a rigorous pathway to polynomial-time convergence under Gaussian inputs. This approach departs from traditional assumptions of activation independence, leveraging network structure to guarantee optimization success, and offers a new theoretical paradigm for analyzing nonlinear neural networks.

• �� Construct a two-layer neural network with an added identity mapping in the hidden layer, defining the target function as f(x,W) = ‖ReLU((I+W)^T x)‖1.
• �� Assume input x follows a Gaussian distribution N(0, I), with weights initialized at O(1/√d).
• �� Define a potential function g = ∑i(‖ei + w* i‖2 − ‖ei + wi‖2), measuring deviation from the true weights.
• �� Analyze the gradient dynamics using Lemma 2.1, Taylor expansion, and geometric bounds, dividing training into two phases:
• Phase I: g decreases despite gradient misdirection.
• Phase II: W enters a one-point convex region, enabling convergence.
• �� Prove that in each phase, SGD steps reduce the potential and distance to W*, ensuring polynomial convergence.
• �� Use probabilistic bounds and potential function control to formalize the convergence guarantees.

The experimental setup involves training networks with and without the identity mapping on datasets like CIFAR-10 and MNIST. Inputs are sampled from Gaussian distributions, and weights are initialized at O(1/√d). The experiments compare training and test errors, parameter distances, and potential g over iterations. Multiple runs ensure statistical robustness. Ablation studies analyze the impact of the identity mapping, initialization schemes, and network depth. Results show that networks with the identity mapping consistently reach near-zero training error within fewer epochs, validating the theoretical predictions. Additional experiments track the dynamics of the potential g and the gradient directions, illustrating the two-phase convergence process.

Results demonstrate that with Gaussian inputs and standard initialization, SGD converges to the true weights within polynomial steps, achieving negligible error. The introduction of the identity mapping significantly improves convergence speed and stability, especially in deeper networks. Empirical trajectories of g and parameter distances align with the theoretical two-phase model, confirming that initial potential reduction precedes convergence. Ablation experiments show that removing the identity mapping leads to stagnation at saddle points or local minima, emphasizing its critical role. Overall, the experiments substantiate the theoretical framework and highlight the importance of structural biases in neural network training.