$$h_t = \left(\frac{3\kappa\sigma^2}{2(\beta-1)(\kappa_\beta L)^2} \right)^{\frac{1}{2\beta}} t^{-\frac{1}{2\beta}},~~~\eta_t=\frac{2}{\alpha t},~~~t= 1,\dots,T~~~~~~~~$$ satisfies $$\label{eq:bound0}
    \forall x\in {\Theta}: \ \sum_{t=1}^T \mathbb{E} [ f(x_t) - f(x)]\le \frac{1}{\alpha}
    \left(
d^2 \Big(A_1 T^{{1}/{\beta}}+A_2 \Big)
+  A_3  d \log T
\right),$$ where $A_1={3\beta}(\kappa\sigma^2)^{\frac{\beta-1}{\beta}}
(\kappa_\beta L)^{\frac{2}{\beta}}$, $A_2=\bar c {\bar L^2} (\sigma/L)^{\frac{2}{\beta}}+{9\kappa G^2}/{d}$ with constant $\bar c>0$ depending only on $\beta$, and $A_3 = 9 \kappa G^2$. The optimization error of averaged estimator ${\bar x}_T=\frac{1}{T}\sum_{t=1}^T x_t$ satisfies $$\label{eq:bound1}
    \mathbb{E} [ f({\bar x}_T) - f(x^*)]\leq \frac{1}{\alpha}
\left(  d^2\left(\frac{A_1}{T^{\frac{\beta-1}{\beta}}}+ \frac{A_2}{T} \right)+ A_3 \,\frac{d\log T}{T} \right),$$ where $x^*= \operatorname*{arg\,min}_{x\in{\Theta}}f(x)$. If $\sigma=0$, then the cumulative regret and the optimization error of Algorithm \[algo\] with any $h_t$ chosen small enough and $\eta_t=\frac{2}{\alpha t}$ satisfy the bounds and , respectively, with $A_1=0, A_2={9\kappa G^2}/{d}$ and $A_3=10\kappa G^2$.

We use the definition of Algorithm \[algo\] and strong convexity of $f$ to obtain an upper bound for $\sum_{t=1}^{T}\mathbb{E} [ f(x_t) - f(x)  \hspace{.03truecm}|\hspace{.03truecm} x_t]$, which depends on the bias term $\sum_{t=1}^{T}\|\mathbb{E} [{\hat g_t}  \hspace{.03truecm}|\hspace{.03truecm} x_t]-\nabla f(x_t)\|$ and on the stochastic error term $\sum_{t=1}^{T}\mathbb{E} [\|{\hat g}_t\|^2]$. By substituting $h_{t}$ (that is derived from balancing the two terms) and $\eta_{t}$ in Lemmas \[lem:1\] and \[lem:2unco\] we obtain upper bounds for $\sum_{t=1}^{T}\|\mathbb{E} [{\hat g_t}  \hspace{.03truecm}|\hspace{.03truecm} x_t]-\nabla f(x_t)\|$ and $\sum_{t=1}^{T}\mathbb{E} [\|{\hat g}_t\|^2]$ that 