# Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 1 Apr 2026.

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

- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Byzantine-Robust Decentralized Federated Learning](https://mlsanity.com/paper/2406.10416/) (2024)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018)
- [Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules](https://mlsanity.com/paper/2206.04568/) (2022)
- [On the Geometric Convergence of Byzantine-Resilient Distributed Optimization Algorithms](https://mlsanity.com/paper/2305.10810/) (2023)

## Abstract (arXiv)

We study distributed optimization over networks with Byzantine agents that may send arbitrary adversarial messages. We propose Gradient Tracking with Probabilistic Edge Dropout (GT-PD), a stochastic gradient tracking method that preserves the convergence properties of gradient tracking under adversarial communication. GT-PD combines two complementary defense layers: a universal self-centered projection that clips each incoming message to a ball of radius τ around the receiving agent, and a fully decentralized probabilistic dropout rule driven by a dual-metric trust score in the decision and tracking channels. This design bounds adversarial perturbations while preserving the doubly stochastic mixing structure, a property often lost under robust aggregation in decentralized settings. Under complete Byzantine isolation (pb=0), GT-PD converges linearly to a neighborhood determined solely by stochastic gradient variance. For partial isolation (pb>0), we introduce Gradient Tracking with Probabilistic Edge Dropout and Leaky Integration (GT-PD-L), which uses a leaky integrator to control the accumulation of tracking errors caused by persistent perturbations and achieves linear convergence to a bounded neighborhood determined by the stochastic variance and the clipping-to-leak ratio. We further show that under two-tier dropout with ph=1, isolating Byzantine agents introduces no additional variance into the honest consensus dynamics. Experiments on MNIST under Sign Flip, ALIE, and Inner Product Manipulation attacks show that GT-PD-L outperforms coordinate-wise trimmed mean by up to 4.3 percentage points under stealth attacks.