Decentralized Gradient Tracking for Continuous DR-Submodular Maximization

[edit]

Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, Hui Qian ;
Proceedings of Machine Learning Research, PMLR 89:2897-2906, 2019.

Abstract

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 $\tilde{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.

Related Material