Timezone: »

 
Poster
Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
Mingrui Zhang · Lin Chen · Hamed Hassani · Amin Karbasi

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #168
in Optimization -- Submodular Optimization »
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.
Keywords: Online Learning · Submodular Optimization · Optimization · Algorithms -> Bandit Algorithms; Algorithms
[ Paper]  [ Poster] 

Author Information

Mingrui Zhang (Yale University)
Lin Chen (Yale University)
Hamed Hassani (UPenn)
Amin Karbasi (Yale)

More from the Same Authors