Generalized Private Selection and Testing with High Confidence
summary
A unified framework produces a private selection algorithm that attains 2 + o(1) pure DP selection from arbitrarily many epsilon‑DP candidates by randomized repeated runs, and a private testing routine that boosts confidence to certainty via confidence boosting by repeated alternating tests: run ~log(1/δ) noisy comparisons of f(D)+Lap(1/ε) against thresholds and switch tests only rarely so privacy cost occurs mainly on rejections with additive error about O((1/ε)·log(1/δ)). Applications improve sparse vector, yield decouples log(1/β) dependence in private MW and adaptive data analysis, and lower sample/error constants.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 7:00Application
- 9:40Priority Testing
- 15:20Innovation
- 19:44Issues
- 23:04Applications
- 24:29Conclusion
related talks
44mPrivate Meta-Selection
43mDifferential Privacy Meets Robust Statistics
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
38mDifferentially Private Inference for Binomial Data
19mPractical Considerations for Differential Privacy
19mGeneral-Purpose f-DP Estimation and Auditing in a Black-Box Setting
48mThe Structure of Optimal Private Tests for Simple Hypotheses
58mLarge-Scale Private Learning, Part III