arXiv (Cornell University) · 2019 · 37 citations · 0 references
Minimax optimal convergence rates for classes of stochastic convex\noptimization problems are well characterized, where the majority of results\nutilize iterate averaged stochastic gradient descent (SGD) with polynomially\ndecaying step sizes. In contrast, SGD's final iterate behavior has received\nmuch less attention despite their widespread use in practice. Motivated by this\nobservation, this work provides a detailed study of the following question:\nwhat rate is achievable using the final iterate of SGD for the streaming least\nsquares regression problem with and without strong convexity?\n First, this work shows that even if the time horizon T (i.e. the number of\niterations SGD is run for) is known in advance, SGD's final iterate behavior\nwith any polynomially decaying learning rate scheme is highly sub-optimal\ncompared to the minimax rate (by a condition number factor in the strongly\nconvex case and a factor of $\\sqrt{T}$ in the non-strongly convex case). In\ncontrast, this paper shows that Step Decay schedules, which cut the learning\nrate by a constant factor every constant number of epochs (i.e., the learning\nrate decays geometrically) offers significant improvements over any\npolynomially decaying step sizes. In particular, the final iterate behavior\nwith a step decay schedule is off the minimax rate by only $log$ factors (in\nthe condition number for strongly convex case, and in T for the non-strongly\nconvex case). Finally, in stark contrast to the known horizon case, this paper\nshows that the anytime (i.e. the limiting) behavior of SGD's final iterate is\npoor (in that it queries iterates with highly sub-optimal function value\ninfinitely often, i.e. in a limsup sense) irrespective of the stepsizes\nemployed. These results demonstrate the subtlety in establishing optimal\nlearning rate schemes (for the final iterate) for stochastic gradient\nprocedures in fixed time horizon settings.\n