Projection-Free Bandit Convex Optimization

Abstract

In this paper, we propose the first computationally efficient projection-free algorithm for bandit convex optimization (BCO). We show that our algorithm achieves a sublinear regret of $O(n{T}^{4/5})$ (where $T$ is the horizon and $n$ is the dimension) for any bounded convex functions with uniformly bounded gradients. We also evaluate the performance of our algorithm against baselines on both synthetic and real data sets for quadratic programming, portfolio selection and matrix completion problems.

Cited by in corpus (6)

• Revisiting Projection-free Online Learning: the Strongly Convex Case
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds
• Online Boosting with Bandit Feedback
• Scalable Projection-Free Optimization