Byzantine Fault-Tolerant Min-Max Optimization

In this report, we consider a min-max optimization problem under adversarial manipulation, where there are $n$ cost functions $Q_i(x)$'s, 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 in spite of the faulty functions. The problem formulation naturally extends to Byzantine fault-tolerant distributed min-max optimization. We present a simple algorithm for fault-tolerant min-max optimization, and provide some bounds on the output of the algorithm. To the best of our knowledge, we are the first to consider this problem.