gradient as $$\label{gt}
   \hat g_t = \frac{d}{2h_t} (y_t- y'_t) \zeta_t,$$ where $y_t=f(x+h_t \tilde \zeta)$ and $y'_t=f(x-h_t \tilde \zeta)$. A well-known observation that goes back to [@NY1983] consists in the fact that $\hat g_t$ defined in is an unbiased estimator of the gradient of the surrogate function $\hat f_t$ defined by $$\hat f_t(x)= \mathbb{E} f(x+h_t \tilde \zeta),\quad \forall x\in\mathbb{R}^d,$$ where the expectation $\mathbb{E}$ is taken with respect to the random vector $\tilde \zeta$ uniformly distributed on the unit ball $B_d=\{u\in \mathbb{R}^d:\|u\|\le 1 \}$. The properties of the surrogate $\hat f_t$ are described in Lemmas \[lem6.2\] and \[lem6.4\] presented in the appendix.

The improvement in the rate that we get for $\beta=2$ is due to the fact that we can consider Algorithm \[algo\] with $\hat g_t$ defined in as the SGD for the surrogate function. Then the bias of approximating $f$ by $\hat f_t$ scales as $h_t^2$, which is smaller than the squared bias of approximating the gradient arising in the proof of Theorem \[thm:1\] that scales as $d^2h_t^{2(\beta-1)}=d^2h_t^2$ when $\beta=2$. On the other hand, the stochastic variability terms are the same for both methods of proof. This explains the gain in dependency on $d$. However, this technique does not work for 