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

EFSkip: A New Error Feedback with Linear Speedup for Compressed Federated Learning with Arbitrary Data Heterogeneity

AAAI 2025 · Federated learning and privacy › Communication-efficient FL · approach: Federated optimization algorithms · 2 citations (OpenAlex)

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 EFSkip, an error-feedback compression framework that reuses gradient information for s rounds (skipsize), achieving linear speedup in the number of clients with arbitrary data heterogeneity for compressed federated learning.

Problem

Error-feedback compressed distributed and decentralized federated learning with biased compressors (e.g., top-k) lacks guarantees that simultaneously handle arbitrary data heterogeneity without strong assumptions and achieve linear speedup in the number of clients.

Approach

Clients compute stochastic gradients only once every s rounds (skipsize s = log_{1/(1-δ)}(n+2)) and reuse the gradient information for the intervening rounds, transmitting compressed error-feedback increments; this removes bounded gradient/dissimilarity assumptions, yields linear speedup in n, and removes the compression factor δ from the computation complexity.

Key results

• EFSkip-SGD achieves computation complexity O(σ²/(nϵ⁴) + 1/ϵ²) with linear speedup in n and no compression factor δ, versus EF21's O(σ²/(δ³ϵ⁴) + 1/(δϵ²)).
• EFSkip-SGD communication complexity is O(s/ϵ²) with skipsize s = log_{1/(1-δ)}(n+2), removing dependence on gradient/dissimilarity bounds.
• Under the PL condition, EFSkip-SGD attains O((σ²/(nµ²ϵ) + 1/µ) log(1/ϵ)) computation complexity, with linear speedup in n.

Measured effects reported in the paper

Limitations

• Theoretical results only; no empirical experiments reported in the provided text.
• Skipsize depends on compression factor δ and number of clients, so s grows with n for small δ.
• Assumes average smoothness of local functions and stochastic gradient variance bounds.

Experimental setup

Metrics: communication complexity computation complexity (stochastic gradients)

Baselines: EF21 EF21-SGD BEER Qsparse-SGD CSER NEOLITHIC DeepSqueeze CHOCO-SGD SQuARM-SGD

Builds on: Error Feedback (EF) EF21 BEER CHOCO-SGD

Closest papers by meaning

• Stochastic Controlled Averaging for Federated Learning with Communication Compression (ICLR 2024 · similarity 0.91)
• Safe-EF: Error Feedback for Non-smooth Constrained Optimization (ICML 2025 · similarity 0.88)
• Achieving Lossless Gradient Sparsification via Mapping to Alternative Space in Federated Learning (ICML 2024 · similarity 0.88)
• FedSMU: Communication-Efficient and Generalization-Enhanced Federated Learning through Symbolic Model Updates (ICML 2025 · similarity 0.87)
• LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression (ICLR 2025 · similarity 0.87)
• An Efficient and Accurate Dynamic Sparse Training Framework Based on Parameter-Freezing (AAAI 2025 · similarity 0.87)