Improved last-iterate bounds for SGD with and without replacement

원문 초록

In this work, we study last-iterate convergence bounds for stochastic gradient descent (SGD) on convex and $\beta$-smooth loss functions and improve the bound from $\cO((\log T)^3/T)$ to $\cO((\log T)^3/(T\log\log T))$ in the interpolation regime. The improvement comes from applying a horizon-dependent multiscale estimate of gradients to the comparison of trajectories. The bound applies to both sampling with replacement and sampling without replacement within one pass.