---
title: "Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization"
authors:
  - "Hongchang Gao"
  - "Hanzi Xu"
  - "Slobodan Vucetic"
doi: "10.24963/ijcai.2021/482"
url: "https://ijcai.org/proceedings/2021/482"
pdf: "https://ijcai.org/proceedings/2021/0482.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "3501-3507"
track: "Main Track"
keywords:
  - "Machine Learning Applications: Big data; Scalability"
---

# Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization

Hongchang Gao, Hanzi Xu, Slobodan Vucetic

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 3501-3507. DOI: [10.24963/ijcai.2021/482](https://doi.org/10.24963/ijcai.2021/482)

## Abstract

Continuous DR-submodular maximization is an important machine learning problem, which covers numerous popular applications.  With the emergence of large-scale distributed data, developing efficient algorithms for the continuous DR-submodular maximization, such as the decentralized Frank-Wolfe method, became an important challenge. However, existing decentralized Frank-Wolfe methods for this kind of problem have the sample complexity of $\mathcal{O}(1/\epsilon^3)$, incurring a large computational overhead. In this paper, we propose two novel sample efficient decentralized Frank-Wolfe methods to address this challenge. Our theoretical results demonstrate that the sample complexity of the two proposed methods is $\mathcal{O}(1/\epsilon^2)$, which is better than $\mathcal{O}(1/\epsilon^3)$ of the existing methods. As far as we know, this is the first published result achieving such a favorable sample complexity. Extensive experimental results confirm the effectiveness of the proposed methods.