Private stochastic convex optimization: optimal rates in linear time
Vitaly Feldman, Tomer Koren, Kunal Talwar · 2020
We study differentially private (DP) algorithms for stochastic convex optimization: the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. (2019) has established the optimal bound on the excess population loss achievable given n samples. Unfortunately, their algorithm achieving this bound is relatively inefficient: it requires O(min{n 3/2, n 5/2/d}) gradient computations, where d is the dimension of the optimization problem.