Decentralized Nonconvex Optimization under Heavy-Tailed Noise with Fixed-Batch Local Updates

Multiple local updates can reduce communication in decentralized optimization, but under heavy-tailed gradient noise, obtaining reliable gradient estimates from a fixed batch is challenging. We study smooth nonconvex decentralized optimization under conditionally centered gradient noise with a bounded conditional $p$-th moment, $p\in (1,2)$, using a fixed batch size per local update. We first establish a dimension-independent lower bound on the trade-off between uniform bias and worst-case mean squared error (MSE) in fixed-sample mean estimation. We then augment a three-block coordinatewise median-of-means (MoM) estimator with a clipped correction toward the pooled mean computed from the same batch, and show that the resulting estimator matches this lower bound up to constants depending only on $p$. Building on this estimator, we propose CRAFT, a decentralized method combining corrected robust estimation, recursive filtering, and local gradient tracking. We establish finite-time stationarity and consensus guarantees and show that, with a fixed batch size per local update, increasing the number of local updates between communications with the horizon reduces the sufficient communication complexity, while the total numbers of local updates and samples required per agent remain of the same order as with a fixed local period. Experiments on image classification, language modeling, and controlled synthetic problems evaluate communication efficiency, robustness under heavy-tailed perturbations, and the roles of estimator correction and recursive filtering.