\log \frac 1 \eta$ steps.

Under the assumptions in [@MaCJFJ18] ($\beta$-smooth $f$, $\nabla(\mathbf{0})=\mathbf{0}$, $\kappa\beta$-strong convexity outside a ball of radius $R$), a direct reduction to our setting will be lossy and a rejection-sampling-based approach will not be efficient. The Langevin dynamics based sampler in that work is more efficient under their assumptions.

\[thm:no\_fast\_opt\] For any algorithm ${\mathcal{A}}$ that queries $f$ or any of its derivatives at less than $(1/4\eps)^d$ points, there is an $f \in \mathcal{F}_{Lip}$ for which ${\mathcal{A}}$ fails to output an $\eps$-optimizer of $f$ except with negligible probability.

Consider the function $f_{\vx}$ that is zero everywhere, except for a small ball of radius $2\eps$ around $\vx$, where it is $f(\vy) = \|\vy - \vx\| - 2\eps$. i.e. the function[^1] is $f_{\vx}(\vy) = \min(0, \|\vy - \vx\| - 2\eps)$. This function has optimum $-2\eps$. Let $g$ be the zero function.

Let ${\mathcal{A}}$ be an algorithm (possibly randomized) that queries $f$ or its derivatives at $T \leq (1/4\eps)^d$ points. Consider running ${\mathcal{A}}$ on a function $f$ chosen randomly as: $$\begin{aligned}
    f &= \left\{ \begin{array}{ll}
    g & \mbox{ with probability $\frac 1 2$}\\
    f_{\vx} & \mbox{ for a $\vx$ chosen u.a.r. from $B(\mathbf{0}, 1)$ otherwise.}\\
  \end{array}\right.
    \end{aligned}$$ Until ${\mathcal{A}}$ has queried 