Research map / Learning theory and algorithms / Sample complexity
Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants
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.
Improves the EF21 communication complexity dependence from the quadratic mean of smoothness constants to their arithmetic mean, via client cloning, a weighted variant EF21-W, and a weighted analysis of vanilla EF21.
Problem
Distributed nonconvex optimization with greedy contractive compressors (e.g., TopK) under error feedback; EF21's best known rate depends on the quadratic mean of local smoothness constants, which can be much larger than the arithmetic mean in heterogeneous settings.
Approach
Replace the quadratic-mean smoothness dependence of EF21 with the arithmetic mean by (i) cloning clients with worse smoothness constants, (ii) reweighting client updates by L_i/sum L_j (EF21-W), and (iii) a smoothness-weighted Lyapunov analysis showing vanilla EF21 attains the same rate.
Key results
- EF21 complexity improves from depending on the quadratic mean L_QM to the arithmetic mean L_AM, with theoretical rate (L + L_AM xi(alpha))/epsilon versus (L + L_QM xi(alpha))/epsilon.
- Client cloning achieves the arithmetic-mean rate within a factor sqrt(2) using at most 2n clients.
- Experiments show EF21-W matches or surpasses EF21 on non-convex logistic regression and linear regression, especially when smoothness constants vary widely.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the quadratic mean of client smoothness constants with the arithmetic mean in the convergence analysis | EF21 · General smooth nonconvex | iteration complexity: L + \LQM \xi (\alpha) -> L + \LAM \xi (\alpha) | Helped |
| Use smoothness-weighted client updates | EF21-W · General smooth nonconvex | iteration complexity: \gamma \leq \frac{1}{L + \LAM \xi(\alpha)} | Helped |
| Clone clients according to their smoothness constants | EF21 · General smooth nonconvex | iteration complexity: \LAM \leq M(N^\star_1,\dots,N^\star_n) \leq \sqrt{2} \LAM | Helped |
| Use the new learning rate | EF21-W · LIBSVM datasets | convergence | Helped |
| Use the new learning rates | EF21-W-PP and EF21-W-SGD · LIBSVM datasets | convergence | Helped |
| Use smoothness-weighted updates | EF21-W · Synthetic linear regression | performance | Helped |
Surprising findings
- Vanilla EF21 with a smoothness-weighted analysis attains the arithmetic-mean rate without any change to the algorithm.
Limitations
- Cloning requires more devices and conflicts with federated privacy constraints
- Experiments are limited to small-scale logistic and linear regression problems
- Improvement is in theory; the analysis assumes smoothness of each local function
Experimental setup
Datasets: LIBSVM benchmark datasets synthetic linear regression data
Benchmarks: LIBSVM datasets (non-convex logistic regression) synthetic linear regression
Metrics: gradient norm squared vs communication rounds
Baselines: EF21 gradient descent
Builds on: EF21 Top-K compression Lyapunov analysis
Closest papers by meaning
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum (NeurIPS 2025 · similarity 0.87)
- Safe-EF: Error Feedback for Non-smooth Constrained Optimization (ICML 2025 · similarity 0.87)
- EFSkip: A New Error Feedback with Linear Speedup for Compressed Federated Learning with Arbitrary Data Heterogeneity (AAAI 2025 · similarity 0.86)
- Tight analyses of first-order methods with error feedback (NeurIPS 2025 · similarity 0.86)
- EControl: Fast Distributed Optimization with Compression and Error Control (ICLR 2024 · similarity 0.84)
- Error Broadcast and Decorrelation as a Potential Artificial and Natural Learning Mechanism (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.