From Theorem REF , we see that the asymptotic convergence rate consists of two terms.
The first term comes from the strong law of large number for a martingale that characterizes the random sampling in each iteration (cf. \(\mathcal {I}_{1,t}\)  in (REF )).
The second term comes from the adaptivity of random stepsizes (cf. \(\mathcal {I}_{2,t}\)  in ()).
It disappears when \(\chi _t=0\) , i.e., setting \({\bar{\alpha }}_t = \beta _t\)  deterministically.
From Lemma REF , we see that all the remaining terms contained in \(\mathcal {I}_{3,t}\)  only contribute higher order errors.
We note that [1]}, [2]}, [3]} set \(\chi _t = O(\beta _t^2)\) .
In this case, \(\chi _t = O(\varphi _t^2)\)  and, hence, the first term dominates the convergence rate.
In fact, our theorem suggests that \(\chi _t = O(\beta _t^{3/2})\)  is sufficient to have the first term dominate, which allows a wider interval for selecting the stepsize \({\bar{\alpha }}_t\) .
