$\mathbb{R}^d$. Our approach, outlined in Algorithm \[algo\], builds upon previous work in which a sequential algorithm queries at each iteration a pair of function values, under a general noise model. Specifically, at iteration $t$ the current guess $x_t$ for the minimizer of $f$ is used to build two perturbations $x_t+\delta_t$ and $x_t-\delta_t$, where the function values are queried subject to additive measurement errors $\xi_t$ and $\xi_t'$, respectively. The values $\delta_t$ can be chosen in different ways. In this paper, we set $ \delta_t=h_tr_r\zeta_t$ (Line 1), where $h_t>0$ is a suitably chosen small parameter, $r_t$ is random and uniformly distributed on $[-1,1]$, and $\zeta_t$ is uniformly distributed on the unit sphere. The estimate for the gradient is then computed at Line 2 and used inside a projected gradient method scheme to compute the next exploration point. We introduce a suitably chosen kernel $K$ that allows us to take advantage of higher order smoothness of $f$.

The idea of using randomized procedures for derivative-free stochastic optimization can be traced back to Nemirovski and Yudin [@NY1983 Sec. 9.3] who suggested an algorithm with one query per step at point $x_t+h_t\zeta_t$, with $\zeta_t$ uniform on the unit sphere. Its versions with one, two or 