We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i) (nearly) optimal sample complexity for matrix completion (in terms of number of items, users), and ii) the best known privacy/utility trade-off both theoretically, as well as on benchmark data sets. In particular, we provide the first global convergence analysis of ALS with noise introduced to ensure DP, and show that, in comparison to the best known alternative (the Private Frank-Wolfe algorithm by Jain et al. (2018)), our error bounds scale significantly better with respect to the number of items and users, which is critical in practical problems. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, thus promising to be the first practical DP embedding model.
翻译:我们研究了用户隐私下不同私人(DP)矩阵完成问题。我们设计了流行的交替-Least-Squares(ALS)方法的不同私人混合变体,实现:(一) (接近) 矩阵完成的最佳样本复杂性(在项目数量、用户方面),以及(二) 在理论上和在基准数据集方面最已知的隐私/通用权取舍。特别是,我们对ALS的第一次全球趋同分析采用了噪音,以确保DP,并表明,与最已知的替代方法(Jain等人(2018年)的私人Frank-Wolfe算法)相比,我们在项目和用户数量方面的错误界限要大得多,这对实际问题至关重要。对标准基准的广泛验证表明,算法与精心设计的取样程序相结合,比现有技术要准确得多,因此有望成为第一个实际的DP嵌入模型。