We focus on proving the implication. [1]} gave lower bounds on accuracy for DP algorithms by providing a reduction to computing mean of the dataset. We present and give the proof of the reduction, adapted to our context, for completeness. The reduction is that if we have a TV-stable algorithm for empirical risk minimization for a particular \(f\)  with some accuracy, then we have a TV-stable algorithm for mean computation problem with certain accuracy.
We will look at mean computation problem over datasets with norm of the mean being \(\Theta (M)\) , for some given \(M\) . Let \(\mu (S) = \frac{1}{n}\sum _{j=1}^n_i\)  denote the mean of dataset \(S={_1,_2,\cdots _n}\) .
