Improved Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandit

We consider β-smooth (satisfies the generalized Holder condition with parameter β > 2) stochastic convex optimization problem with zero-order one-point oracle. The best known result was arXiv:2006.07862: mathbbE left[f(overlinexN) - f(x^*)right] = tildeO left(dfracn2γ N^fracβ-1β right) in γ-strongly convex case, where n is the dimension. In this paper we improve this bound: mathbbE left[f(overlinexN) - f(x^*)right] = tildeO left(dfracn^2-frac1βγ N^fracβ-1β right).