Differentially Private Empirical Risk Minimization Revisited: Faster and More General
Differentially Private Empirical Risk Minimization Revisited: Faster and More General
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Di Wang;Minwei Ye;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Di Wang;Minwei Ye;Jinhui Xu
在本文中，我们研究了在不同的设置不同的私人经验风险最小化（ERM）问题。对于光滑的（强）凸损失函数与或不（非）光滑正则化，我们给出的算法，实现最佳或接近最佳的效用界，与以前的工作相比，梯度复杂度较低。对于高维（$p\gg n$）情形下具有光滑凸损失函数的ERM，我们给出了一个比以往算法具有更小梯度复杂度的上界算法.最后，我们将期望超额经验风险从凸损失函数推广到满足Polyak-Lojasiewicz条件的非凸损失函数，并给出了比文献[ijcai 2017 -548]更严格的效用上界.
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\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 loss functions to non-convex ones satisfying the Polyak-Lojasiewicz condition and give a tighter upper bound on the utility than the one in \cite{ijcai2017-548}.