2022/10/03 by Hai‐Bo Yang, Yang, Haibo, Peiwen Qiu +3 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #Distributed #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2210.00690
openalex publication_date 2022/10/03 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
A key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochastic first-order information has a finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many fat-tailed noise distributions (i.e., ``heavier-tailed'' with potentially infinite variance) that have been empirically observed in the FL literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us to fill this gap in this paper by proposing an algorithmic framework called FAT-Clipping (\ulfederated \ulaveraging with \ultwo-sided learning rates and \ulclipping), which contains two variants: FAT-Clipping per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-PI). Specifically, for the largest α∈ (1,2] such that the fat-tailed noise in FL still has a bounded α-moment, we show that both variants achieve O((mT)^\frac2-αα) and O((mT)(1-α)/(3α-2)) convergence rates in the strongly-convex and general non-convex settings, respectively, where m and T are the numbers of clients and communication rounds. Moreover, at the expense of more clipping operations compared to FAT-Clipping-PR, FAT-Clipping-PI further enjoys a linear speedup effect with respect to the number of local updates at each client and being lower-bound-matching (i.e., order-optimal). Collectively, our results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.