Decentralized Gradient Tracking for Continuous DR-Submodular Maximization

Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, Hui QianAISTATS 2019 · OpenReview

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: DeGTFW and DeSGTFW. Our theoretical analysis shows that DeGTFW and DeSGTFW achieve the optimal $O(1/\epsilon)$ and $\tilde{O}(1/\epsilon)$ communication complexity, respectively. Experimental results on both synthetic and real-world datasets demonstrate the superiority of our proposed algorithms.

Introduction

Many large-scale optimization problems, such as sensor placement, movie recommendations, and budget allocation, involve maximizing functions with "diminishing returns," known as submodularity. In decentralized settings, data is distributed across multiple nodes, and centralizing it is often impractical due to privacy or bandwidth constraints. Previous decentralized methods for continuous DR-submodular maximization suffered from inaccurate global gradient surrogates, leading to slow convergence ($O(1/\epsilon^2)$) and high communication costs.

Methodology

We address these challenges by integrating Gradient Tracking into the Frank-Wolfe (Conditional Gradient) framework.

DeGTFW: Deterministic Gradient Tracking

For scenarios where full local gradients are available, DeGTFW maintains a local gradient surrogate that tracks the average of all local gradients across the network. By utilizing a tracking update rule, nodes can follow the global objective's gradient more accurately than simple neighbor averaging.

DeSGTFW: Stochastic Gradient Tracking

For large-scale datasets where full gradients are computationally prohibitive, DeSGTFW employs unbiased stochastic gradient estimators. To ensure convergence to the optimal approximation ratio, the algorithm uses an increasing mini-batch size strategy, where the number of samples grows quadratically with iterations ($t^2$).

The core of both algorithms is a weight matrix $W$ that facilitates information diffusion across the network, ensuring that local updates eventually reflect global objective properties.

Experimental Evaluation

We evaluated our algorithms on two benchmarks: a synthetic Non-convex Quadratic Programming (NQP) problem and a real-world movie recommendation task using the MovieLens1M dataset.

Performance comparison of DeGTFW/DeSGTFW against DeCG/DeSCG benchmarks across various metrics including communication rounds and computation effort.

Key Results

  • Communication Efficiency: DeGTFW achieves $\epsilon$-accuracy in $O(1/\epsilon)$ communication rounds, matching centralized benchmarks and improving upon the $O(1/\epsilon^2)$ complexity of prior decentralized methods.
  • Stochastic Performance: DeSGTFW reduces communication complexity from $O(1/\epsilon^3)$ to $\tilde{O}(1/\epsilon)$.
  • Empirical Gains: In our experiments, the proposed methods reached higher objective values significantly faster than DeCG and DeSCG. As shown in the figures, the gradient tracking mechanism allows for much smoother and faster convergence towards the $(1 - 1/e)$ approximation bound.
Comparison of objective value vs. computation effort for deterministic algorithms on a different problem scale, highlighting the robustness of the gradient tracking approach.

Conclusion

By introducing gradient tracking to decentralized submodular maximization, we have bridged the gap between centralized and decentralized communication complexities. DeGTFW and DeSGTFW provide a robust and efficient framework for large-scale non-convex optimization in networked environments. Future work will focus on optimizing mini-batch scaling and exploring projection-free variants for more complex constraint sets.

Summary updated

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 stocha...
BibTeX
@inproceedings{xie2019decentralized,
  author = {Jiahao Xie and Chao Zhang and Zebang Shen and Chao Mi and Hui Qian},
  title = {{Decentralized Gradient Tracking for Continuous DR-Submodular Maximization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=Ou5sCrFFadX},
}
Figure