Considering the Lipschitz, smoothness parameters and diameter as constants, for smooth convex functions and \(k\)  edit requests, [1]} (Theorem 3.4) achieve an excess empirical risk of \(O{\frac{\sqrt{d}\sqrt{\log {1/\delta }}}{\epsilon n k}}^{2/5}\)  with an unlearning runtime of \(k^2\)  full-gradient computations. On the other hand, our algorithms achieve an an excess empirical risk of \(\min {\frac{1}{\sqrt{\rho n}}, {\frac{\sqrt{d}}{\rho n}}^{4/5}}\)  with \(\rho k\)  expected re-computations. Each re-computation takes \(m\cdot T\)  gradient computations where \(m\)  is the mini-batch size and \(T\)  the number of iterations. Therefore, in order to have the same runtime, we need \(\rho k m T= k^2n \iff \rho = \frac{kn}{mT}\) .
Firstly, note that as as long as \(d \le (\rho n)^{3/4}\) , noisy-m-A-SGD has smaller excess empirical risk than sub-sample-GD - this are the two regimes of interest.
We now set \(m\)  and \(T\)  for both the algorithms:
for Algorithm REF , \(m=\frac{\rho n}{T}\)  and \(T= \sqrt{\rho n}\) . This gives us \(\rho = \frac{kn}{\rho n} \iff \rho = \sqrt{k}\) , however \(\rho \)  is the Total Variation distance and is at most 1. Hence in regime \(d\ge (\rho n)^{3/4}\) , our runtime is always smaller than [1]}: \(kn\)  as opposed to \(k^2n\)  gradient computations. Even with \(\rho =1\) , our excess empirical risk is \(\frac{1}{\sqrt{n}}\)  and the excess empirical risk of [1]} is smaller than ours when \({\frac{\sqrt{d}\sqrt{\log {1/\delta }}}{\epsilon n k}}^{2/5} \lesssim \frac{1}{\sqrt{n}} \iff \frac{\epsilon }{\sqrt{\log {1/\delta }}} \gtrsim \frac{\sqrt{d}n^{1/4}}{k}\) .
In the second regime \(d< (\rho n)^{3/4}\) , we use Algorithm REF , wherein we have \(mT = \frac{(\rho n)^2}{d}\) . This gives us \(\rho = \frac{kn d}{(\rho n)^2} \iff \rho = \sqrt{\frac{kd}{n}}\) , and our excess empirical risk is \(O{{\frac{\sqrt{d}}{\rho n}}^{4/5}} = O{\frac{1}{(nk)^{2/5}}}\) .
Therefore, excess empirical risk of [1]} is smaller than ours when \({\frac{\sqrt{d}\sqrt{\log {1/\delta }}}{\epsilon n k}}^{2/5} \lesssim \frac{1}{(nk)^{2/5}} \iff \frac{\epsilon }{\sqrt{\log {1/\delta }}} \gtrsim d\) .
We therefore have that unless \(k\)  is very large, the accuracy of [1]} is smaller than ours when \(\epsilon \)  and \(\delta \) , take prohibitively large values which correspond to a weak notion of approximate unlearning.
We can similarly compare against Theorem 3.5 in [1]}, which will yield qualitatively similar conclusions.
