There is this "folklore" result that gradient descent on a non-convex function takes $O(\frac n {\epsilon^2})$ steps to get to a point whose gradient norm is below $\epsilon$ and with SGD this takes $O(\frac {1}{\epsilon^4})$ steps.
• What are you assuming about the function? If nothing, take your favorite function and then for each $m \in \mathbb{N}$, pick a starting point, run gradient descent from that point for $m \cdot \frac{n}{\varepsilon^2}$ iterations, then modify the function to make the gradient get steep there. – Solomonoff's Secret Mar 8 '18 at 1:16