The Last Iterate of the Projected Stochastic Subgradient Method Pays a Logarithm, Even in Dimension One

Abstract

We prove that the projected stochastic subgradient method with the standard anytime stepsizes ${\eta }_t=\gamma /\sqrt{t}$ can suffer expected last-iterate optimization error of order $(\log n)/\sqrt{n}$ already on the real line. Combined with the classical in-expectation upper bound, this establishes the sharp worst-case order of the projected stochastic subgradient method.