We study convergence of Stochastic Gradient Descent (SGD) for strongly convex and smooth objective functions $F$. We prove a lower bound on the expected convergence rate which holds for any sequence of diminishing stepsizes that are designed based on only global knowledge such as the fact that $F$ is smooth and strongly convex, the component functions are smooth and convex, together with more additional information. Our lower bound meets the expected convergence rate of a recently proposed sequence of stepsizes at ICML 2018, which is based on such knowledge, within a factor 32. This shows that the stepsizes as proposed in the ICML paper are close to optimal. Furthermore, we conclude that in order to be able to construct stepsizes that beat our lower bound, more detailed information about $F$ must be known. Our work significantly improves over the state-of-the-art lower bound which we show is another factor $643\cdot d$ worse, where $d$ is the dimension. We are the first to prove a lower bound that comes within a small constant -- independent from any other problem specific parameters -- from an optimal solution.

研究随机梯度下降法（SGD）在强凸目标函数上的收敛性，证明了ICML 2018和2019提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到32倍，为最优状态；该下限相较于现有工作大约高出了因子775×d，其中d是维度。

随机梯度下降法在递减步长下期望收敛速率的紧凑维度无关下限