more queries were studied in several papers including [@agarwal2010; @BP2016; @flaxman2004; @Shamir17]. Using two queries per step leads to better performance bounds as emphasized in [@agarwal2010; @BP2016; @duchi2015; @flaxman2004; @PT90; @Shamir17]. Randomizing sequences other than uniform on the sphere were also explored: $\zeta_t$ uniformly distributed on a cube [@PT90], Gaussian $\zeta_t$ [@Nesterov2011; @NS17], $\zeta_t$ uniformly distributed on the vertices of a cube [@Shamir13] or satisfying some general assumptions [@dippon; @duchi2015]. Except for [@BP2016; @dippon; @PT90], these works study settings with low smoothness of $f$ (2-smooth or less) and do not invoke kernels $K$ (i.e. $K(\cdot)\equiv 1$ and $r_t\equiv 1$ in Algorithm \[algo\]). The use of randomization with smoothing kernels was proposed by Polyak and Tsybakov [@PT90] and further developed by Dippon [@dippon], and Perchet [@BP2016] to whom the current form of Algorithm \[algo\] is due.

  Kernel $K :[-1,1]\rightarrow \mathbb{R}$, step size $\eta_t>0$ and parameter $h_t$, for $t=1,\dots,T$   Generate scalars $r_1,\dots,r_T$ uniformly on the interval $[-1,1]$, vectors $\zeta_1,\dots,\zeta_T$ uniformly distributed on the unit sphere $S_d=\{\zeta\in \mathbb{R}^d:  {\left\lVert\zeta\right\rVert}=1\}$, and choose $x_1\in {\Theta}$ $t=1,\dots, T$    Let $y_t = f(x_t+h_tr_r\zeta_t)+ \xi_t$ and $y_t' = f(x_t-h_tr_t\zeta_t)+ \xi_t',$ 2.    Define $\hat g_t = \frac{d}{2h_t} (y_t- y'_t) \zeta_t K(r_t)$ 3.    Update $x_{t+1}= {\ensuremath{\text{\rm Proj}}}_{{\Theta}}(x_{t}- \eta_t \hat g_t)$   