Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget
Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget
复制标题
DOI：
10.1145/3219819.3220076
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Jaewoo Lee;Daniel Kifer
中科院分区：
文献类型：
--
作者：
Jaewoo Lee;Daniel Kifer
迭代算法（例如梯度下降）是解决模型拟合等各种问题的常用工具。出于这个原因，人们有兴趣创建它们的差异化私有版本。然而，它们向差分隐私算法的转换通常是幼稚的。例如，选择固定数量的迭代，将隐私预算平均分配，并且在每次迭代时，用噪声梯度更新参数。在本文中，我们表明可以通过每次迭代更仔细地分配隐私预算来改进基于梯度的算法。直观上，在优化开始时，梯度预计会很大，因此不需要精确测量。然而，当参数接近其最佳值时，梯度会减小，因此需要更准确地测量。我们添加了基本的线搜索功能，帮助算法决定何时需要更准确的梯度测量。我们的梯度下降算法适用于最近推出的 zCDP 版本的差分隐私。它优于现有的模型拟合算法，并且在$(ε,δ)$-差分隐私方面与最先进的算法具有竞争力，这是一个比 zCDP 严格弱的定义。
Iterative algorithms, like gradient descent, are common tools for solving a variety of problems, such as model fitting. For this reason, there is interest in creating differentially private versions of them. However, their conversion to differentially private algorithms is often naive. For instance, a fixed number of iterations are chosen, the privacy budget is split evenly among them, and at each iteration, parameters are updated with a noisy gradient. In this paper, we show that gradient-based algorithms can be improved by a more careful allocation of privacy budget per iteration. Intuitively, at the beginning of the optimization, gradients are expected to be large, so that they do not need to be measured as accurately. However, as the parameters approach their optimal values, the gradients decrease and hence need to be measured more accurately. We add a basic line-search capability that helps the algorithm decide when more accurate gradient measurements are necessary. Our gradient descent algorithm works with the recently introduced zCDP version of differential privacy. It outperforms prior algorithms for model fitting and is competitive with the state-of-the-art for $(ε,δ)$-differential privacy, a strictly weaker definition than zCDP.