For Algorithm REF , we can similarly search in constant time whether the deleted point was used in any iteration or not.
For every iteration in which the deleted point is in the mini-batch, we need to compute a gradient at a new point, so as to replace the deleted point. Sampling a point uniformly from a discrete universe takes linear time (in the size) in the worst case, but with some pre-processing can be done in logarithmic/constant time. For example, when saving the mini-batch indices \(b_t\) , if we save a sorted list of the indices not sampled, using binary search, we can sample in \(O(\log {n-(m-1)})\)  time. The more efficient way is, if we save a probability table, then we can use Alias method to sample in \(O(1)\)  time [1]}. Hence for such iterations, we query two gradients, and it takes \(O(d)\)  compute to add/subtract this gradients.
Since the total number of iterations in which a deleted point was sampled in, in expectation, is \(\frac{Tm}{n}\) , the expected total compute is \(\frac{Tm(\mathfrak {G}+d)}{n}\) .
