Abstract
In this article, we study the stochastic gradient descent (SGD) optimization method in the training of fully-connected feedforward artificial neural networks with ReLU activation. The main result of this work proves that the risk of the SGD process converges to zero if the target function under consideration is constant. In the established convergence result, the considered artificial neural networks consist of one input layer, one hidden layer, and one output layer (with $d \in \mathbb{N}$ neurons on the input layer, $H \in \mathbb{N}$ neurons on the hidden layer, and one neuron on the output layer). The learning rates of the SGD process are assumed to be sufficiently small and the input data used in the SGD process to train the artificial neural networks is assumed to be independent and identically distributed.
Introduction
Despite the ubiquity of Stochastic Gradient Descent (SGD) in modern deep learning, a comprehensive mathematical understanding of its success remains elusive. Most classical optimization theory relies on two pillars: convexity (ensuring any local minimum is a global one) and smoothness (the existence of derivatives everywhere).
Artificial Neural Networks (ANNs) using Rectified Linear Unit (ReLU) activations violate both conditions. They are inherently non-convex and non-differentiable at the origin. This paper addresses this theoretical gap by providing a rigorous proof that SGD converges to a global minimum when training a shallow ReLU network to learn a constant target function. By formalizing how optimization handles non-differentiable points, this work bridges the gap between empirical practice and theoretical guarantees.
The Challenge of ReLU Networks
The ReLU activation function, defined as $\max\{x, 0\}$, introduces a "kink" at zero where the derivative is undefined. In practice, deep learning libraries like PyTorch and TensorFlow employ heuristics to bypass this, typically assigning a gradient of zero at the point of non-differentiability. However, proving that this heuristic leads to global convergence in a non-convex landscape is mathematically complex.
To make this problem tractable, the authors analyze a fully-connected feedforward network with:
- Input Layer: $d$ neurons.
- Hidden Layer: $H$ neurons with ReLU activation.
- Output Layer: A single neuron.
- Target: A constant value $\xi \in \mathbb{R}$.
Methodology
Generalized Gradients
To address the non-differentiability of ReLU, the authors utilize generalized gradients. These are defined as the limit of gradients of smooth approximations (such as the softplus function). This approach mathematically justifies the heuristic methods used in modern software frameworks, proving that the optimization path remains valid even when crossing non-differentiable boundaries.
Lyapunov Stability Analysis
The core of the convergence proof rests on Lyapunov functions, a concept borrowed from dynamical systems. The authors construct a Lyapunov function that represents the "energy" or "risk" of the neural network. By analyzing the evolution of this function under SGD, they demonstrate that the system's energy must eventually dissipate, forcing the risk to zero.
Learning Rate and Data Assumptions
The proof requires specific conditions on the learning rate $\gamma_n$:
- Upper Bound: The learning rate must be sufficiently small relative to the initial weights and dimensions to prevent the optimizer from entering "exploding" regions of the loss landscape.
- Non-summability: The learning rates must satisfy $\sum \gamma_k = \infty$, ensuring the optimizer has sufficient "fuel" to reach the global minimum regardless of the starting point.
- Data Distribution: Input data is assumed to be independent and identically distributed (i.i.d.) following an arbitrary probability distribution on a bounded hypercube $[a, b]^d$.
Key Results
Convergence to Zero Risk
The paper's primary contribution, Theorem 3.12, establishes that the risk $L(\Theta_n)$ converges to zero in two distinct senses:
- Almost Sure Convergence: The risk will reach zero with probability 1.
- $L^1$ Convergence: The expected (average) error across the distribution converges to zero.
Weight Stability
Beyond risk convergence, the authors prove that the network weights remain bounded throughout the training process with probability 1. This ensures that the SGD process is numerically stable and does not diverge to infinity.
Empirical Alignment
The authors include a verification using TensorFlow to demonstrate that the "generalized gradients" defined in their mathematical framework align perfectly with the gradients computed by standard deep learning libraries. This confirms that the theoretical model accurately reflects real-world implementation.
Limitations and Future Directions
While this proof represents a significant step forward, it is constrained by two factors:
- Constant Target Functions: Real-world applications involve complex, non-constant functions. This study serves as a baseline to isolate the effects of ReLU non-linearity and SGD stochasticity.
- Shallow Architectures: The proof is limited to a single hidden layer. Deep networks introduce more complex topological features, such as saddle points and plateaus, which require further investigation.
Future research may extend these Lyapunov-based estimates to affine target functions (linear relationships) and eventually to more general function classes, moving closer to a complete theory of deep learning optimization.
Summary updated