In this paper we tackle the challenge of making the stochastic coordinate descent algorithm differentially private. Compared to the classical gradient descent algorithm where updates operate on a single model vector and controlled noise addition to this vector suffices to hide critical information about individuals, stochastic coordinate descent crucially relies on keeping auxiliary information in memory during training. This auxiliary information provides an additional privacy leak and poses the major challenge addressed in this work. Driven by the insight that under independent noise addition, the consistency of the auxiliary information holds in expectation, we present DP-SCD, the first differentially private stochastic coordinate descent algorithm. We analyze our new method theoretically and argue that decoupling and parallelizing coordinate updates is essential for its utility. On the empirical side we demonstrate competitive performance against the popular stochastic gradient descent alternative (DP-SGD) while requiring significantly less tuning.
翻译:在本文中,我们处理使随机协调的下降算法具有不同私密性的挑战。与古典的梯度下降算法相比,在一种单一的模型矢量上进行更新,并在此矢量上增加受控的噪音足以隐藏关于个人的重要信息,这种随机协调的下降关键地依赖于在培训期间将辅助信息保存在记忆中。这种辅助信息提供了额外的隐私泄漏,并构成了这项工作中处理的主要挑战。我们之所以提出这种观点,是因为在独立噪声添加下,辅助信息的一致性令人期待,我们提出了DP-SCD,这是第一个差异化的私人随机协调的下降算法。我们从理论上分析了我们的新方法,并论证脱钩和平行协调更新对于其效用至关重要。在经验方面,我们展示了与流行的随机梯度梯度下降替代方法(DP-SGD)相比的竞争性业绩,而同时要求的调整要少得多。