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.
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.
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