Differentially Private Ordinary Least Squares
Or Sheffet
Abstract
Linear regression is one of the most prevalent techniques in machine learning; however, it is also common to use linear regression for its explanatory capabilities rather than label prediction. Ordinary Least Squares (OLS) is often used in statistics to establish a correlation between an attribute (e.g. gender) and a label (e.g. income) in the presence of other (potentially correlated) features. OLS assumes a particular model that randomly generates the data, and derives $t$ -values — representing the likelihood of each real value to be the true correlation. Using $t$ -values, OLS can release a confidence interval, which is an interval on the reals that is likely to contain the true correlation; and when this interval does not intersect the origin, we can reject the null hypothesis as it is likely that the true correlation is non-zero. Our work aims at achieving similar guarantees on data under differentially private estimators. First, we show that for well-spread data, the Gaussian Johnson-Lindenstrauss Transform (JLT) gives a very good approximation of $t$ -values; secondly, when JLT approximates Ridge regression (linear regression with $l_{2}$ -regularization) we derive, under c
中文速览
传统普通最小二乘法（Ordinary Least Squares, OLS）被社会科学广泛用于推断某个变量与结果之间的相关性，但当数据涉及个人隐私时，如何在保护隐私的同时仍能做出可靠的统计推断，始终是个未解难题。本文首次系统分析了在差分隐私（differential privacy）约束下进行OLS统计推断的可行性，核心工具是高斯Johnson-Lindenstrauss变换（JLT）和"Analyze Gauss"算法——前者通过随机投影压缩数据，后者对协方差矩阵添加高斯噪声。研究证明，对于分布足够分散的数据，JLT能很好地近似OLS的t值，进而给出置信区间并判断相关性的正负；在附加一定条件下，对岭回归（Ridge regression）和Analyze Gauss算法同样推导出了置信区间。结果显示，引入隐私保护后，正确拒绝零假设所需的样本量仅增加约 $\tilde{O}(\sqrt{N_0}\cdot\kappa/\epsilon)$，代价可控，这为在真实隐私场景下用线性回归做因果与相关性推断提供了首个严格的理论保障。
原文 arXiv:1507.02482;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1507.02482v4