Benign Underfitting of Stochastic Gradient Descent. (arXiv:2202.13361v3 [cs.LG] UPDATED)

We study to what extent may stochastic gradient descent (SGD) be understood
as a "conventional" learning rule that achieves generalization performance by
obtaining a good fit to training data. We consider the fundamental stochastic
convex optimization framework, where (one pass, without-replacement) SGD is
classically known to minimize the population risk at rate $O(1/\sqrt n)$, and
prove that, surprisingly, there exist problem instances where the SGD solution
exhibits both empirical risk and generalization gap of $\Omega(1)$.
Consequently, it turns out that …

arxiv gradient lg stochastic underfitting