Differentially Private Empirical Risk Minimization Revisited: Faster and\n More General

Abstract

In this paper we study the differentially private Empirical Risk Minimization\n(ERM) problem in different settings. For smooth (strongly) convex loss function\nwith or without (non)-smooth regularization, we give algorithms that achieve\neither optimal or near optimal utility bounds with less gradient complexity\ncompared with previous work. For ERM with smooth convex loss function in\nhigh-dimensional ($p\\gg n$) setting, we give an algorithm which achieves the\nupper bound with less gradient complexity than previous ones. At last, we\ngeneralize the expected excess empirical risk from convex loss functions to\nnon-convex ones satisfying the Polyak-Lojasiewicz condition and give a tighter\nupper bound on the utility than the one in \\cite{ijcai2017-548}.\n