Private Stochastic Non-convex Optimization with Improved Utility Rates
Private Stochastic Non-convex Optimization with Improved Utility Rates
复制标题
DOI：
10.24963/ijcai.2021/464
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Qiuchen Zhang;Jing Ma;Jian Lou;Li Xiong
中科院分区：
文献类型：
--
作者：
Qiuchen Zhang;Jing Ma;Jian Lou;Li Xiong
我们研究差分私人（DP）的随机非凸优化，重点是其研究不足的效用措施的预期超额经验和人口风险。凸优化中的超额风险问题已经得到了广泛的研究，而非凸优化中的超额风险问题，尤其是期望种群风险问题，却很少被研究。对于凸情况，最近的研究表明，在某些条件下，私人优化有可能实现与非私人优化相同数量级的超额人口风险。对于非凸情形，这种理想的超额人口风险是否可以实现仍然是一个悬而未决的问题。在本文中，我们对这个开放问题的肯定回答取得了进展：DP非凸优化确实能够在某些条件下（即，条件良好的非凸性）。我们实现了这样的改进效用率相比，现有的结果，通过设计和分析的阶段DP-SGD与早期的动量算法。我们同时获得超额经验风险和超额人口风险，以实现差异隐私。我们的算法还具有第一个已知的DP-SGD动量过剩和人口风险的结果。分别应用于简单和复杂真实的数据集的浅层和深层神经网络的实验结果证实了理论结果。
We study the differentially private (DP) stochastic nonconvex optimization with a focus on its under-studied utility measures in terms of the expected excess empirical and population risks. While the excess risks are extensively studied for convex optimization, they are rarely studied for nonconvex optimization, especially the expected population risk. For the convex case, recent studies show that it is possible for private optimization to achieve the same order of excess population risk as to the nonprivate optimization under certain conditions. It still remains an open question for the nonconvex case whether such ideal excess population risk is achievable. In this paper, we progress towards an affirmative answer to this open problem: DP nonconvex optimization is indeed capable of achieving the same excess population risk as to the nonprivate algorithm in most common parameter regimes, under certain conditions (i.e., well-conditioned nonconvexity). We achieve such improved utility rates compared to existing results by designing and analyzing the stagewise DP-SGD with early momentum algorithm. We obtain both excess empirical risk and excess population risk to achieve differential privacy. Our algorithm also features the first known results of excess and population risks for DP-SGD with momentum. Experiment results on both shallow and deep neural networks when respectively applied to simple and complex real datasets corroborate the theoretical results.