minimax lower bound of the order $\frac{d}{\alpha}T^{-\frac{\beta-1}{\beta}}$ for the optimization risk when $\alpha$ is not very small. This shows that to within the factor of $d$ the bound for Algorithm \[algo\] cannot be improved for all $\beta\ge 2$;

3.  We show that, when $\alpha$ is too small, below some specified threshold, higher order smoothness does not help to improve the convergence rate. We prove that in this regime the rate cannot be faster than $d/\sqrt{T}$, which is not better (to within the dependency on $d$) than for derivative-free minimization of simply convex functions [@agarwal2011; @liang2014zeroth];

4.  For $\beta=2$, we obtain a bracketing of the optimal rate between $O(d/\sqrt{\alpha T})$ and\
    $\Omega(d/(\max(1,\alpha)\sqrt{T}))$. In a special case when $\alpha$ is a fixed numerical constant, this validates a conjecture in [@Shamir13] (claimed there as proved fact) that the optimal rate for $\beta=2$ scales as $d/\sqrt{T}$;

5.  We propose a simple algorithm of estimation of the value $\min_x f(x)$ requiring three queries per step and attaining the optimal rate $1/\sqrt{T}$ for all $\beta\ge 2$. The best previous work on this problem [@belitser] suggested a method with exponential complexity and proved a bound of the order $c(d,\alpha)/\sqrt{T}$ for $\beta> 2$ where $c(d,\alpha)$ is an unspecified 