Byzantine-Robust Federated Linear Bandits
This work addresses the vulnerability of federated learning to Byzantine attacks in distributed linear bandit optimization, offering a robust solution with privacy enhancements, though it is incremental in improving existing methods.
The paper tackles the problem of Byzantine attacks in federated linear bandits by proposing a novel algorithm with a robust aggregation oracle using the geometric median, achieving sublinear regret of $ ilde{\mathcal{O}}(T^{3/4})$ with $\mathcal{O}(\sqrt{T})$ communication steps and robustness to attacks on fewer than half of agents.
In this paper, we study a linear bandit optimization problem in a federated setting where a large collection of distributed agents collaboratively learn a common linear bandit model. Standard federated learning algorithms applied to this setting are vulnerable to Byzantine attacks on even a small fraction of agents. We propose a novel algorithm with a robust aggregation oracle that utilizes the geometric median. We prove that our proposed algorithm is robust to Byzantine attacks on fewer than half of agents and achieves a sublinear $\tilde{\mathcal{O}}({T^{3/4}})$ regret with $\mathcal{O}(\sqrt{T})$ steps of communication in $T$ steps. Moreover, we make our algorithm differentially private via a tree-based mechanism. Finally, if the level of corruption is known to be small, we show that using the geometric median of mean oracle for robust aggregation further improves the regret bound.