On the Origin of Implicit Regularization in Stochastic Gradient Descent

Samuel Smith, Benoît Dherin, David G. T. Barrett, Soham De

arXiv (Cornell University) · 2021 · 40 citations · 19 references

DOIFull text

Open access

Concepts

TL;DR

SGD with infinitesimal learning rates follows gradient flow, yet moderately large learning rates can yield higher test accuracy, a benefit not captured by convergence bounds because the optimal test‑accuracy rate often exceeds the rate minimizing training loss. The authors aim to explain this generalization advantage by analyzing SGD with random shuffling. They prove that the mean SGD iterate tracks gradient flow on a modified loss that adds an implicit regularizer penalizing minibatch gradient norms, whose magnitude scales with the learning‑rate‑to‑batch‑size ratio. Empirical results show that explicitly incorporating this implicit regularizer into the loss improves test accuracy when the learning rate is small.

Abstract

For infinitesimal learning rates, stochastic gradient descent (SGD) follows the path of gradient flow on the full batch loss function. However moderately large learning rates can achieve higher test accuracies, and this generalization benefit is not explained by convergence bounds, since the learning rate which maximizes test accuracy is often larger than the learning rate which minimizes training loss. To interpret this phenomenon we prove that for SGD with random shuffling, the mean SGD iterate also stays close to the path of gradient flow if the learning rate is small and finite, but on a modified loss. This modified loss is composed of the original loss function and an implicit regularizer, which penalizes the norms of the minibatch gradients. Under mild assumptions, when the batch size is small the scale of the implicit regularization term is proportional to the ratio of the learning rate to the batch size. We verify empirically that explicitly including the implicit regularizer in the loss can enhance the test accuracy when the learning rate is small.

References

19