Efficient Empirical Risk Minimization with Smooth Loss Functions in Non-interactive Local Differential Privacy
Efficient Empirical Risk Minimization with Smooth Loss Functions in Non-interactive Local Differential Privacy
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Di Wang;Marco Gaboardi;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Di Wang;Marco Gaboardi;Jinhui Xu
本文研究了非交互局部差分隐私模型中的经验风险最小化问题。我们首先证明，如果ERM损失函数是$（\infty，T）$-光滑的，那么我们可以避免样本复杂度的依赖性，以实现误差$\alpha$，对以1/\alpha$（{\em即，} $\alpha^{-p}$），它回答了\cite{smith 2017 interaction}中的一个问题。我们的方法是基于伯恩斯坦多项式逼近。然后，我们提出了玩家有效的算法与$1$位的通信复杂度和$O（1）$的计算成本为每个球员。误差界是渐近相同的原始。此外，与额外的假设，我们展示了一个服务器有效的算法与多项式运行时间。最后，我们提出了（有效的）非交互式局部差分私有算法，基于不同类型的多项式近似，学习的k路边缘查询集和光滑查询集。
In this paper, we study the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. We first show that if the ERM loss function is $(\infty, T)$-smooth, then we can avoid a dependence of the sample complexity, to achieve error $\alpha$, on the exponential of the dimensionality $p$ with base $1/\alpha$ ({\em i.e.,} $\alpha^{-p}$), which answers a question in \cite{smith2017interaction}. Our approach is based on Bernstein polynomial approximation. Then, we propose player-efficient algorithms with $1$-bit communication complexity and $O(1)$ computation cost for each player. The error bound is asymptotically the same as the original one. Also with additional assumptions we show a server efficient algorithm with polynomial running time. At last, we propose (efficient) non-interactive locally differential private algorithms, based on different types of polynomial approximations, for learning the set of k-way marginal queries and the set of smooth queries.