Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem D.2 — scalar PFR PFRbε,δ(Nσ/(τn)(g),φ,τ)\mathrm{PFR}_b^{\varepsilon,\delta}(\mathcal N_{\sigma/(\tau n)}(g),\varphi,\tau)PFRbε,δ​(Nσ/(τn)​(g),φ,τ) is (ε,δ)(\varepsilon,\delta)(ε,δ)-DP

Open
PFRelease.Supplement.theorem_D_2

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-privacyp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitypropose-filter-release

Let n,b∈Nn,b\in\mathbb Nn,b∈N with n/b∈Nn/b\in\mathbb Nn/b∈N, ε∈(0,1]\varepsilon\in(0,1]ε∈(0,1], δ∈(0,1)\delta\in(0,1)δ∈(0,1), and σ>0\sigma>0σ>0 with δNσ(ε/2)≤δ/4\delta_{\mathcal N_\sigma}(\varepsilon/2)\le\delta/4δNσ​​(ε/2)≤δ/4. Let τ>0\tau>0τ>0 be a friendliness threshold, ggg a real-valued function on nonempty datasets, and Δ\DeltaΔ a function that bounds the per-instance sensitivity of ggg. Suppose the score

φ(s,x):=1∣s∣ Δ(s,x)(s≠∅, x≠⊥, 1/0:=∞, 1/∞:=0)\varphi(s,x):=\frac1{|s|\,\Delta(s,x)}\qquad(s\neq\emptyset,\ x\neq\perp,\ 1/0:=\infty,\ 1/\infty:=0)φ(s,x):=∣s∣Δ(s,x)1​(s=∅, x=⊥, 1/0:=∞, 1/∞:=0)

is a concave friendliness score, and

n≥400 bln⁡2(16/δ)ε3/2.n\ge\frac{400\,b\ln^2(16/\delta)}{\varepsilon^{3/2}}.n≥ε3/2400bln2(16/δ)​.

Then PFRbε,δ(Nσ/(τn)(g),φ,τ)\mathrm{PFR}_b^{\varepsilon,\delta}\big(\mathcal N_{\sigma/(\tau n)}(g),\varphi,\tau\big)PFRbε,δ​(Nσ/(τn)​(g),φ,τ) is (ε,δ)(\varepsilon,\delta)(ε,δ)-differentially private on datasets of nnn records.

Here PFRbε,δ(M,φ,τ)=M∘Fb,t,κ,σF,σF′(F2τ(φ))\mathrm{PFR}_b^{\varepsilon,\delta}(M,\varphi,\tau)=M\circ\mathcal F_{b,t,\kappa,\sigma_F,\sigma_F'}(F_{2\tau}(\varphi))PFRbε,δ​(M,φ,τ)=M∘Fb,t,κ,σF​,σF′​​(F2τ​(φ)) uses the parameters of Theorem 4.5: L=ln⁡(16/δ)L=\ln(16/\delta)L=ln(16/δ), t=7n/(8b)t=7n/(8b)t=7n/(8b), σF=12/ε\sigma_F=12/\varepsilonσF​=12/ε, σF′=108L/ε3/2\sigma_F'=108L/\varepsilon^{3/2}σF′​=108L/ε3/2, κ=2σFL\kappa=2\sigma_FLκ=2σF​L; and Nσ/(τn)(g)\mathcal N_{\sigma/(\tau n)}(g)Nσ/(τn)​(g) adds Gaussian noise of standard deviation σ/(τn)\sigma/(\tau n)σ/(τn) to ggg.

The theorem turns a per-instance sensitivity bound with a concave reciprocal into a differentially private scalar release whose noise scales with the typical, not the worst-case, sensitivity.

Formalization Note The score is any function X∗×X→[0,∞]\mathcal X^*\times\mathcal X\to[0,\infty]X∗×X→[0,∞] equal to (∣s∣ Δ(s,x))−1(|s|\,\Delta(s,x))^{-1}(∣s∣Δ(s,x))−1 (inverse in [0,∞][0,\infty][0,∞]) on nonempty sss and non-null xxx; "concave friendliness score" is the published IsScore and IsConcave, and the first forces the value 000 on the empty dataset. The PFR law is the published compose of the Gaussian mechanism over filterLaw; differential privacy is the published IsDPOn.

Differences from the source:

  • encoding: n/b ∈ ℕ → hypotheses 0 < b and b ∣ n; reason: same instances
  • encoding: PFR^{ε,δ}b(N{σ/(τn)}(g), φ, τ) → compose (gaussMech g (σ/(τn))) (filterLaw b t κ σ_F σ_F′ (predOf φ (2τ))) with t, κ, σ_F, σ_F′ of Theorem 4.5; reason: the definition of PFR^{ε,δ}_b on p.13 in the published base encodings
  • encoding: the score φ defined for nonempty s and x ≠ ⊥ → any φ : X* × X → [0, ∞] equal to (|s| Δ(s, x))⁻¹ there, with IsScore φ and IsConcave φ; reason: the paper leaves φ(∅, x) to Definition 4.4 (which forces 0, as IsScore does) and the value at ⊥ free (footnote 5)
  • encoding: Δ bounds the per-instance sensitivity of g, a real-valued function on nonempty datasets → IsPerInstanceBound g Δ with g : List (Option X) → ℝ; reason: Definition D.1 with its quantifier over every n ≥ 1; the value of g on the empty list is never used
  • encoding: N_{σ/(τn)}(g) adds N(0, (σ/(τn))²) → gaussianReal (g s) ((σ/(τn))²); reason: Mathlib's Gaussian takes the variance
Preamble
import Mathlib
import Definitions.Def_PFRelease_Indist
import Definitions.Def_PFRelease_compose
import Definitions.Def_PFRelease_IsScore
import Definitions.Def_PFRelease_IsConcave
import Definitions.Def_PFRelease_filterLaw
import Definitions.Def_PFRelease_Supplement_gaussMech

open MeasureTheory
Formal statement
namespace PFRelease.Supplement

/-- **Theorem D.2 (Scalar PFR)** (Shenfeld, Tsfadia, Ligett, *Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private
Filtering*, arXiv:2610.40654 (held version, sha256 e1d516b3…), Theorem D.2, p.39 = PDF p.41). Given `n, b ∈ ℕ` with
`n/b ∈ ℕ`, `ε ∈ (0, 1]`, `δ ∈ (0, 1)`, `σ > 0` with `δ_{N_σ}(ε/2) ≤ δ/4`, a friendliness threshold
`τ > 0`, a real-valued function `g` on nonempty datasets and a function `Δ` that bounds its per-instance
sensitivity, if the score `φ(s, x) := 1/(|s| Δ(s, x))` (nonempty `s`, `x ≠ ⊥`, `1/0 := ∞`, `1/∞ := 0`) is
a concave friendliness score and `n ≥ 400b ln²(16/δ)/ε^{3/2}`, then `PFR_b^{ε,δ}(N_{σ/(τn)}(g), φ, τ)` is
`(ε, δ)`-DP on datasets of `n` records.

**Formalization Note** `PFR_b^{ε,δ}(M, φ, τ) = M ∘ F_{b,t,κ,σ_F,σ_F′}(F_{2τ}(φ))` with the parameters of
Theorem 4.5 (p.13): `t = 7n/(8b)`, `σ_F = 12/ε`, `σ_F′ = 108L/ε^{3/2}`, `κ = 2σ_F L`, `L = ln(16/δ)`;
its law is the published `compose` over `filterLaw`. `N_{σ/(τn)}(g)` adds Gaussian noise of standard
deviation `σ/(τn)` (variance `(σ/(τn))²`). `φ` is any function `X* × X → [0, ∞]` equal to
`(|s| Δ(s, x))⁻¹` (in `ℝ≥0∞`) on nonempty `s` and `x ≠ ⊥`; its value on `∅` is forced to `0` by
`IsScore` and its value at `⊥` is free, as the paper leaves them. "Concave friendliness score" is
`IsScore φ ∧ IsConcave φ`. `b > 0`, `b ∣ n` encode `n/b ∈ ℕ`. -/
theorem theorem_D_2 {X : Type*} (n b : ℕ) (hb : 0 < b) (hbn : b ∣ n) (ε δ σ τ : ℝ)
    (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hδ0 : 0 < δ) (hδ1 : δ < 1) (hσ : 0 < σ)
    (hprof : gaussProfile σ (ε / 2) ≤ δ / 4) (hτ : 0 < τ)
    (g : List (Option X) → ℝ) (Δ : List (Option X) → Option X → ENNReal)
    (hΔ : IsPerInstanceBound g Δ) (φ : List (Option X) → Option X → ENNReal)
    (hφ : ∀ (l : List (Option X)) (x : Option X), l ≠ [] → x ≠ none →
      φ l x = ((l.length : ENNReal) * Δ l x)⁻¹)
    (hscore : IsScore φ) (hconc : IsConcave φ)
    (hn : 400 * (b : ℝ) * Real.log (16 / δ) ^ 2 / ε ^ (3 / 2 : ℝ) ≤ n) :
    let L := Real.log (16 / δ)
    let t := 7 * (n : ℝ) / (8 * (b : ℝ))
    let σF := 12 / ε
    let σF' := 108 * L / ε ^ (3 / 2 : ℝ)
    let κ := 2 * σF * L
    IsDPOn (compose (gaussMech (n := n) g (σ / (τ * n)))
      (filterLaw b t κ σF σF' (predOf φ (2 * τ)))) ε δ := by sorry

end PFRelease.Supplement
Source
Shenfeld, Tsfadia, Ligett, Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering, arXiv:2610.40654 (held version, sha256 e1d516b3…), Theorem D.2, p.39 (PDF p.41); PFR^{ε,δ}_b, p.13 (PDF p.15)

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