Projection-Free Bandit Convex Optimization over Strongly Convex Sets

Projection-free algorithms for bandit convex optimization have received increasing attention, due to the ability to deal with the bandit feedback and complicated constraints simultaneously. The state-of-the-art ones can achieve an expected regret bound of \(O(T^{3/4})\) . However, they need to utilize a blocking technique, which is unsatisfying in practice due to the delayed reaction to the change of functions, and results in a logarithmically worse high-probability regret bound of \(O(T^{3/4}\sqrt{\log T})\) . In this paper, we study the special case of bandit convex optimization over strongly convex sets, and present a projection-free algorithm, which keeps the \(O(T^{3/4})\) expected regret bound without employing the blocking technique. More importantly, we prove that it can enjoy an \(O(T^{3/4})\) high-probability regret bound, which removes the logarithmical factor in the previous high-probability regret bound. Furthermore, empirical results on synthetic and real-world datasets have demonstrated the better performance of our algorithm.