We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most d3.5 √n polylog(n, d) with high probability where d is the dimension and n is the time horizon. In the stochastic setting the bound improves to M d² √n polylog(n, d) where M ∈ [d-1/2, d-1 / 4] is a constant that depends on the geometry of the constraint set and the desired computational properties.
No takes yet. Share an insight, caveat, or question.
Fokkema et al. (2024) studied this question.