Reviews: Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD

Update: Thank you for the feedback, I have read it as well as other reviews. Compared with the vast literature on obtaining upper bounds on convergence rates of stochastic convex optimization problems, less work has been done towards deriving corresponding lower bounds that depict the fundamental hardness of these problems. This paper aims to fill this gap and proposes a general framework for comparing upper and lower bounds. The framework also suggests potential future research directions for obtaining better convergence rates. In addition, this paper proved, for all round t, a lower bound on the expected convergence rate of SGD over any diminishing step-size sequences when applied to strongly convex problems. This bound shows that the step-size schemes proposed in recent work (Gower et al. 2019, and Nguyen et al. 2018) are optimal within a dimension independent constant factor.