We now unfix \(b_t\) , and use the fact the \(b_t\)  is a uniform sample of \(m\)  out of \(n\)  (or \(n-1\)  or \(n+1\) ) indices. By privacy amplification by sub-sampling result in [1]}, for \(\alpha \le 2\) , we will argue that the Rènyi divergence upper bound amplifies to
\(\frac{32\alpha G^2}{n^2 \sigma ^2}\) . There are certain subtleties about the application of this result, so we explain, as follows. The first is that Theorem 9 stated in [1]},
when considering \(\alpha \le 2\) , the right hand side
simplifies as \( \frac{1}{\alpha -1}\log {1+\frac{m^2}{n^2}\frac{\alpha (\alpha -1)}{2}4{\exp {\frac{8G^2}{m^2\sigma ^2}}-1}} \le \frac{2\alpha m^2}{n^2}{\exp {\frac{8G^2}{m^2\sigma ^2}}-1} \le \frac{32\alpha G^2}{n^2 \sigma ^2}\)  where the last inequality use the numeric inequality \(\exp {x} \le 1+2x\)  when \(x\le 1.256\) ; this means that we need the following condition \(\frac{8G^2}{m^2\sigma ^2} \le 1.256\)  - we will revisit this condition later.
The second point is that Theorem 9 in [1]}
holds integer \(\alpha \ge 2\) , which only leaves us with \(\alpha =2\) .
In the subsequent part of the proof, we will need to take \(\alpha \rightarrow 1\) . This discrepancy can be accounted for by using the fact the \(\alpha \) -Rènyi Divergence is non-decreasing for \(\alpha \in [0,\infty ]\)  (see Theorem 3 in [4]}). Therefore the result holds for all \(\alpha \le 2\) , and we can replace the upper bound to be \(\frac{64G^2}{n^2\sigma ^2}\) 
The third and final point is that even though the amplification result in [1]} is established under the neighbouring relation that one point is replaced between datasets, it can be shown that the same result holds (perhaps upto constants) when the neighbouring relation is add/delete one data-point; see Lemma 3, [6]} for example.
We now use adaptive sequential composition property of Rènyi divergence (Proposition 1 in [7]}) which linearly accumulates the divergence across iterations, yielding that the Rènyi divergence between the iterates \((_1,_2,\ldots ,_T)\)  and \((_1^{\prime },_2^{\prime },\ldots ,_T^{\prime })\)  is bounded as, \(D_\alpha ((_1,_2,\ldots ,_T) \Vert (_1^{\prime },_2^{\prime },\ldots ,_T^{\prime })) \le \frac{64T G^2}{n^2 \sigma ^2}\) . An application of data-processing inequality gives us the same upper bound on the Rènyi divergence between the final iterates \(\hat{}_S\)  and \(\hat{}_S^{\prime }\) .
Moreover, this holds uniformly over all neighbouring datasets \(S^{\prime }\) . We now use the result that \(\lim _{\alpha \rightarrow 1}D_\alpha (\hat{}_S \Vert \hat{}_S^{\prime }) = D_{\text{KL}}(\hat{}_S \Vert \hat{}_S^{\prime })\)  where \(D_{\text{KL}}\)  denotes the KL-divergence (see Theorem 5 in [4]}). Hence we get that \( D_{\text{KL}}(\hat{}_S \Vert \hat{}_S^{\prime }) \le \frac{64TG^2}{n^2 \sigma ^2}\) . Finally, we use Pinsker's inequality to further lower bound the left hand side by total variation distance, which yields \(\text{TV}(\hat{}_S \Vert \hat{}_S^{\prime }) \le \sqrt{\frac{ D_{\text{KL}}(\hat{}_S \Vert \hat{}_S^{\prime })}{2}} \le \frac{8\sqrt{T}G}{n\sigma }\) . As remarked before, this is a uniform bound over all neighbouring datasets. Finally, as before, we trivially have that \(\text{TV}(\hat{}_S \Vert \hat{}_S^{\prime }) \le 1\) ; therefore setting \(\sigma = \frac{8\sqrt{T}G}{n\rho }\)  gives us that the algorithm's output is \(\min {\rho ,1}\)  TV-stable.
