Decentralized Gradient Tracking for Continuous DR-Submodular Maximization

摘要

In this paper, we focus on the continuous DR-submodular maximization over a network. By using the gradient tracking technique, two decentralized algorithms are proposed for deterministic and stochastic settings, respectively. The proposed methods attain the $epsilon$-accuracy tight approximation ratio for monotone continuous DR-submodular functions in only $O(1/epsilon)$ and $ilde{O}(1/epsilon)$ rounds of communication, respectively, which are superior to the state-of-the-art. Our numerical results show that the proposed methods outperform existing decentralized methods in terms of both computation and communication complexity.