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.
Related
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
- Near-Optimal Decentralized Stochastic Convex Optimization over Networks
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
BibTeX
@misc{hu2026resilient,
title = {{Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks}},
author = {Jinhui Hu and Guo Chen and Huaqing Li and Tao Han and Tingwen Huang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.10791},
eprint = {2607.10791},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.10791},
}
RIS
TY - UNPB
TI - Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
AU - Jinhui Hu
AU - Guo Chen
AU - Huaqing Li
AU - Tao Han
AU - Tingwen Huang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2607.10791
UR - https://arxiv.org/abs/2607.10791
AB - 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.
ER -