Improved Projection-free Online Continuous Submodular Maximization

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(T4/5). In this paper, we propose an improved projection-free algorithm, namely POBGA, which reduces the regret bound to O(T3/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(T4/5) to O(T3/4), but also reduces the total communication complexity from O(T) to O(√T).