Projection-Free Bandit Convex Optimization
Abstract
In this paper, we propose the first computationally efficient projection-free algorithm for bandit convex optimization (BCO) with a general convex constraint. 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.
Cite
Text
Chen et al. "Projection-Free Bandit Convex Optimization." Artificial Intelligence and Statistics, 2019.Markdown
[Chen et al. "Projection-Free Bandit Convex Optimization." Artificial Intelligence and Statistics, 2019.](https://mlanthology.org/aistats/2019/chen2019aistats-projectionfree/)BibTeX
@inproceedings{chen2019aistats-projectionfree,
title = {{Projection-Free Bandit Convex Optimization}},
author = {Chen, Lin and Zhang, Mingrui and Karbasi, Amin},
booktitle = {Artificial Intelligence and Statistics},
year = {2019},
pages = {2047-2056},
volume = {89},
url = {https://mlanthology.org/aistats/2019/chen2019aistats-projectionfree/}
}