Algorithms for Answering Linear Queries, Part II
summary
Adds Gaussian noise to query answers and then projects back onto the feasible set of answers so noisy outputs become consistent; this Gaussian noise + projection never increases error and yields root mean squared error on counting queries about O(sqrt(n) · polylog |Universe|) in the small-database regime. Exact projection is NP‑hard (reduces from max‑cut), but a semidefinite relaxation gives an efficiently projectable polytope within constant factors. For large workloads, a learning approach using multiplicative weights / exponential mechanism privately learns the empirical distribution and achieves worst‑case guarantees with comparable sample bounds.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:11Projection mechanism
- 5:30Mean squared error
- 10:22Compactly specified queries
- 16:50Projection
- 19:03Data Dependent
- 21:04Boosting
- 23:48Recap
- 25:43Private Multiplicative Voice
- 29:54Synthetic Data
- 31:01Above Threshold Mechanism
- 33:08Linear Counting Queries
- 34:29Outline
- 35:14Two Approaches
- 42:05Intuition
- 47:59Comparison
- 50:47Data agnostic algorithms
- 55:35DataAdaptive vs DataAgnostic
related talks
01h 00mDifferential Privacy And The Complexity Of Simple Queries
26mAlgorithms with More Granular Differential Privacy Guarantees
39mVirtual talk by Jonathan Ullman (Northeastern)
01h 19mOpen Problem Session
27mYou've got trust issues, we've got solutions: Differential Privacy
54mPrivacy Amplification from Structured Algorithmic Randomness
01h 17mTutorial: Privacy, Part I
36mPrivately Learning High-Dimensional Distributions