MAKING THE LAST ITERATE OF SGD INFORMATION THEORETICALLY OPTIMAL

Stochastic gradient descent (SGD) is one of the most widely used algorithms for large-scale optimization problems. While classical theoretical analysis of SGD for convex problems studies (suffix) averages of iterates and obtains information theoretically optimal bounds on suboptimality, the last point of SGD is, by far, the most preferred choice in practice. The best known results for the last point of SGD [O. Shamir and T. Zhang, Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 71-79] however, are suboptimal compared to information theoretic lower bounds by a log T factor, where T is the number of iterations. Harvey, Liaw, Plan, and Randhawa [Conference on Learning Theory, PMLR, 2019, pp. 1579-1613] shows that in fact, this additional log T factor is tight for standard step size sequences of Theta(1/root t) and Theta(1/t) for non-strongly convex and strongly convex settings, respectively. Similarly, even for subgradient descent (GD) when applied to nonsmooth, convex functions, the best known step size sequences still lead to O(log T)-suboptimal convergence rates (on the final iterate). The main contribution of this work is to design new step size sequences that enjoy information theoretically optimal bounds on the suboptimality of the last point of SGD as well as GD. We achieve this by designing a modification scheme that converts one sequence of step sizes to another so that the last point of SGD/GD with modified sequence has the same suboptimality guarantees as the average of SGD/GD with original sequence. We also show that our result holds with high probability. We validate our results through simulations which demonstrate that the new step size sequence indeed improves the final iterate significantly compared to the standard step size sequences.

Automated summary

Stochastic gradient descent (SGD) is widely used for large-scale optimization, but the conventional step size sequences often lead to suboptimal convergence rates. This work presents new step size sequences that achieve information theoretically optimal bounds on the suboptimality, improving the final iterate significantly compared to standard sequences.