Theorem 3.2 — lower bound for private mean estimation under unknown diagonal covariance
OpenUnknownCovDP.General.Supplement.theorem_3_2differential-privacylower-boundmean-estimationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with . Under the prior , the mean is and, independently, with the i.i.d. . Given , the dataset is . For a prior , is the Bayes risk: the infimum of the such that some -differentially private algorithm has .
There is an absolute constant such that, whenever :
- every -differentially private algorithm satisfies
- for all and ,
When the covariance is diagonal but unknown, private mean estimation in the regime thus costs error of order up to a logarithm. This matches the third term of the known upper bound, so that term is necessary.
Differences from the source:
- encoding: d, n ∈ ℕ with c/n in the DP parameter → 1 ≤ n; reason: c/n is undefined at n = 0; the base mission's accepted encoding (Theorem 2.1)
- reading: That is, ℜ_{ε,δ}(P_diag, n) = Ω̃(d^{3/2}/n²) → ENNReal.ofReal (c d^{3/2}/(n² log d)) ≤ bayesRisk (Pdiag d) n ε δ with the theorem's own c; reason: the Ω̃ is pinned to the threshold the proof on p. 17 delivers; this is stronger than Ω̃ and a separate conclusion from the probability clause
- encoding: c d^{3/2}/(n² log d), undefined at d = 1 where log d = 0 → real division with x/0 = 0, so both clauses are trivial at d ≤ 1; reason: Lean convention; no hypothesis d ≥ 2 is added and no instance with d ≥ 2 changes
- encoding: a randomized algorithm 𝒜 and probability over the prior, the data and the coins of 𝒜 → a Markov kernel κ and the base experimentProb (iterated lintegral); reason: the base mission's model; same instances
- encoding: (1, c/n)-DP → PrivRobustStat.IsApproxDP (fun X => κ X) 1 (c / n) with replace-one neighbours; reason: the published definition used by the base mission; adds no condition
Preamble
import Mathlib import Definitions.Def_UnknownCovDP_General_Supplement_DiagPrior open MeasureTheory ProbabilityTheory open scoped ENNReal NNReal
Formal statement
namespace UnknownCovDP.General.Supplement
/-- Theorem 3.2, printed p. 16, PDF p. 17. There is `c > 0` such that for all `d, n` with
`n log n ≤ c√d`: every `(1, c/n)`-DP algorithm has
`Pr[‖𝒜(X) − μ‖₂ ≥ c d^{3/2}/(n² log d)] ≥ 1/4` under `(μ,Σ) ∼ P_diag`, `X ∼ N(μ,Σ)^{⊗n}`; and for all
`ε ≤ 1`, `δ ≤ c/n`, `ℜ_{ε,δ}(P_diag, n) ≥ c d^{3/2}/(n² log d)` (the `Ω̃` of the "That is" clause,
pinned to the same threshold). `n ≥ 1` because `c/n` is undefined at `n = 0`. At `d = 1`,
`log d = 0` and the threshold is `0` in Lean. -/
theorem theorem_3_2 :
∃ c : ℝ, 0 < c ∧ ∀ (d n : ℕ), 1 ≤ n → (n : ℝ) * Real.log n ≤ c * Real.sqrt d →
(∀ κ : Algorithm d n, IsMarkovKernel κ →
PrivRobustStat.IsApproxDP (fun X => κ X) 1 (c / n) →
1 / 4 ≤ experimentProb (Pdiag d) n κ
(fun μ _ _ => {y | c * (d : ℝ) ^ ((3 : ℝ) / 2) / ((n : ℝ) ^ 2 * Real.log d) ≤ ‖y - μ‖})) ∧
(∀ ε δ : ℝ, ε ≤ 1 → δ ≤ c / n →
ENNReal.ofReal (c * (d : ℝ) ^ ((3 : ℝ) / 2) / ((n : ℝ) ^ 2 * Real.log d)) ≤
bayesRisk (Pdiag d) 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 3.2, printed p. 16 (PDF p. 17); prior eq. (9) and Definition 3.1, same page; Bayes risk Definition 1.2, printed p. 2 (PDF p. 3)