NeurIPS 2019poster65 citations
Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
Mingrui Zhang, Lin Chen, Hamed Hassani, Amin Karbasi
Abstract
In this paper, we propose three online algorithms for submodular maximization. The first one, Mono-Frank-Wolfe, reduces the number of per-function gradient evaluations from $T^{1/2}$ [Chen2018Online] and $T^{3/2}$ [chen2018projection] to 1, and achieves a $(1-1/e)$-regret bound of $O(T^{4/5})$. The second one, Bandit-Frank-Wolfe, is the first bandit algorithm for continuous DR-submodular maximization, which achieves a $(1-1/e)$-regret bound of $O(T^{8/9})$. Finally, we extend Bandit-Frank-Wolfe to a bandit algorithm for discrete submodular maximization, Responsive-Frank-Wolfe, which attains a $(1-1/e)$-regret bound of $O(T^{8/9})$ in the responsive bandit setting.
BibTeX
@inproceedings{NEURIPS2019_b43a6403,
author = {Zhang, Mingrui and Chen, Lin and Hassani, Hamed and Karbasi, Amin},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/b43a6403c17870707ca3c44984a2da22-Paper.pdf},
volume = {32},
year = {2019}
}