Skip to yearly menu bar Skip to main content


Poster

Differentially Private Empirical Risk Minimization Revisited: Faster and More General

Di Wang · Minwei Ye · Jinhui Xu

Pacific Ballroom #67

Keywords: [ Privacy, Anonymity, and Security ] [ Computational Complexity ]


Abstract: In this paper we study differentially private Empirical Risk Minimization(ERM) in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithms which achieve either optimal or near optimal utility bound with less gradient complexity compared with previous work. For ERM with smooth convex loss function in high-dimension($p\gg 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 to Polyak-Lojasiewicz condition and give a tighter upper bound of the utility comparing with the result in \cite{DBLP:journals/corr/ZhangZMW17}.

Live content is unavailable. Log in and register to view live content