Algorithms for Answering Linear Queries, Part III
summary
Presents a scalable variant of the matrix mechanism that replaces a global semidefinite program with local gradient optimization over a parameterized family of “identity strategies,” uses implicit workload representations and Kronecker factoring to avoid materializing huge matrices, and implements efficient pseudo‑inverse routines. Empirical claims: consistent 1.8× accuracy improvement over hierarchical range strategies and up to ~3× over naive identity baselines in some workloads; scales strategy search to domains ≈10k–1M (with techniques aiming toward larger sizes). The methods run and give concrete error bounds but still leave gaps to theoretical lower bounds.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 3:45Interpretive Structure
- 5:48Concrete Numbers
- 6:43Multidimensional Workloads
- 8:03Census Workloads
- 8:19Associativity
- 13:46Marginal Strategies
- 16:39Questions
- 22:36Challenges
- 29:33Aggregation
- 34:54Workload Tuning
- 38:49Tradeoffs
- 43:12Algorithm Performance
- 52:03Open Questions
related talks
07mJoin Algorithms Meet New Constraints: Scalability, Latency and Privacy
01h 19mOpen Problem Session
36mTalk by Mahdi Haghifam (Toyota Technological Institute at Chicago)
01h 00mDifferential Privacy And The Complexity Of Simple Queries
38mTowards Privacy-Respectful Cyber-Physical Systems: Two Perspectives
19mBeing Intentional: AB Testing and Data Minimization
26mAlgorithms with More Granular Differential Privacy Guarantees
44mPrivate Meta-Selection