Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares

arXiv:2404.15409v1 Announce Type: new
Abstract: 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 condition number of $X^\top X$, where $X$ is the design matrix. All prior private algorithms for this task require either $d^{3/2}$ examples, error growing polynomially with the condition number, or exponential time. Our near-optimal accuracy guarantee holds for any dataset with bounded statistical leverage and bounded residuals. Technically, we …

abstract algorithm algorithms arxiv cs.cr cs.lg design error independent least matrix ordinary prior sample squares statistics stat.ml type