Efficiently Computing Similarities to Private Datasets
summary
Proposes a private summary that answers similarity queries (sum of f(x,y)) with small additive error that does not grow with n by reducing L1 to per-coordinate one-dimensional problems, building binary tree counts with log sensitivity and adding calibrated noise to each node; query time is sublinear, construction runs roughly linear time, and the additive error scales with d and log factors (no n dependence). Shows L2 handled via an oblivious JL-style reduction and a CIFAR-10 experiment where the method is far faster but modestly less accurate than DP-trained neural nets.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 3:58Problem formalization
- 8:14Sublinear algorithms fit
- 12:31L1 distance reduction
- 16:50Private data structure
- 20:48Other similarity functions
- 21:54Private classification
- 24:44Neural network comparison
- 26:28Sublinear algorithm links
- 27:10Closing & Q&A
related talks
01h 14mStatistical Inference and Privacy, Part III
01h 02mLarge-Scale Private Learning, Part I
58mLarge-Scale Private Learning, Part III
46mPrivate Center Points and Learning of Halfspaces
17mData privacy and reliable learning
01h 14mTutorial: Privacy, Part III
48mSynthetic Data as an Enabler for Learning from Decentralized Private Data
26mGeneralized Private Selection and Testing with High Confidence