English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Minimax optimal convergence rates for classes of stochastic convexoptimization problems are well characterized, where the majority of resultsutilize iterate averaged stochastic gradient descent (SGD) with polynomiallydecaying step sizes. In contrast, SGD's final iterate behavior has receivedmuch less attention despite their widespread use in practice. Motivated by thisobservation, this work provides a detailed study of the following question:what rate is achievable using the final iterate of SGD for the streaming leastsquares regression problem with and without strong convexity?  First, this work shows that even if the time horizon T (i.e. the number ofiterations SGD is run for) is known in advance, SGD's final iterate behaviorwith any polynomially decaying learning rate scheme is highly sub-optimalcompared to the minimax rate (by a condition number factor in the stronglyconvex case and a factor of $\sqrt{T}$ in the non-strongly convex case). Incontrast, this paper shows that Step Decay schedules, which cut the learningrate by a constant factor every constant number of epochs (i.e., the learningrate decays geometrically) offers significant improvements over anypolynomially decaying step sizes. In particular, the final iterate behaviorwith a step decay schedule is off the minimax rate by only $log$ factors (inthe condition number for strongly convex case, and in T for the non-stronglyconvex case). Finally, in stark contrast to the known horizon case, this papershows that the anytime (i.e. the limiting) behavior of SGD's final iterate ispoor (in that it queries iterates with highly sub-optimal function valueinfinitely often, i.e. in a limsup sense) irrespective of the stepsizesemployed. These results demonstrate the subtlety in establishing optimallearning rate schemes (for the final iterate) for stochastic gradientprocedures in fixed time horizon settings.

The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares