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 imes 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.