Proof of Theorem 5.16(2), p. 30 — Σ_{(r,a)} 2⟨f⁰_g, c⁰_{r,a}⟩² ≤ 1
ProvedPrivLearn.MaskedParity.besselfourier-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1paritystatistical-query-learning
Let be a power of two, let examples be uniform on the MASKED-PARITY domain , and let be a statistical query with values in on labels . Then
This Bessel inequality bounds the total correlation of one query with all the halves of the concepts, which is what limits how many targets a single nonadaptive query can distinguish.
Formalization Note. The range condition on is the paper's (, p. 29); values of at other labels play no role.
Preamble
import Mathlib import Definitions.Def_PrivLearn_MaskedParity_Model import Definitions.Def_PrivLearn_MaskedParity_Oracle
Formal statement
namespace PrivLearn.MaskedParity
/-- **Bessel display** (p. 30). Let `d` be a power of two and let `g` be a statistical query
with values `±1` on labels `±1`. Then
`∑_{(r,a) ∈ {0,1}^d × {0,1}} 2 · ⟨f^0_g, c^0_{r,a}⟩² ≤ 1`. -/
theorem bessel {d : ℕ} (hd : ∃ m : ℕ, d = 2 ^ m) (g : Dom d → ℝ → ℝ)
(hg : ∀ u y, (y = 1 ∨ y = -1) → (g u y = 1 ∨ g u y = -1)) :
∑ ra : (Fin d → ZMod 2) × ZMod 2, 2 * ip (half 0 (fg g)) (half 0 (cMP ra.1 ra.2)) ^ 2 ≤ 1 := by sorry
end PrivLearn.MaskedParity
Source
Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can We Learn Privately?, arXiv:0803.0924v3, p. 30, proof of Theorem 5.16 part (2), display 'Summing the two previous equations'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.