from $T/2$ to $T$ rather than from 1 to $T$, in the spirit of [@rakhlin2011making]. We refer to Appendix \[app:C\] for the details and proofs of these facts.

We now study the performance of Algorithm \[algo\] when ${\Theta}=\mathbb{R}^d$. In this case we make the following choice for the parameters $h_t$ and $\eta_t$ in Algorithm \[algo\]: $$\begin{aligned}
h_t &=T^{-\frac{1}{2\beta}},~~~\eta_t = \frac{1}{\alpha T},~~~t= 1,\dots,T_0, \\
h_t &= t^{-\frac{1}{2\beta}},~~~~~\eta_t = \frac{2}{\alpha t},~~~~t= T_0+ 1,\dots,T,
\end{aligned}
\label{eq:hhh}$$ where $T_0 = \max \left\{k \geq 0 : C_1 {\bar L}^2 d > {\alpha^2 k}/{2} \right\}$ and $C_1$ is a positive constant[^2] depending only on the kernel $K(\cdot)$ (this is defined in the proof of Theorem \[thm:2\] in Appendix \[app:B\]) and recall ${\bar L}$ is the Lipschitz constant on the gradient $\nabla f$. Finally, define the estimator $$\label{eq:ppmean}
{\bar x}_{T_0,T} = \frac{1}{T-T_0} \sum_{t=T_0+1}^T x_t.$$

[theorem]{}[fiftheorem]{}[*(Upper Bounds, Unconstrained Case.)*]{} \[thm:2\] Let $f\in {\cal F} _{\alpha,\beta}(L)$ with $\alpha, L>0$ and $\beta \geq 2$. Let Assumptions \[ass1\] and \[ass:lip\] hold. Assume also that $\alpha > \sqrt{{C_*d}/{T}}$, where $C_* > 72 \kappa {\bar L}^2$. Let $x_t$’s be the updates of Algorithm \[algo\] with ${\Theta}=\mathbb{R}^d$, $h_t$ and $\eta_t$ as in and a non-random $x_1 \in \mathbb{R}^d$. Then the estimator defined by satisfies 