.png){kind=icon}
.png){kind=icon}
Return
Jacobi-Style Iteration for Distributed Submodular Maximization
.png){kind=icon}
OA
AI
DOI：10.1109/TAC.2022.3180696.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article presents a novel Jacobi-style iteration algorithm for solving the problem of distributed submodular maximization, in which multiple agents determine their strategies from the private sets so that a global, nonseparable submodular objective function is jointly maximized. Building on the multilinear extension of the submodular function, we expect to achieve the solution from a probabilistic, rather than deterministic, perspective, and thus, transfer the considered problem from the discrete domain into the continuous domain. Since it is observed that an unbiased estimation of the gradient of multilinear extension function can be obtained by sampling the agents' local strategies, a projected stochastic gradient algorithm is proposed to solve the problem. Our algorithm enables simultaneous updates among all individual agents and guarantees to converge asymptotically to a desirable equilibrium solution. Such an equilibrium solution is shown to be at least 1/2 suboptimal, which is comparable to the state-of-art in the literature. The convergence rate, which is characterized by the running average of gradient mapping, is proved to be O(1/T), where T is the number of iterations. Moreover, we further enhance the proposed algorithm by handling the scenario in which agents' communication delays are present. The enhanced algorithm admits a more realistic distributed implementation of our approach. Finally, a movie recommendation task is conducted on a real-world movie rating dataset to validate the numerical performance of our algorithms.
Keywords:
Distributed algorithms
nash equilibrium
stochastic gradient descent
submodular maximization
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W