Differentially Private Empirical Risk Minimization Revisited: Faster and More General *
In this paper we study the differentially private Empirical Risk Minimization (ERM) problem in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithms that achieve either optimal or near optimal utility bounds with less gradient complexity compared with previous work. For ERM with smooth convex loss function in high-dimensional (p n) setting, we give an algorithm which achieves the upper bound with less gradient complexity than previous ones. At last, we generalize the expected excess empirical risk from convex loss functions to non-convex ones satisfying the PolyakLojasiewicz condition and give a tighter upper bound on the utility than the one in [34].
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. Similar improvements are presented for other
settings of interest, when the loss function is not strongly convex, or when the
constraint set has small complexity.
A different viewpoint on the results is that the authors show that DP noise
addition techniques and modern optimization methods can be made to work well
together. Speficially, one can use SVRG with noise addition at each step and the
authors show that this noisy SVRG also gets near optimal privacy risk. Similarly
for the case of constraint sets with small Gaussian width (such as l_1), where
previous work used noisy mirror descent, the authors show that one can use an
accelerated noisy mirror descent and get faster runtimes without paying in the
privacy cost.
I think the problem is very important and interesting. While the tools are somewhat
standard, I think this paper advances the state of the art sufficiently that I
am compelled to recommend acceptance.