us to quantify exactly how small such $\alpha$ should be. Also, quite naturally, the threshold becomes smaller when the smoothness $\beta$ increases.\
Finally note that for $\beta=2$ the lower bounds and are, in the interesting regime of large enough $T$, of order $d/(\max(\alpha, 1)\sqrt{T})$ and $d/(\max(\alpha^2, 1)\sqrt{T})$, respectively. This highlights the near minimax optimal properties of Algorithm \[algo\] in the setting of Theorem \[th6.3\].

Discussion and related work {#sec:PW}
===========================

There is a great deal of attention to zero-order feedback stochastic optimization and convex bandits problems in the recent literature. Several settings are studied: (i) deterministic in the sense that the queries contain no random noise and we query functions $f_t$ depending on $t$ rather than $f$ where $f_t$ are Lipschitz or 2-smooth [@agarwal2010; @flaxman2004; @Nesterov2011; @NS17; @saha2011; @Shamir17]; (ii) stochastic with two-point feedback where the two noisy evaluations are obtained with the same noise and the noisy functions are Lipschitz or 2-smooth [@duchi2015; @Nesterov2011; @NS17] (this setting does not differ much from (i) in terms of the analysis and the results); (iii) stochastic, where the noises $\xi_i$ are independent zero-mean random variables [@agarwal2011; @BP2016; @bartlett2018simple; @dippon; @Fabian; @jamieson2012; @Locatelli; @PT90; @Shamir13]. In this paper, we considered a setting, which 