Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions
Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions
复制标题
DOI：
10.23919/acc45564.2020.9147396
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
K. Kuwaranancharoen;Lei Xin;S. Sundaram
中科院分区：
文献类型：
--
作者：
K. Kuwaranancharoen;Lei Xin;S. Sundaram
分布式优化问题要求一组智能体使用从它们的邻居那里接收到的信息，在一个参数上达成一致，使它们的局部成本函数的平均值最小。虽然有各种各样的分布式优化算法可以解决这个问题，但它们通常容易受到不遵循算法的恶意（或“拜占庭”）代理的攻击。最近解决这个问题的尝试集中在单维函数上，或者在某些假设下对代理上的函数的统计特性进行分析。本文提出了一种求解多维凸函数的弹性分布式优化算法。我们的方案在算法的每次迭代中涉及两个过滤步骤：(1)基于距离的和(2)组件明智地去除极端状态。我们表明，该算法可以在不事先知道拜占庭代理身份的情况下减轻每个常规节点附近多达F个拜占庭代理的影响。特别地，我们证明了如果网络拓扑满足一定的条件，所有的正则状态都保证渐近收敛到一个包含全局最小值的有界区域。
The problem of distributed optimization requires a group of agents to reach agreement on a parameter that minimizes the average of their local cost functions using information received from their neighbors. While there are a variety of distributed optimization algorithms that can solve this problem, they are typically vulnerable to malicious (or "Byzantine") agents that do not follow the algorithm. Recent attempts to address this issue focus on single dimensional functions, or provide analysis under certain assumptions on the statistical properties of the functions at the agents. In this paper, we propose a resilient distributed optimization algorithm for multidimensional convex functions. Our scheme involves two filtering steps at each iteration of the algorithm: (1) distance-based and (2) component-wise removal of extreme states. We show that this algorithm can mitigate the impact of up to F Byzantine agents in the neighborhood of each regular node, without knowing the identities of the Byzantine agents in advance. In particular, we show that if the network topology satisfies certain conditions, all of the regular states are guaranteed to asymptotically converge to a bounded region that contains the global minimizer.