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

Hongchang Gao, Hanzi Xu, Slobodan VuceticIJCAI 2021 · DOI

Introduction

Decentralized optimization is increasingly critical as machine learning datasets are often distributed across multiple devices or workers. This paper addresses the challenge of maximizing continuous DR-submodular functions in a decentralized setting. These functions, characterized by the "diminishing returns" property, are foundational to tasks like resource allocation and recommendation systems. Previous decentralized stochastic Frank-Wolfe (DSFW) methods suffered from high sample complexity, requiring $O(1/\epsilon^3)$ samples to reach an accuracy $\epsilon$, making them computationally expensive for individual workers.

Proposed Methods: DeSVRFW-gp and DeSVRFW-gt

The authors introduce two novel algorithms that integrate variance reduction into the decentralized Frank-Wolfe framework to improve sample efficiency.

  1. DeSVRFW-gp (Gossip-based): This method utilizes a standard gossip protocol for parameter averaging among neighbors. While it reduces sample complexity, it converges to a neighborhood of the optimum due to persistent consensus error.
  2. DeSVRFW-gt (Gradient-tracking-based): By employing a gradient tracking mechanism, this algorithm estimates the global average gradient across the network. This allows it to overcome consensus errors and achieve asymptotic convergence to the true approximate optimum.

Theoretical Results

The primary theoretical contribution is the reduction of sample complexity from $O(1/\epsilon^3)$ to $O(1/\epsilon^2)$, matching the efficiency of centralized state-of-the-art algorithms while maintaining a low communication overhead of $O(1/\epsilon)$.

Comparison of sample and communication complexities for various decentralized methods.

Empirical Evaluation

The proposed methods were evaluated on movie recommendation tasks using the MovieLens-100K and MovieLens-1M datasets. The data was partitioned across a decentralized network of 4 to 8 workers.

Objective value vs. number of function evaluations on the MovieLens-1M dataset, demonstrating faster convergence for the proposed methods.

Experimental results demonstrate that both DeSVRFW-gp and DeSVRFW-gt significantly outperform existing baselines like DeSCG and DeSGTFW. They achieve higher objective values with fewer function evaluations, confirming the practical benefits of the improved sample complexity.

Conclusion and Future Work

This work sets a new benchmark for decentralized DR-submodular maximization by achieving $O(1/\epsilon^2)$ sample complexity. Future research may extend these techniques to non-monotone functions, explore the impact of different network topologies, or adapt the algorithms for asynchronous communication environments.

Summary updated

BibTeX
@inproceedings{gao2021sample,
  author = {Hongchang Gao and Hanzi Xu and Slobodan Vucetic},
  title = {{Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/482},
}
Figure