Theorem 5.7 — an ε-local algorithm simulates any t-query SQ algorithm
ProvedPrivLearn.LocalSim.theorem_5_7There is an absolute constant with the following property. Let be an SQ algorithm on a domain that makes queries , with , and let . Consider the simulation of that answers the -th query by running on the -th block of previously unused entries of the database , and outputs what outputs on the simulated answers.
- Privacy. For every block size and every database size , the simulation is -differentially private.
- Accuracy. Let every query have tolerance at least , where , , and . If the block size satisfies
(so the simulation uses entries, and the database has entries) and the entries of are i.i.d. from , then with probability at least over the database and the noise, every simulated answer is within the tolerance of for the query actually asked. The simulated answers are then the answers of a valid SQ oracle , so the simulation gives the same output as 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 " is before every other quantifier; the block size is with , so ; we use the natural logarithm (the paper's base 2 only changes ) 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 queries. "Gives the same output as " is formalized as: the simulated transcript is a valid transcript of against ; the accuracy claim bounds the measure of the failure event by . 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; and in the accuracy claim only, without which it is false already for (see Lemma 5.6); the privacy claim holds for every . "Noninteractive if is nonadaptive" and "efficient if is efficient" are not formalized.
import Mathlib import Definitions.Def_PrivLearn_LocalSim_Privacy import Definitions.Def_PrivLearn_LocalSim_Simulation
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.