{"ID":6536230,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10791","arxiv_id":"2607.10791","title":"RED-SEGA:Resilient Decentralized 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) for its ability to mitigate gradient noise and thereby enhance 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 pursues an alternative technical line that achieves variance reduction via gradient sketching. To this end, we first formulate a class of structural risk minimization (SRM) problems, where the local objectives are not necessarily decomposable and their gradients may be unavailable. To solve the SRM problems in a decentralized manner, we integrate a gradient-sketching technique into decentralized stochastic proximal gradient descent with gossip communication to propose a decentralized VR stochastic gradient algorithm, dubbed Gossip-SEGA.Since Gossip-SEGA does not provide any resilience against Byzantine attacks, a resilient extension of Gossip-SEGA,namely RED-SEGA,is developed via replacing the weighted average in Gossip-SEGA by a norm-penalized approximation. Theoretically, we derive sufficient conditions for both consensus (among reliable agents) and linear convergence rate of RED-SEGA over time-varying networks. The effectiveness and resilience of the proposed algorithms are validated through numerical experiments.","short_abstract":"Variance reduction is indispensable in Byzantine-resilient decentralized stochastic optimization over multi-agent systems (MASs) for its ability to mitigate gradient noise and thereby enhance the resilient aggregation process. However, most existing Byzantine-resilient decentralized variance-reduced (VR) stochastic gra...","url_abs":"https://arxiv.org/abs/2607.10791","url_pdf":"https://arxiv.org/pdf/2607.10791v1","authors":"[\"Jinhui Hu\",\"Guo Chen\",\"Huaqing Li\",\"Liang Ran\",\"Hexi Liang\",\"Tao Han\",\"Tingwen Huang\"]","published":"2026-07-12T14:45:56Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}