is more general than (iii) by allowing for adversarial noise (no independence or zero-mean assumption in contrast to (iii), no Lipschitz assumption in contrast to settings (i) and (ii)), which are both covered by our results when the noise is set to zero. One part of our results are bounds on the cumulative regret, cf. and . We emphasize that they remain trivially valid if the queries are from $f_t$ depending on $t$ instead of $f$, and thus cover the setting (i). To the best of our knowledge, there were no such results in this setting previously, except for [@BP2016] that gives bounds with suboptimal dependency on $T$ in the case of classical (non-adversarial) noise. In the non-noisy case, we get bounds on the cumulative regret with faster rates than previously known for the setting (i). It remains an open question whether these bounds can be improved.

The second part of our results dealing with the optimization error $\mathbb{E}[f(\bar x_T)-f(x^*)]$ is closely related to the work on derivative-free stochastic optimization under strong convexity and smoothness assumptions initiated in [@Fabian; @PT90] and more recently developed in [@BP2016; @dippon; @jamieson2012; @Shamir13]. It was shown in [@PT90] that the minimax optimal rate for 