Loading [MathJax]/jax/output/CommonHTML/jax.js
Skip to yearly menu bar Skip to main content


Poster

Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback

Mingrui Zhang · Lin Chen · Hamed Hassani · Amin Karbasi

East Exhibition Hall B, C #168

Keywords: [ Submodular Optimization ] [ Optimization ] [ Online Learning ] [ Algorithms -> Bandit Algorithms; Algorithms ]


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 T1/2 [Chen2018Online] and T3/2 [chen2018projection] to 1, and achieves a (11/e)-regret bound of O(T4/5). The second one, Bandit-Frank-Wolfe, is the first bandit algorithm for continuous DR-submodular maximization, which achieves a (11/e)-regret bound of O(T8/9). Finally, we extend Bandit-Frank-Wolfe to a bandit algorithm for discrete submodular maximization, Responsive-Frank-Wolfe, which attains a (11/e)-regret bound of O(T8/9) in the responsive bandit setting.

Live content is unavailable. Log in and register to view live content