Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks

Abstract

Variance reduction is indispensable in Byzantine-resilient decentralized stochastic optimization over multi-agent systems (MASs), as it effectively mitigates gradient noise to facilitate the resilient aggregation process. However, most existing Byzantine-resilient decentralized variance-reduced (VR) stochastic gradient algorithms rely on random data sampling, which proves inefficient in data-scarce yet high-dimensional tasks, for instance, image deblurring. This paper aims to pursue an alternative approach that achieves variance reduction via gradient sketching. We first formulate a class of structural risk minimization (SRM) problems over time-varying networks, where the local objectives are not necessarily decomposable and their gradients may be inaccessible. To solve the SRM problems in a decentralized manner, we incorporate a localized gradient-sketching technique into a preconditioned stochastic proximal gradient framework, proposing a novel gossip-based decentralized algorithm with variance reduction, dubbed Gossip-SEGA. To further enhance its resilience, we substitute the weighted-average aggregation in Gossip-SEGA with a norm-penalized approximation, thereby developing a Byzantine-resilient decentralized algorithm, namely RED-SEGA. Theoretically, we derive sufficient conditions for both consensus among reliable agents and (sub)linear convergence rate of RED-SEGA over time-varying networks in the presence of Byzantine agents with unknown identities. This is challenging, as the convergence and consensus errors must be bounded within a transformed variable-metric geometry, where the inherent complexities are further compounded by adversarial Byzantine agents and time-varying networks. The effectiveness and resilience of RED-SEGA are validated by solving a constrained least-squares problem and an image deblurring task under various Byzantine attacks.

arXiv comment21 pages, 39 figures