$\beta>2$ since then the error of approximating $f$ by $\hat f_t$, which is of the order $h_t
^\beta$ (with $h_t$ small), becomes too large compared to the bias $d^2h_t^{2(\beta-1)}$ of Theorem \[thm:1\].

[theorem]{}[eiththeorem]{} \[th6.3\] Let $f\in \mathcal{F}_{\alpha, 2}(L)$ with $\alpha,L>0$. Let Assumption \[ass1\] hold and let ${\Theta}$ be a convex compact subset of $\mathbb{R}^d$. Assume that $\max_{x\in{\Theta}}\|\nabla f(x)\|\le G $. If $\sigma>0$ then for Algorithm \[algo\] with $\hat g_t$ defined in and parameters $h_t= \left(\frac{3d^2\sigma^2}{4L\alpha t+9L^2d^2}\right)^{1/4}$ and $\eta_t = \frac{1}{\alpha t}$ we have $$\label{eq1:th6.3}
\forall x\in \Theta: \ \ \mathbb{E} \sum_{t=1}^{T} \big(f(x_t) - f(x)\big)  
\le  \min\left(GBT, 2\sqrt{3L}\sigma
\frac{d}{\sqrt{\alpha}} \sqrt{T}+ A_4\frac{d^2}{\alpha} \log T\right),$$ where $B$ is the Euclidean diameter of ${\Theta}$ and $A_4=
6.5 L\sigma+ 22 G^2/d$. Moreover, if $x^*= \operatorname*{arg\,min}_{x\in{\Theta}}f(x)$ the optimization error of averaged estimator ${\bar x}_T=\frac{1}{T}\sum_{t=1}^T x_t$ is bounded as $$\label{eq2:th6.3}
    \mathbb{E} [ f({\bar x}_T) - f(x^*)]\leq 
    \min\left(GB, 2\sqrt{3L}\sigma
 \frac{d}{\sqrt{\alpha T}}+ A_4 \frac{d^2}{\alpha} \frac{\log T}{T}\right).$$ Finally, if $\sigma=0$, then the cumulative regret of Algorithm \[algo\] with any $h_t$ chosen small enough and $\eta_t=\frac{1}{\alpha t}$ and the optimization error of its averaged version are of the order $\frac{d^2}{\alpha} \log T$ and $\frac{d^2}{\alpha} \frac{\log T}{T}$, respectively.

Note that the terms $\frac{d^2}{\alpha} \log T$ and $\frac{d^2}{\alpha} \frac{\log T}{T}$ appearing in these 