Timezone: »

 
Poster
Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency
Xiyang Liu · Prateek Jain · Weihao Kong · Sewoong Oh · Arun Suggala

Wed Dec 13 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1524
in Poster Session 3 »
We study the canonical problem of linear regression under $(\varepsilon,\delta)$-differential privacy when the datapoints are sampled i.i.d.~from a distribution and a fraction of response variables are adversarially corrupted. We provide the first provably efficient -- both computationally and statistically -- method for this problem, assuming standard assumptions on the data distribution. Our algorithm is a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two key innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. Our method requires only linear time in input size, and still matches the information theoretical optimal sample complexity up to a data distribution dependent condition number factor. Interestingly, the same algorithm, when applied to a setting where there is no adversarial corruption, still improves upon the existing state-of-the-art and achieves a near optimal sample complexity.

Author Information

Xiyang Liu (University of Washington)
Prateek Jain (Google Research)
Weihao Kong (Google Research)
Sewoong Oh (University of Washington)
Arun Suggala (Google)

More from the Same Authors