Gradient sparsification

Overview

Gradient sparsification sends only some entries of a gradient or model update. The paper's variant is top-k: keep the k entries with the largest magnitude and set the rest to zero 2012.11804 §III-A. The message then needs fewer bits, but the receiver gets a distorted update. The paper states that heavier sparsity raises this distortion and can need more communication rounds 2012.11804 §I 2012.11804 §III-B.

The paper names sparsity by a ratio. Device m has sparsity delta_m = d / k_m, where d is the model dimension and k_m the number of kept entries 2012.11804 §III-A. A larger delta means fewer entries are sent.

The variant also keeps the unsent part. Each device stores what it did not send in an error memory and adds it to the next upload 2012.11804 alg. 1. Error feedback is covered on its own page: error feedback.

Variants

Top-k with error memory and per-device sparsity

Each device has its own k, so its own sparsity, and uploads only every H local steps 2012.11804 alg. 1. Between uploads it trains locally, as in local SGD. The paper chooses each device's sparsity and H by an optimisation over energy, so devices with worse channels sparsify more 2012.11804 §IV-A 2012.11804 §IV-B.

Reported results are simulated, not measured. The text states 1.5 to 100 times less energy than the compared schemes to reach a target accuracy on ResNet20 with CIFAR-10 and LeNet5 with MNIST 2012.11804 §V fig. 2. The compared schemes include one sparsity shared by all devices 2012.11804 §V. Card: To Talk or to Work.

No other variant (such as random-k, thresholding or quantised values) has a card yet.

When to use which

Only one card covers this slug, so this section compares constraints, not variants. Each row states what the paper's setting supports.

Implementation sketch

The sketch shows one device's upload step, in our own words. The full loop, including batch growth and the server average, is in the paper's algorithm 2012.11804 alg. 1.

# One upload step with error memory  [arxiv:2012.11804 alg. 1, lines 8-10]

def upload_step(local_change, error, k):
    # Add back what earlier uploads did not send  [alg. 1, line 8]
    corrected = error + local_change
    # Keep the k largest-magnitude entries  [arxiv:2012.11804 §III-A]
    sent = top_k(corrected, k)
    # Keep the unsent remainder for the next upload  [alg. 1, line 10]
    new_error = corrected - sent
    return sent, new_error

Points where the paper is unclear or inconsistent with itself:

• Initial error memory. Algorithm 1 sets the initial error memory to the initial model. The paper does not say whether this is intended 2012.11804 alg. 1.
• Gradient point. Algorithm 1 takes the gradient at the global model. The appendix analysis takes it at the local iterate 2012.11804 alg. 1 2012.11804 app.. The theorem is stated for the appendix version.
• Ties. The definition keeps all entries at or above the threshold, so ties can keep more than k entries. The bit count assumes exactly k 2012.11804 §III-A 2012.11804 §IV-A. Select exactly k if the budget matters.
• Index cost. The bit count uses the binomial coefficient for positions. The paper does not discuss practical index encodings, which will cost more 2012.11804 §IV-A.

Contradictions

None known. Only one card covers this slug. The paper's inconsistencies are internal and are listed above.

Papers

• To Talk or to Work: top-k sparsity per device with error memory, and a control step that picks sparsity and sync interval to minimise energy (author-reported, simulated).