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嵌入模型。

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
专知会员服务
50+阅读 · 2021年8月8日
【Google】梯度下降,48页ppt
专知会员服务
80+阅读 · 2020年12月5日
一份循环神经网络RNNs简明教程,37页ppt
专知会员服务
172+阅读 · 2020年5月6日
专知会员服务
159+阅读 · 2020年1月16日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
学术报告|港科大助理教授宋阳秋博士
科技创新与创业
7+阅读 · 2019年7月19日
度量学习中的pair-based loss
极市平台
65+阅读 · 2019年7月17日
已删除
将门创投
11+阅读 · 2019年7月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Differentially Private Quantiles
Arxiv
0+阅读 · 2021年9月20日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
学术报告|港科大助理教授宋阳秋博士
科技创新与创业
7+阅读 · 2019年7月19日
度量学习中的pair-based loss
极市平台
65+阅读 · 2019年7月17日
已删除
将门创投
11+阅读 · 2019年7月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员