Theorem 4.1 — private mean estimation with finite Mahalanobis error is impossible when d ≥ n + 2
OpenUnknownCovDP.General.Supplement.theorem_4_1differential-privacylower-boundmean-estimationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the prior , the mean is and, independently, with uniform on the unit sphere of . Given , the dataset is . For a positive semidefinite with pseudo-inverse , the Mahalanobis norm is if lies in the column space of , and otherwise.
There is a constant such that for all and all , if then every -differentially private mechanism satisfies
the probability being also over the coins of . (The constant appears nowhere else in the statement, as printed.)
So with fewer than samples no private algorithm can estimate the mean with finite error measured relative to the unknown covariance, unless is at least of order .
Differences from the source:
- reading: There exists a constant C > 0 (C appears nowhere else) → ∃ C : ℝ, 0 < C ∧ … with C unused; reason: kept as printed; it is vacuous and does not change the conclusion
- encoding: Pr over (µ,Σ) ∼ P_rel and X ∼ N(µ,Σ)^{⊗n} → the base experimentProb, which also integrates over the mechanism's coins; reason: the output M(X) is random; the probability of the event is over the coins as well
- encoding: d_Σ(M(X) − µ) < ∞ → mahalanobis S (y − μ) < ⊤ with mahalanobis valued in [0, ∞] and Σ† the published LatentRobust.pinv; reason: the paper's definition of d_Σ on p. 27, verbatim
- encoding: nδ → ENNReal.ofReal (n * δ); reason: probabilities are in [0, ∞]; n δ ≥ 0 since δ ≥ 0
- encoding: (ε, δ)-DP mechanism M → Markov kernel M with PrivRobustStat.IsApproxDP (fun X => M X) ε δ; reason: the base mission's model and published DP definition
Preamble
import Mathlib import Definitions.Def_UnknownCovDP_General_Supplement_RelPrior open MeasureTheory ProbabilityTheory open scoped ENNReal NNReal
Formal statement
namespace UnknownCovDP.General.Supplement
/-- Theorem 4.1, printed p. 27, PDF p. 28. There is a constant `C > 0` such that for all `d, n ∈ ℕ`
and `ε, δ ≥ 0`, if `d ≥ n + 2` then every `(ε, δ)`-DP mechanism `M` satisfies
`Pr_{(μ,Σ) ∼ P_rel, X ∼ N(μ,Σ)^{⊗n}}[d_Σ(M(X) − μ) < ∞] ≤ nδ` (the probability also over the
mechanism's coins). The constant `C` occurs nowhere else, as printed. -/
theorem theorem_4_1 :
∃ C : ℝ, 0 < C ∧ ∀ (d n : ℕ) (ε δ : ℝ), 0 ≤ ε → 0 ≤ δ → n + 2 ≤ d →
∀ M : Algorithm d n, IsMarkovKernel M →
PrivRobustStat.IsApproxDP (fun X => M X) ε δ →
experimentProb (Prel d) n M (fun μ S _ => {y | mahalanobis S (y - μ) < ⊤}) ≤
ENNReal.ofReal (n * δ) := by sorry
end UnknownCovDP.General.Supplement
Source
Gaucher, Linder, Smith, Ullman, Zakynthinou, Dimension-Free Private Mean Estimation is Impossible Without the Covariance, STOC 2027 submission #573 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/573.pdf, Theorem 4.1, printed p. 27 (PDF p. 28); d_Σ and prior eq. (17), same page