Lipschitz composable compressor
It turns out that there is a simple answer: $O(k)$-composable $\frac kd$ compressor (in expectation) just returns $k$ random coordinates. The proof is trivial and can be found in Stich et al., &quot;Sparsified SGD with Memory&quot;, Section A.1