Lemma 18, p.21 — selection gap of the exponential mechanism:
ProvedPureDPQR.lemma_18differential-privacyexponential-mechanismp2o-gran-per-chapterp2o-plan-paperp2o-v1query-release
Lemma 18 (Selection gap from exponential mechanism). Let , , , and on . Then
It is applied to each round's softmax selection in the proof of Proposition 21.
Formalization Note The maximum is a supremum over the nonempty finite index set Fin K.
Differences from the source:
- reading: [K] for a_i, i ∈ [K] → K ≥ 1; reason: max_i a_i requires a nonempty index set
- encoding: 1-based labels [K] → Fin K; reason: Lean convention
Preamble
import Mathlib
Formal statement
namespace PureDPQR
/-- **Lemma 18** (Selection gap from exponential mechanism), p.21 (PDF p.22).
Z. Zou, *Pure Differentially Private Query Release via Laplace Input Smoothing*, arXiv:2611.04721
(held version, sha256 69b70d59…).
"Let a_i ∈ R for each i ∈ [K]. If P(i) = e^{λa_i} / ∑_j e^{λa_j} on [K] and λ > 0, then
max_i a_i − E_{i∼P} a_i ≤ log K / λ."
**Formalization Note.** Labels are `Fin K` (0-based). The maximum over `[K]` exists only for
`K ≥ 1`, which is stated (`0 < K`); `max_i a_i` is `⨆ i, a i`, a maximum of finitely many reals.
`λ` is written `lam`. -/
theorem lemma_18 {K : ℕ} (hK : 0 < K) (a : Fin K → ℝ) (lam : ℝ) (hlam : 0 < lam) :
let P : Fin K → ℝ := fun i => Real.exp (lam * a i) / ∑ j, Real.exp (lam * a j)
(⨆ i, a i) - ∑ i, P i * a i ≤ Real.log K / lam := by sorry
end PureDPQR
Source
Zou, Pure Differentially Private Query Release via Laplace Input Smoothing, arXiv:2611.04721 (held version, sha256 69b70d59…), Lemma 18, p.21 (PDF p.22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.