$\mathbb{R}^d$ in ${\Theta}$ and belong to $\mathcal{F}_{\alpha,\beta}(L)\cap \{f: \max_{x\in{\Theta}}\|\nabla f(x)\|\le G\}$, where $G> 2\alpha$. Then for any strategy in the class $\Pi_T$ we have $$\label{eq1:lb}
\sup_{f \in \mathcal{F}'_{\alpha,\beta}}\mathbb{E}\big[f(z_T)-\min_{x}f(x)\big]\geq C\min\Big(\max(\alpha, T^{-1/2+1/\beta}), \frac{d}{\sqrt{T}}, \,\frac{d}{\alpha}T^{-\frac{\beta-1}{\beta}}\Big),$$ and $$\label{eq2:lb}
\sup_{f \in \mathcal{F}'_{\alpha,\beta}}\mathbb{E}\big[{\left\lVertz_{T}-x^{*}(f)\right\rVert}^{2}\big]\geq C\min\Big(1, \frac{d}{T^{\frac{1}{\beta}}}, \,\frac{d}{\alpha^{2}}T^{-\frac{\beta-1}{\beta}}\Big),$$ where $C>0$ is a constant that does not depend of $T,d$, and $\alpha$, and $x^*(f)$ is the minimizer of $f$ on ${\Theta}$.

The proof is given in Appendix \[app:B\] and relies on Assouad’s Lemma, see e.g. [@Tsybakov09] with a careful choice of least favorable functions.

We stress that the condition $G> 2\alpha$ in this theorem is necessary. It should always hold if the intersection $\mathcal{F}_{\alpha,\beta}(L)\cap \{f: \max_{x\in{\Theta}}\|\nabla f(x)\|\le G\}$ is not empty. Notice also that the threshold $T^{-1/2+1/\beta}$ on the strong convexity parameter $\alpha$ plays an important role in bounds and . Indeed, for $\alpha$ below this threshold, the bounds start to be independent of $\alpha$. Moreover, in this regime, the rate of becomes $\min(T^{1/\beta},d)/\sqrt{T}$, which is asymptotically $d/\sqrt{T}$ and thus not better as function of $T$ than the rate attained for zero-order minimization of simply convex functions [@agarwal2011; @belloni2015escaping]. Intuitively, it seems reasonable that $\alpha$-strong convexity should be of no added value for very small $\alpha$. Theorem \[lb\] allows 