Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Di Wang;Marco Gaboardi;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Di Wang;Marco Gaboardi;Jinhui Xu
在本文中，我们重新审视的经验风险最小化问题的非交互式局部模型的差异隐私。在常数或低维（$p\ll n$）的情况下，我们首先证明，如果损失函数是$（\infty，T）$-光滑的，我们可以避免样本复杂度的依赖性，以实现误差$\alpha$，对维数$p$的指数的依赖性，以$1/\alpha$（{\em即，} $\alpha^{-p}$），它回答了\cite{smith 2017 interaction}中的一个问题。我们的方法是基于多项式逼近。然后，我们提出了玩家有效的算法与$1$位的通信复杂度和$O（1）$的计算成本为每个球员。误差界是渐近相同的原始。在一些额外的假设下，我们还给出了一个有效的算法。在高维（$n\ll p$）的情况下，我们证明了如果损失函数是凸广义线性函数，则误差可以通过使用约束集的高斯宽度而不是$p$来有界，这改进了\cite{smith 2017 interaction}中的一个。
In this paper, we revisit the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensions ($p\ll n$), we first show that if the loss function is $(\infty, T)$-smooth, 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 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. With some additional assumptions, we also give an efficient algorithm for the server. In the case of high dimensions ($n\ll p$), we show that if the loss function is a convex generalized linear function, the error can be bounded by using the Gaussian width of the constrained set, instead of $p$, which improves the one in \cite{smith2017interaction}.