QUIC-FL: Quick Unbiased Compression for Federated Learning
Distributed Mean Estimation (DME) is a fundamental building block in
communication efficient federated learning. In DME, clients communicate their
lossily compressed gradients to the parameter server, which estimates the
average and updates the model. State of the art DME techniques apply either
unbiased quantization methods, resulting in large estimation errors, or biased
quantization methods, where unbiasing the result requires that the server
decodes each gradient individually, which markedly slows the aggregation time.
In this paper, we propose QUIC-FL, a DME algorithm that achieves the best of
all worlds. QUIC-FL is unbiased, offers fast aggregation time, and is
competitive with the most accurate (slow aggregation) DME techniques. To
achieve this, we formalize the problem in a novel way that allows us to use
standard solvers to design near-optimal unbiased quantization schemes.