Improved Projection-free Online Continuous Submodular Maximization
Yucheng Liao Yuanyu Wan Chang Yao Mingli Song
We investigate the problem of online learning with monotone and continuous
DR-submodular reward functions, which has received great attention recently. To
efficiently handle this problem, especially in the case with complicated
decision sets, previous studies have proposed an efficient projection-free
algorithm called Mono-Frank-Wolfe (Mono-FW) using $O(T)$ gradient evaluations
and linear optimization steps in total. However, it only attains a
$(1-1/e)$-regret bound of $O(T^{4/5})$. In this paper, we propose an improved
projection-free algorithm, namely POBGA, which reduces the regret bound to
$O(T^{3/4})$ while keeping the same computational complexity as Mono-FW.
Instead of modifying Mono-FW, our key idea is to make a novel combination of a
projection-based algorithm called online boosting gradient ascent, an
infeasible projection technique, and a blocking technique. Furthermore, we
consider the decentralized setting and develop a variant of POBGA, which not
only reduces the current best regret bound of efficient projection-free
algorithms for this setting from $O(T^{4/5})$ to $O(T^{3/4})$, but also reduces
the total communication complexity from $O(T)$ to $O(\sqrt{T})$.