Reviews: Differentially Private Empirical Risk Minimization Revisited: Faster and More General

Summary: A large number of machine learning models are trained on potentially sensitive data, and it is often import to guarantee privacy of the training data. Chaudhuri and Monteleoni formulated the differentially private ERM problem and started a line of work on designing differentially private optimization algorithms for variants of ERM problems. Recent works have gotten nearly optimal tradeoffs between the additional error introduced by the DP algorithm (the privacy risk) and the privacy parameter, for a large class of settings. In this work, these results are improved in the additional axis of computational efficiency. For smooth and strongly convex losses, this work gets privacy risk bounds that are essentially the best known, but do so at a computational cost that is essentially (n \kappa) gradient computaitons, instead of n\kappa, where \kappa is the condition number.