Jacobi-Style Iteration for Distributed Submodular Maximization
Jacobi-Style Iteration for Distributed Submodular Maximization
复制标题
DOI：
10.1109/tac.2022.3180696
复制
发表时间：
2020-10
影响因子：
6.8
通讯作者：
Bin Du;Kun Qian;C. Claudel;Dengfeng Sun
中科院分区：
文献类型：
--
作者：
Bin Du;Kun Qian;C. Claudel;Dengfeng Sun
本文提出了一种新颖的雅可比式迭代算法，用于解决分布式子模最大化问题，其中多个代理从私有集合中确定其策略，以便共同最大化全局、不可分离的子模目标函数。基于子模函数的多线性扩展，我们期望从概率而非确定性的角度实现解决方案，从而将所考虑的问题从离散域转移到连续域。由于观察到可以通过对智能体的局部策略进行采样来获得多线性扩展函数梯度的无偏估计，因此提出了投影随机梯度算法来解决该问题。我们的算法可以实现所有个体代理之间的同步更新，并保证渐近收敛到理想的平衡解。这样的平衡解决方案被证明至少是次优的 $1/2$，这与文献中的最新技术相当。收敛速度用梯度映射的运行平均值来表征，被证明为$\mathcal {O}(1/T)$，其中$T$是迭代次数。此外，我们通过处理代理通信延迟存在的场景进一步增强了所提出的算法。增强的算法允许我们的方法更现实的分布式实现。最后，在现实世界的电影评级数据集上进行电影推荐任务，以验证我们算法的数值性能。
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 $\mathcal {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.