DoubleSqueeze (Double-Pass Error-Compensated Gradient Compression)

Defining the virtual sequence x_tilde_t = x_t - eta gamma (epsilon_{t-1} + (1/n) sum_{i=1}^n delta_{t-1}^{(i)}) yields the exact recurrence x_tilde_{t+1} = x_tilde_t - eta g_bar_t + eta (1 - gamma) (epsilon_t + delta_bar_t) (Supplementary Lemma 1), so setting gamma = 1 exactly cancels both worker-side and server-side compression errors in the virtual iterate and achieves the smooth non-convex convergence rate O(sigma / sqrt(n T) + xi^{2/3} / T^{2/3} + 1 / T) matching uncompressed parallel SGD's dominant O(1/sqrt(n T)) term (Theorem 1, Corollary 2).

Under bounded compression error E||C(u) - u|| <= xi / 2, the combined double-pass error satisfies xi^2 = O(xi_s^2 + xi_w^2 / n), showing that worker-side compression errors delta_t^{(i)} enjoy a 1/n averaging variance reduction across n workers whereas server-side broadcast compression error epsilon_t does not.

Requires a centralized parameter-server aggregation step to maintain the server error memory epsilon_t in R^d and assumes either bounded absolute compression error or contractive relative compression error to keep ||epsilon_t|| and ||delta_t^{(i)}|| bounded.

Applied to distributed parameter-server training of ResNet-18 and ResNet-50 on CIFAR-10 and ImageNet with 1-bit quantization and Top-k sparsification in both communication directions.