L  d h_t^{\beta-1}.
\label{eq:}$$

The next lemma provides a bound on the stochastic variability of the estimated gradient by controlling its second moment.

[lemma]{}[sndlemma]{} \[lem:2unco\] Let Assumption \[ass1\](i) hold, let ${\hat g}_t$ and $x_t$ be defined by Algorithm \[algo\] and set $\kappa = \int K^2(u) du$. Then

-   If ${\Theta}\subseteq \mathbb{R}^d$, $\nabla f(x^*)=0$ and Assumption \[ass:lip\] holds, $$\mathbb{E} [\|{\hat g}_t \|^2 \hspace{.04truecm}|\hspace{.04truecm} x_t] \leq 
    9\kappa{\bar L}^2  \left(d\|x_t-x^*\|^2 + \frac{d^2h_t^2}{8} \right) + \frac{3\kappa d^2 \sigma^2}{2h_t^2},$$

-   If $f\in \mathcal{F}_2(L)$ and ${\Theta}$ is a closed convex subset of $\mathbb{R}^d$ such that $\displaystyle{\max_{x \in {\Theta}}} \| \nabla f(x)\|\le G$, then $$\mathbb{E} [\|{\hat g}_t \|^2 \hspace{.04truecm}|\hspace{.04truecm} x_t] \leq 
    9\kappa  \left(G^2 d + \frac{{L}^2d^2h_t^2}{2} \right) + \frac{3\kappa d^2 \sigma^2}{2h_t^2}.$$

Upper bounds {#sec:UB}
============

In this section, we provide upper bounds on the cumulative regret and on the optimization error of Algorithm \[algo\]. First we consider Algorithm \[algo\] when the convex set ${\Theta}$ is bounded (constrained case).

[theorem]{}[thdtheorem]{}[*(Upper Bound, Constrained Case.)*]{} \[thm:1\] Let $f \in {\cal F}_{\alpha, \beta}(L)$ with $\alpha,L>0$ and $\beta \geq 2$. Let Assumptions \[ass1\] and \[ass:lip\] hold and let ${\Theta}$ be a convex compact subset of $\mathbb{R}^d$. Assume that $\max_{x\in{\Theta}}\|\nabla f(x)\|\le G $. If $\sigma>0$ then the cumulative regret of Algorithm \[algo\] with 