Research map / Federated learning and privacy / Communication-efficient FL

Accelerating Federated Learning with Quick Distributed Mean Estimation

ICML 2024 · Federated learning and privacy › Communication-efficient FL · approach: Communication-efficient heterogeneous FL

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes QUIC-FL, a distributed mean estimation method with O(d log d) encoding and O(n·d + d log d) decoding that keeps optimal O(1/n) NMSE, using bounded support quantization and solver-designed distribution-aware unbiased quantizers.

Problem

Distributed mean estimation for communication-efficient federated learning: existing methods achieving the optimal O(1/n) NMSE incur high encoding or decoding complexity, especially on the client or server side.

Approach

Use a shared randomized Hadamard transform so all clients share one rotation (enabling a single server-side inverse transform), send large coordinates exactly (bounded support quantization), and design unbiased quantization levels for the normal distribution by discretizing the non-convex problem and solving it with off-the-shelf solvers, optionally with client-specific shared randomness.

Key results

• QUIC-FL achieves O(d log d) encoding and O(n·d + d log d) decoding with O(1/n) NMSE, improving over EDEN's decode time (O(n·d·log d)) and Kashin's encode time (O(d log d log(n·d))).
• With p=2^-9 and b=1, QUIC-FL reaches NMSE ≈8.58/n without shared randomness, and ≈3.29 vNMSE with one shared random bit, versus 8.58 without.
• QUIC-FL compresses vectors with over 33 million coordinates within 44 ms and is markedly more accurate than QSGD, Hadamard and Kashin, with NMSE competitive with EDEN at much lower decode time.

Measured effects reported in the paper

Surprising findings

• EDEN with RHT can have NMSE that does not decay with n on adversarial (similar-client) inputs, as shown with a counterexample in Appendix A.
• The default TensorFlow Kashin implementation is biased, so its NMSE does not scale as O(1/n).

Limitations

• Cannot exploit gradient structure such as correlations across coordinates; RHT can destroy structure (e.g., all ±1 vectors).
• Unbiased quantizer design relies on the normal-distribution approximation of rotated coordinates; RHT guarantees carry larger constants.
• The optimal quantization tables are computed offline with a solver, and the solver may time out for large parameter settings.

Experimental setup

Datasets: Shakespeare next-word prediction LogNormal(0,1) synthetic vectors

Benchmarks: Shakespeare next-word prediction

Metrics: NMSE encode time decode time training accuracy

Baselines: QSGD Hadamard Kashin Kashin-TF EDEN DRIVE Float32

Builds on: DRIVE EDEN Hadamard quantization (Suresh et al., 2017) Lloyd-Max quantizer FedAvg

Closest papers by meaning

• EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning (ICML 2022 · similarity 0.93)
• Decentralized Sporadic Federated Learning: A Unified Algorithmic Framework with Convergence Guarantees (ICLR 2025 · similarity 0.89)
• DRIVE: One-bit Distributed Mean Estimation (NeurIPS 2021 · similarity 0.89)
• Communication-Efficient Federated Learning with Accelerated Client Gradient (CVPR 2024 · similarity 0.87)
• FedSMU: Communication-Efficient and Generalization-Enhanced Federated Learning through Symbolic Model Updates (ICML 2025 · similarity 0.87)
• Revisiting Ensembling in One-Shot Federated Learning (NeurIPS 2024 · similarity 0.87)