To demonstrate the generality of our framework, we give two more algorithms. The first is noisy-m-SGD which is the same as alg:noisy-m-a-sgd but without acceleration, and the second is quantized-m-SGD, based on randomized quantization. We note that both algorithms have worse theoretical guarantees than alg:noisy-m-a-sgd, however the first establishes our claim that acceleration is beneficial, whereas the second shows how a previous work of [1]} for \(k\) -means clustering, can, not only be seen as a special case of our framework, but also extended to general convex risk minimization problems.
Moreover, in the second case, we consider a more general setup of batch edit requests, and show that our techniques are flexible enough to easily generalize to the batch variant.
