Demystifying the Myths and Legends of Nonconvex Convergence of SGD
Aritra Dutta El Houcine Bergou Soumia Boucherouite Nicklas Werge Melih Kandemir Xin Li
Stochastic gradient descent (SGD) and its variants are the main workhorses
for solving large-scale optimization problems with nonconvex objective
functions. Although the convergence of SGDs in the (strongly) convex case is
well-understood, their convergence for nonconvex functions stands on weak
mathematical foundations. Most existing studies on the nonconvex convergence of
SGD show the complexity results based on either the minimum of the expected
gradient norm or the functional sub-optimality gap (for functions with extra
structural property) by searching the entire range of iterates. Hence the last
iterations of SGDs do not necessarily maintain the same complexity guarantee.
This paper shows that an $\epsilon$-stationary point exists in the final
iterates of SGDs, given a large enough total iteration budget, $T$, not just
anywhere in the entire range of iterates -- a much stronger result than the
existing one. Additionally, our analyses allow us to measure the density of the
$\epsilon$-stationary points in the final iterates of SGD, and we recover the
classical $O(\frac{1}{\sqrt{T}})$ asymptotic rate under various existing
assumptions on the objective function and the bounds on the stochastic
gradient. As a result of our analyses, we addressed certain myths and legends
related to the nonconvex convergence of SGD and posed some thought-provoking
questions that could set new directions for research.