Error Feedback for Accelerated Distributed Optimization with Single Compressed Uplink

Distributed optimization across multiple workers can incur substantial communication costs due to frequent exchange with a central server. Compressing high-dimensional gradients alleviates this bottleneck, but biased compression introduces persistent errors that complicate acceleration. Error feedback can correct compression error, yet combining it with Nesterov acceleration is subtle because acceleration accumulates gradient-estimation errors with time-varying weights. We introduce $\text{EC-NAG}$, a Nesterov-aligned error-compensation method for smooth distributed convex optimization. Each worker compresses a gradient-difference message corrected using its two most recent controlled-error states, with coefficients chosen so that the Nesterov-weighted history of gradient-estimation errors telescopes to the current averaged error state. Consequently, EC-NAG requires only one compressed uplink vector per worker per iteration. We develop a non-asymptotic analysis and show that EC-NAG preserves the deterministic $\mathcal{O}(1/T^2)$ accelerated rate, while in the stochastic setting it achieves the standard $\mathcal{O}(1/\sqrt{T})$ decay. Thus, we match the stochastic lower-bound exponent in $\epsilon$. Experiments on distributed least-squares and classification problems demonstrate favorable convergence as a function of communicated uplink bits.