For the problem of TV stable convex empirical risk minimization, we propose two algorithms: sub-sample-GD and noisy-m-A-SGD. We show that the expected excess empirical risk of noisy-m-A-SGD is better than that of sub-sample-GD, in regimes of small dimension.
The algorithm noisy-m-A-SGD is essentially noisy-m-SGD algorithm, which appeared in [1]} for DP convex ERM, with an additional Nesterov's acceleration on top.
For ease of presentation, we discuss using noisy-m-SGD (no acceleration), and in
paragraph titled "Fast algorithms and maximal coupling" in the next section, it would become clear why adding acceleration helps us.
In noisy-m-SGD,
at iteration \(j\) , we sample a mini-batch \(b_j\)  uniformly randomly, use it to compute the gradient on the previous iterate \(_{j}\)  denoted as \(\nabla \hat{F}_S(_{j},_{b_{j}})\)  and update as follows:
\(_{j+1} = _j - \eta {\nabla \hat{F}_S(_{j},_{b_{j}}) + \theta _t}\) 
