Projection-Free Bandit Convex Optimization

Lin Chen, Mingrui Zhang, Amin Karbasi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2047-2056, 2019.

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 this Paper

BibTeX
@InProceedings{pmlr-v89-chen19f, title = {Projection-Free Bandit Convex Optimization}, author = {Chen, Lin and Zhang, Mingrui and Karbasi, Amin}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2047--2056}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/chen19f/chen19f.pdf}, url = {https://proceedings.mlr.press/v89/chen19f.html}, 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.} }
Endnote
%0 Conference Paper %T Projection-Free Bandit Convex Optimization %A Lin Chen %A Mingrui Zhang %A Amin Karbasi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-chen19f %I PMLR %P 2047--2056 %U https://proceedings.mlr.press/v89/chen19f.html %V 89 %X 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.
APA
Chen, L., Zhang, M. & Karbasi, A.. (2019). Projection-Free Bandit Convex Optimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2047-2056 Available from https://proceedings.mlr.press/v89/chen19f.html.

Related Material