The \((k_1,k_2,(k_1+k_2)\rho )\) -TV stability guarantee follows from lemma:tv-stability-qsgd by taking a supremeum over all datasets \(S\)  and \(S^{\prime }\)  of sizes \(n\)  and \(n+k_2\)  (or \(n-k_2)\)  to get that that TV stability is uniformly upper bound by \(\frac{4GTd(k_1+k_2)}{n\tau } =(k_1+k_2)\rho \) , where the equality follows upon setting \(\tau = \frac{4GdT}{\rho n}\) .
For the excess empirical risk bound, we use the guarantee on excess empirical risk of SGD on smooth convex functions (for example, Theorem 4.1 from [1]}), combined with the fact in claim:quantize that quantization produces unbiased estimates of the gradient with bounded variance \(^2 \le \frac{2G^2}{m} + \tau ^2 d = \frac{2G^2}{m} +\frac{16G^2d^3T^2}{(\rho n)^2}\) . Therefore, choosing step size \(\eta \le \frac{1}{2L}\) , we get
\({ \hat{F}_S(\hat{}_S) - \hat{F}_S(^*_S)} \le O{ 2\eta ^2 + \frac{D^2}{\eta T}} = O{2\eta {\frac{2G^2}{m} +\frac{16G^2d^3T^2}{(\rho n)^2}} + \frac{D^2}{\eta T}}\) 
