PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression

Or Sheffet

arXiv:1507.00056v2cs.DS

TL;DR

The paper addresses private linear regression when existing methods handle one regression at a time and private matrix approximations may not be positive definite. It develops three private 2nd-moment-matrix approximation techniques based on regression methods and compares them with Analyze Gauss. The comparison varies by setting: Analyze Gauss is best for a simple single regression at sufficiently large n, while the proposed algorithms have smaller errors for multiple regressions with small singular values unless n is extremely large.

  • Problem

    Existing differentially private linear-regression techniques handle one regression at a time, and Analyze Gauss does not necessarily output a positive-definite matrix.

    Source: §1 · pp. 1–2

  • Method

    The paper develops three differentially private 2nd-moment-matrix approximations corresponding to existing regression techniques, including privacy-calibrated Ridge regression and inverse-Wishart posterior sampling.

    Source: §1 · pp. 2–3, §3 · p. 5

  • Results

    Analyze Gauss is clearly best for a simple single-regression case once n is sufficiently large, but the proposed algorithms achieve smaller errors for multiple regressions with small singular values unless n is extremely large.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The proposed techniques provide positive-definite private matrix approximations whose relative performance against Analyze Gauss depends on the regression setting and sample size.

    Source: §1 · pp. 2–3

    The authors leave regression over data with large correlations between multiple columns as an open question and report that their Lasso experiments were not extensive.

    Source: §6.2 · p. 14

Abstract

from arXiv · show

We introduce three differentially-private algorithms that approximates the 2nd-moment matrix of the data. These algorithm, which in contrast to existing algorithms output positive-definite matrices, correspond to existing techniques in linear regression literature. Specifically, we discuss the following three techniques. (i) For Ridge Regression, we propose setting the regularization coefficient so that by approximating the solution using Johnson-Lindenstrauss transform we preserve privacy. (ii) We show that adding a small batch of random samples to our data preserves differential privacy. (iii) We show that sampling the 2nd-moment matrix from a Bayesian posterior inverse-Wishart distribution is differentially private provided the prior is set correctly. We also evaluate our techniques experimentally and compare them to the existing "Analyze Gauss" algorithm of Dwork et al.

1 Introduction

The paper studies private approximations of the data’s 2nd-moment matrix for linear regression, addressing the limits of regression-specific methods and the lack of guaranteed positive-definite outputs. It develops three approaches based on existing regression techniques and compares them with Analyze Gauss.

1 Introduction

  • Existing private linear-regression techniques address one regression at a time, while approximating the 2nd-moment matrix can support many regressions and can yield positive-definite outputs.Analyze Gauss does not necessarily output a positive-definite matrix; the paper notes this can be detrimental, even after projection.Source: §1 · pp. 1–2
  • An existing solution to the many-regression problem uses the more cumbersome online model and requires exponential curator running time, whereas these techniques use an offline approach.The cited solution is attributed to Ullman [Ull15].Source: §1 · p. 1
  • The paper presents three differentially private techniques for approximating the 2nd-moment matrix, analyzes their utility, and compares them with Analyze Gauss.The techniques correspond to existing methods in linear-regression literature.Source: §1 · p. 2
  • For Ridge Regression, the authors set the regularization coefficient to preserve privacy while using a Johnson-Lindenstrauss transform to approximate the solution.They improve the prior analysis by reducing the required lower bound on σmin(A) by a factor of log(r).Source: §1 · p. 2
  • Adding Wishart noise to A^TA corresponds to appending A with k independent Gaussian samples, extending the Ridge-regression interpretation to random examples.The expected noise is kV, enabling post-processing by subtracting kV.Source: §1 · p. 2
  • Sampling from an inverse-Wishart posterior is (ϵ, δ)-differentially private when the prior is sufficiently spread, giving a third approach to approximating A^TA.This extends the focus of Vadhan and Zheng [VZ15] from estimating the mean to estimating variances or the 2nd moment.Source: §1 · pp. 2–3
  • For multiple regressions with small singular values, our algorithms achieve smaller errors than Analyze Gauss unless n is extremely large; for the simple single-regression case, Analyze Gauss is clearly best once n is sufficiently large.The authors describe the experiments as preliminary proof-of-concept and say more evaluation is needed.Source: §1 · p. 3
  • The JL privacy analysis studies the specific repeated projection rather than applying the standard composition theorem, obtaining a bound dependent on O(√r) instead of O(√r log(r)).The proof combines determinant and exponent contributions to the Gaussian density ratio before bounding the resulting exponent.Source: §1 · p. 3

2 Preliminaries and Notation

This section establishes notation and the distributions and privacy concepts used in the paper. It also describes the Analyze Gauss baseline and the paper’s data and neighboring-input setup.

2 Preliminaries and Notation

  • The paper uses lower-case letters for scalars, bold characters for vectors, and uppercase letters for matrices; it denotes spectral and Frobenius norms and the largest and smallest singular values.For a general Johnson-Lindenstrauss transform, the stated guarantee is known only for r = O(d·η^-2), where it preserves all vector lengths in R^d.Source: §2 · pp. 3–4
  • The Wishart distribution describes scatter matrices of independent Gaussian samples and is supported on positive-definite matrices; the inverse-Wishart distribution describes matrices whose inverses are Wishart-distributed.The paper also introduces the χ2 distribution as the squared l2 norm of independent standard normal samples.Source: §2 · p. 4
  • The input is an n × d matrix with rows bounded in l2 norm, and neighboring inputs differ in one row; differential privacy bounds outcome probabilities on neighboring inputs.The formal definition allows parameters ϵ and δ, with δ = 0 corresponding to ϵ-differential privacy.Source: §2 · p. 4
  • Analyze Gauss adds independent Gaussian noise to coordinates of A^TA, with symmetric noise to match the symmetry of the matrix.The cited sensitivity bound is B^4 in squared Frobenius norm.Source: §2 · p. 4

3 Ridge Regression — Set the Regularization Coefficient to Preserve Privacy

The section makes ridge regularization serve as a privacy parameter: a suitable penalty enables a Johnson–Lindenstrauss transform to approximate regression privately. Experiments find that privately estimating the least singular value can improve accuracy at large sample sizes, after initially costing some utility.

3 Ridge Regression — Set the Regularization Coefficient to Preserve Privacy

  • The method appends a regularization matrix, then applies a Johnson–Lindenstrauss transform to approximate the regularized regression while preserving differential privacy.The penalty raises the singular values of the augmented data matrix; the privacy-preserving choice of penalty differs from data-driven choices aimed at minimizing risk.Source: §3 · p. 5
  • Algorithm 2 spends part of the privacy budget estimating the least singular value, enabling a smaller penalty when that value is large.The section also describes using this estimate to choose the transform’s row count and, when the singular value is sufficiently large, to use any non-negative penalty.Source: §3 · p. 5, §3.2 · p. 7

3.2 Experiment on Ridge Regression — Measuring the Effect of Regularization

  • At n = 2^25, Algorithm 2’s mean accuracy was 0.0192 vs. 0.0671 for Algorithm 1 when ϵ = 0.1, and 0.0058 vs. 0.0639 when ϵ = 0.5.Algorithm 2 generally outperformed Algorithm 1 only once n reached 2^19 or 2^20; the non-private estimator was best at every tested n.Source: §3.2 · p. 7, Figure 1 · p. 7

4 Additive Wishart Noise — Regression with Additional Random Examples

The section approximates the second-moment matrix by adding positive-definite Wishart noise, equivalent to appending random Gaussian examples. In experiments, reducing the expected noise shift reduced error, while a Bayesian interpretation of the resulting regression procedure remains unresolved.

4 Additive Wishart Noise — Regression with Additional Random Examples

  • Adding a suitably parameterized Wishart matrix to ATA is (ϵ, δ)-differentially private and corresponds to appending more than d random, independent examples.The added matrix is positive definite and is equivalent to the contribution of k Gaussian samples; the noise depends on the row-norm bound B.Source: §4 · p. 8, §4.1 · p. 8
  • The noise is not simply a Bayesian prior on β, because the algorithm also adds random noise to XTy.For y = 0, the estimator is always zero regardless of the prior, so the authors leave the Bayesian-prior interpretation open.Source: §4 · p. 8

4.1 Experiment on Additive Wishart Noise

  • Reducing the added Wishart noise reduced error, and the shift-corrected estimator consistently outperformed the naïve estimator.Figure 2 compares Algorithm 3, the estimator after deducting the expected shift, and the non-private version across data sizes.Source: §4.1 · p. 9, Figure 2 · p. 9

5 Sampling from an Inverse-Wishart Distribution (Bayesian Posterior)

The section samples the second-moment matrix from an inverse-Wishart Bayesian posterior, with privacy depending on a sufficiently spread prior. Experiments report large errors for both inverse-Wishart algorithms, while the variant with minimum degrees of freedom 2d outperforms the JL comparator across tested sample sizes.

5 Sampling from an Inverse-Wishart Distribution (Bayesian Posterior)

  • The Bayesian procedure assumes i.i.d. Gaussian datapoints with unknown covariance V, updates a prior using the data, and samples from the posterior to estimate V.The method uses an inverse-Wishart posterior, whose scale-matrix prior must have sufficiently large minimum singular value for the sample to be (ϵ, δ)-differentially private.Source: §5 · pp. 9–10
  • Algorithm 5 can estimate the least singular value of ATA and use it to set ψ, paralleling the adaptive parameter choice in the JL approach.The algorithms’ outputs are related to Wishart and inverse-Wishart sampling, respectively.Source: §5 · p. 10

5.1 Experiments on Sampling from the Inverse Wishart Distribution

  • Algorithms 4 and 5 had fairly large errors; Algorithm 5 with minimum degrees of freedom 2d outperformed Algorithm 2 across all tested n.The authors attribute the large errors mainly to ψ depending on n, and report that splitting the privacy budget in Algorithm 5 was consistently costlier than Algorithm 4.Source: §5.1 · p. 11

6 Comparison to the Analyze Gauss Baseline

The experiments compare Analyze Gauss and five alternatives, finding that the winner depends on the regression setting: Analyze Gauss leads for a single regression at sufficiently large sample sizes, while alternatives can do better with multiple regressions.

6 Comparison to the Analyze Gauss Baseline

  • For the six-estimator comparison, Analyze Gauss adds Gaussian noise to ATA, while the alternatives include JL and Wishart-based methods and scaled variants.The experiment also tests a post-processing choice for Analyze Gauss: adding cI with c = E[∥N∥]; alternative tested post-processing approaches performed comparably overall but worse.Source: §6 · pp. 11–12

6.1 The Basic Single-Regression Experiment

  • At sufficiently large n, Analyze Gauss has the smallest l2-distance to the true β in the single-regression experiment.At small n its errors are out of scale, and the other methods also have fairly large errors; Algorithm 5 consistently beats Algorithm 2, though both have the largest variances.Source: §6.1 · p. 13

6.2 The Multiple-Regressions Experiment

  • The multiple-regression experiment uses 20 independent features and 20 generated features, then varies the sample size n and the number m of additional y-features in each regression.The target coefficients should be roughly zero on those additional y-features, reflecting the task of identifying relevant and irrelevant features.Source: §6.2 · pp. 13–14
  • For multiple regressions, when m > 0, the scaled Analyze Gauss estimator is consistently worse than the JL variants and scaled additive Wishart noise for n < 2^22.As m increases, errors become large for all algorithms; scaled Analyze Gauss has the smallest variance, while scaled additive Wishart noise also has good variance and outperforms it over a wide range of n.Source: §6.2 · p. 14
  • The authors leave regression over highly correlated columns and finding sparse coefficients with private Gram-matrix approximations as open problems.In limited Lasso experiments, the private-method estimators were sparse across both feature groups, unlike the non-private estimator, which was sparse over the latter m coordinates.Source: §6.2 · p. 14

in private data analysis. In TCC, 2006.

The appendix collects mathematical tools used in the privacy proofs, including Gaussian concentration, Wishart matrix bounds, and rank-one update identities. The authors note that most lemmas were known before this work.

A Useful Lemmas

  • Most lemmas in this section were known before this work; the authors include them to provide complete proofs and make no claim of originality.The proofs of Lemma A.1 and Claim A.2 draw partly on Dasgupta and Gupta [DG03] and Wishart results in [MKB79].Source: A Useful Lemmas · p. 17
  • Lemma A.1 bounds how a Gaussian matrix transforms a fixed vector, using concentration of a chi-squared random variable.For a fixed v, the squared norm of Xv, normalized by ∥v∥², follows a chi-squared distribution with r degrees of freedom.Source: A Useful Lemmas · p. 17
  • The appendix uses Wishart eigenvalue bounds and Sherman–Morrison rank-one update formulas among its tools for the privacy proofs.The Wishart construction factors the sampled matrix through Gaussian rows; the rank-one identities give determinant and inverse updates.Source: A Useful Lemmas · pp. 20–21

B Privacy Theorems

The section presents formal privacy proofs for the algorithms, with exact constants chosen with implementation in mind. It also gives a privacy theorem for adding Gaussian noise to the inverse of the data.

B Privacy Theorems

  • The section supplies formal proofs that the algorithms satisfy differential privacy.The authors state that the lemmas and theorems are presented with exact constants rather than asymptotic O(·) notation, because they hope the algorithms will be implemented.Source: B Privacy Theorems · p. 21
  • The proofs track exact constants rather than relying on O(·) notation.The stated motivation is to make the analyses useful for algorithms that may be implemented.Source: B Privacy Theorems · p. 21
  • The section also proves a privacy theorem for an algorithm that adds Gaussian noise to the inverse of the data.The authors note that this result may be of independent interest.Source: B Privacy Theorems · p. 21

B.1 Privacy Proof for Algorithm 1

The proof establishes privacy for a Gaussian Johnson–Lindenstrauss projection under bounded-row and minimum-singular-value conditions. It compares neighboring datasets through rank-one changes and bounds the resulting output distributions.

B.1 Privacy Proof for Algorithm 1

  • If d < r, each row of A has L2-norm at most B, and σmin(A) ≥ w, then publishing R·A for Gaussian R is (ϵ, δ)-differentially private.R is an r × n matrix with independent standard normal entries.Source: §B.1 · p. 21
  • The proof models neighboring datasets as matrices differing in one row and expresses the change in their Gram matrices as a rank-one update.It assumes both neighboring matrices meet the minimum-singular-value bound and that the row difference has norm at most 2B.Source: §B.1 · p. 22
  • After normalizing by (ATA)^−1/2, the proof uses independent standard-Gaussian entries and a Gaussian matrix concentration lemma to bound the projected output.The columns of the normalized matrix are independent, enabling the stated concentration step.Source: §B.1 · pp. 22–23

B.2 Privacy Proof for Algorithm 3

The proof establishes differential privacy for additive Wishart noise by comparing output densities on neighboring datasets. Under bounded row norms and suitable scale and degrees-of-freedom conditions, the released matrix is the data’s second-moment matrix plus Wishart noise.

B.2 Privacy Proof for Algorithm 3

  • With row norms bounded by B, suitable scale matrix V, and sufficient degrees of freedom ν, releasing X = A^T A + N is (ϵ, δ)-differentially private.The theorem requires σmin(V) ≥ C1 and ν ≥ ⌊d + 2C2 ln(4/δ)⌋.Source: §B.2 · p. 24
  • Wishart noise can be generated as the cross-product of a ν-by-d matrix of independent Gaussian samples scaled by B/√ϵ.The resulting noise is added to A^T A.Source: §B.2 · p. 24
  • The proof compares output-density ratios for neighboring datasets that differ in one row, using the shared matrix formed after removing that row.It handles the two neighboring-dataset cases symmetrically and bounds the corresponding terms with high probability.Source: §B.2 · pp. 24–26

B.3 Privacy Proof for Algorithm 4

This proof establishes privacy for sampling from an inverse-Wishart distribution centered on the inverse second-moment matrix. Its argument relates inverse-Wishart sampling to Wishart sampling and requires enough degrees of freedom for the sampled matrix to be invertible.

B.3 Privacy Proof for Algorithm 4

  • When σmin(A) ≥ w, sampling from W^-1_d(A^T A, ν) is (ϵ, δ)-differentially private under the theorem’s stated conditions.The theorem fixes ν ≥ d; this lower bound ensures the sampled matrix is invertible.Source: §B.3 · pp. 26–27
  • The proof connects inverse-Wishart and Wishart sampling through matrix inversion, yielding similar privacy bounds for the two approaches.The inverse-Wishart result requires ν ≥ d, unlike the cited Wishart-sampling bound.Source: §B.3 · p. 27
  • For neighboring datasets, the proof removes the changed row to form a shared matrix and bounds the resulting change in the inverse matrices.It uses the Sherman–Morrison formula and bounds involving the removed rows and the least singular value.Source: §B.3 · pp. 27–28

B.4 An Additional Privacy Theorem — Gaussian Noise for the Inverse

This additional theorem considers Gaussian noise added to the inverse second-moment matrix. Its privacy analysis bounds the sensitivity of that inverse under a lower-bound condition on the input matrix’s least singular value.

B.4 An Additional Privacy Theorem — Gaussian Noise for the Inverse

  • With bounded row norms and σmin(A^T A)/B^2 ≥ 1 + ρ for ρ > 0, the theorem considers releasing (A^T A)^-1 plus symmetric Gaussian noise.The noise entries on and above the main diagonal are sampled independently from a Gaussian distribution.Source: §B.4 · p. 28
  • The proof bounds the global sensitivity of the inverse using the Sherman–Morrison formula, then adds independent noise to its entries.The row norms are bounded by B, and the least-singular-value condition supplies the stated separation from B^2.Source: §B.4 · pp. 28–29

C Utility Theorems

The utility analysis studies how noise in the second-moment matrix affects regression predictors under conditions on the input matrices. It treats Gaussian noise and additive Wishart noise, and notes that the utility bounds depend on input parameters.

C Utility Theorems

  • The utility analysis assumes the data matrix is D = [X; y], with y as the response and X as the feature matrix; y may be any column of D.The remaining columns may supply any subset of the features.Source: C Utility Theorems · p. 29
  • The analysis gives input-parameter-dependent utility bounds, unlike prior DP ERM work described as giving uniform bounds through regularization.The passage notes that without regularization the unnoised predictor is ill-defined when X = 0.Source: C Utility Theorems · p. 29
  • If σmin(X^T X) ≥ 2Cη^-1σ√(p log(1/ν)), the Gaussian-noise analysis bounds the error between the noisy and unnoised regression predictors with probability at least 1 − ν.The theorem assumes X^T X is invertible and independently adds Gaussian noise to entries of the Gram matrix and feature-response vector.Source: C Utility Theorems · p. 30
  • Corollary C.2 states a result when ρ ≥ 2C, using the same constant C as Theorem C.1; ρ is defined using the least singular value of the hatted XᵀX, σ, p, and ν.Source: C Utility Theorems · p. 30
  • For the additive Wishart analysis, the theorem decomposes the sampled matrix into a noisy feature Gram matrix and a noisy feature-response vector.The construction uses W ∼ Wp+1(σ²I, k) and writes the perturbed quantities as X^T X + N and X^T y + n.Source: C Utility Theorems · p. 30
  • The authors conjecture that the stated bound may be smaller by a factor of log(p).This is presented as a conjecture about the true bound, not as a proved improvement.Source: C Utility Theorems · p. 31
Loading 1507.00056v2…