DIANA Distributed Learning with Compressed Gradient Differences

A distributed composite and nonconvex stochastic optimization algorithm (DIANA) for minimizing f(x) + R(x) = (1/n) sum_{i=1}^n f_i(x) + R(x) across n workers in which each worker i maintains a local gradient-memory shift vector h_i^k in R^d (with server mean h^k = (1/n) sum_{i=1}^n h_i^k), computes a stochastic gradient g_i^k, compresses only the gradient difference Delta_i^k = g_i^k - h_i^k via an unbiased block l_p quantizer Delta_hat_i^k = Quant_p(Delta_i^k) satisfying E[||Delta_hat_i^k - Delta_i^k||_2^2] <= (1/alpha_p - 1) ||Delta_i^k||_2^2, updates its local memory h_i^{k+1} = h_i^k + alpha * Delta_hat_i^k, and transmits Delta_hat_i^k to the server to form the unbiased global gradient estimator g_hat^k = h^k + (1/n) sum_{i=1}^n Delta_hat_i^k, update h^{k+1} = h^k + alpha * (1/n) sum_{i=1}^n Delta_hat_i^k, and take a momentum/proximal step x^{k+1} = prox_{gamma R}(x^k - gamma * v^k), enabling each h_i^k to converge to the local optimum gradient nabla f_i(x^*) so quantization variance vanishes at the optimum even under arbitrary inter-worker heterogeneity and nonsmooth regularization R != 0.