Smooth Sensitivity for k-Nearest Neighbor

on YouTube ↗48m

" summary

Proposes using smooth sensitivity for k‑nearest‑neighbor imputation to avoid the astronomic global sensitivity that simple donor reuse causes, derives an upper bound (extends 1‑NN to k‑NN) and tweaks the beta scaling so epsilon‑DP noise is feasible, observes typical donor‑to‑donee ratios around four on ACS public microdata, builds a simulation from 1940 census to model realistic missingness, and finds results reduce bias at the cost of higher variance — a clear bias‑variance tradeoff for private imputation.

AI-written summary · about

" chapters (8)

1. 0:00Research context and goals
2. 2:15Sensitivity in data allocation
3. 7:13Addressing imputation bias
4. 11:02Smooth sensitivity approach
5. 14:32Theoretical framework
6. 20:28Greedy algorithms and bounds
7. 25:43Empirical evaluation plan
8. 33:30Implementation and policy

" related talks

• 01h 08mNearest Neighbors IKamalika Chaudhuri · Deep Learning Boot Camp 2019
• 01h 05mNearest Neighbors IIKamalika Chaudhuri · Deep Learning Boot Camp 2019
• 40mFast NN Prediction with No Statistical TradeoffSamory Kpotufe · Sublinear Algorithms and Nearest-Neighbor Search
• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 22mGeneralization IVPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 47mSmooth Sensitivity, RevisitedThomas Steinke · Privacy and the Science of Data Analysis 2019
• 40mEfficient Reductions for k-Nearest Neighbor SearchRasmus Pagh · Sublinear Algorithms and Nearest-Neighbor Search
• 40mTools and Tricks from a Pragmatic Data ScientistLucas Javier Bernardi · PyData Amsterdam 2016