# Distributed Online Optimization with Byzantine Adversarial Agents

arXiv: https://arxiv.org/abs/2109.12340 · HTML: https://mlsanity.com/paper/2109.12340/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 25 Sep 2021.

## Builds on (most cited first, 6 of 6)

- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions](https://mlsanity.com/paper/2003.09038/) (2020)
- [Byzantine Multi-Agent Optimization: Part I](https://mlsanity.com/paper/1506.04681/) (2015)
- [Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks](https://mlsanity.com/paper/1511.01821/) (2015)

## Built on by (most cited first, 2 of 2)

- [Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment](https://mlsanity.com/paper/2307.07980/) (2023)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)

## Abstract (arXiv)

We study the problem of non-constrained, discrete-time, online distributed optimization in a multi-agent system where some of the agents do not follow the prescribed update rule either due to failures or malicious intentions. None of the agents have prior information about the identities of the faulty agents and any agent can communicate only with its immediate neighbours. At each time step, a locally Lipschitz strongly convex cost function is revealed locally to all the agents and the non-faulty agents update their states using their local information and the information obtained from their neighbours. We measure the performance of the online algorithm by comparing it to its offline version, when the cost functions are known apriori. The difference between the same is termed as regret. Under sufficient conditions on the graph topology, the number and location of the adversaries, the defined regret grows sublinearly. We further conduct numerical experiments to validate our theoretical results.