Abstract
Modern deep learning relies heavily on Stochastic Gradient Descent with Momentum (SGDM), yet theoretical justifications for its success often assume smooth loss landscapes. In practice, neural networks are frequently non-smooth due to components like ReLU activations and quantization. This paper bridges this gap by introducing a random exponential scaling factor to the update rule. We demonstrate that this modification allows SGDM to achieve optimal convergence rates on non-smooth, non-convex functions. Our framework, "Exponentiated O2NC," provides a theoretically sound foundation for momentum-based heuristics, showing that they are not merely heuristics but robust tools for complex optimization landscapes.
Introduction
In the field of deep learning optimization, there is a persistent disconnect between theory and practice. Most convergence proofs for Stochastic Gradient Descent (SGD) and its variants rely on the assumption of smoothness—specifically, that the gradient of the loss function does not change too abruptly. However, the architectures that define modern AI, such as ResNets and Transformers, are inherently non-smooth. Features like ReLU activations, max-pooling, and various quantization layers create landscapes where Taylor expansions—the bread and butter of optimization analysis—fail to provide reliable predictions.
While specialized algorithms for non-smooth landscapes exist, such as those targeting "Goldstein stationary points," they are often computationally expensive, memory-intensive, and rarely used by practitioners. This research seeks to reconcile this by asking: Can we modify the algorithms engineers actually use (like SGDM) to make them theoretically optimal for non-smooth problems?
The Challenge of Non-smoothness
In a non-smooth setting, deterministic algorithms can easily become trapped or misled by "walls" in the loss landscape where the gradient provides poor information about the surrounding area. Traditional analysis fails because it cannot bound the change in function value using the gradient at a single point. To address this, the authors introduce a new success metric: $(c, \epsilon)$-stationary points. This metric is a variance-based relaxation of classic stationarity, allowing algorithms to take more aggressive steps when far from a solution while maintaining a rigorous definition of convergence.
The Random Scaling Identity
The core innovation of this work is the "Exponential Scaling Trick" (Lemma 3.1). The authors propose scaling each update step by a random variable $s$ drawn from an exponential distribution with mean 1 ($s \sim \text{Exp}(1)$).
Mathematically, this identity ensures that the expected change in the function value exactly equals the expected inner product of the gradient and the step. By introducing this specific type of noise, the algorithm effectively "smooths" the landscape in expectation, bypassing the need for traditional smoothness assumptions. This randomization acts as a natural explorer, allowing the optimizer to account for the average landscape around a point rather than being misled by local non-smooth artifacts.
Exponentiated O2NC Framework
The authors build upon the "Online to Non-Convex" (O2NC) framework, which converts Online Convex Optimization (OCO) algorithms into non-convex ones. Their improved version, Exponentiated O2NC, offers two major advantages:
- Practicality: Unlike previous iterations that required evaluating gradients at auxiliary "mid-points" (increasing memory overhead), this version evaluates gradients at the current iterate.
- Direct Mapping to SGDM: When Online Mirror Descent is plugged into this framework, the resulting update rule is nearly identical to standard SGDM, with the only addition being the random scaling factor.
Theoretical and Empirical Results
Theoretical Optimality
The proposed algorithm achieves a convergence rate of $O(\epsilon^{-4})$ for smooth functions and $O(\epsilon^{-7/2})$ for second-order smooth functions. These rates are significant because they match the known theoretical lower bounds for these classes of problems, proving that the addition of random scaling does not sacrifice efficiency for robustness.
Empirical Validation
To ensure that the theoretical modification remains practical, the authors tested "Randomly Scaled SGDM" against standard SGDM on the CIFAR-10 dataset using a ResNet-18 architecture. The results showed that the added noise from the exponential distribution did not hinder the training process or final performance:
- Standard SGDM: 94.6% Test Accuracy
- Randomly Scaled SGDM: 94.4% Test Accuracy
The training loss and accuracy curves were nearly indistinguishable, suggesting that random scaling is a "safe" modification that provides rigorous theoretical guarantees without a performance penalty in real-world scenarios.
Conclusion and Future Work
This work demonstrates that the gap between practical momentum methods and non-smooth optimization theory can be bridged with a simple randomized tweak. By showing that SGDM is a "natural" derivative of regret-minimization frameworks, the authors provide a stronger theoretical footing for the most common tools in deep learning.
Future research directions include extending this framework to adaptive optimizers like Adam, which are even more prevalent in large-scale model training. Additionally, while random scaling is essential for the current proofs, the question of whether a purely deterministic algorithm can achieve similar optimal rates in non-smooth landscapes remains an open and intriguing challenge.
Summary updated