---
kind: concept
slug: gradient-sparsification
title: Gradient sparsification
summary: >-
  Gradient sparsification uploads only a subset of an update's entries, so each message is smaller, at the cost of distortion. Error memory can hold back the unsent part for later rounds. One card so far: a federated scheme where each device picks its own top-k level. Its energy savings are author-reported and simulated.
tags: [sparsity, communication-efficiency, federated-learning]
papers: ["2012.11804"]
related: [error-feedback, local-sgd, federated-learning, network-pruning, quantization-aware-training]
status: draft
updated_at: 2026-11-09
---

## 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 [arxiv: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
[arxiv:2012.11804 §I] [arxiv: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
[arxiv: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 [arxiv:2012.11804 alg. 1].
Error feedback is covered on its own page: [error feedback](/concepts/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 [arxiv:2012.11804 alg. 1]. Between uploads it trains locally, as in
[local SGD](/concepts/local-sgd). The paper chooses each device's sparsity and
H by an optimisation over energy, so devices with worse channels sparsify more
[arxiv:2012.11804 §IV-A] [arxiv: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 [arxiv:2012.11804 §V] [fig. 2]. The compared
schemes include one sparsity shared by all devices [arxiv:2012.11804 §V].
Card: [To Talk or to Work](/papers/2012.11804).

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.

| Situation | Use | Why |
|---|---|---|
| Battery-limited devices with different uplink rates, each with an energy budget | Per-device top-k level, chosen by a control step | The paper's setting; it argues one shared level wastes energy when channels differ [arxiv:2012.11804 §I] [arxiv:2012.11804 §IV-A] |
| Choosing the sync interval H together with sparsity | Solve for both jointly | The paper's sweeps show a trade-off between sparsity and H in the energy result [arxiv:2012.11804 §V] [fig. 1] (c, d) |
| Datacentre training with fast, reliable links | No card covers this | The paper's energy model is for mobile devices [arxiv:2012.11804 §IV-A] |
| Adopting the reported savings | Re-measure first | The results are simulated, and the training hyperparameters of the experiments are not stated [arxiv:2012.11804 §V] |

## 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
[arxiv:2012.11804 alg. 1].

```pseudocode
# 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
  [arxiv:2012.11804 alg. 1].
- **Gradient point.** Algorithm 1 takes the gradient at the global model. The
  appendix analysis takes it at the local iterate [arxiv:2012.11804 alg. 1]
  [arxiv: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
  [arxiv:2012.11804 §III-A] [arxiv: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
  [arxiv: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](/papers/2012.11804): top-k sparsity per device with error memory, and a control step that picks sparsity and sync interval to minimise energy (author-reported, simulated).