

Intuitively, a differentially private algorithm promises that the output distributions are close in a specific sense: the likelihood ratios for all events for two neighbouring datasets is uniformly close to \(e^{\pm \epsilon }\) , upto a failure probability \(\delta \) .
Note that we have identified that we want our outputs to be \(\rho \) -TV stable. A natural question is whether we can relate the \((\epsilon , \delta )\) -DP notion to \(\rho \) -TV-stability. An easy to see direction is that any \(\rho \) -TV stable method is (at least) \((0,\rho )\) -DP.
Similarly, for the other direction, under additional assumptions, such relations can be derived. The important part is that certain widely used DP methods are TV stable as well. The primary example, which we will use in this work, is Gaussian mechanism. It is known that adding Gaussian noise of variance \(\frac{\sqrt{\log {1/\delta }}}{\epsilon }\)  to a 1-sensitive function, provides \((\epsilon ,\delta )\) -DP [1]}. It can be shown that the same method also provides \(\rho \) -TV stability, with \(\rho = \frac{\epsilon }{\sqrt{\log {1/\delta }}}\) .
