Firstly, as discussed in [1]}, we consider \(G=D=1\) , since a simple reduction gives a factor of \(GD\)  for general \(G\)  and \(D\) . Furthermore, similar to [1]}, we show that the problem of TV-stable convex ERM is at least as hard as that of TV stable mean computation of a dataset with bounded mean - we state this reduction in prop:lowerboundreduction.
We now focus on showing accuracy lower bounds for \(\rho \) -TV-stable mean computation of dataset \(S\)  of size \(n\) , with mean \(\frac{M}{2}\le {\mu (S)} \le 2M\) . The accuracy, denoted by \(\alpha \) , is defined as \(\alpha ^2 = \mathbb {E}{(S)-\mu (S)}^2\) ,
\(\)  is a \(\rho \) -TV stable algorithm, and the expectation is taken over the algorithm's randomness.
The first part of thm:main-lower-bound follows thm:lowerbound11 which is based on a simple reduction argument.
This gives us that \(\alpha \ge \frac{1}{\rho n}\)  with \(M = \frac{1}{\rho n}\) . Plugging it in prop:lowerboundreduction, this gives us that excess empirical risk is lower bounded by \(\Omega {\frac{1}{\rho n}}\) .
Similarly, the second part follows from thm:lowerbound2 which gives us \(\alpha \ge \frac{1}{\sqrt{\rho n}}\)  with \(M=\frac{1}{\sqrt{\rho n}}\)  - the condition \(\alpha \le \frac{1}{4}\)  in the statement of thm:lowerbound2 can be absorbed in the trivial lower bound \(GD\) .
\(\Box \)
