Title: The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence. Abstract: Stochastic Gradient Descent (SGD) is among the simplest and most popular optimization and machine learning methods. Running SGD with a fixed step size and outputting the final iteration is an ideal strategy one can hope for, but it is still not well-understood even though SGD has been studied extensively for over 70 years. Given the $\Theta(\log T)$ gap between current upper and lower bounds for running SGD for $T$ steps, it was then asked by [Koren and Segal COLT 20'] how to characterize the final-iterate convergence of SGD with a fixed step size in the constant dimension setting, i.e., $d=O(1)$. 

In this paper, we consider the more general setting for any $d\leq T$, proving $\Omega(\log d/\sqrt{T})$ lower bounds for the sub-optimality of the final iterate of SGD in minimizing non-smooth Lipschitz convex functions with standard step sizes. Our results provide the first general dimension-dependent lower bound on the convergence of SGD's final iterate, partially resolving the COLT open question raised by [Koren and Segal COLT 20'].
Moreover, we present a new method in one dimension based on martingale and Freedman’s inequality, which gets the tight $O(1/\sqrt{T})$ upper bound with mild assumptions and recovers the same bounds $O(\log T/\sqrt{T})$ as previous best results under the standard assumptions.