Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation

We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most O(d^{2.5} \sqrt{n} \mathrm {log}(n)) , where d is the dimension and n is the number of interactions. This improves on the bound of O(d^{9.5} \sqrt{n} \mathrm {log}(n)^{7.5}) by Bubeck et al. (2017). The proof is based on identifying an improved exploratory distribution for convex functions.