On Sparse Linear Regression in the Local Differential Privacy Model
On Sparse Linear Regression in the Local Differential Privacy Model
复制标题
DOI：
10.1109/tit.2020.3040406
复制
发表时间：
2021-02-01
影响因子：
2.5
通讯作者：
Xu, Jinhui
中科院分区：
文献类型：
--
作者：
Wang, Di;Xu, Jinhui
本文研究了局部差分隐私（LDP）模型下的稀疏线性回归问题。我们首先表明，多项式依赖于空间的维数p是不可避免的非交互式和顺序交互式局部模型的估计误差，如果需要保护整个数据集的隐私。类似的限制也存在于其他类型的误差测量和放松的局部模型。这表明，在高维空间中的差分隐私是不可能实现的问题。了解这个限制，我们然后提出两个算法的结果。第一个是一个顺序交互式LDP算法的低维稀疏的情况下，称为局部差分私有迭代硬存储（LDP-IHT），它实现了一个接近最优的上限。该算法实际上是相当通用的，可以用来解决相当多的其他问题，如（本地）DP-ERM与稀疏约束和稀疏回归与非线性测量。第二种是受限（高维）情况，其中仅需要保留响应（标签）的隐私。对于这种情况，我们证明了误差估计的最佳速率可以在数学上依赖于p（即，log p），其中通过LDP-IHT的标签隐私版本获得上限。在真实的世界和合成数据集上的实验证实了我们的理论分析。
In this paper, we study the sparse linear regression problem under the Local Differential Privacy (LDP) model. We first show that polynomial dependency on the dimensionality p of the space is unavoidable for the estimation error in both non-interactive and sequential interactive local models, if the privacy of the whole dataset needs to be preserved. Similar limitations also exist for other types of error measurements and in the relaxed local models. This indicates that differential privacy in high dimensional space is unlikely achievable for the problem. With the understanding of this limitation, we then present two algorithmic results. The first one is a sequential interactive LDP algorithm for the low dimensional sparse case, called Locally Differentially Private Iterative Hard Thresholding (LDP-IHT), which achieves a near optimal upper bound. This algorithm is actually rather general and can be used to solve quite a few other problems, such as (Local) DP-ERM with sparsity constraints and sparse regression with non-linear measurements. The second one is for the restricted (high dimensional) case where only the privacy of the responses (labels) needs to be preserved. For this case, we show that the optimal rate of the error estimation can be made logarithmically dependent on p (i.e., log p) in the local model, where an upper bound is obtained by a label-privacy version of LDP-IHT. Experiments on real world and synthetic datasets confirm our theoretical analysis.