Advertisement
Published in:
2016 | OriginalPaper | Chapter
Robust Multi-agent Optimization: Coping with Byzantine Agents with Input Redundancy
Authors : Lili Su, Nitin H. Vaidya
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This paper addresses the multi-agent optimization problem in which the agents try to collaboratively minimize \(\frac{1}{k}\sum _{i=1}^k h_i\) for a given choice of k input functions \(h_1, \ldots , h_k\). This problem finds its application in distributed machine learning, where the data set is too large to be processed and stored by a single machine. It has been shown that when the networked agents may suffer Byzantine faults, it is impossible to minimize \(\frac{1}{k}\sum _{i=1}^k h_i\) with no redundancy in the local cost functions.
We are interested in the impact of the local cost functions redundancy on the solvability of \(\frac{1}{k}\sum _{i=1}^k h_i\). In particular, we assume that the local cost function of each agent is formed as a convex combination of the k input functions \(h_1, \ldots , h_k\). Depending on the availability of side information at each agent, two slightly different variants are considered. We show that for a given graph, the problem can indeed be solved despite the presence of faulty agents. In particular, even in the absence of side information at each agent, when adequate redundancy is available in the optima of input functions, a distributed algorithm is proposed in which each agent carries minimal state across iterations.