MARINA Faster Non-Convex Distributed Learning with Compression

A communication-efficient nonconvex distributed optimization method (MARINA, together with its variance-reduced finite-sum/online variant VR-MARINA and partial-participation variant PP-MARINA) for minimizing f(x) = (1/n) sum_{i=1}^n f_i(x) that constructs a biased SARAH/PAGE-style recursive gradient estimator g^{k+1} using an independent unbiased omega-quantizer Q at each worker: after updating x^{k+1} = x^k - gamma * g^k and drawing c_k ~ Bernoulli(p) (typically p = 1/(1 + omega)), each worker i transmits the exact gradient g_i^{k+1} = nabla f_i(x^{k+1}) if c_k = 1 or the compressed consecutive gradient difference g_i^{k+1} = g^k + Q(nabla f_i(x^{k+1}) - nabla f_i(x^k)) if c_k = 0, so the server average g^{k+1} = (1/n) sum_{i=1}^n g_i^{k+1} satisfies E[||g^{k+1} - nabla f(x^{k+1})||^2] <= (1 - p)||g^k - nabla f(x^k)||^2 + ((1 - p)*omega*L^2/n) E[||x^{k+1} - x^k||^2] and achieves O((Delta_0 * L / eps^2) * (1 + sqrt((1 - p)*omega / (p*n)))) iteration complexity (O((Delta_0 * L / eps^2) * (1 + omega / sqrt(n))) under p = 1/(1 + omega)), improving over DIANA by a factor of O(sqrt(omega)) without any bounded gradient dissimilarity assumption.