random sparsification

Random Sparsification is a gradient compression technique that randomly selects a subset of gradient components for communication — each component is included with probability $p$, providing an unbiased estimator of the full gradient with reduced communication cost.

Random Sparsification Details

• Sampling: Each gradient component $g_i$ is included with probability $p$ (independently).
• Rescaling: Included components are rescaled by $1/p$ to maintain an unbiased estimate: $E[\hat{g}] = g$.
• Variance: Higher compression (lower $p$) = higher variance — slower convergence.
• Communication: Expected communication = $p \times d$ components (where $d$ is gradient dimension).

Why It Matters

• Unbiased: Unlike top-K, random sparsification is an unbiased estimator — simpler convergence proofs.
• Privacy: Random selection adds uncertainty that makes gradient inversion attacks harder.
• Simplicity: No need to sort gradients (unlike top-K) — simpler implementation.

Random Sparsification is randomly sampling gradients — an unbiased compression method that trades variance for communication savings.