The Complexity of Finding Stationary Points with Stochastic Gradient Descent
This provides theoretical limits for optimization algorithms, which is incremental for researchers in machine learning and optimization.
The paper tackles the problem of determining the iteration complexity of stochastic gradient descent (SGD) for minimizing gradient norms in smooth, possibly nonconvex functions, showing that the O(ε^{-4}) upper bound cannot be improved without additional assumptions, even for convex quadratics, and that feasibility is sensitive to optimality criteria in nonconvex cases.
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}(ε^{-4})$ upper bound of Ghadimi and Lan~\cite{ghadimi2013stochastic} (for making the average gradient norm less than $ε$) 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.