The guarantee in (REF ) is the same as when SGD uses a deterministic-learning-rate, e.g., as given in [1]}. The step size is \( \frac{ c_1}{c_2^2} \)  times smaller than in the deterministic-learning-rate case. This is pragmatically nonrestrictive for convergence speed as supported by experimental results, since \( c_1 \)  and \( c_2 \)  are adequately close in practice (see discussion in Section ).
