bounds can be improved to $\frac{d}{\alpha} \log T$ and $\frac{d}{\alpha} \frac{\log T}{T}$ at the expense of assuming that the norm $\|\nabla f\|$ is uniformly bounded by $G$ not only on ${\Theta}$ but also on a large enough Euclidean neighborhood of ${\Theta}$. Moreover, the $\log T$ factor in the bounds for the optimization error can be eliminated by considering averaging from $T/2$ to $T$ rather than from 1 to $T$ in the spirit of [@rakhlin2011making]. We refer to Appendix \[app:C\] for the details and proofs of these facts. A major conclusion is that, when $\sigma>0$ and we consider the optimization error, those terms are negligible with respect to $d/\sqrt{\alpha T}$ and thus an attainable rate is $\min(1,d/\sqrt{\alpha T})$. We close this section by noting, in connection with the bandit setting, that the bound extends straightforwardly (up to a change in numerical constants) to the cumulative regret of the form $\mathbb{E}\sum_{t=1}^{T} \big(f_t(x_t\pm h_t\zeta_t) - f_t(x)\big)$, where the losses are measured at the query points and $f$ depends on $t$. This fact follows immediately from the proof of Theorem \[th6.3\] presented in the appendix and the property , see Lemma \[lem6.4\] in the appendix.

Lower bound {#sec:LB}
===========

In this section we prove 