Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

원문 초록

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), which combines a universal self-centred projection that clips incoming messages to a radius-$\tau$ ball around the receiver with a fully decentralized probabilistic dropout rule driven by a threshold-gated, dual-metric trust score in the decision and tracking channels. These identity-free defences bound adversarial perturbations while preserving doubly stochastic mixing. The projection preserves the honest network average exactly in every realization, even when honest messages are clipped. Under complete Byzantine isolation ($p_b=0$), GT-PD converges linearly to a neighbourhood of order $\alpha\sigma^2/(\mu n_{\mathcal H})$ plus higher-order network terms, matching centralized stochastic gradient descent to first order in the step size. We also give a radius computable from problem data that ensures honest messages remain unclipped with high probability. Under partial isolation ($p_b>0$), a leaky variant, GT-PD-L, controls accumulated tracking perturbations and converges linearly to a bounded neighbourhood governed by stochastic variance and the clipping-to-leak ratio, under explicit conditions on the step size, leak, and aggregate Byzantine mixing weight. With two-tier dropout and $p_h=1$, Byzantine isolation adds no variance to honest consensus dynamics. MNIST experiments 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.