CoinPress: Practical Private Mean and Covariance Estimation

1 Introduction

• The empirical mean can reveal sensitive information, motivating estimators that are both accurate and protective of the individuals represented in the sample.The paper identifies small datasets and multivariate settings as practical challenges for private estimation.Source: §1 · pp. 1–2

1.1 Contributions

• CoinPress’s mean and covariance estimators match state-of-the-art asymptotic bounds and show error comparable to non-private estimates at small sample sizes.The paper also reports that its mean estimator improves over Du et al. [DFM+20].Source: §1.1 · p. 2
• The method remains practical with extremely large prior parameter bounds, so users need only weak prior knowledge.For mean estimation, the assumed bound is a ball of radius R; for covariance estimation, the covariance is bounded relative to a matrix A.Source: §1.1 · pp. 2–3
• Although the evaluation primarily uses Gaussian data, the method relies on tail bounds shared by sub-Gaussian distributions and remains useful in heavier-tailed and real-world experiments.The paper notes that worst-case optimal error can depend strongly on the distribution’s tail-decay rate [KSU20].Source: §1.1 · p. 3
• The estimators iteratively refine parameter estimates, reducing the confidence region before a final private estimate is made.For the mean, each step clips data to a ball and adds noise proportional to its radius divided by sample size.Source: §1.1 · p. 3

1.2 Problem Formulation

• The formulation requires privacy across neighboring datasets while measuring estimation accuracy under an i.i.d. distributional model.The paper measures mean and covariance error in Mahalanobis distance, which it describes as affine-invariant.Source: §1.2 · pp. 3–4

1.3 Related Work

• Prior work spans univariate practical estimators and mainly theoretical multivariate methods; CoinPress presents its covariance estimator as a simpler, more practical variant of.The paper distinguishes its multivariate focus from practical private confidence intervals developed for univariate data [DFM+20].Source: §1.3 · p. 5

2 Preliminaries

• Differential privacy bounds how an algorithm’s output distribution changes between neighboring datasets, with pure DP as the special case where δ = 0.The paper also presents zCDP as a distinct privacy formulation.Source: §2 · p. 5
• Adaptive mechanisms satisfying ρ_t-zCDP compose with total privacy parameter equal to the sum of their ρ_t values.The preliminaries also state that privacy guarantees are preserved under post-processing.Source: §2 · p. 6
• The Gaussian mechanism adds noise calibrated to a function’s ℓ2-sensitivity to obtain (ε, δ)-DP or ρ-zCDP.The preliminaries define sensitivity as the maximum output change across neighboring datasets.Source: §2 · p. 6

3 New Algorithms for Multivariate Gaussian Estimation

• The algorithms target more practical multivariate Gaussian estimation while avoiding the curse of dimensionality from multivariate histograms and many hyperparameters in previous methods.They do not improve asymptotic sample-complexity bounds.Source: §3 · p. 6

3.1 Multivariate Private Mean Estimation

• MVMRec repeatedly refines a ball containing the mean, then clips the data and noises the empirical mean; each step aims to shrink the ball by a constant factor.The method is presented for identity covariance, and the same argument applies to known covariance or a proxy satisfying the stated spectral condition.Source: §3.1 · pp. 7–8
• MVMRec is (sum_i rho_i)-zCDP and, under the theorem's conditions, returns a mean estimate with l2 error at most α with probability at least 1−β.The theorem considers Gaussian samples with identity covariance and an initial ball containing the mean.Source: §3.1 · p. 8

3.2 Multivariate Private Covariance Estimation

• MVCRec repeatedly refines a PSD-matrix ellipsoid upper-bounding the covariance, rescaling after each step so the upper bound is identity; O(log K) iterations suffice.The covariance step clips points using Gaussian tail bounds, noises a covariance estimate, and derives a confidence ellipsoid to maintain accuracy.Source: §3.2 · pp. 8–9
• MVCRec returns a covariance estimate whose relative Frobenius error is at most α with probability at least 1−β.The theorem states a zCDP guarantee; the displayed result also specifies an O(log K) iteration count.Source: §3.2 · p. 10

4.1.1 Results and Discussion

• At n = 1,000 and n = 10,000, privacy adds about 27% and just 2% error, respectively, while t = 2 outperforms other mean estimators.The mean experiments use 100 trials and report 0.1-trimmed means under ρ-CDP; plots show ℓ2 error, sometimes as excess over non-private error.Source: Figure 3 · p. 11, §4.1 · p. 11, §4.1.1 · p. 12
• With d = 50 and n = 1,000, t = 10 shows no visible error change as R grows by three orders of magnitude, while other methods worsen substantially.Even when SYMQ receives twice as many samples (n = 2,000), the method has somewhat lower error at large R.Source: §4.1.1 · p. 12, Figure 4 · p. 12
• At d = 2 and d = 500, the method remains competitive or best; at ρ = 0.04, its privacy cost stays below a factor of 2 while coordinatewise methods falter.For d = 500, the cost is below a factor of 2 even with n < 4d samples.Source: Figure 5 · p. 12, Figure 6 · p. 12, §4.1.1 · p. 13
• With heavier-tailed multivariate Laplace and Student’s t data (3 degrees of freedom), the mean estimator remains effective despite model misspecification.The experiment fixes d = 50 and t = 2 and plots excess error over non-private estimation.Source: §4.1.1 · p. 13, Figure 8 · p. 13

4.2.1 Synthetic Data Experiments

• For isotropic covariance, t = 3 gives the best result and privacy cost within a factor of 1.5 at n = 3,000; for skewed covariance, t = 2 beats the non-private baseline.For the skewed case, accuracy degrades at larger t.Source: Figure 9 · p. 14, §4.2.1 · p. 14, Figure 10 · p. 15
• As K increases, t = 1 is least accurate and t = 3, 4, or 5 performs significantly better; under small privacy budgets, the preferred t differs between isotropic and skewed covariance.For isotropic covariance, larger t performs better as ρ becomes very small; for skewed covariance, t = 2 is most accurate and larger t can perform poorly at small budgets.Source: §4.2.1 · pp. 14–15, Figure 11 · p. 15, Figure 14 · p. 17
• In d = 2, all methods beat the naïve baseline for isotropic data and t = 2 does so for skewed data; in d = 100, t > 1 substantially beats t = 1, with t = 3 near the non-private baseline at larger n.For bivariate skewed data, accuracy is more sensitive to t; privacy cost is low around n = 1,000.Source: §4.2.1 · p. 15, Figure 13 · p. 16, Figure 12 · p. 16

4.3 Map of Europe

• For the randomly rotated dataset scaled by a factor of 20 with K = 30, naïve private projection (t = 1) yields dot products 0.48 and 0.28; our method yields 0.98 and 0.48 at t = 3, and 0.96 and 0.92 at t = 5.The t = 5 projection bears the strongest resemblance to the original image.Source: §4.3 · p. 18

5 Conclusions

• CoinPress matches state-of-the-art theoretical bounds and is accurate at low sample sizes and high dimensions, significantly outperforming prior methods with few hyperparameters and minimal prior information.The conclusion also reports a private version of PCA for exploratory data analysis.Source: §5 · p. 18

A New Algorithms for Univariate Gaussian Parameter Estimation

• The univariate Gaussian algorithms provide zCDP guarantees, and the same approach can yield pure differential privacy by switching to Laplace noise and basic composition.The pure-DP variant also requires appropriate tail bounds for the confidence interval.Source: A New Algorithms for Univariate… · p. 22

A.1 Univariate Private Mean Estimation

• UVMRec iteratively invokes a private interval-improvement algorithm and returns the midpoint of the final interval.The univariate mean algorithm is described as an iterative invocation of Algorithm 5.Source: §A.1 · p. 23
• For |µ| < Rσ and the stated sample-size condition, UVMRec returns an estimate within ασ of µ with probability at least 1 − β.The theorem uses t = O(log R).Source: §A.1 · p. 23
• The algorithm is ρ-zCDP through the Gaussian mechanism and composition of zCDP across its calls.Source: §A.1 · p. 23
• Each interval-improvement call retains µ with probability at least 1 − 2βs, and halves the interval width when that width exceeds Cσ.The coverage argument uses a union bound after comparing the procedure with a variant that omits rounding.Source: §A.1 · pp. 23–24
• After the earlier intervals shrink, the final call adds insignificant noise, yielding the stated ασ accuracy with the theorem's failure-probability bound.The proof conditions on the true mean remaining in the preceding interval and that interval having width O(1) · σ.Source: §A.1 · p. 24

A.2 Univariate Private Variance Estimation

• UVVRec iteratively invokes a private variance-interval improvement algorithm and returns the midpoint of the final interval.Source: §A.2 · pp. 24–25
• The first two sample-complexity terms are optimal up to logarithmic factors, but the algorithm leaves a K-dependent third term unoptimized for simplicity.The passage notes that another method reduces that term's dependence on K from √log K to √log log K.Source: §A.2 · p. 24
• The proof bounds each step's interval coverage using scaled chi-squared variables and conservatively scales by the upper variance bound u.Source: §A.2 · p. 26
• When u/ℓ is sufficiently large, a variance-interval step returns an interval of width at most half the previous width.The argument combines the initial width condition with a bound on the confidence-interval width.Source: §A.2 · p. 26
• With t = log2 K, the final interval has width at most ασ² under the theorem's sample-size condition.The setup normalizes the supplied variance interval to [1, K].Source: §A.2 · pp. 24, 26

B.1 Proof of Theorem 3.1

• An interval-improvement call returns a confidence ball containing µ with probability at least 1 − β1 − β2.The proof uses a multivariate Gaussian tail bound.Source: §B.1 · p. 26
• The passage states that, under an incompletely specified condition involving d and some constant C > 0, the updated radius r′ is less than half the prior radius r.Source: §B.1 · p. 26
• The final-call argument uses the contracted radius and accounts for failure probability at earlier steps to complete the proof.Source: §B.1 · p. 26

• The neighboring datasets differ by replacing a single point X with Y.Source: §B.2 · p. 27
• The proof evaluates a trace expression involving squared and cross-product terms in XXT and YYT.Source: §B.2 · p. 27
• The first inequality follows from Tr(AB) ≥ 0 for positive semidefinite matrices A and B.Source: §B.2 · p. 27

• Privacy follows from the Gaussian mechanism and zCDP composition, with sensitivity analysis relying on Lemma 3.2.Source: §B.3 · p. 27
• The proof represents each scaling matrix Ai as MiAi−1 and rescales Z by At−1 to obtain the desired result.Mi is the matrix U−1/2 produced at iteration i.Source: §B.3 · pp. 27–28
• At each iteration, A−1_i is explicitly known, upper-bounds Σ, and is not too loose an upper bound.Source: §B.3 · p. 27
• An induction starts from A0 = 1/√K and bounds each subsequent step using adjustment probabilities and spectral-norm sampling and Gaussian-noise errors.The base case uses the assumption Σ ⪯ KI; the inductive step invokes Fact C.2 and Lemmas C.3 and C.4.Source: §B.3 · p. 27
• A directional empirical covariance concentration bound may yield tighter bounds than the spectral-norm bound from Lemma C.3.The proposed form includes a quantity ζ; the passage presents this as a possibility.Source: §B.3 · p. 27

• The tail-bound argument uses a result from and Gaussian concentration, noting that spectral norm is 2-Lipschitz for the specified symmetric matrices [Ver12].Source: C Concentration Inequalities and Tail… · pp. 28–29
• Fact C.2 gives a chi-squared tail bound, attributed to.Source: C Concentration Inequalities and Tail… · p. 29
• Lemma C.3 states a spectral-error bound for empirical covariance from Gaussian samples, following.Source: C Concentration Inequalities and Tail… · p. 29
• Lemma C.4 bounds the spectral norm of a symmetric matrix with random Gaussian entries.Source: C Concentration Inequalities and Tail… · p. 29