Privately Estimating Black-Box Statistics
summary
Provides a concrete scheme that privately estimates arbitrary black‑box functions by evaluating F on overlapping subsets and aggregating with the shifted inverse mechanism, trading sample cost m against oracle calls k. Key parameters: T roughly equals 1/ε, worst‑case query complexity k ≈ n^T (so k ≈ n^{1/ε} up to logs), and matching statistical lower bounds show near‑optimality. Uses covering designs for subset choice and yields a tunable accuracy vs evaluation‑count tradeoff.
AI-written summary · about
chapters (13)
- 0:00Private black-box estimation intro
- 1:30Black-box function in privacy
- 3:16Sensitivity challenges
- 5:45Down local algorithms
- 8:15Theorem for down local DP
- 11:24Sample and aggregate method
- 14:48Accuracy guarantees
- 16:34Unified algorithm trade-offs
- 19:22Algorithm with overlapping subsets
- 23:37Shifted inverse mechanism
- 25:23Limitations and future work
- 27:09Summary
- 28:11Q&A