Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions 3.1, 3.3 and eq. (9) — the prior Pdiag(d)\mathcal P_{\mathrm{diag}}(d)Pdiag​(d) and (k,ℓ)(k,\ell)(k,ℓ)-selection mechanisms

Definition
UnknownCovDP_General_Supplement_DiagPrior

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

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

Fix a dimension ddd and a sample size nnn. This module sets up the diagonal-covariance experiment of §3.

  1. The law invχ2(1,1)\mathrm{inv}\chi^2(1,1)invχ2(1,1) (Definition 3.1 with ν=τ=1\nu=\tau=1ν=τ=1). A random variable σ2\sigma^2σ2 has this law when 1/σ2∼χ121/\sigma^2\sim\chi^2_11/σ2∼χ12​; equivalently σ2=1/g2\sigma^2=1/g^2σ2=1/g2 with g∼N(0,1)g\sim N(0,1)g∼N(0,1). Its density on x>0x>0x>0 is proportional to e−1/(2x)x−3/2e^{-1/(2x)}x^{-3/2}e−1/(2x)x−3/2.
  2. The prior Pdiag(d)\mathcal P_{\mathrm{diag}}(d)Pdiag​(d) (eq. (9)). The mean and the covariance are independent, with
μ∼N(0,d2Id),Σ=Diag(σ12,…,σd2),(σi2)i∈[d]∼invχ2(1,1)⊗d.\mu\sim N(0,d^2 I_d),\qquad \Sigma=\mathrm{Diag}(\sigma_1^2,\dots,\sigma_d^2),\quad (\sigma_i^2)_{i\in[d]}\sim \mathrm{inv}\chi^2(1,1)^{\otimes d}.μ∼N(0,d2Id​),Σ=Diag(σ12​,…,σd2​),(σi2​)i∈[d]​∼invχ2(1,1)⊗d.
  1. The kkk largest variances. Let π\piπ be the permutation with σπ(1)2≥⋯≥σπ(d)2\sigma^2_{\pi(1)}\ge\dots\ge\sigma^2_{\pi(d)}σπ(1)2​≥⋯≥σπ(d)2​, and write Tk(Σ)={π(1),…,π(k)}T_k(\Sigma)=\{\pi(1),\dots,\pi(k)\}Tk​(Σ)={π(1),…,π(k)}.
  2. Selection mechanisms (Definition 3.3). A randomized algorithm M\mathcal MM maps a dataset XXX of nnn points of Rd\mathbb R^dRd to s=M(X)∈{0,1}ds=\mathcal M(X)\in\{0,1\}^ds=M(X)∈{0,1}d. It is a (k,ℓ)(k,\ell)(k,ℓ)-selection mechanism for Pdiag\mathcal P_{\mathrm{diag}}Pdiag​ with sample complexity nnn if
    • (Boundedness) ∑j=1dsj≤ℓ\sum_{j=1}^d s_j\le \ell∑j=1d​sj​≤ℓ for every output, and
    • (Accuracy) with Σ\SigmaΣ drawn from the covariance marginal of Pdiag\mathcal P_{\mathrm{diag}}Pdiag​, centered data X∼N(0,Σ)⊗nX\sim N(0,\Sigma)^{\otimes n}X∼N(0,Σ)⊗n and the coins of M\mathcal MM,
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​.

These objects are used by Theorems 3.2 and 3.4. The mean-estimation experiment and the Bayes risk Rε,δ(P,n)\mathfrak R_{\varepsilon,\delta}(\mathcal P,n)Rε,δ​(P,n) come from the mission's published model and apply to Pdiag\mathcal P_{\mathrm{diag}}Pdiag​ unchanged.

Formalization Note invχ2(1,1)\mathrm{inv}\chi^2(1,1)invχ2(1,1) is the pushforward of N(0,1)N(0,1)N(0,1) under g↦1/g2g\mapsto 1/g^2g↦1/g2; at the null point g=0g=0g=0 Lean returns 000. The defining maps are proved measurable, so the laws are probability measures. An output sss is a function Fin d→Bool\mathrm{Fin}\,d\to\mathrm{Bool}Find→Bool. Ties among the variances have probability zero; TkT_kTk​ breaks them by index (the smaller index first), and when k≥dk\ge dk≥d every index is in TkT_kTk​. Boundedness is stated as: for every dataset, the output law gives probability 000 to {s:∑jsj>ℓ}\{s:\sum_j s_j>\ell\}{s:∑j​sj​>ℓ}.

Definition code
import Mathlib
import Definitions.Def_UnknownCovDP_General_Model

open MeasureTheory ProbabilityTheory
open scoped ENNReal NNReal

namespace UnknownCovDP.General.Supplement

/-!
# The diagonal inverse-χ² prior `P_diag` and `(k, ℓ)`-selection mechanisms

Gaucher, Linder, Smith, Ullman, Zakynthinou, *Dimension-Free Private Mean Estimation is Impossible
Without the Covariance*, STOC 2027 submission #573 (October 2026), Definition 3.1 and eq. (9)
(printed p. 16, PDF p. 17), Definition 3.3 (printed p. 17, PDF p. 18).

**Formalization Note.**
* Only `invχ²(1, 1)` is used. By Definition 3.1, `σ² ∼ invχ²(1, 1)` iff `1/σ² ∼ χ²₁`, i.e. `σ²` has
  the law of `1/g²` with `g ∼ N(0, 1)`. It is realized as that pushforward; at `g = 0` (a null event)
  Lean's `(0 ^ 2)⁻¹ = 0`. The defining maps are proved measurable, so no law is the junk zero
  measure.
* `P_diag(d)` is a measure on `Vec d × Mat d` (the base mission's types), so the base
  `experimentProb` and `bayesRisk` apply to it unchanged.
* A selection mechanism outputs `s ∈ {0,1}^d`, encoded as `Fin d → Bool` (finite, discrete σ-algebra).
* "The `k` indices with the largest variances" (`π(1), …, π(k)` with `σ²_{π(1)} ≥ … ≥ σ²_{π(d)}`) is
  encoded by `topK`: index `i` is selected iff fewer than `k` indices precede it in the strict order
  "larger variance, ties broken by smaller index". Ties have probability zero under `P_diag`. If
  `k ≥ d`, every index is selected.
-/

/-- The law `invχ²(1, 1)` of Definition 3.1 (`ν = τ = 1`): the law of `1/g²` with `g ∼ N(0,1)`,
equivalently `1/σ² ∼ χ²₁`; density `∝ exp(−1/(2x)) x^{−3/2}` on `x > 0`. -/
noncomputable def invChiSq11 : Measure ℝ :=
  (gaussianReal 0 1).map fun g : ℝ => (g ^ 2)⁻¹

lemma measurable_invSq : Measurable fun g : ℝ => (g ^ 2)⁻¹ :=
  (measurable_id.pow_const 2).inv

instance invChiSq11_prob : IsProbabilityMeasure invChiSq11 :=
  Measure.isProbabilityMeasure_map measurable_invSq.aemeasurable

/-- `σ ↦ Diag(σ₁, …, σ_d)` is measurable. -/
lemma measurable_diagonal (d : ℕ) :
    Measurable (fun σ : Fin d → ℝ => (Matrix.diagonal σ : Mat d)) := by
  refine measurable_pi_iff.2 fun i => measurable_pi_iff.2 fun j => ?_
  by_cases h : i = j
  · subst h
    simp only [Matrix.diagonal_apply_eq]
    exact measurable_pi_apply i
  · simp only [Matrix.diagonal_apply_ne _ h]
    exact measurable_const

/-- The `Σ`-marginal of `P_diag(d)` (eq. (9)): `Σ = Diag(σ₁², …, σ_d²)` with `σᵢ²` i.i.d.
`invχ²(1, 1)`. -/
noncomputable def diagCovPrior (d : ℕ) : Measure (Mat d) :=
  (Measure.pi fun _ : Fin d => invChiSq11).map fun σ => (Matrix.diagonal σ : Mat d)

instance diagCovPrior_prob (d : ℕ) : IsProbabilityMeasure (diagCovPrior d) :=
  Measure.isProbabilityMeasure_map (measurable_diagonal d).aemeasurable

/-- The prior `P_diag(d)` of eq. (9): `μ ∼ N(0, d² I_d)` and, independently,
`Σ = Diag(σ₁², …, σ_d²)` with `σᵢ²` i.i.d. `invχ²(1, 1)`. -/
noncomputable def Pdiag (d : ℕ) : Measure (Vec d × Mat d) :=
  (multivariateGaussian (0 : Vec d) (((d : ℝ) ^ 2) • (1 : Mat d))).prod (diagCovPrior d)

/-- The indices of the `k` largest diagonal entries of `S` (Definition 3.3, `{π(1), …, π(k)}`):
`i` is selected iff fewer than `k` indices `j` have `S j j > S i i`, or `S j j = S i i` and `j < i`.
-/
noncomputable def topK {d : ℕ} (k : ℕ) (S : Mat d) : Finset (Fin d) := by
  classical
  exact Finset.univ.filter fun i =>
    (Finset.univ.filter fun j => S i i < S j j ∨ (S j j = S i i ∧ j < i)).card < k

/-- The number of selected indices of `s ∈ {0,1}^d` among the indices in `J`, as a natural number. -/
def countSel {d : ℕ} (J : Finset (Fin d)) (s : Fin d → Bool) : ℕ :=
  (J.filter fun j => s j = true).card

/-- A selection mechanism with sample complexity `n`: a randomized map (Markov kernel, its coins
being the kernel's randomness) from `n`-point datasets in `ℝ^d` to `s ∈ {0,1}^d`. -/
abbrev SelMech (d n : ℕ) := Kernel (Fin n → Vec d) (Fin d → Bool)

/-- `Pr_{Σ ∼ P_diag, X ∼ N(0,Σ)^{⊗n}, coins of M}[Σ_{j ≤ k} s_{π(j)} ≥ k/4]` (Definition 3.3,
Accuracy): the data are centered, the inequality is between real numbers. -/
noncomputable def selAccuracy {d n : ℕ} (k : ℕ) (M : SelMech d n) : ℝ≥0∞ :=
  ∫⁻ S, ∫⁻ X, M X {s | (k : ℝ) / 4 ≤ (countSel (topK k S) s : ℝ)} ∂(dataLaw n (0 : Vec d) S)
    ∂(diagCovPrior d)

/-- Definition 3.3: `M` is a `(k, ℓ)`-selection mechanism for `P_diag` with sample complexity `n`:
1. Boundedness: `Σ_j s_j ≤ ℓ` for every output, i.e. for every dataset the output law puts no mass on
   `{s | ℓ < Σ_j s_j}`;
2. Accuracy: `Pr[Σ_{j=1}^k s_{π(j)} ≥ k/4] ≥ 1/3`. -/
def IsSelectionMechanism {d n : ℕ} (k ℓ : ℕ) (M : SelMech d n) : Prop :=
  (∀ X, M X {s | ℓ < countSel Finset.univ s} = 0) ∧ 1 / 3 ≤ selAccuracy k M

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, Definition 3.1 and eq. (9), printed p. 16 (PDF p. 17); Definition 3.3, printed p. 17 (PDF p. 18)

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