Decentralized Gradient Tracking for Continuous DR-Submodular Maximization
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.
Cite
Text
Xie et al. "Decentralized Gradient Tracking for Continuous DR-Submodular Maximization." Artificial Intelligence and Statistics, 2019.Markdown
[Xie et al. "Decentralized Gradient Tracking for Continuous DR-Submodular Maximization." Artificial Intelligence and Statistics, 2019.](https://mlanthology.org/aistats/2019/xie2019aistats-decentralized/)BibTeX
@inproceedings{xie2019aistats-decentralized,
title = {{Decentralized Gradient Tracking for Continuous DR-Submodular Maximization}},
author = {Xie, Jiahao and Zhang, Chao and Shen, Zebang and Mi, Chao and Qian, Hui},
booktitle = {Artificial Intelligence and Statistics},
year = {2019},
pages = {2897-2906},
volume = {89},
url = {https://mlanthology.org/aistats/2019/xie2019aistats-decentralized/}
}