Aside from extending the analysis of this approach to population loss, we show that it can lead to algorithms for private SCO that use only near-linear number of gradient evaluations (whenever these assumptions hold).
we give a variant of objective perturbation in conjunction with the stochastic variance reduced gradient descent (SVRG) with only O(n log n) gradient evaluations.