Efficient Private Federated Learning with Error Feedback under Random Allocation

Gradient sparsification is widely used in differentially private federated learning to reduce communication cost. However, sparsification drops coordinates that may carry useful gradient information. Error feedback can recover this information by storing the dropped coordinates and reusing them later, but its effectiveness is limited by how often a client participates: under partial client participation, each client is selected infrequently, so the dropped coordinates become stale and rarely reintroduced. Under differential privacy two further problems arise: adding the stored coordinates back inflates the update norm before clipping, and storing them after the noise carries that noise into later rounds. In this paper, we propose Clean Error Residual Feedback (CERF), where each client stores the coordinates dropped by sparsification from its clipped model update before noise is added, overwrites them at each participation, and feeds them back only at the coordinates the current mask keeps. To tackle the problem of infrequent participation, we use random allocation for client selection, which lets each client participate more regularly while still benefiting from the privacy amplification of subsampling. We derive the privacy and convergence analysis of CERF, showing the trade-off between compression, staleness, and noise terms. Empirical experiments show that at a fixed privacy level, there exists a sparsification rate and allocation cycle length where CERF matches or improves the accuracy of DP-FedAvg at a fraction of the communication and energy cost per client.