and $\xi_t'$ are independent from $\zeta_t$ and from $r_t$, and the random variables $\zeta_t$ and $r_t$ are independent; $ \mathbb{E} [\xi_t^2]\le \sigma^2,$ and $\mathbb{E} [(\xi_t')^2]\le \sigma^2$, where $\sigma\ge 0$.

Note that we do not assume $\xi_t$ and $\xi_t'$ to have zero mean. Moreover, they can be non-random and no independence between noises on different steps is required, so that the setting can be considered as adversarial. Having such a relaxed set of assumptions is possible because of randomization that, for example, allows the proofs go through without assuming the zero mean noise.

We will also use the following assumption.

\[ass:lip\] Function $f:\mathbb{R}^d\to \mathbb{R}$ is 2-smooth, that is, differentiable on $\mathbb{R}^d$ and such that $\|\nabla f(x)-\nabla f(x')\|\leq {\bar L} \|x-x'\|$ for all $x,x' \in \mathbb{R}^d$, where $\bar L>0$.

It is easy to see that this assumption implies that $f\in {\cal F}_2(\bar L/2)$. The following lemma gives a bound on the bias of the gradient estimator.

[lemma]{}[firstlemma]{} \[lem:1\] Let $f \in {\cal F}_\beta(L)$, with $\beta \geq 1$ and let Assumption \[ass1\] (i) hold. Let ${\hat g}_t$ and $x_t$ be defined by Algorithm \[algo\] and let $\kappa_\beta = \int |u|^{\beta} |K(u)| du.$ Then $$\|\mathbb{E} [{\hat g}_t \hspace{.03truecm}|\hspace{.03truecm} x_t] - \nabla f(x_t)\| \leq  \kappa_\beta 