a minimax lower bound on the optimization error over all sequential strategies that allow the query points depend on the past. For $t=1,\dots, T$, we assume that $y_t=f(z_t)+\xi_t$ and we consider strategies of choosing the query points as $z_t= \Phi_t(z_1^{t-1},y_1^{t-1})$ where $\Phi_t$ are Borel functions and $z_1\in \mathbb{R}^d$ is any random variable. We denote by $\Pi_T$ the set of all such strategies. The noises $\xi_1,\dots,\xi_T$ are assumed in this section to be independent with cumulative distribution function $F$ satisfying the condition $$\label{distribution}
\int \log\big(dF(u)/dF(u+v)\big)dF(u)\leq I_{0}v^{2}, \quad |v|< v_{0}$$ for some $0<I_{0}<\infty$, $0<v_{0}\leq \infty$. For example, for Gaussian distribution $F$ this condition holds with $v_0=\infty$. Note that the class $\Pi_T$ includes the sequential strategy of Algorithm \[algo\] that corresponds to taking $T$ as an even number, and choosing $z_t=x_t+\zeta_tr_t$ and $z_t=x_t-\zeta_tr_t$ for even $t$ and odd $t$, respectively. The presence of the randomizing sequences $\zeta_t, r_t$ is not crucial for the lower bound. Indeed, Theorem \[lb\] below is valid conditionally on any randomization, and thus the lower bound remains valid when taking expectation over the randomizing distribution.

[theorem]{}[lowerB]{} \[lb\] Let ${\Theta}=\{x\in\mathbb{R}^d: {\left\lVertx\right\rVert}\le 1\}$. For $\alpha, L>0$,$ \beta\ge 2$, let $\mathcal{F}'_{\alpha,\beta}$ denote the set of functions $f$ that attain their minimum over 