Projection-Free Bandit Convex Optimization
This work addresses a computational bottleneck in optimization for machine learning and decision-making, offering a more efficient method for scenarios where projections are costly.
The paper tackles the problem of bandit convex optimization by proposing the first computationally efficient projection-free algorithm, achieving a sublinear regret of O(nT^{4/5}) for bounded convex functions with uniformly bounded gradients.
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(nT^{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.