# "Private Prediction Strikes Back!'' Private Kernelized Nearest Neighbors with Individual Renyi Filter

arXiv: https://arxiv.org/abs/2306.07381 · HTML: https://mlsanity.com/paper/2306.07381/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 12 Jun 2023.

## Builds on (most cited first, 23 of 23)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Hypothesis Testing Interpretations and Renyi Differential Privacy](https://mlsanity.com/paper/1905.09982/) (2019)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [The Trade-Offs of Private Prediction](https://mlsanity.com/paper/2007.05089/) (2020)
- [PAC learning with stable and private predictions](https://mlsanity.com/paper/1911.10541/) (2019)
- [Compressing Sentence Representation for Semantic Retrieval via Homomorphic Projective Distillation](https://mlsanity.com/paper/2203.07687/) (2022)

## Built on by (most cited first, 5 of 5)

- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [DP-RDM: Adapting Diffusion Models to Private Domains Without Fine-Tuning](https://mlsanity.com/paper/2403.14421/) (2024)
- [Adaptively Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2410.02016/) (2024)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)

## Abstract (arXiv)

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'enyi 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.