
where the last inequality holds when \(\frac{\epsilon }{\log {1/\rho \delta }} \le O(1)\) , which usually is the case in DP, and so is a reasonable regime. We now compare against [1]} - we ignore \(G,D\)  and \(\text{log}\)  factor in both the bounds. To have the same runtime, we need \(\rho k Tm = k^2 n \iff \rho = \frac{kn}{Tm} = \frac{kd}{\epsilon ^2n}\) , where in the last equality we substituted \(Tm = \frac{(\epsilon n)^2}{d}\) , parameters for the DP convex ERM algorithm. Our accuracy bound is \(O{\frac{\sqrt{d}}{n \rho \epsilon }} = O{\frac{\epsilon }{k \sqrt{d}}}\) , which is smaller than that of [1]}, when \(\frac{\epsilon }{k \sqrt{d}} \le {\frac{\sqrt{d}}{n k \epsilon }}^{2/5} \iff \epsilon ^7 \le \frac{\sqrt{d}^7 k^3}{n^2} \iff \epsilon \le \frac{\sqrt{d}k^{3/7}}{n^{2/7}}\) . Hence in regimes where the unlearning parameter \(\epsilon \)  is small enough, which corresponds to a stronger unlearning criterion, this algorithm is better than that of [1]}.
