Private Linear Regression via a Down-Sensitivity to Privacy Reduction

摘要

We present a sample- and time-efficient (ε,δ)-differentially private (DP) algorithm for d-dimensional linear regression with a sample complexity of n_STAR = O(d/α^2 + d log(1/δ)/αε + d log(1/δ)/ε) + o(d). This improves upon prior polynomial-time algorithms whose sample complexity either depends on the condition number of the design matrix κ (for DP-SGD with gradient clipping), scales quadratically with the dimension (for Sum-of-Squares algorithms) or with the inverse of the privacy parameter (for outlier removal algorithms such as insufficient statistics perturbation or ISSP), n_SoS = Ω(d^2/α^2), n_DPSGD = Ω(d √(κ)/ε), n_ISSP = Ω(d/ε^2). Our algorithm is based on a novel subsample-test-aggregate (STA) approach for ensuring privacy given only bounded down-sensitivity – robustness to removal, but not addition, of a small number of samples. The intuition that down-sensitivity should be related to privacy is not new, but STA formalizes this by providing an efficient black-box reduction from down-sensitivity to privacy which we expect to be applicable beyond the setting of linear regression.