Byzantine Fault-Tolerant Min-Max Optimization
Authors:
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents2022
- Cooperative–Competitive Multiagent Systems for Distributed Minimax Optimization Subject to Bounded ConstraintsIEEE Transactions on Automatic Control, 2018
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009
- Byzantine Agreement with Median Validity