Private Stochastic Convex Optimization with Optimal Rates
Private Stochastic Convex Optimization with Optimal Rates
复制标题
DOI：
--
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Raef Bassily;V. Feldman;Kunal Talwar;Abhradeep Thakurta
中科院分区：
文献类型：
--
作者：
Raef Bassily;V. Feldman;Kunal Talwar;Abhradeep Thakurta
研究了随机凸优化问题的差分隐私算法。在这个问题中，目标是近似最小化给定i.i.d.~样本来自凸和Lipschitz损失函数的分布。现有的一长串关于私有凸优化的工作集中在经验损失上，并推导出超额经验损失的渐近紧界。然而，已知的种群损失界限存在显着差距。我们发现，对数因子，DP算法的最佳过剩人口损失等于较大的最佳非私人过剩人口损失，和DP算法的最佳过剩经验损失。这意味着，相反的直觉基于私人的ERM，私人SCO有渐近相同的利率为1美元/\sqrt{n}$的非私人SCO的参数制度在实践中最常见的。此设置中的最佳先前结果给出$1/n^{1/4}$的速率。我们的方法建立在现有的差分隐私算法，并依赖于算法的稳定性分析，以确保泛化。
We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d.~samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of $1/\sqrt{n}$ as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of $1/n^{1/4}$. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.