The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy

1. Introduction.

• Differential privacy protects individuals against adversaries using algorithm outputs and is widely adopted in statistical analysis and real-world systems.The paper emphasizes that privacy is typically achieved by perturbing non-private outputs, which causes accuracy loss.Source: §1 · pp. 1–2

Our contributions and related literature

• The paper establishes minimax-risk lower bounds for low-dimensional mean estimation and new lower bounds for high-dimensional mean estimation and linear regression using tracing-adversary arguments.These results improve existing bounds and provide first lower bounds of their kind for the high-dimensional mean and regression settings discussed.Source: Our contributions and related literature · pp. 2–3
• Private algorithms match the corresponding lower-bound rates up to logarithmic factors, including noisy sample means, noisy gradient descent, peeling, and private iterative hard thresholding.The high-dimensional methods target sparse estimation, with parameter estimation error as the principal theoretical criterion.Source: Our contributions and related literature · pp. 3–4

Other related literature

• The paper distinguishes (ε, δ)-privacy from stronger α-local privacy, noting that their costs differ in high-dimensional statistical estimation.Prior work found slower convergence under local privacy and established minimax results for selected locally private problems.Source: Other related literature · p. 4

Organization of the paper

• The paper organizes its analysis around formal privacy-cost definitions, technical upper- and lower-bound tools, applications to mean estimation and regression, simulations, real-data analysis, and proofs.The theoretical developments appear before empirical demonstrations and broader discussion.Source: Organization of the paper · p. 4

2. Problem Formulation

• The privacy cost is defined as the difference between constrained and unconstrained minimax risks, with the paper deriving upper and lower bounds for the constrained quantity.The framework evaluates the best (ε, δ)-differentially private estimator by worst-case risk over a distribution family.Source: §2.1 · p. 5

The Laplace and Gaussian mechanisms

• Differentially private algorithms commonly perturb non-private procedures with noise whose scale is calibrated to the algorithm’s sensitivity.Sensitivity measures output changes after replacing one datum, motivating perturbations that stabilize outputs against individual presence or absence.Source: §2.2 · p. 6, The Laplace and Gaussian mechanisms · p. 6
• The Laplace mechanism uses Laplace noise for finite ℓ1-sensitivity to achieve (ε, 0)-differential privacy, whereas the Gaussian mechanism uses Gaussian noise for finite ℓ2-sensitivity to achieve (ε, δ)-differential privacy.Post-processing preserves the privacy guarantee, while composition and post-processing can make these simple mechanisms part of more complex private algorithms.Source: The Laplace and Gaussian mechanisms · p. 6, Post-processing and Composition · p. 6

Post-processing and Composition.

• Differential privacy is preserved under deterministic post-processing, while composing mechanisms adds their privacy parameters: (ε1 + ε2, δ1 + δ2).These principles support the construction of private mean-estimation and regression algorithms.Source: Post-processing and Composition · pp. 6–7

2.3. Minimax Risk Lower Bounds with Differential Privacy Constraint.

• Refined tracing-adversary arguments yield sharper low-dimensional mean-estimation lower bounds and new lower bounds for sparse mean estimation and linear regression.The method argues that an accurate private estimator would enable detecting whether a candidate datum appears in the dataset, contradicting differential privacy.Source: §2.3 · p. 7

Example: a preliminary lower bound for mean estimation.

• The preliminary mean-estimation lower bound is limited by targeting the sample mean rather than minimax risk and by the artificial range n < c1 d/log(1/δ).These limitations motivate the sharper result developed for the usual low-dimensional regime.Source: Example: a preliminary lower bound for… · p. 9

3. The Cost of Privacy in Mean Estimation.

• The paper’s mean-estimation results pair refined lower bounds with private algorithms that attain the low-dimensional rate exactly in bounded-support settings and the sparse lower bound up to logarithmic factors.The sparse estimator attains its lower bound up to factors of log n.Source: §3 · p. 9, §3.2 · p. 11, §3.3 · p. 13

3.1. Lower bound of low-dimensional mean estimation.

• The low-dimensional mean lower bound applies in a broad sample-size regime and shows privacy dominates statistical risk when d log(1/δ)/nε^2 ≳ 1.It improves the dependence on δ over [28] and matches the sample-complexity lower bound in.Source: §3.1 · p. 10

3.2. Algorithm for low-dimensional mean estimation.

• A truncated Gaussian-mechanism estimator attains the low-dimensional lower-bound rate for bounded-support distributions and matches it for unbounded sub-Gaussian distributions up to O(log n).The method requires selecting a truncation level R; this tuning requirement limits practicality.Source: §3.2 · p. 11

3.3. Lower bound of sparse mean estimation.

• For sparse mean estimation, the paper establishes a minimax lower bound whose privacy term depends only logarithmically on dimension d when s* = o(d^(1−ω)).This suggests high-dimensional estimation remains viable under central (ε, δ)-differential privacy, contrasting with local differential privacy.Source: §3.3 · pp. 12–13

3.4. Algorithm for sparse mean estimation.

• The sparse-mean estimator privately selects large coordinates of a truncated sample mean and sets the remaining coordinates to zero.Its selection stage uses an efficient peeling procedure that iteratively chooses top coordinates by absolute value [22].Source: §3.4 · p. 13

• Algorithm 3 applies the Peeling procedure to a truncated sample mean to estimate the sparse mean privately.It computes coordinatewise truncated averages before applying the private selection mechanism.Source: §7 · p. 14
• Truncation bounds the change between neighboring datasets by 2R/n in infinity norm, enabling the differential-privacy guarantee.The privacy result applies whenever the input vector has bounded coordinatewise change.Source: §7 · pp. 13–14
• With R = Kσ√log n and sparsity parameters satisfying s ≥ s* and s ≍ s*, Theorem 3.4 establishes high-probability accuracy for Algorithm 3.The stated success probability is at least 1 − c1 exp(−c2 log n) − c1 exp(−c2 log d).Source: §7 · p. 14
• For δ = n^−(1+ω), Algorithm 3 attains the lower-bound convergence rate up to a log^2 n gap.The theoretical analysis uses tuning parameters R and s, while later data-driven selection methods achieve reasonably good numerical performance.Source: §7 · p. 14

4. The Cost of Privacy in Linear Regression.

• The analysis covers classical d=o(n) regression and high-dimensional regression with sparse β under (ε,δ)-differential privacy.The high-dimensional setting is the primary focus, while low-dimensional regression is also treated.Source: §4 · p. 15, §4.2 · p. 17

4.1. Lower bound of low-dimensional linear regression.

• Tracing attacks yield a minimax lower bound for differentially private low-dimensional regression when ε<1 and δ<n^−(1+ω).The attack is large when a data point belongs to the sample and small otherwise; the bound is later shown sharp up to log n factors.Source: §4.1 · pp. 15–16

4.2. Algorithm for low-dimensional linear regression.

• Noisy gradient descent solves low-dimensional private regression in O(log n) iterations and is (ε,δ)-private when B≥4(R+c0cx)cx and C≤c0.Under assumptions (D1), (D2), and (P1), Theorem 4.2 provides the convergence guarantee; the theoretical truncation level depends on the often unknown σ.Source: §4.2 · pp. 16–17

4.3. Lower bound of high-dimensional linear regression.

• For sparse high-dimensional regression with s*=o(d^(1−ω)), tracing attacks establish a private minimax lower bound depending only logarithmically on d.The result assumes restricted covariance conditions and δ<n^−(1+ω), and the subsequent algorithm matches it up to log n factors.Source: §4.3 · p. 18

4.4. Algorithm for high-dimensional linear regression.

• Private iterative hard thresholding uses peeling to exploit sparsity, achieves privacy with B≥4(R+c0cx)cx/√s, and attains the lower bound up to log n factors.The method is needed because rank deficiency makes direct least-squares minimization and the low-dimensional noisy-gradient algorithm inaccurate; its guarantee assumes (P1’), (D1’), and (D2’).Source: §4.4 · pp. 18–20

5.1. Tuning of truncation level.

• Data-driven truncation achieves errors comparable to no truncation and the theoretical R = 4σ√log n choice, supporting practical tuning under Gaussian data.This optimistic result relies on Gaussian symmetry and light tails and may not extend to all distributions.Source: §5.1 · pp. 20–21, Figure 1 · p. 21

5.2. Tuning of s.

• Private cross-validation selects sparsity s with errors comparable to supplying the true s*, using truncated errors and the exponential mechanism to preserve differential privacy.The candidate grid ranges from s*/2 to 2s*, and cross-validation uses five folds.Source: §5.2 · pp. 21–22, Figure 2 · p. 22, Figure 3 · p. 22

5.3. Comparisons with other algorithms.

• Our algorithms show significant performance gaps over competing private methods, although those methods target test statistics or excess empirical risk rather than the reported metrics.The comparison includes Algorithm 4 in [29] for low-dimensional mean estimation, Algorithm 1 in for regression, and for high-dimensional problems.Source: §5.3 · p. 23
• Our method’s sparse construction and convergence toward the non-private solution explain its numerical advantage, whereas [41] incurs ridge bias and [45] often produces nonsparse solutions.The ridge regularization parameter in [41] is of order O(log(1/δ)/ε), while [45] can assign large values outside β’s true support.Source: §5.3 · p. 23

6.1. SNP array of adults with schizophrenia.

• The schizophrenia SNP analysis uses 387 subjects and the 2000 SNPs with highest minor allele frequencies to study private sparse mean estimation.The data comprise 241 average-IQ and 146 low-IQ subjects, with sparsity arising because group MAF differences are expected at only a small number of SNPs.Source: §6.1 · pp. 23–24
• Differentially private mean estimation can report SNP minor allele frequencies while reducing disclosure risks from summary-statistic attacks on genetic datasets.In the SNP matrix, entries encode minor-allele counts, so SNP MAFs are obtained from row means.Source: §6.1 · p. 23
• The SNP experiment repeatedly subsamples equal-sized IQ groups, applies the private sparse mean estimator with s = 20 and (ε, δ) = (0.5, 10/n^1.1), and compares error curves with.Figure 4(a) reports E[∥µ̂ − µ∥2] as sample size increases from 50 to 120.Source: §6.1 · p. 24, Figure 4 · p. 24

6.2. Housing prices in California.

• The California housing analysis evaluates private OLS on 20640 census block groups using economic and demographic covariates, including income, age, population, households, and rooms.Privacy remains relevant because non-private summary statistics can expose sensitive household information.Source: §6.2 · p. 24
• The experiment repeatedly subsamples m subjects from 100 to 20600, standardizes the design matrix, and compares differentially private OLS error with full-sample non-private OLS and method.With (ε, δ) = (0.5, 10/n^1.1), Figure 4(b) estimates E[∥β̂ − β∥2] as m increases from 2000 to 20000, repeating the procedure 100 times.Source: §6.2 · pp. 24–25

7. Discussion.

• The paper establishes tracing-adversary lower bounds for differentially private mean estimation and linear regression, with algorithms matching them up to logarithmic factors.This formalizes the statistical accuracy–privacy tradeoff addressed by the paper.Source: §7 · p. 25
• Private algorithms show robust tuning performance, accuracy comparable to or better than existing differentially private methods, and efficient computation at dimensions and sample sizes up to tens of thousands.Their numerical results also exhibit shrinking but non-vanishing accuracy gaps relative to non-private counterparts.Source: §7 · p. 25
• Future work includes privacy–accuracy tradeoffs beyond mean estimation and linear regression, more general private algorithms and lower bounds, private uncertainty quantification, and alternative privacy notions.Suggested applications include covariance estimation, graphical models, nonparametric regression, PCA, sparse inference, concentrated differential privacy [19], Rényi differential privacy, and Gaussian differential privacy [13].Source: §7 · pp. 25–26

8.1. Proof of Lemma 3.1.

• Group privacy converts repeated appearances in the constructed sample into effective privacy parameters, enabling the preliminary lower bound after controlling the maximum multiplicity.The proof uses a dichotomy for the privacy regime and bounds the maximum multiplicity through multinomial and Chernoff arguments.Source: §8.1 · pp. 26, 28

8.2. Proof of Theorem 3.1.

• Theorem 3.1 follows by representing observations as zero values or selected informative samples, rescaling the conditional private mechanism, and applying Lemma 3.1 to the informative subsample.For fixed support S, the rescaled conditional mechanism remains (ε,δ)-differentially private, while the mean satisfies μ = αEy1.Source: §8.2 · pp. 28–29

8.3. Proof of Theorem 4.4.

• Restricted strong convexity and smoothness control sparse iterates, while truncation, Laplace-noise bounds, and high-probability events yield exponential decay of the regression loss.The proof combines the deterministic contraction under E1 with simultaneous probability control for truncation and accumulated noise events.Source: §8.3 · pp. 29–30

A.1. Proof of Theorem 3.2.

• Theorem 3.2 completes its upper-bound argument by combining a norm decomposition with the distribution of w and sub-Gaussianity of x.The proof uses the bound 2∥w∥2^2 + 2∥X−µ∥2^2 after taking expectation.Source: §A.1 · p. 34

A.2. Proof of Lemma 3.4.

• Lemma 3.4 derives a comparison inequality from Algorithm 2’s selection criterion by pairing selected indices through a bijection and summing over them.For each paired index, the criterion compares |vj|+wij with |vψ(j)|+wiψ(j).Source: §A.2 · p. 34

A.3. Proof of Theorem 3.4.

• Theorem 3.4 decomposes sparse-estimation error into perturbation, shared-support, and mismatched-support terms before combining these bounds.The resulting inequality includes 2∥(X−µ)S*∥2^2 and 12∥XS∩(S*)c∥2, bounded relative to s*∥X−µ∥∞^2.Source: §A.3 · pp. 34–35
• Theorem 3.4 uses sub-Gaussian maxima and a further lemma to obtain high-probability control of coordinatewise deviations and the remaining support terms.The coordinatewise bound is ∥X−µ∥∞^2 < Cσ^2 log d/n with probability at least 1−c1 exp(−c2 log n).Source: §A.3 · p. 35

A.4. Proof of Lemma 4.2.

• Lemma 4.2 proves overall (ε,δ)-differential privacy by assigning each of T iterations (ε/T,δ/T)-privacy and applying composition to Gaussian-mechanism updates.The proof controls the ℓ2-sensitivity of each gradient step for neighboring data sets.Source: §A.4 · p. 36

A.5. Proof of Theorem 4.2.

• Theorem 4.2 analyzes private gradient descent under smoothness and strong convexity, controlling optimization error through contraction, noise bounds, and high-probability design events.The objective is shown to be (2L/d)-smooth and (1/2Ld)-strongly convex under E1 and assumption (D2).Source: §A.5 · pp. 36–37
• Theorem 4.2 bounds the iteration noise by Kλd ≍σ2 d3 log(1/δ) log3 n/(n2ε2) with probability at least 1−c1 exp(−c2d).The bound follows from Lemma A.2 and the chosen tail parameter λ.Source: §A.5 · pp. 36–37
• Lemma A.2 controls the weighted noise sum by establishing sub-exponential behavior and applying standard sub-exponential tail bounds.The proof notes that the weighted sum remains sub-exponential after establishing the component parameters.Source: §A.5 · p. 37

A.6. Proof of Lemma 4.4.

• Algorithm 5 is overall (ε,δ)-differentially private because its T iterations are each shown to be (ε/T,δ/T)-differentially private, using composition.Source: §A.6 · p. 37
• For neighboring data sets differing in one datum, conditions (D1’) and (P1’) establish the per-iteration privacy requirement through Lemma 3.3.Source: §A.6 · p. 37

A.7. Proof of Lemma 8.3.

• Lemma 8.3 begins by stating a key property of the Peeling algorithm, formalized as Lemma A.3 for sparse vectors and top-coordinate selection.Source: §A.7 · pp. 38, 42
• The proof tracks successive supports, the target support, gradient updates, and the accumulated noise W from the Laplace vectors used during iterative support selection.Source: §A.7 · p. 38
• Applying Lemma A.3, the derivation uses the bound above and (A.8), together with |It \ R| ≤ 2s∗ + s and It \ (St ∪ S∗) ⊆ St+1.Source: §A.7 · pp. 39–40
• The argument fixes η = 2/3, chooses c using the RSM condition, and sets s = 72(γ/α)^2s* = ρL^4s* to satisfy the required inequalities.Source: §A.7 · p. 41
• The proof concludes by combining the derived inequality with Lemma A.4 (, Lemma 6) and rearranging after adding L_n(β_t) − L_n(β-hat).Source: §A.7 · p. 42
• Lemma A.3 follows by comparing the top s coordinates of v with an arbitrary s-hat-sparse vector and using cardinality and absolute-value ordering arguments.Source: §A.7 · p. 42

B.1. Proof of Lemma 2.1.

• The first part applies Hoeffding’s inequality to a sum of d independent, zero-mean variables bounded by −2σ^2 and 2σ^2.The independence and boundedness conditions are explicitly used to invoke Hoeffding’s inequality.Source: §B.1 · p. 44
• For the second part, the proof assigns μ = σp, with independent coordinates p_j sampled uniformly from (−1,1).This prior is introduced to analyze the required probability under the assumed sample-size range.Source: §B.1 · p. 44
• The argument defines F = {X, M(X)} and controls the relevant term through its conditional moment-generating function.The proof uses F to condition on the data and mechanism output before analyzing the centered variables.Source: §B.1 · p. 45
• Conditional on F, the coordinates p_1,...,p_d remain independent and identically distributed, enabling coordinatewise sub-Gaussian control.The proof bounds the centered auxiliary quantity by nσ in magnitude and sub-Gaussian norm, yielding an exponential bound with n^2σ^2u^2.Source: §B.1 · p. 45
• The conditional expectation is lower-bounded using the transformed statistic ˜S_j and the bound involving M(X)_j.The proof first relates the relevant expression to φ_X,j(p_j) and then derives a lower bound for E[W_j | F].Source: §B.1 · pp. 45–46
• Marginally, ˜S_j is uniform because ˜p_j follows a beta-binomial mixture whose beta-function probability simplifies to 1/(n+1).The proof represents ˜S_j through a binomial distribution and evaluates the resulting beta-function expression.Source: §B.1 · p. 46
• Combining the bounds yields the target probability inequality, including a final upper bound that is strictly less than δ.The proof states that combining all pieces gives the desired result and concludes with the displayed δ-bound.Source: §B.1 · pp. 46–47

B.2. Proof of Lemma 3.2.

• Lemma 3.2 uses a prior formed by retaining the s∗ largest absolute values among d truncated-normal coordinates, producing an s∗-sparse parameter.The coordinates are i.i.d. from N(0, γ2) truncated to [-1,1].Source: §B.2 · p. 47
• Stein’s Lemma is applied to analyze the prior-dependent expectation appearing in the lower-bound argument.The proof then sums the resulting coordinatewise expressions using the truncated-normal density.Source: §B.2 · pp. 47–48
• Setting γ2 = 1/(4 log(d/4s∗)) and examining the (d−s∗+1)th absolute-value order statistic establishes that sufficiently many prior coordinates exceed a fixed threshold.The proof studies Y = |ν|(d−s∗+1) and uses tail probabilities for the truncated normal.Source: §B.2 · pp. 48–49
• The lemma’s privacy term is proved separately from the statistical sparse-mean term, under s∗ = o(d1−ω) and the stated prior-risk conditions.The first minimax term is identified as the classical statistical minimax lower bound for sparse mean estimation.Source: §B.2 · p. 49, §B.3 · p. 49

B.3. Proof of Theorem 3.3.

• Lemma B.2 states that if M is an (ε, δ)-differentially private algorithm with 0 < ε < 1 and δ > 0, then an inequality holds for every T > 0.This inequality previously appeared in and [28] in their respective analyses of tracing attacks.Source: §B.3 · p. 49
• The proof applies Lemma 3.2 to bound tracing-statistic tails uniformly over sparse parameters satisfying ∥µ∥0 ≤ s∗ and ∥µ∥∞ < 1.These parameter restrictions supply the tail-probability control used in the theorem.Source: §B.3 · p. 49
• Under δ < n−(1+ω), the resulting inequality yields the theorem’s lower bound, and Bayes risk completes the passage to maximum risk.The final step uses that Bayes risk always lower bounds max risk.Source: §B.3 · pp. 49–50

B.4. Proof of Lemma 4.1.

• Lemma 4.1 uses an i.i.d. truncated N(0,1) prior scaled so that the parameter satisfies ∥β∥2 < 1.The proof defines coordinatewise expectations gj(β) and sums the resulting bounds over j.Source: §B.4 · p. 51
• The Lemma 4.1 argument completes by showing the remaining aggregate term is o(1) under the stated assumption.Source: §B.4 · p. 51

B.5. Proof of Theorem 4.1.

• Theorem 4.1 proves the privacy-dependent part of the lower bound using Lemma 4.1, Lemma B.2, and a bound on P(|Ai| > t).The first lower-bound term is inherited from the statistical minimax lower bound.Source: §B.5 · p. 52
• For Theorem 4.1, the conclusion applies to every (ε, δ)-differentially private mechanism when δ < n^−(1+ω), using Bayes risk as a lower bound for max risk.Source: §B.5 · p. 52

B.6. Proof of Lemma 4.3.

• Lemma 4.3 constructs a sparse prior by retaining the s∗ largest absolute values from truncated N(0, γ2) draws and scaling them so that ∥β∥2 ≤ 1.The proof again defines coordinatewise expectations and sums bounds over coordinates.Source: §B.6 · p. 53
• The Lemma 4.3 bound follows from the corresponding sparse-mean order-statistic calculation under s∗ = o(d^(1−ω)).Source: §B.6 · p. 53

B.7. Proof of Theorem 4.3.

• Theorem 4.3 derives its privacy-dependent lower-bound term from Lemma 4.3, Lemma B.2, and control of P(|Ai| > t).Its first lower-bound term is inherited from the statistical minimax lower bound.Source: §B.7 · p. 54
• Theorem 4.3 concludes for every (ε, δ)-differentially private mechanism when δ < n^−(1+ω), because Bayes risk lower bounds max risk.Source: §B.7 · p. 54