论文标题
拜占庭式耐断层的最低 - 最大优化
Byzantine Fault-Tolerant Min-Max Optimization
论文作者
论文摘要
在本文中，我们考虑了在对抗操作下的最小最大优化问题，那里有$ n $成本功能，最多可由对手的任意错误功能代替$ f $。目的是在$ n $功能中最小化$ x $的最高成本，尽管功能有故障。问题的表述自然可以扩展到拜占庭式耐受性分布的最低最大最大优化。 我们提出了一种简单的算法，用于拜占庭式最低 - 最大优化，并为算法的输出提供界限。我们还为此问题提供了近似算法。然后，我们将问题扩展到分布式设置，并提出分布式算法。据我们所知，我们是第一个考虑这个问题的人。
In this paper, we consider a min-max optimization problem under adversarial manipulation, where there are $n$ cost functions, up to $f$ of which may be replaced by arbitrary faulty functions by an adversary. The goal is to minimize the maximum cost over $x$ among the $n$ functions despite the faulty functions. The problem formulation could naturally extend to Byzantine fault-tolerant distributed min-max optimization. We present a simple algorithm for Byzantine min-max optimization, and provide bounds on the output of the algorithm. We also present an approximate algorithm for this problem. We then extend the problem to a distributed setting and present a distributed algorithm. To the best of our knowledge, we are the first to consider this problem.
