Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.7 — an ε-local algorithm simulates any t-query SQ algorithm

Proved
PrivLearn.LocalSim.theorem_5_7

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-privacylocal-privacyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1statistical-queries

There is an absolute constant c>0c>0c>0 with the following property. Let ASQ\mathcal A_{SQ}ASQ​ be an SQ algorithm on a domain DDD that makes ttt queries gk:D→[−b,b]g_k:D\to[-b,b]gk​:D→[−b,b], with ∣gk∣≤b|g_k|\le b∣gk​∣≤b, and let b,ε>0b,\varepsilon>0b,ε>0. Consider the simulation of ASQ\mathcal A_{SQ}ASQ​ that answers the kkk-th query by running Agk(m,ε,LRz)\mathcal A_{g_k}(m,\varepsilon,LR_z)Agk​​(m,ε,LRz​) on the kkk-th block of mmm previously unused entries of the database zzz, and outputs what ASQ\mathcal A_{SQ}ASQ​ outputs on the simulated answers.

  1. Privacy. For every block size mmm and every database size n≥tmn\ge tmn≥tm, the simulation is ε\varepsilonε-differentially private.
  2. Accuracy. Let every query have tolerance at least τ\tauτ, where τ>0\tau>0τ>0, 0<β<10<\beta<10<β<1, ε≤1\varepsilon\le1ε≤1 and ετ≤4b\varepsilon\tau\le4bετ≤4b. If the block size satisfies
m ≥ c⋅ln⁡(t/β) b2ε2τ2m\ \ge\ c\cdot\frac{\ln(t/\beta)\,b^2}{\varepsilon^2\tau^2}m ≥ c⋅ε2τ2ln(t/β)b2​

(so the simulation uses tm ≥ c tln⁡(t/β)b2/(ε2τ2)tm\ \ge\ c\,t\ln(t/\beta)b^2/(\varepsilon^2\tau^2)tm ≥ ctln(t/β)b2/(ε2τ2) entries, and the database has n≥tmn\ge tmn≥tm entries) and the entries of zzz are i.i.d. from PPP, then with probability at least 1−β1-\beta1−β over the database and the noise, every simulated answer aka_kak​ is within the tolerance τk\tau_kτk​ of Eu∼P[gk(u)]\mathbb E_{u\sim P}[g_k(u)]Eu∼P​[gk​(u)] for the query gkg_kgk​ actually asked. The simulated answers are then the answers of a valid SQ oracle SQPSQ_PSQP​, so the simulation gives the same output as ASQ\mathcal A_{SQ}ASQ​ run against that oracle.

This is the direction "SQ ⊆ local" of the equivalence between private learning in the local model and SQ learning.

Formalization Note. "For sufficiently large constant ccc" is ∃c>0\exists c>0∃c>0 before every other quantifier; the block size is n′=clog⁡(1/β′)b2/(ε2τ2)n'=c\log(1/\beta')b^2/(\varepsilon^2\tau^2)n′=clog(1/β′)b2/(ε2τ2) with β′=β/t\beta'=\beta/tβ′=β/t, so log⁡(1/β′)=log⁡(t/β)\log(1/\beta')=\log(t/\beta)log(1/β′)=log(t/β); we use the natural logarithm (the paper's base 2 only changes ccc) and allow any block size above the threshold. The SQ algorithm is a deterministic adaptive strategy (a randomized one is a mixture over its coins), with exactly ttt queries. "Gives the same output as ASQ\mathcal A_{SQ}ASQ​" is formalized as: the simulated transcript is a valid transcript of ASQ\mathcal A_{SQ}ASQ​ against SQPSQ_PSQP​; the accuracy claim bounds the measure of the failure event by β\betaβ. Privacy is stated for the output law of the simulation and assumes the output map is measurable (otherwise the push-forward is the zero measure). Added hypotheses: each query is jointly measurable in (earlier answers, input), which the paper does not discuss and which makes the simulated answers measurable functions of the noise and the data; ε≤1\varepsilon\le1ε≤1 and ετ≤4b\varepsilon\tau\le4bετ≤4b in the accuracy claim only, without which it is false already for t=1t=1t=1 (see Lemma 5.6); the privacy claim holds for every ε>0\varepsilon>0ε>0. "Noninteractive if ASQ\mathcal A_{SQ}ASQ​ is nonadaptive" and "efficient if ASQ\mathcal A_{SQ}ASQ​ is efficient" are not formalized.

Preamble
import Mathlib
import Definitions.Def_PrivLearn_LocalSim_Privacy
import Definitions.Def_PrivLearn_LocalSim_Simulation
Formal statement
namespace PrivLearn.LocalSim

open MeasureTheory

/-- Theorem 5.7 (Local simulation of SQ, p. 21). There is an absolute constant `c > 0` such that
for every SQ algorithm `A` making `t` queries `g_k : Dom → [−b, b]`, each with tolerance at least
`τ`:

1. (privacy) for every block size `m` and every database size `n ≥ t m`, the simulation, which
   answers the `k`-th query by running `A_{g_k}(m, ε, LR_z)` on the `k`-th block of `m` entries of
   `z`, and outputs `A`'s output on the simulated answers, is ε-differentially private;
2. (accuracy) if the block size is `m ≥ c · ln(t/β) b² / (ε² τ²)` (so `n ≥ t m` entries are used)
   and the entries of `z` are i.i.d. from `P`, then with probability at least `1 − β` the
   simulated answers form a transcript of `A` against a valid SQ oracle `SQ_P`, so the simulation
   gives the same output as `A` run against that oracle: the failure event has measure `≤ β`.

The accuracy claim is stated for `ε ≤ 1` and in the regime `ε τ ≤ 4 b`, without which it is false;
the privacy claim holds for every `ε > 0` and carries neither hypothesis. -/
theorem theorem_5_7 :
    ∃ c : ℝ, 0 < c ∧
      ∀ (Dom Out : Type) [MeasurableSpace Dom] [MeasurableSpace Out] (t : ℕ) (A : SQAlg Dom Out t)
        (b ε : ℝ),
        0 < b → 0 < ε →
        (∀ (k : Fin t) (a : Fin k → ℝ) (u : Dom), |A.query k a u| ≤ b) →
        (∀ k : Fin t, Measurable fun p : (Fin k → ℝ) × Dom => A.query k p.1 p.2) →
        -- privacy (for every ε > 0, every block size and every database)
        (Measurable A.output →
          ∀ (m n : ℕ) (h : t * m ≤ n),
            PrivLearn.Generic.IsDP (fun z : Fin n → Dom => simOutputLaw A b ε m h z) ε) ∧
        -- accuracy
        (∀ (τ β : ℝ), ε ≤ 1 → 0 < τ → ε * τ ≤ 4 * b → 0 < β → β < 1 →
          (∀ (k : Fin t) (a : Fin k → ℝ), τ ≤ A.tol k a) →
          ∀ (P : Measure Dom) [IsProbabilityMeasure P] (m n : ℕ) (h : t * m ≤ n),
            c * Real.log (t / β) * b ^ 2 / (ε ^ 2 * τ ^ 2) ≤ m →
            ((Measure.pi fun _ : Fin n => P).prod (noiseLaw t m b ε))
                {p | ¬ A.IsValidTranscript P (simTranscript A m h p.1 p.2)}
              ≤ ENNReal.ofReal β) := by sorry

end PrivLearn.LocalSim
Source
Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can We Learn Privately?, arXiv:0803.0924v3, p. 21, Theorem 5.7 (with the Simulation paragraph above it)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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