# VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 12 May 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [BRIDGE: Byzantine-resilient Decentralized Gradient Descent](https://mlsanity.com/paper/1908.08098/) (2019)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [Byzantine-resilient Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2002.08569/) (2020)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018)
- [Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training](https://mlsanity.com/paper/2109.07706/) (2021)
- [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)
- [Resilient Distributed Estimation Through Adversary Detection](https://mlsanity.com/paper/1701.00878/) (2017)
- [Distributed Bayesian Detection with Byzantine Data](https://mlsanity.com/paper/1307.3544/) (2013)
- [Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity](https://mlsanity.com/paper/1504.02547/) (2015)
- [Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates](https://mlsanity.com/paper/1809.02920/) (2018)

## Abstract (arXiv)

We introduce the paradigm of validated decentralized learning for undirected networks with heterogeneous data and possible adversarial infiltration. We require (a) convergence to a global empirical loss minimizer when adversaries are absent, and (b) either detection of adversarial presence of convergence to an admissible consensus irrespective of the adversarial configuration. To this end, we propose the VALID protocol which, to the best of our knowledge, is the first to achieve a validated learning guarantee. Moreover, VALID offers an O(1/T) convergence rate (under pertinent regularity assumptions), and computational and communication complexities comparable to non-adversarial distributed stochastic gradient descent. Remarkably, VALID retains optimal performance metrics in adversary-free environments, sidestepping the robustness penalties observed in prior byzantine-robust methods. A distinctive aspect of our study is a heterogeneity metric based on the norms of individual agents' gradients computed at the global empirical loss minimizer. This not only provides a natural statistic for detecting significant byzantine disruptions but also allows us to prove the optimality of VALID in wide generality. Lastly, our numerical results reveal that, in the absence of adversaries, VALID converges faster than state-of-the-art byzantine robust algorithms, while when adversaries are present, VALID terminates with each honest either converging to an admissible consensus of declaring adversarial presence in the network.