Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training
Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training
复制标题
具有改进的群体损失界限、运行时间和私人对抗训练应用的差分私人凸优化的输出扰动
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Meisam Razaviyayn
中科院分区：
文献类型：
--
作者：
Andrew Lowy;Meisam Razaviyayn
在现代机器学习中，找到具有强大多余风险界限的有效，易于实现的私人（DP）算法是一个重要的问题。迄今为止，大多数工作都集中在私人经验风险最小化（ERM）或私人人口损失最小化上。但是，通常还有其他目标 - 例如公平性，对抗性鲁棒性或对异常值的敏感性 - 平均表现在经典的ERM设置中未捕获。为此，我们研究了一个完全一般的凸，Lipschitz损失功能的家族，并建立了首个已知的DP多余风险和运行时界，以优化这一广泛类别。我们在平滑度和/或强凸度的其他假设下提供类似的界限。我们还谈到了私人随机凸优化（SCO）。虽然$（\ epsilon，\ delta）$ - dp（$ \ delta> 0 $）一直是私人SCO最近工作的重点，证明了人口损失界限和运行时界限，$（\ epsilon，0）$ - - DP仍然是一个具有挑战性的开放问题。我们提供最紧张的$（\ epsilon，0）$ - DP人口损失界限，并且在存在（或缺乏）平滑度和强大的凸度的情况下最快的运行时间。我们的方法扩展到$ \ delta> 0 $设置，我们提供了独特的好处，即通过合并一种新形式的高斯噪声来确保任意$ \ epsilon> 0 $的差异隐私。最后，我们将理论应用于两个学习框架：倾斜的ERM和对抗性学习。特别是，我们的理论量化了对抗性鲁棒性，隐私和运行时之间的权衡。我们的结果是使用最简单的DP算法来实现的：输出扰动。尽管这种方法在概念上不是新颖的，但我们的新颖实施方案和分析表明，实现强大隐私，实用性和运行时保证的力量在先前的工作中尚未得到充分的理解。
Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. To date, most work has focused on private empirical risk minimization (ERM) or private population loss minimization. However, there are often other objectives--such as fairness, adversarial robustness, or sensitivity to outliers--besides average performance that are not captured in the classical ERM setup. To this end, we study a completely general family of convex, Lipschitz loss functions and establish the first known DP excess risk and runtime bounds for optimizing this broad class. We provide similar bounds under additional assumptions of smoothness and/or strong convexity. We also address private stochastic convex optimization (SCO). While $(\epsilon, \delta)$-DP ($\delta>0$) has been the focus of much recent work in private SCO, proving tight population loss bounds and runtime bounds for $(\epsilon, 0)$-DP remains a challenging open problem. We provide the tightest known $(\epsilon, 0)$-DP population loss bounds and fastest runtimes under the presence of (or lack of) smoothness and strong convexity. Our methods extend to the $\delta>0$ setting, where we offer the unique benefit of ensuring differential privacy for arbitrary $\epsilon>0$ by incorporating a new form of Gaussian noise. Finally, we apply our theory to two learning frameworks: tilted ERM and adversarial learning. In particular, our theory quantifies tradeoffs between adversarial robustness, privacy, and runtime. Our results are achieved using perhaps the simplest DP algorithm: output perturbation. Although this method is not novel conceptually, our novel implementation scheme and analysis show that the power of this method to achieve strong privacy, utility, and runtime guarantees has not been fully appreciated in prior works.