Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares

Gavin Brown, Jonathan Hayase, Samuel Hopkins +5

We present a sample- and time-efficient differentially private algorithm for ordinary least squares, with error that depends linearly on the dimension and is independent of the con…