Online Non-monotone DR-Submodular Maximization: 1/4 Approximation Ratio and Sublinear Regret

In an era of data explosion and uncertain information, online optimization becomes a more and more powerful framework. And online DR-submodular maximization is an important subclass because its wide aplications in machine learning, statistics, etc., and significance for exploring general non-convex problems. In this paper, we focus on the online non-monotone DR-submodular maximizaition under general constraint set, and propose a meta-Frank-Wolfe online algorithm with appropriately choosing parameters. Based on the Lyapunov function approach in [8] and variance reduction technique in [16], we show that the proposed online algorithm attains sublinear regret against a 1/4 approximation ratio to the best fixed action in hindsight.