$(x_t)_{t=1}^T$

In this paper we consider higher order smooth functions $f$ satisfying the generalized Hölder condition with parameter $\beta \geq 2$, cf. inequality  below. For integer $\beta$, this parameter can be roughly interpreted as the number of bounded derivatives. Furthermore, we assume that $f$ is $\alpha$-strongly convex. For such functions, we address the following two main questions:

-   What is the performance of Algorithm \[algo\] in terms of the cumulative regret and optimization error, namely what is the explicit dependency of the rate on the main parameters $d,T,\alpha,\beta$?

-   What are the fundamental limits of any sequential search procedure expressed in terms of minimax optimization error?

To handle task (a), we prove upper bounds for Algorithm \[algo\], and to handle (b), we prove minimax lower bounds for any sequential search method.

[**Contributions.**]{} Our main contributions can be summarized as follows:

1.  Under an adversarial noise assumption (cf. Assumption \[ass1\] below), we establish for all $\beta\ge 2$ upper bounds of the order $\frac{d^2}{\alpha}T^{-\frac{\beta-1}{\beta}}$ for the optimization risk and $\frac{d^2}{\alpha}T^{\frac{1}{\beta}}$ for the cumulative regret of Algorithm \[algo\], both for its constrained and unconstrained versions;

2.  In the case of independent noise satisfying some natural assumptions (including the Gaussian noise), we prove a 