Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.4 — lower bound for private selection of large-variance coordinates

Open
UnknownCovDP.General.Supplement.theorem_3_4

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-privacylower-boundmean-estimationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let Pdiag(d)\mathcal P_{\mathrm{diag}}(d)Pdiag​(d) be the prior under which Σ=Diag(σ12,…,σd2)\Sigma=\mathrm{Diag}(\sigma_1^2,\dots,\sigma_d^2)Σ=Diag(σ12​,…,σd2​) with the σi2\sigma_i^2σi2​ i.i.d. invχ2(1,1)\mathrm{inv}\chi^2(1,1)invχ2(1,1). A randomized algorithm M\mathcal MM that maps a dataset of nnn points of Rd\mathbb R^dRd to s∈{0,1}ds\in\{0,1\}^ds∈{0,1}d is a (k,ℓ)(k,\ell)(k,ℓ)-selection mechanism for Pdiag\mathcal P_{\mathrm{diag}}Pdiag​ with sample complexity nnn if every output satisfies ∑jsj≤ℓ\sum_j s_j\le\ell∑j​sj​≤ℓ, and, with Σ\SigmaΣ from Pdiag\mathcal P_{\mathrm{diag}}Pdiag​, X∼N(0,Σ)⊗nX\sim N(0,\Sigma)^{\otimes n}X∼N(0,Σ)⊗n and π\piπ ordering the variances decreasingly,

Pr⁡[∑j=1ksπ(j)≥k4]≥13.\Pr\Bigl[\sum_{j=1}^k s_{\pi(j)}\ge \tfrac k4\Bigr]\ge\tfrac13 .Pr[j=1∑k​sπ(j)​≥4k​]≥31​.

There are absolute constants C,c>0C,c>0C,c>0 such that for all d,k,n∈Nd,k,n\in\mathbb Nd,k,n∈N with n≥1n\ge1n≥1 and

Cmax⁡{n2log⁡n, log⁡d}≤k≤c d,C\max\{n^2\log n,\ \log d\}\le k\le c\,d,Cmax{n2logn, logd}≤k≤cd,

every (k,ℓ)(k,\ell)(k,ℓ)-selection mechanism for Pdiag\mathcal P_{\mathrm{diag}}Pdiag​ with sample complexity nnn that is (1,c/n)(1,c/n)(1,c/n)-differentially private has

ℓ ≥ dClog⁡d.\ell\ \ge\ \frac{d}{C\log d}.ℓ ≥ Clogdd​.

A private mechanism that reliably finds a constant fraction of the kkk largest-variance coordinates must therefore select almost all ddd coordinates. Combined with a reduction from mean estimation, this gives Theorem 3.2.

Differences from the source:

  • encoding: d, k, n ∈ ℕ with c/n in the DP parameter → 1 ≤ n; reason: c/n is undefined at n = 0; the base mission's accepted encoding
  • reading: ℓ ≥ d/C log(d) → d / (C * log d) ≤ ℓ; reason: the other parse (d/C)·log d is false: the constant all-ones mechanism is a (1,0)-DP (k, d)-selection mechanism, so ℓ = d is always achievable and d ≥ (d/C) log d fails for large d; the proof of Theorem 3.2 (p. 17) also uses ℓ ≥ d/(C log d)
  • encoding: d/(C log d), undefined at d = 1 → real division with x/0 = 0, so the bound is 0 at d ≤ 1; reason: Lean convention; no hypothesis is added
  • encoding: s ∈ {0,1}^d, π the permutation ordering the variances decreasingly → s : Fin d → Bool; {π(1),…,π(k)} = topK k Σ, ties broken by the smaller index; reason: ties among the σ_j² have probability zero under P_diag
  • encoding: Boundedness Σ_j s_j ≤ ℓ of the output → for every dataset X, M X {s | ℓ < Σ_j s_j} = 0; reason: the output satisfies the bound for every input and almost every coin
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.4 (Lower bound for private selection), printed p. 17, PDF p. 18. There are
`C, c > 0` such that for all `d, k, n` with `C max{n² log n, log d} ≤ k ≤ cd`, every
`(k, ℓ)`-selection mechanism for `P_diag` with sample complexity `n` that is `(1, c/n)`-DP has
`ℓ ≥ d/(C log d)`. `n ≥ 1` because `c/n` is undefined at `n = 0`. At `d = 1` the bound is `0` in
Lean. -/
theorem theorem_3_4 :
    ∃ C : ℝ, 0 < C ∧ ∃ c : ℝ, 0 < c ∧ ∀ (d k n : ℕ), 1 ≤ n →
      C * max ((n : ℝ) ^ 2 * Real.log n) (Real.log d) ≤ k → (k : ℝ) ≤ c * d →
      ∀ (ℓ : ℕ) (M : SelMech d n), IsMarkovKernel M →
        IsSelectionMechanism k ℓ M →
        PrivRobustStat.IsApproxDP (fun X => M X) 1 (c / n) →
        (d : ℝ) / (C * Real.log d) ≤ ℓ := 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.4, printed p. 17 (PDF p. 18); Definition 3.3, same page; prior eq. (9), printed p. 16 (PDF p. 17)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me