constant.

[**Notation.**]{} Throughout the paper we use the following notation. We let $\langle \cdot, \cdot \rangle$ and $\|\cdot\|$ be the standard inner product and Euclidean norm on $\mathbb{R}^d$, respectively. For every close convex set ${\Theta}\subset \mathbb{R}^d$ and $x\in \mathbb{R}^d$ we denote by ${\ensuremath{\text{\rm Proj}}}_{\Theta}(x) = {\rm argmin} \{ \|z-x\| : z \in {\Theta}\}$ the Euclidean projection of $x$ to ${\Theta}$. We assume everywhere that $T\ge 2$. We denote by ${\cal F_\beta}(L)$ the class of functions with Hölder smoothness $\beta$ (inequality  below). Recall that $f$ is $\alpha$-strongly convex for some $\alpha>0$ if, for any $x,y \in \mathbb{R}^d$ it holds that $f(y) \geq f(x) + \langle \nabla f(x),y-x\rangle + \frac{\alpha}{2} \|x-y\|^2$. We further denote by ${\cal F_{\alpha,\beta}}(L)$ the class of all $\alpha$-strongly convex functions belonging to ${\cal F_\beta}(L)$.

[**Organization.**]{} We start in Section \[sec:BM\] with some preliminary results on the gradient estimator. Section \[sec:UB\] presents our upper bounds for Algorithm \[algo\], both in the constrained and unconstrained case. In Section \[sec:sec4\] we observe that a slight modification of Algorithm 1 can be used to estimated the minimum value (rather than the minimizer) of $f$. Section \[sec:sec4\] presents improved upper bounds in the case $\beta=2$. In Section \[sec:LB\] we establish minimax lower bounds. 