2019/05/31 by Andrea Testa, Testa, Andrea, Francesco Farina +3
Computer Science · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1905.13682
openalex publication_date 2019/05/31 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
In this paper we deal with a network of computing agents with local\nprocessing and neighboring communication capabilities that aim at solving\n(without any central unit) a submodular optimization problem. The cost function\nis the sum of many local submodular functions and each agent in the network has\naccess to one function in the sum only. In this \distributed set-up, in\norder to preserve their own privacy, agents communicate with neighbors but do\nnot share their local cost functions. We propose a distributed algorithm in\nwhich agents resort to the Lov `asz extension of their local submodular\nfunctions and perform local updates and communications in terms of single\nblocks of the entire optimization variable. Updates are performed by means of a\ngreedy algorithm which is run only until the selected block is computed, thus\nresulting in a reduced computational burden. The proposed algorithm is shown to\nconverge in expected value to the optimal cost of the problem, and an\napproximate solution to the submodular problem is retrieved by a thresholding\noperation. As an application, we consider a distributed image segmentation\nproblem in which each agent has access only to a portion of the entire image.\nWhile agents cannot segment the entire image on their own, they correctly\ncomplete the task by cooperating through the proposed distributed algorithm.\n