A Class of Gradient-Type Methods for Secure and Robust Decentralized Stochastic Optimization

<p dir="ltr">Multi-agent networked systems are ubiquitous across diverse domains, including smart cities, autonomous driving, power systems, Internet of Things (IoT), and large-scale training of machine learning models. Decentralized optimization provides a basis for understanding the algorithmic foundations for many inference and learning tasks over multi-agent networked systems. However, state-of-the-art decentralized optimization algorithms and theory fail to address many practical concerns. For example, most decentralized stochastic optimization algorithms are vulnerable to adversarial data attacks on a subset of the networked agents, and are divergent under heavy-tailed gradient noise that has been observed in training attention models. </p><p dir="ltr">We provide a unified perspective on designing algorithms for decentralized stochastic optimization under unconventional noise, including both adversarial and heavy-tailed types. First, to address adversarial noise affecting a subset of networked agents, we propose provably secure decentralized gradient type methods. These algorithms guarantee exact convergence to the optimum under mild and practical conditions, which have not been achieved under similar conditions in prior work. Second, to cope with heavy-tailed gradient noise affecting all networked agents, we develop two robust decentralized gradient methods with convergence guarantees: one for symmetric heavy-tailed noise with only a bounded first absolute moment, and another for non-symmetric heavy-tailed noise with a p-moment bound for p ∈ (1, 2]. These are the first results in the literature to establish convergence for decentralized networked stochastic optimization under merely such moment conditions. In designing secure and robust decentralized algorithms for both adversarial and heavy-tailed noise, we adopt a unified algorithmic approach. Namely, we combine nonlinear operators including (smoothed) clipping, normalization, sign, with momentum variance reduction, to suppress both adversarial and unconventional stochastic noise. Theoretically, this unified perspective leads to the development of decentralized algorithms with provable guarantees under non-standard noise and adversarial environments. Empirically, following this perspective, we develop and demonstrate a new method for distributed training of Transformers as an example.</p>