the same order as the main term $\sigma/\sqrt{T}$.

Note that in Theorem \[thm:min\] the noises $(\xi''_t)_{t=1}^T$ are assumed to be independent and zero mean random variables, which is essential to obtain the $1/\sqrt{T}$ rate. Nevertheless, we do not require independence between the noises $(\xi''_t)_{t=1}^T$ and the noises in the other two queries $(\xi_t)_{t=1}^T$ and $(\xi'_t)_{t=1}^T$. Another interesting point is that for $\beta=2$ the third query is not needed and $f(x^*)$ is estimated with the $1/\sqrt{T}$ rate either by $
\hat M = \frac{1}{T}\sum_{t=1}^T y_t
$ or by $
\hat M = \frac{1}{T}\sum_{t=1}^T y'_t.
$ This is an easy consequence of the above argument, the property – see Lemma \[lem6.4\] in the appendix – which is specific for the case $\beta=2$, and the fact that the optimal choice of $h_t$ is of order $t^{-1/4}$ for $\beta=2$.

Improved bounds for $\beta=2$ {#sec:beta2}
=============================

In this section, we consider the case $\beta=2$ and obtain improved bounds that scale as $d$ rather than $d^2$ with the dimension in the constrained optimization setting analogous to Theorem \[thm:1\]. First note that for $\beta=2$ we can simplify the algorithm. The use of kernel $K$ is redundant when $\beta=2$, and therefore in this section we define the approximate 