Differentially Private Empirical Risk Minimization Revisited: Faster and More General
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}.
Cite
Text
Wang et al. "Differentially Private Empirical Risk Minimization Revisited: Faster and More General." Neural Information Processing Systems, 2017.Markdown
[Wang et al. "Differentially Private Empirical Risk Minimization Revisited: Faster and More General." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/wang2017neurips-differentially/)BibTeX
@inproceedings{wang2017neurips-differentially,
title = {{Differentially Private Empirical Risk Minimization Revisited: Faster and More General}},
author = {Wang, Di and Ye, Minwei and Xu, Jinhui},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {2722-2731},
url = {https://mlanthology.org/neurips/2017/wang2017neurips-differentially/}
}