PaperlayerView exact revision on arXiv

Source-linked AI summary

MARINA: Faster Non-Convex Distributed Learning with Compression

Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, Peter Richtárik

arXiv:2102.07845v3cs.LGmath.OC

TL;DR

Distributed learning can be communication-bound because exchanging information may cost much more than computation. MARINA compresses gradient differences using a biased gradient estimator, with variants for stochastic local objectives and partial participation. The paper reports communication-complexity advantages, including a regime where MARINA matches gradient descent’s iteration complexity with lower communication cost.

  • Problem

    Distributed methods can face a communication bottleneck, with communication costs sometimes orders of magnitude higher than computation.

    Source: §1 · p. 1

  • Method

    MARINA applies an unbiased compression operator to gradient differences with some probability, yielding a biased gradient estimator.

    Source: §1.1 · p. 2

  • Results

    When n ≥ ω(d/ζQ − 1), MARINA’s iteration complexity coincides with gradient descent while its communication complexity is provably better.

    Source: §2.1 · p. 5

  • Takeaways & Limitations

    With probability chosen small enough, the partial-participation setting can result in the server receiving quantized vectors from only a subset of clients at each iteration.

    Source: §4 · p. 8

    The cited FedCOMGATE result assumes a quantization bound that does not hold for classical RandK and ℓ2-quantization on R^d.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

We develop and analyze MARINA: a new communication efficient method for non-convex distributed learning over heterogeneous datasets. MARINA employs a novel communication compression strategy based on the compression of gradient differences that is reminiscent of but different from the strategy employed in the DIANA method of Mishchenko et al. (2019). Unlike virtually all competing distributed first-order methods, including DIANA, ours is based on a carefully designed biased gradient estimator, which is the key to its superior theoretical and practical performance. The communication complexity bounds we prove for MARINA are evidently better than those of all previous first-order methods. Further, we develop and analyze two variants of MARINA: VR-MARINA and PP-MARINA. The first method is designed for the case when the local loss functions owned by clients are either of a finite sum or of an expectation form, and the second method allows for a partial participation of clients -- a feature important in federated learning. All our methods are superior to previous state-of-the-art methods in terms of oracle/communication complexity. Finally, we provide a convergence analysis of all methods for problems satisfying the Polyak-Lojasiewicz condition.

1. Introduction

MARINA addresses the communication bottleneck in distributed non-convex learning with compressed gradient differences and a biased gradient estimator. Its variants extend the approach to local stochastic gradients and partial client participation, with the paper reporting improved complexity bounds over prior methods.

1.1. Contributions

  • MARINA compresses gradient differences with an unbiased operator, producing a biased gradient estimator and convergence guarantees reported as strictly better than prior state-of-the-art methods.The method is presented for distributed optimization with clients connected to a parameter server, each accessing only its own local loss.Source: §1.1 · p. 2
  • VR-MARINA handles finite-sum or expectation-form local losses and performs local variance reduction, progressively removing variance from stochastic approximation.The paper reports better oracle complexity than previous state-of-the-art results; with one node and no compression, VR-MARINA reduces to PAGE (Li et al., 2020).Source: §1.1 · p. 2
  • PP-MARINA adds partial client participation, while the paper also analyzes all proposed methods under the Polyak-Łojasiewicz condition and reports improved prior complexity results.The paper identifies partial participation as important in federated learning.Source: §1.1 · p. 2
  • The authors say their analysis can accommodate different quantizers and client batch sizes, and that VR-MARINA and PP-MARINA can be combined.They omit that combined algorithm to keep the exposition simpler.Source: §1.1 · p. 2

1.2. Related Work

  • Prior compressed-communication work includes unbiased quantization and biased compressors; biased compression can be problematic, while error compensation is one proposed remedy.The related-work discussion also places distributed non-convex optimization within the broader study of ε-stationary points.Source: §1.2 · pp. 2–3

1.3. Preliminaries

  • The preliminaries assume a uniform lower bound and smooth local losses, and define quantization as a stochastic mapping satisfying a variance bound.The expected density of a quantizer is defined as the supremum expected number of nonzero output components.Source: §1.3 · p. 4

2. MARINA

MARINA probabilistically alternates between sending full gradients and compressed gradient differences, producing a biased estimator under nontrivial quantization. Its analysis gives convergence and communication-complexity results for generally non-convex problems and a convergence result under the Polyak-Łojasiewicz condition.

2. MARINA

  • With probability p, workers send full gradients; otherwise they send quantized gradient differences, whose aggregation makes MARINA’s estimator biased under nontrivial quantization.With identity quantization, MARINA reduces to Gradient Descent.Source: §2 · p. 5

2.1. Convergence Results for Generally Non-Convex Problems

  • MARINA reaches E[∥∇f(ˆxK)∥²] ≤ ε² with expected communication cost per worker O(d + ζQK).When n ≥ ω(d/ζQ − 1), its iteration complexity coincides with Gradient Descent while its communication complexity is better.Source: §2.1 · p. 5

2.2. Convergence Results Under Polyak-Łojasiewicz condition

  • Under the Polyak-Łojasiewicz condition, MARINA produces xK with E[f(xK) − f(x∗)] ≤ ε.The result is stated under Assumptions 1.1, 1.2, and 2.1.Source: §2.2 · pp. 5–6

3. Variance Reduction

VR-MARINA extends MARINA with local variance reduction for finite-sum and expectation-form losses. Its finite-sum and online analyses give oracle and communication bounds, with reported comparisons to VR-DIANA and PAGE.

3. Variance Reduction

  • VR-MARINA handles local finite-sum or expectation-form losses by performing local variance reduction to progressively remove variance from stochastic approximation.The paper describes this variance reduction as leading to better oracle complexity than previous state-of-the-art results.Source: §3.1 · p. 6, §3 · p. 6

3.1. Finite Sum Case

  • For finite-sum losses, VR-MARINA uses O(m + b′K) expected stochastic oracle calls per node and expected communication cost O(d + ζQK) per worker.The paper reports its rates as strictly better than VR-DIANA’s; without quantization and with n = 1, its bounds recover PAGE’s.Source: §3.1 · pp. 6–7

3.2. Online Case

  • For online losses, VR-MARINA uses O(ζQK + σ²/(nε²)) stochastic oracle calls per node and expected communication cost O(d + ζQK) per worker.With no quantization and n = 1, its iteration and oracle complexities recover PAGE’s bounds, which are stated to be optimal for online smooth non-convex optimization.Source: §3.2 · p. 7

4. Partial Participation

PP-MARINA modifies MARINA to allow partial client participation. Its smooth non-convex analysis gives a stationarity guarantee and a communication bound, and the paper reports better complexity than previous state-of-the-art methods for a wide class of quantizers.

4. Partial Participation

  • With probability 1 − p, the server receives quantized gradient differences from r uniformly sampled clients; with probability p, it aggregates full gradients from all clients.When p is small enough, the server receives quantized vectors from only a subset of clients at each iteration with high probability.Source: §4 · p. 8
  • PP-MARINA achieves E[∥∇f(ˆxK)∥²] ≤ ε² with expected total communication cost O(dn + ζQrK).The result is for smooth non-convex problems under Assumptions 1.1 and 1.2.Source: §4 · p. 8
  • The paper reports strictly better complexity than previous state-of-the-art methods for a wide class of quantizers, including identical quantization, RandK, and ℓp-quantization.When r = n, the rate recovers MARINA’s rate under the stated assumption on ω, d, and ζQ.Source: §4 · p. 8

5. Numerical Experiments

The experiments report faster convergence for MARINA-family methods than their DIANA counterparts on non-convex binary classification and ResNet-18 image classification. Additional experiments compare the methods across communication, oracle, and transmitted-bit measures and describe the data and parameter settings.

5.1. Binary Classification with Non-Convex Loss

  • MARINA outperforms DIANA in iteration/communication complexity and transmitted bits, while VR-MARINA outperforms VR-DIANA in oracle complexity and transmitted bits.The comparisons concern non-convex binary classification; FedCOMGATE and FedPATH were excluded because their oracle complexities were significantly worse (see Table 1).Source: §5.1 · p. 9

5.2. Image Classification

  • VR-MARINA converges significantly faster than VR-DIANA in oracle complexity and transmitted bits when training ResNet-18 on CIFAR100.The experiments use five workers; the figure caption specifies RandK sparsification and batchsizes of approximately m/50.Source: §5.2 · p. 9, Figure 2 · p. 9

A.1.1. SETUP

  • The binary-classification experiments use LibSVM datasets split into five equal parts across five clients, excluding any remainder datapoints.The appendix summarizes the datasets and client splits in Table 3.Source: §A.1.1 · p. 12, Table 3 · p. 12

A.1.2. EXTRA EXPERIMENTS

  • MARINA and VR-MARINA converge faster than DIANA and VR-DIANA across gradient and loss decrease, communication rounds, per-node oracle calls, and transmitted bits.An additional MARINA–DIANA comparison uses the mushrooms dataset with 20 workers.Source: §A.1.2 · p. 12

A.2.1. SETUP

  • The CIFAR100 setup splits 50,000 images across five workers, and uses batchsize 256 per worker with separately tuned stepsizes.Other parameters are chosen according to theory, except the uncompressed VR-MARINA setting that reuses p from the RandK, K = 100,000 experiment.Source: §A.2.1 · p. 12, Table 4 · p. 13

A.2.2. EXTRA EXPERIMENTS

The appendix reports that compression benefits VR-MARINA and VR-DIANA in transmitted-bit efficiency on CIFAR100. It also links VR-MARINA’s faster epoch convergence at K = 100,000 to its lower theoretical choice of p and less frequent full-gradient computation.

A.2.2. EXTRA EXPERIMENTS

  • Compressed VR-MARINA and VR-DIANA converge much faster than their uncompressed versions in transmitted bits to reach a given accuracy.The comparison is on ResNet-18 training at CIFAR100, with five workers and RandK sparsification in the compressed runs.Source: §A.2.2 · p. 14, Figure 6 · p. 16
  • Figure 5 tests MARINA against DIANA on the mushrooms dataset with 20 workers using RandK sparsification at K ∈ {1, 5, 10}.The caption specifies stepsizes chosen according to theory.Source: Figure 5 · p. 15
  • At K = 100,000, VR-MARINA converges faster in epochs and needs fewer oracle calls than at larger K because its theoretical p is smaller and full gradients are computed less often.The same faster convergence appears without compression when using that smaller p.Source: §A.2.2 · p. 15

B. Basic Facts and Auxiliary Results

The appendix records expectation identities and a smoothness lemma used as auxiliary results. The lemma is attributed to Li et al. (2020), whose proof is reused.

B.1. Useful Properties of Expectations

  • B.1 states a variance decomposition for a random vector ξ and deterministic vector x.Source: §B.1 · p. 17
  • B.1 states the tower property of expectation for random variables ξ and η, assuming the expectations involved are well-defined.Source: §B.1 · p. 17

B.2. One Lemma

  • B.2 gives a lemma from Li et al. (2020) for an L-smooth function with update xk+1 = xk − γgk, and omits its identical proof.Source: §B.2 · p. 17

C.1. Generally Non-Convex Problems

The appendix states MARINA’s guarantee under Assumptions 1.1 and 1.2, including a gradient-norm target and an expected per-worker communication-cost characterization. Its proof uses smoothness, variance decomposition, and the tower property.

C.1. Generally Non-Convex Problems

  • Theorem C.1 states MARINA’s result under Assumptions 1.1 and 1.2.Source: §C.1 · p. 18
  • After K iterations, MARINA returns a uniformly selected iterate xhatK with E[||∇f(xhatK)||2] ≤ ε2; ∆0 is f(x0) − f*.Source: §C.1 · p. 18
  • The appendix characterizes expected total communication per worker assuming cost is proportional to transmitted nonzero components; ζQ denotes expected quantization density.Source: §C.1 · pp. 18, 20
  • The proof combines smoothness, variance decomposition, the tower property, and bounds on the gradient estimator.Source: §C.1 · pp. 18–19

C.2. Convergence Results Under Polyak-Łojasiewicz condition

The section gives convergence results for MARINA under the Polyak–Łojasiewicz condition and for VR-MARINA on generally non-convex finite-sum problems. It also extends the VR-MARINA analysis to workers with different batch sizes.

C.2. Convergence Results Under Polyak-Łojasiewicz condition

  • Under the Polyak–Łojasiewicz condition, MARINA’s theorem and corollaries bound the iterations needed to reach an objective gap of ε and give expected communication cost per worker.The communication-cost statement assumes cost is proportional to the number of nonzero transmitted components.Source: §C.2 · pp. 20–22

D.1.1. GENERALLY NON-CONVEX PROBLEMS

  • For generally non-convex finite-sum problems, VR-MARINA’s results bound iterations, stochastic oracle calls per node, and expected communication cost per worker.The returned point is chosen uniformly at random from the iterates.Source: §D.1.1 · p. 23
  • The VR-MARINA analysis extends to different batch sizes across workers, with a small modification to the complexity bounds.The theorem’s statement is otherwise unchanged.Source: §D.1.1 · p. 25

D.1.2. CONVERGENCE RESULTS UNDER POLYAK-ŁOJASIEWICZ CONDITION

This block presents VR-MARINA results for finite-sum problems under the Polyak–Łojasiewicz condition, describes its online-case algorithm, and gives online-case results for generally non-convex problems. The analysis also allows workers to use different batch sizes.

D.1.2. CONVERGENCE RESULTS UNDER POLYAK-ŁOJASIEWICZ CONDITION

  • For finite-sum problems under the Polyak–Łojasiewicz condition, VR-MARINA’s results bound iterations, stochastic oracle calls per node, and expected communication cost per worker.The communication-cost bound assumes cost is proportional to the number of nonzero transmitted components.Source: §D.1.2 · pp. 27–28

D.2. Online Case

  • In the online case, VR-MARINA uses minibatches, a probability p, and sampled stochastic gradients, then returns an iterate chosen uniformly at random.The algorithm broadcasts its gradient estimator each iteration.Source: §D.2 · p. 30

D.2.1. GENERALLY NON-CONVEX PROBLEMS

  • For generally non-convex online problems, VR-MARINA’s results bound iterations, stochastic oracle calls per node, and expected communication cost per worker.The result is stated under the theorem’s assumptions and a communication-cost model based on nonzero transmitted components.Source: §D.2.1 · p. 30
  • The online-case analysis also extends to different batch sizes across workers, with a small modification to the theorem’s complexity bounds.The passage describes this as an extension of the finite-sum case’s batch-size treatment.Source: §D.2.1 · p. 32

D.2.2. CONVERGENCE RESULTS UNDER POLYAK-ŁOJASIEWICZ CONDITION

This block gives online-case VR-MARINA results under the Polyak–Łojasiewicz condition, includes PP-MARINA’s procedure, and presents PP-MARINA guarantees for generally non-convex problems. The PP-MARINA procedure samples clients when its full-participation branch is not taken.

D.2.2. CONVERGENCE RESULTS UNDER POLYAK-ŁOJASIEWICZ CONDITION

  • For online problems under the Polyak–Łojasiewicz condition, VR-MARINA’s results bound iterations, stochastic oracle calls per node, and expected communication cost per worker.The stated communication-cost bound assumes cost is proportional to the number of nonzero transmitted components.Source: §D.2.2 · pp. 33–35

E. Missing Proofs for PP-MARINA

  • PP-MARINA samples r clients uniformly when its Bernoulli choice does not select all clients, and broadcasts the gradient estimator to workers.The procedure returns an iterate chosen uniformly at random.Source: E. Missing Proofs for PP-MARINA · p. 37

E.1. Generally Non-Convex Problems

  • For generally non-convex problems, PP-MARINA’s results bound iterations to reach an ε-stationary point and give expected total communication cost across workers.The communication-cost statement assumes cost is proportional to the number of nonzero transmitted components.Source: §E.1 · pp. 37, 39

E.2. Convergence Results Under Polyak-Łojasiewicz condition

The section analyzes PP-MARINA under the Polyak–Łojasiewicz condition. Its theorem and corollary give iteration and communication bounds for reaching an objective gap of ε.

E.2. Convergence Results Under Polyak-Łojasiewicz condition

  • Under the Polyak–Łojasiewicz condition, PP-MARINA’s theorem and corollary bound iterations to reach an objective gap of ε and give expected communication cost.The communication-cost statements assume cost is proportional to the number of nonzero transmitted components.Source: §E.2 · pp. 40–41
  • The proof derives a recurrence under the PŁ condition and uses it to establish the stated bounds.The proof is described as similar to that of the generally non-convex PP-MARINA theorem.Source: §E.2 · pp. 40–41
  • The corollary specifies a choice of p in terms of the expected quantization density, client batch size, and number of clients.Its communication-cost conclusion retains the nonzero-component cost assumption.Source: §E.2 · p. 41
Loading 2102.07845v3…