Research map / Optimization / Distributed and compressed
Tight analyses of first-order methods with error feedback
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.
Derives tight, matching-lower-bound convergence rates and optimal Lyapunov functions for classic error feedback (EF) and EF21 (and compressed gradient descent) in the single-agent smooth strongly convex setting, using performance estimation plus symbolic regression.
Problem
Compressed communication degrades convergence of distributed gradient methods; error feedback (EF, EF21) mitigates this, but their tight worst-case convergence rates and fair comparison with compressed gradient descent remain unclear, since prior analyses used loose, ad hoc Lyapunov functions.
Approach
Combines performance estimation (SDP-based search over quadratic Lyapunov functions with bisection on the rate), log-det rank heuristics, symbolic regression (PySR) and Mathematica to find optimal Lyapunov functions and exact closed-form rates for EF, EF21 and CGD in the single-agent smooth strongly convex setting, showing EF and EF21 share the same optimal rate, which is worse than CGD.
Key results
- Theorem: EF and EF21 with step size eta*=(2/(L+mu))((1-sqrt(eps))/(1+sqrt(eps))) achieve the same tight contraction rate rho* = sqrt(eps) + ..., with matching lower bounds.
- Numerically, max absolute difference between EF and EF21 contraction factors is on the order of 1e-7 to 1e-5 across kappa in {2,4,10}.
- CGD achieves a strictly better optimal contraction rate than both EF and EF21 for every compression level tested, and EF/EF21 have larger non-convergence regions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EF21 instead of EF | Single-agent compressed optimization · L-smooth μ-strongly convex functions | optimal contraction rate: 4.34e-07; 6.02e-07; 1.21e-06 maximum absolute differences for κ = 2, 4, 10 | No clear effect |
| Use optimally tuned CGD instead of optimally tuned EF or EF21 | Single-agent compressed optimization · L-smooth μ-strongly convex functions, every tested compression level | optimal contraction rate | Helped |
| Add error feedback (EF or EF21) to compressed gradient descent | Single-agent deterministic-gradient optimization · L-smooth μ-strongly convex functions | convergence | Hurt |
Surprising findings
- EF and EF21 have identical optimal worst-case rates in the single-agent deterministic setting despite different motivations.
- Error feedback is detrimental to convergence relative to CGD in the single-agent deterministic gradient regime.
Limitations
- Analysis restricted to single-agent setting (n=1) and deterministic compressors; stochastic compressors handled only via expectation argument.
- Restricted to smooth strongly convex functions and quadratic Lyapunov function class.
Experimental setup
Metrics: contraction factor worst-case convergence rate
Baselines: CGD EF EF21
Builds on: error feedback (EF) EF21 performance estimation problem (PEP) PySR
Closest papers by meaning
- A Tight Theory of Error Feedback Algorithms in Distributed Optimization (ICML 2026 · similarity 0.95)
- Safe-EF: Error Feedback for Non-smooth Constrained Optimization (ICML 2025 · similarity 0.88)
- EControl: Fast Distributed Optimization with Compression and Error Control (ICLR 2024 · similarity 0.87)
- EFSkip: A New Error Feedback with Linear Speedup for Compressed Federated Learning with Arbitrary Data Heterogeneity (AAAI 2025 · similarity 0.87)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.87)
- Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants (ICLR 2024 · similarity 0.86)
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.