Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
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.
Cite
Text
Zhang et al. "Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback." Neural Information Processing Systems, 2019.Markdown
[Zhang et al. "Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/zhang2019neurips-online/)BibTeX
@inproceedings{zhang2019neurips-online,
title = {{Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback}},
author = {Zhang, Mingrui and Chen, Lin and Hassani, Hamed and Karbasi, Amin},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {9210-9221},
url = {https://mlanthology.org/neurips/2019/zhang2019neurips-online/}
}