Abstract
Knowledge distillation has emerged as a scalable and effective way for privacy-preserving machine learning. One remaining drawback is that it consumes privacy in a model-level (i.e., client-level) manner, every distillation query incurs privacy loss of one client's all records. In order to attain fine-grained privacy accountant and improve utility, this work proposes a model-free reverse $k$-NN labeling method towards record-level private knowledge distillation, where each record is employed for labeling at most $k$ queries. Theoretically, we provide bounds of labeling error rate under the centralized/local/shuffle model of differential privacy (w.r.t. the number of records per query, privacy budgets). Experimentally, we demonstrate that it achieves new state-of-the-art accuracy with one order of magnitude lower of privacy loss. Specifically, on the CIFAR-$10$ dataset, it reaches $82.1\%$ test accuracy with centralized privacy budget $1.0$; on the MNIST/SVHN dataset, it reaches $99.1\%$/$95.6\%$ accuracy respectively with budget $0.1$. It is the first time deep learning with differential privacy achieve comparable accuracy with reasonable data privacy protection (i.e., $\exp(\epsilon)\leq 1.5$).
1. Introduction
In the landscape of Federated Learning (FL), maintaining user data privacy is paramount. A prevalent technique is Knowledge Distillation (KD), where clients use private data to train a "teacher" model, which then labels public, unlabeled data to train a "student" model. However, traditional KD methods suffer from being "privacy-hungry." Because teacher models are typically trained on a client's entire dataset, every query answered by the teacher potentially leaks information about all of that client's records—a paradigm known as client-level privacy.
This blunt approach means a single query can exhaust the privacy budget ($\epsilon$) for thousands of records simultaneously. Consequently, practitioners often face a trade-off between model utility and acceptable privacy risk. This paper introduces a "reverse $k$-NN" labeling method that shifts the focus to fine-grained record-level privacy, significantly improving the privacy-utility frontier.
2. Methodology: Reverse $k$-NN Labeling
The proposed approach is "model-free," bypassing the need to train local neural network teachers. The workflow consists of several key stages:
- Representation Learning: Unsupervised learning (e.g., SimCLR) is performed on public data to create a semantic feature space where similar images are clustered.
- Reverse $k$-NN Mapping: Instead of a black-box model, each client identifies the $k$ most similar public "query" images for every private record in the feature space.
- Bounded Contribution: By design, a single private record influences at most $k$ specific queries. This mathematically bounds the sensitivity of the data, allowing for precise record-level accounting.
- Bucketized Sparse Vector Summation (BSVS): Labels are treated as one-hot vectors, and specialized Differential Privacy (DP) mechanisms are used to add noise efficiently during aggregation.
This framework supports three trust scenarios: Centralized (trusted server), Local (zero trust, noise added by client), and Shuffle (intermediate anonymization for privacy amplification).
3. Experimental Evaluation
The researchers evaluated the method on three standard benchmarks: MNIST, SVHN, and CIFAR-10. Unlike many DP studies that focus solely on simple digit datasets, this work demonstrates robust performance on the semantically complex CIFAR-10 dataset.
3.1 Key Results
The results represent a significant leap in performance, achieving state-of-the-art (SOTA) accuracy with privacy losses an order of magnitude lower than previous methods like PATE (LNMAX/GNMAX) or Noisy SGD.
- CIFAR-10: Reached 82.1% accuracy with a centralized budget of $\epsilon = 1.0$. Previous SOTA methods often fail to reach 70% even with higher budgets.
- MNIST/SVHN: Achieved 99.1% and 95.6% accuracy respectively with a minimal budget of $\epsilon = 0.1$.
- Local DP: Even under stringent Local DP requirements, the method achieved 98.5% on MNIST with $\epsilon = 0.4$.
4. Discussion and Limitations
The success of this method relies heavily on the quality of the unsupervised feature extractor. If the embeddings do not cluster classes effectively, the $k$-NN labels become noisy. Additionally, the method requires a representative set of unlabeled public data to serve as queries; a significant distribution shift between public and private data can degrade performance.
Future work includes applying Rényi Differential Privacy to further tighten privacy bounds and exploring more sophisticated connection rules to ensure all public queries receive sufficient private label contributions.
Summary updated