The Complexity of Finding Stationary Points with Stochastic Gradient
  Descent
  We study the iteration complexity of stochastic gradient descent (SGD) for
minimizing the gradient norm of smooth, possibly nonconvex functions. We
provide several results, implying that the $\mathcal{O}(\epsilon^{-4})$ upper
bound of Ghadimi and Lan~\cite{ghadimi2013stochastic} (for making the average
gradient norm less than $\epsilon$) cannot be improved upon, unless a
combination of additional assumptions is made. Notably, this holds even if we
limit ourselves to convex quadratic functions. We also show that for nonconvex
functions, the feasibility of minimizing gradients with SGD is surprisingly
sensitive to the choice of optimality criteria.
