Linear regression is one of the most prevalent techniques in data analysis. Given a large collection of samples composed of features x x x and a label y, linear regression is used to find the best prediction of the label as a linear combination of the features. 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 uses linear regression in order to estimate the correlation between the label and a feature x j on a given dataset; and then, under the assumption of a certain random generative model for the data, OLS outputs an interval on the reals that is likely to contain the correlation between y and x j in the underlying distribution (a confidence interval ). When this interval does not intersect the origin, we can reject the null hypothesis as it is likely that x j indeed has a non-zero correlation with y. Our work aims at achieving similar guarantees on data under differential privacy. We use the Gaussian Johnson-Lindenstrauss transform, which has been shown to satisfy differential privacy if the given data has large singular values [BBDS12] . We analyze the result of projecting the data using the JL transform under the OLS model and show how to approximate confidence intervals using only the projected data. We also bound the number of samples needed to reject the null hypothesis with differential privacy, when the data is drawn i.i.d from a multivariate Gaussian. When not all singular values of the data are sufficiently large, we alter the input and increase its singular values and then project it using a JL transform. Thus our projected data yields an approximation for the Ridge Regression problem -a variant of the linear regression that uses a l 2 -regularization term. We give conditions under which the regularized problem is still helpful in establishing correlations. Since the early days of differential privacy, its main goal was to design privacy preserving versions of existing techniques for data analysis. It is therefore no surprise that several of the first differentially private algorithms were machine learning algorithms [BDMN05, KLN + 08] and among them private linear regression [CMS11, KST12, BST14]. After all, linear regression is extremely prevalent in data analysis. However, there are two drawbacks to the existing techniques. First (and perhaps easier to explain), is that the above-mentioned algorithms are designed for a single linear regression problem: each sample point is composed from (x x x • y) where x x x denotes the problem's features and y denotes the label. Yet in a database D in which each sample has d attributes, we are free to choose any attribute as the label and any subset of the remaining attributes as the problem features. Thus D can allow for exp(d) different linear-regression problems. Naïvely running the above-mentioned algorithms exponentially many times runs into the inevitable problem of privacy-utility tradeoff: the added noise is so big that it obliterates any usefulness in the answer. 1 The second and the more serious drawback of the existing body of work on differentially private linear regression lies in its utility analysis. The utility analysis in these works bounds the expected l 2 -distance between the linear coefficients found by the standard algorithm and the coefficients found by the privacy-preserving version. This is motivated from a machine-learning perspective, since bounds on the difference in the estimators translate to error bounds on prediction (or on the loss function). However, as interesting and (highly) non-trivial as they are, such bounds are of little use in situations where one uses linear regression to establish correlations rather than predict labels. In the statistics literature, linear regression is a technique used to determine the correlation between a variable and an outcome, especially in the presence of others factors, in the Ordinary Least Squares (OLS) model. 2 Social science has been using OLS for nearly a century, in works that range from determining whether Catholics tend to vote for the Democrats in the 1932 elections [GG35], to works that quantify the effect of education on income [Car99], to modern works establishing that Tweeting helps in getting elected for office [DMBR13] . Such works do not aim to use linear regression to predict the label on a new unlabeled batch of samples. Rather they aim to establish the existence of a strong correlation between the label and some feature. Needless to say, in such works, protecting the privacy of the individuals who contributed to the data is an important concern. In order to determine that a certain variable x j is positively (resp. negatively) correlated with an outcome y, OLS assumes a model where the outcome y is a noisy version of a linear mapping of all variables: y = β β β · x x x + e (with e denoting random Gaussian noise) for some predetermined and unknown β β β. Then, given many samples (x x x i , y i ) OLS establishes two things: (i) when fitting a linear function to best predict y from x x x over the sample (via computingβ β β = i x x x i x x x T i −1 ( i y i x x x i )) the coefficientβ j is positive (resp. negative); and (ii) the confidence in havingβ j not far from the true β j is high. In fact, the crux in OLS is in defining the suitable confidence interval -the interval 1 Indeed, Ullman [Ull15] has devised a solution to this problem based on the Iterative-Database Construction of [GRU12], but this solution works in the more-cumbersome online model and requires exponential running-time for the curator; whereas our technique is computationally tractable and works in the offline model. 2 And so, in this paper, we draw a distinction between "linear regression," by which we refer to the machine learning technique of finding a specific estimator for a specific loss function; and the "Ordinary Least Squares" model, by which we refer to a specific generative model for the data which is solved using the linear regression technique. Algorithm 1: Outputting a private Johnson-Lindenstrauss projection of a matrix. Input: A matrix A ∈ R n×d and a bound B > 0 on the l 2 -norm of any row in A. Privacy parameters: ǫ, δ > 0. Parameter r indicating the number of rows in the resulting matrix.
In the context of model coefficients, Sheffet REF studied ( , δ)-differentially private Ordinary Least Squares Regression (OLS) and generated confidence intervals for the parameters.
Differentially Private Ordinary Least Squares
ICML 2017
arXiv: Data Structures and Algorithms
Mathematics Computer Science