We now use Theorem 2 from [1]} - they use notation \({\beta _t}_t\)  and \({\gamma _t}_t\)  for the step size schedule of Accelerated SGD and set \(\beta _t = \frac{t+1}{2}\)  and \(\gamma _t = \frac{t+1}{2}\gamma \) . Even though the updates of their A-SGD seem different than us, it can be verified that they are the same with \(\alpha _t = \beta _{t+1}(1-\beta _{t}^{-1}) = \frac{1-t}{t+2}\)  with \(\alpha _0=0\)  and \(\eta = \gamma \) .
Finally, using step-size \(\eta \le \frac{1}{2L}\) , and appealing to Theorem 2 in [1]}, we get,
\({ \hat{F}(\hat{}_S) - \hat{F}(^*)} \le O{ T\eta ^2 + \frac{D^2}{\eta T^2}} = O{\eta T {\frac{2G^2}{m} +\sigma ^2d} + \frac{D^2}{\eta T^2}}\) 
