We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm with adaptive stepsizes, as well as the AdaGrad algorithm. We provide upper bounds on the regret of both algorithms and show that the bounds are (worst-case) optimal. As a consequence of our development, we show that our private versions of AdaGrad outperform adaptive SGD, which in turn outperforms traditional SGD in scenarios with non-isotropic gradients where (non-private) Adagrad provably outperforms SGD. The major challenge is that the isotropic noise typically added for privacy dominates the signal in gradient geometry for high-dimensional problems; approaches to this that effectively optimize over lower-dimensional subspaces simply ignore the actual problems that varying gradient geometries introduce. In contrast, we study non-isotropic clipping and noise addition, developing a principled theoretical approach; the consequent procedures also enjoy significantly stronger empirical performance than prior approaches.


翻译:我们研究有差别的私人二次曲线优化的适应方法,提出并分析具有适应性阶梯和AdaGrad算法的软体渐变法(SGD)的有差别的私人变体,提出并分析具有适应性阶梯的软体渐变法和AdaGrad算法。我们提供了两种算法的遗憾的上限,并表明界限是(最差的)最佳的。由于我们的发展,我们显示我们的AdaGrad的私人版本优于适应性适应性 SGD,这反过来又优于传统的SGD,在(非私人)Adagrad可明显优于SGD的非异性梯度梯度的假想情况中,在(非私人)Adadadadad可明显优于SGD。主要挑战在于,在高维度问题的梯度几何测中,偏度测法中通常增加的偏移噪音在信号中占主导地位;为此有效优化低度子空间的方法只是忽略了不同的梯度所引入的实际问题。相比之下,我们研究非热带剪裁剪和噪音添加了原则理论方法;随后的程序也比以往的经验表现要大得多。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
最新《神经架构搜索NAS》教程,33页pdf
专知会员服务
26+阅读 · 2020年12月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
12+阅读 · 2021年3月24日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员