TL;DR
While untuned Stochastic Gradient Descent (SGD) can theoretically achieve an order-optimal convergence rate, it suffers from a catastrophic exponential dependence on the objective's smoothness constant, explaining its real-world vulnerability to gradient explosion. This paper proves that this exponential penalty is completely unavoidable for SGD, but demonstrates that adaptive methods like AdaGrad and Normalized SGD with momentum naturally eliminate it—even without assuming bounded gradients.
What Problem Does This Paper Address?
In textbook optimization, analyzing SGD requires carefully tuning the learning rate ($\eta$) based on problem-specific parameters like the Lipschitz smoothness constant ($\ell$). In practice, however, $\ell$ is rarely known. Practitioners resort to "untuned SGD," picking an arbitrary starting stepsize and decaying it over time (e.g., $\eta_t = \eta / \sqrt{t}$).
When this arbitrary stepsize is too large, training often suffers from the notorious "gradient explosion" effect, leading to divergence or painfully slow convergence. Traditional theoretical analyses fail to explain this behavior because they typically rely on a highly unrealistic assumption: that gradients are globally bounded ($\|\nabla f(x)\| \le G$). This assumption is false for even a simple quadratic function ($f(x) = x^2$).
This paper tackles a fundamental question: Can we rigorously explain why untuned SGD explodes, and mathematically justify why adaptive methods (like AdaGrad and AMSGrad) fix this issue without pretending gradients are bounded?
Methods
The authors analyze stochastic non-convex optimization under standard, realistic assumptions: the objective function is $\ell$-smooth, and the stochastic gradient noise has a bounded variance ($\sigma^2$), but the gradients themselves can be infinitely large.
They evaluate two regimes:
- Untuned SGD: Standard SGD with a polynomially decaying stepsize schedule ($\eta_t = \eta / \sqrt{t+1}$) where $\eta$ is independent of $\ell$.
- Adaptive Methods (Norm Versions): Algorithms that dynamically adjust their stepsizes based on the norms of past or current gradients. Specifically, they analyze:
- Normalized SGD (NSGD): Stepsize is normalized by the current gradient norm.
- NSGD with Momentum (NSGD-M): Incorporates a momentum buffer into the normalization.
- AdaGrad-norm: Scales the stepsize down using the running sum of all past squared gradient norms.
- AMSGrad-norm: A variant designed to fix Adam's non-convergence by tracking the maximum of past gradient norms.
To prove that SGD's flaws are inherent, the authors construct a worst-case "hard instance" function in 1D consisting of four distinct quadratic segments (illustrated in Figure 2).
Datasets
The paper primarily focuses on theoretical proofs, but validates its findings using two setups:
- Synthetic Quadratic Functions: $f(x) = \ell x^2 / 2$, used to isolate the effect of the smoothness parameter $\ell$.
- MNIST: A classic handwritten digit dataset used to train a 3-layer neural network with cross-entropy loss to observe gradient behavior in a practical deep learning setting.
Key Insights and Ideas
- The Exponential Curse of SGD: The authors prove that the convergence bound for untuned SGD contains a disastrous exponential term: $\exp(\eta^2 \ell^2)$. If your initial stepsize $\eta$ is even slightly larger than $1/\ell$, the expected gradient norm explodes exponentially during the initial training phase before it can recover.
- The Explosion is Unavoidable: Through their adversarial 4-segment function, the authors prove a matching lower bound. This confirms that gradient explosion isn't an artifact of loose math; untuned SGD is fundamentally vulnerable to being kicked into steep valleys where it gets trapped expanding its gradients exponentially.
- Adaptive Methods as an Exponential Shield: Because adaptive methods automatically shrink the stepsize when encountering massive gradients, they completely eliminate the exponential dependency. The complexity bounds for AdaGrad-norm and NSGD-M drop from exponential to purely polynomial relationships with $\ell$.
- The Dark Side of AMSGrad: In a surprising twist, the authors show that while AMSGrad-norm excels in deterministic settings, it can fail drastically in stochastic settings with unbounded noise. Because it tracks the maximum historical gradient norm, a single massive noise spike can permanently crush the stepsize, forcing the algorithm to converge at an arbitrarily slow polynomial rate.
Key Results
The core theoretical complexities derived by the authors are summarized in Table 1:
- SGD Bound: Achieves the optimal $\widetilde{O}(\epsilon^{-4})$ dependency on accuracy, but suffers from an $\Omega((8e)^{\eta^2\ell^2/8}\epsilon^{-4})$ deterministic lower bound.
- AdaGrad-norm & NSGD-M Victory: Both successfully eliminate the exponential factor. In the stochastic setting, they achieve a clean polynomial complexity of $\widetilde{O}(\epsilon^{-4})$ without needing any parameter tuning.
These mathematical bounds perfectly mirror empirical realities. As shown in Figure 1, when the smoothness constant $\ell$ or initial stepsize is large, SGD's gradients skyrocket into the billions, while AdaGrad and NSGD-M remain perfectly stable:
Limitations and Future Work
- Norm vs. Coordinate-wise Adaptivity: This work analyzes "norm" versions of adaptive algorithms where a single scalar stepsize modifies the entire gradient vector. Practical implementations of Adam and AdaGrad typically scale stepsizes coordinate-wise. Extending this theory to coordinate-wise updates remains an open challenge.
- AMSGrad Vulnerability: The slow convergence of AMSGrad under unbounded stochastic noise highlights a structural weakness. Future work could investigate modifications (like gradient clipping or altered tracking metrics) to protect AMSGrad from noise spikes without reintroducing exponential smoothness dependencies.
Summary updated