Fine-Grained Private Knowledge Distillation

Yuntong Li, Shaowei Wang, Yingying Wang, Jin Li, Yuqiu Qian, Bangzhou Xin, Wei Yang

TL;DR

This paper introduces a "reverse $k$-NN" labeling method that shifts the focus of private knowledge distillation from coarse client-level privacy to fine-grained record-level privacy. By limiting each private data point to influencing at most $k$ public queries, the authors achieve state-of-the-art accuracy on complex datasets like CIFAR-10 with a privacy loss ($\epsilon$) an order of magnitude lower than previous methods.

What Problem Does This Paper Address?

In the world of Federated Learning (FL), keeping user data private is the top priority. One popular technique is Knowledge Distillation (KD): instead of sharing raw data or gradients (which can leak info), clients use their private data to train a "teacher" model. This teacher then labels a set of public, unlabeled images, and those labels are used to train a "student" model.

The problem? Current KD methods are "privacy-hungry." Because a teacher model is trained on a client's entire dataset, every single query the teacher answers potentially leaks information about all of that client's records. This is known as client-level privacy. It’s a blunt instrument; if you have 1,000 photos on your phone, a single query might "cost" the privacy budget of all 1,000. This makes it incredibly difficult to scale to many queries without exhausting the privacy budget ($\epsilon$), often leading to a choice between a uselessly inaccurate model or a dangerously high privacy risk.

Methods

The authors propose a "model-free" approach called Reverse $k$-NN Labeling. Here’s how it works:

  1. Representation Learning: First, they use unsupervised learning (like SimCLR) on public data to create a "feature space" where similar images are close together.
  2. The Reverse $k$-NN Trick: Instead of training a neural network teacher, each client looks at their private records. For every private record, they find the $k$ most similar public "query" images in the feature space.
  3. Bounded Contribution: This is the "Aha!" moment. By design, a single private record is only allowed to contribute its label to those $k$ specific queries. This mathematically bounds the "sensitivity" of the data. We now know exactly how much influence one record has: it affects $k$ labels, and that’s it.
  4. Bucketized Sparse Vector Summation (BSVS): They formalize this process as a summation problem. Since labels are "one-hot" vectors (mostly zeros), they can use specialized Differential Privacy (DP) mechanisms to add noise efficiently.
  5. Multi-Model DP: The paper provides solutions for three trust scenarios:
  6. Centralized: A trusted server aggregates the noisy labels.
  7. Local: Each client adds noise before sending anything (zero trust).
  8. Shuffle: An intermediate "shuffler" anonymizes reports to boost privacy without adding as much noise as the Local model.

Datasets

The researchers evaluated their method on three standard computer vision benchmarks:

  • MNIST: 70,000 grayscale images of handwritten digits.
  • SVHN (Street View House Numbers): Over 600,000 images of digits in the wild.
  • CIFAR-10: 60,000 color images across 10 diverse categories (planes, dogs, etc.).

Unlike many DP papers that stick to simple digits, this work shows strong results on the more semantically complex CIFAR-10.

Key Insights and Ideas

  • Record-Level vs. Client-Level: By moving to record-level accounting, the privacy budget is spent much more efficiently. You aren't "paying" for the whole dataset every time you answer a question; you're only paying for the specific records that were close enough to the query to matter.
  • Model-Free is a Feature, Not a Bug: By skipping the local teacher model training, the method avoids the "black box" nature of neural networks, where it's nearly impossible to track exactly which training image influenced which output.
  • Semantic Embeddings are Essential: The success of $k$-NN depends entirely on the distance metric. Using modern unsupervised representation learning allows the "nearest neighbors" to be semantically meaningful (e.g., a private picture of a cat helping to label a public picture of a cat) rather than just matching raw pixel values.

Key Results

The results represent a significant leap in the privacy-utility tradeoff:

  • CIFAR-10: Achieved 82.1% accuracy with a centralized privacy budget of $\epsilon = 1.0$. For context, previous SOTA methods often struggle to break 70% accuracy even with much higher (less private) budgets.
  • MNIST/SVHN: Reached 99.1% and 95.6% accuracy respectively with a tiny budget of $\epsilon = 0.1$.
  • Efficiency: The method achieved these results with roughly one order of magnitude less privacy loss than competitive approaches like PATE (LNMAX/GNMAX) or Noisy SGD.
  • Local DP Breakthrough: Even in the most stringent "Local DP" setting (where users don't trust the server at all), they achieved 98.5% on MNIST with $\epsilon = 0.4$, proving that high-accuracy private federated learning is practical.

Limitations and Future Work

  • Dependency on Public Data: The method requires a representative set of unlabeled public data ($D_{pub}$) to act as the "queries." If the public data is wildly different from the private data, the $k$-NN mapping will fail.
  • Representation Quality: The accuracy is bottlenecked by the quality of the unsupervised feature extractor. If the embeddings don't cluster classes well, the labels will be noisy.
  • Future Directions: The authors suggest that applying Rényi Differential Privacy (a more advanced accounting technique) could tighten the privacy bounds even further. They also see potential in exploring more balanced connection rules beyond simple $k$-NN to handle cases where some public queries are "ignored" by all private records.

Summary updated

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 client-level manner. 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 private record is employed for labeling at most k queries. Theoretically, we provide bounds of labeling error rate under the centralized/local model of differential privacy. Experimentally, we demonstrate that it achieves new state-of-the-art accuracy in MNIST/SVHN/CIFAR-10 dataset with one order of magnitude lower of privacy loss.
BibTeX
@inproceedings{li2023fine,
  author = {Yuntong Li and Shaowei Wang and Yingying Wang and Jin Li and Yuqiu Qian and Bangzhou Xin and Wei Yang},
  title = {{Fine-Grained Private Knowledge Distillation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  url = {https://openreview.net/forum?id=10j7ZagcS9},
}

Loading related content...

Figure