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).$

References in corpus (6)

• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Stochastic gradient methods with inexact oracle
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• Gradient and gradient-free methods for stochastic convex optimization with inexact oracle

Cited by in corpus (2)

• Distributed Zero-Order Optimization under Adversarial Noise
• Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation