"Private Prediction Strikes Back!'' Private Kernelized Nearest Neighbors with Individual Renyi Filter
This work addresses the need for flexible and updatable privacy-preserving machine learning, particularly for compliance with regulations like GDPR, though it is incremental in building on private prediction methods.
The paper tackles the problem of adapting differentially private machine learning to incremental dataset changes, such as deletions under GDPR, by proposing a private prediction algorithm called Ind-KNN that allows precise control of individual privacy loss. The results show that Ind-KNN consistently improves accuracy over existing private prediction methods across four vision and language tasks for a wide range of privacy budgets.
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é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 $ε$ on four vision and language tasks. We also illustrate several cases under which Ind-KNN is preferable over private training with NoisySGD.