Equation (7) — E[g(u, c_{r,a}(u))] = C_g + ⟨f⁰_g, c⁰_{r,a}⟩ + ⟨f¹_g, c¹_{r,a}⟩
ProvedPrivLearn.MaskedParity.eq_7fourier-analysislearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1statistical-query-learning
Let examples be uniform on the MASKED-PARITY domain . For every statistical query with real values and every target ,
The true answer to a query splits into a part independent of the target, a part that depends only on (the half ), and the only part that depends on the mask bit (the half ).
Formalization Note. The identity holds for every real-valued because the labels are . The statement imposes no condition on .
Preamble
import Mathlib import Definitions.Def_PrivLearn_MaskedParity_Model import Definitions.Def_PrivLearn_MaskedParity_Oracle
Formal statement
namespace PrivLearn.MaskedParity
/-- **Equation (7)** (p. 29). For every real-valued query `g(u, y)` and every target `c_{r,a}`,
`E[g(u, c_{r,a}(u))] = C_g + ⟨f^0_g, c^0_{r,a}⟩ + ⟨f^1_g, c^1_{r,a}⟩`. -/
theorem eq_7 {d : ℕ} (r : Fin d → ZMod 2) (a : ZMod 2) (g : Dom d → ℝ → ℝ) :
qval (cMP r a) g =
Cg g + ip (half 0 (fg g)) (half 0 (cMP r a)) + ip (half 1 (fg g)) (half 1 (cMP r a)) := by sorry
end PrivLearn.MaskedParity
Source
Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can We Learn Privately?, arXiv:0803.0924v3, p. 29, equation (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.