Improved Projection-free Online Continuous Submodular Maximization
This work addresses an incremental improvement in optimization algorithms for online submodular maximization, relevant to researchers in machine learning and optimization.
The paper tackles the problem of online learning with monotone continuous DR-submodular reward functions by proposing an improved projection-free algorithm, POBGA, which reduces the regret bound from O(T^{4/5}) to O(T^{3/4}) while maintaining computational efficiency, and extends it to a decentralized setting with reduced communication complexity from O(T) to O(√T).
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})$.