We study the canonical statistical estimation problem of linear regression from $n$ i.i.d.~examples under $(\varepsilon,\delta)$-differential privacy when some response variables are adversarially corrupted. We propose a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves a near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both $(\varepsilon,\delta)$-DP and robustness. Synthetic experiments confirm the superiority of our approach.
翻译:我们研究从美元(i.d.d.)到美元(\\varepsilon,\delta)以美元为单位的线性回归的理论统计估计问题,当一些响应变量受到对抗性腐蚀时,我们研究了以美元(\\varepsilon,\delta)为单位的不同隐私为单位的线性回归。我们提出了一种流行的私人随机梯度下降算法(DP-SGD)的变种,有两种创新:一种全包梯度下降,以提高样本复杂性,一种新颖的适应性剪辑,以保证稳健。在没有对抗性腐败的情况下,这种算法将改进现有的最新方法,并达到接近最佳的样本复杂性。在标签腐败下,这是第一个保证美元(\varepsilon,\delta)的美元(DP)和稳健的高效线性回归算法。合成实验证实了我们方法的优越性。