Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

Junchi Yang, Xiang Li, Ilyas Fatkhullin, Niao He

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:

  1. Untuned SGD: Standard SGD with a polynomially decaying stepsize schedule ($\eta_t = \eta / \sqrt{t+1}$) where $\eta$ is independent of $\ell$.
  2. Adaptive Methods (Norm Versions): Algorithms that dynamically adjust their stepsizes based on the norms of past or current gradients. Specifically, they analyze:
  3. Normalized SGD (NSGD): Stepsize is normalized by the current gradient norm.
  4. NSGD with Momentum (NSGD-M): Incorporates a momentum buffer into the normalization.
  5. AdaGrad-norm: Scales the stepsize down using the running sum of all past squared gradient norms.
  6. 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:

  1. Synthetic Quadratic Functions: $f(x) = \ell x^2 / 2$, used to isolate the effect of the smoothness parameter $\ell$.
  2. 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:

Complexities of finding an $\epsilon$-stationary point
  • 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:

Empirical comparison of gradient norms

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

Abstract

The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize $η_t = η/\sqrt{t}$ relies on well-tuned $η$ depending on problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary $η> 0$, referred to as untuned SGD, still attains an order-optimal convergence rate $\widetilde{O}(T^{-1/4})$ in terms of gradient norm for minimizing smooth objectives. Unfortunately, it comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods $\unicode{x2013}$ Normalized SGD (NSGD), AMSGrad, and AdaGrad $\unicode{x2013}$ unveiling their power in preventing such exponential dependency in the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide theoretical justification for the advantage of adaptive methods over untuned SGD in alleviating the issue with large gradients.
BibTeX
@inproceedings{yang2023two,
  author = {Junchi Yang and Xiang Li and Ilyas Fatkhullin and Niao He},
  title = {{Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=fUZUoSLXw3},
}
Figure