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

Abstract

We consider $\beta$-smooth (satisfies the generalized Holder condition with parameter $\beta >2$) stochastic convex optimization problem with zero-order one-point oracle. The best known result was arXiv:2006.07862: $\mathbb{E}\left[f({\overline{x}}_N)-f(x^{\ast })\right]=\tilde{\mathcal{O}}\left(\frac{n^2}{\gamma N^{\frac{\beta -1}{\beta }}}\right)$ in $\gamma$-strongly convex case, where $n$ is the dimension. In this paper we improve this bound: $\mathbb{E}\left[f({\overline{x}}_N)-f(x^{\ast })\right]=\tilde{\mathcal{O}}\left(\frac{n^{2-\frac{1}{\beta }}}{\gamma N^{\frac{\beta -1}{\beta }}}\right).$