$$\label{eq:pmean}
\mathbb{E}  [f({\bar x}_{T_0,T}) - f(x^*)] \leq 
C \kappa {\bar L}^2 \frac{d}{\alpha T} \|x_1- x^*\|^2
 + C
\frac{d^2}{\alpha} \left(
(\kappa_\beta L)^2 + \kappa \big({\bar L}^2
+ \sigma^2\big)
\right) 
T^{-\frac{\beta-1}{\beta}}$$ where $C>0$ is a constant depending only on $\beta$ and $x^*=\operatorname*{arg\,min}_{x\in \mathbb{R}^d}f(x)$.

As in the proof of Theorem \[thm:1\], we apply Lemmas \[lem:1\] and \[lem:2unco\]. But we can only use Lemma \[lem:2unco\](i) and not Lemma \[lem:2unco\](ii) and thus the bound on the stochastic error now involves ${\left\lVertx_{t}-x^{*}\right\rVert}^{2}$. So, after taking expectations, we need to control an additional term containing $r_t=\mathbb{E}[{\left\lVertx_{t}-x^{*}\right\rVert}^{2}]$. However, the issue concerns only small $t$ ($t\le T_0\sim d^2/\alpha$) since for bigger $t$ this term is compensated due to the strong convexity with parameter $\alpha > \sqrt{{C_*d}/{T}}$. This motivates the method where we use the first $T_0$ iterations to get a suitably good (but not rate optimal) bound on $r_{T_0+1}$ and then proceed analogously to Theorem \[thm:1\] for iterations $t\ge T_0+1$.

Estimation of $f(x^*)$ {#sec:sec4}
======================

In this section, we apply the above results to estimation of the minimum value $f(x^*)=\min_{x\in{\Theta}}f(x)$. The literature on this problem either assumes that $x_t$’s are distributed uniformly enough and $f\in \mathcal{F}_\beta(L)$ (with no strong convexity) [@Ibra; @muller] or $f\in \mathcal{F}_{\alpha,\beta}(L)$ and $x_t$’s are chosen 