We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP). This algorithm achieves an approximation ratio arbitrarily close to the best non private approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, this is the first constant-factor approximation algorithm for k-means that requires only one round of communication in the local DP model, positively resolving an open question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible; we demonstrate this by showing that it also yields a similar near-optimal approximation algorithm in the (one-round) shuffle DP model.


翻译:我们为一回合(不互动的)当地差异隐私模式中的 k 手段分组提供了一种近似算法。 这个算法实现了任意接近于最佳非私人近似算法的近似比率,改进了以前已知的仅保证大( 固定的) 近似比率的算法。 此外, 这是K 手段的第一个恒定因素近似算法, 只需要本地DP 模式的一回合通信, 就能正面解决 Stemmer (SODA 2020) 的未决问题 。 我们的算法框架相当灵活; 我们通过显示它在( 一回合) 的 DP 模式中也产生类似的近乎最佳的近似近似算法来证明这一点 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年9月7日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Xgboost算法——Kaggle案例
R语言中文社区
13+阅读 · 2018年3月13日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Sublinear Regret for Learning POMDPs
Arxiv
0+阅读 · 2021年7月8日
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月5日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年9月7日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Xgboost算法——Kaggle案例
R语言中文社区
13+阅读 · 2018年3月13日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员