We study the problem of privacy-preserving collaborative filtering where the objective is to reconstruct the entire users-items preference matrix using a few observed preferences of users for some of the items. Furthermore, the collaborative filtering algorithm should reconstruct the preference matrix while preserving the privacy of each user. We study this problem in the setting of joint differential privacy where each user computes her own preferences for all the items, without violating privacy of other users' preferences. We provide the first provably differentially private algorithm with formal utility guarantees for this problem. Our algorithm is based on the Frank-Wolfe (FW) method, and consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. We also empirically evaluate our FW-based algorithm on a suite of datasets, and show that our method provides nearly same accuracy as the state-of-the-art non-private algorithm, and outperforms the state-of-the-art private algorithm by as much as 30%.

该研究提供了第一个具有正式效用保证的证明联合差分隐私算法，用于处理用户级别的隐私保护协同过滤问题。基于Frank-Wolfe方法，该算法可以一致地估计潜在的偏好矩阵，只要用户数量$m$大于$\omega{(n^{5/4})}$，其中$n$是物品数量，每个用户提供至少$\sqrt{n}$个随机选择的偏好物品。在此过程中，我们提供了一种基于著名的Oja方法的奇异向量计算的最优差分隐私算法，它在操作稀疏矩阵时具有显着的节省空间和时间的优势。我们还通过一系列数据集对算法进行了实证评估，并展示了它始终优于最先进的隐私算法。

再谈差分隐私矩阵补全