"Private Prediction Strikes Back!'' Private Kernelized Nearest Neighbors
  with Individual Renyi Filter
Yuqing Zhu Xuandong Zhao Chuan Guo Yu-Xiang Wang
Most existing approaches of differentially private (DP) machine learning
focus on private training. Despite its many advantages, private training lacks
the flexibility in adapting to incremental changes to the training dataset such
as deletion requests from exercising GDPR's right to be forgotten. We revisit a
long-forgotten alternative, known as private prediction, and propose a new
algorithm named Individual Kernelized Nearest Neighbor (Ind-KNN). Ind-KNN is
easily updatable over dataset changes and it allows precise control of the
R\'{e}nyi DP at an individual user level -- a user's privacy loss is measured
by the exact amount of her contribution to predictions; and a user is removed
if her prescribed privacy budget runs out. Our results show that Ind-KNN
consistently improves the accuracy over existing private prediction methods for
a wide range of $\epsilon$ on four vision and language tasks. We also
illustrate several cases under which Ind-KNN is preferable over private
training with NoisySGD.