Differentially Private Distributed Data Summarization under Covariate Shift

Kanthi K. Sarpatwar, Karthikeyan Shanmugam, Venkata Sitaramagiridharganesh Ganapavarapu, Ashish Jagmohan, Roman Vaculín

In the burgeoning world of "AI Marketplaces," data is the primary currency. However, a major hurdle exists: how can a company (the consumer) build a model using data from multiple private sources (the owners) when those sources are often competitors who refuse to share their raw datasets? To make matters more complicated, the data held by these owners often looks very different from the specific task the consumer wants to solve—a phenomenon known as covariate shift.

This paper, presented at NeurIPS 2019 by researchers at IBM, introduces a novel protocol for Differentially Private Distributed Data Summarization. It allows a central curator to pick the most relevant data points from various private sources to match a target task, all while providing rigorous privacy guarantees and minimizing the amount of data actually transferred.

TL;DR

The authors propose a protocol to create a representative "summary" dataset from multiple private distributed sources to match a specific target task. By combining random Fourier features with a novel private auctioning mechanism, they achieve strong differential privacy and "parsimonious" data access (minimizing the data the curator sees) while nearly matching the performance of non-private algorithms.

What Problem Does This Paper Address?

Imagine a new hospital wants to build a cancer prediction model. They have a small "validation" set of their own patients, but they need a massive training set. Other hospitals have that data, but they won't just hand it over due to patient privacy and competitive interests. Furthermore, the data from a hospital in New York might have different demographics than one in Tokyo (covariate shift).

The challenge is threefold:

  1. Selection: How do we pick the specific data points from the sources that best match the consumer's target distribution?
  2. Privacy: How do we ensure that Hospital A doesn't learn anything about Hospital B's data during the process?
  3. Parsimony: How do we prevent the central "curator" (the marketplace platform) from seeing more data than absolutely necessary?

The authors use Maximum Mean Discrepancy (MMD) as their yardstick—a popular metric for measuring the statistical distance between two distributions.

Methods

The authors transform a standard greedy algorithm for MMD minimization into a privacy-preserving distributed protocol. Their solution relies on two clever "hashing" steps and a unique auction:

  • Hash Function 1 ($h_1$): Based on the Rahimi-Recht random features method. This maps high-dimensional data into a space where a simple dot product approximates a complex kernel function. This allows the curator to calculate "marginal gain" (how much a new point helps the summary) without seeing the raw data.
Algorithm for Hash Function 1
  • Hash Function 2 ($h_2$): A novel adaptation of the Multiplicative Weights Exponential Mechanism (MWEM). This adds carefully calibrated noise to the summary statistics before they are broadcast to data owners, ensuring Differential Privacy (DP).
  • The Private Auction: To be "parsimonious," the curator shouldn't just download everything. The authors developed a "noiseless" DP auctioning protocol. Data owners submit "bids" (how well their data matches the current needs), and the curator selects winners in a way that doesn't leak information about the losing bids.
Distributed Summarization Protocol and Private Auction

Datasets

The researchers evaluated their protocol on two real-world benchmarks:

  1. Allstate Insurance Dataset (Kaggle): Used to predict insurance product choices. They simulated covariate shift by using data from Florida and Connecticut as sources to match a target task based on a different subset of Connecticut data.
  2. MNIST: The classic handwritten digit dataset. They created a skewed distribution where different data owners held different sets of digits (e.g., one owner has 0s and 1s, another has 3s and 4s) to test the protocol's ability to pick the right "mix" for a target task.

Key Insights and Ideas

  • The Power of Linearization: By using Rahimi-Recht features, the authors turned a non-linear optimization problem (MMD) into a linear one. This is the "secret sauce" that allows distributed participants to calculate their contributions privately.
  • Parsimony as a Privacy Layer: Most DP papers assume a central curator sees everything. This paper introduces the Parsimonious Curator Privacy Model, arguing that a truly private system should also limit what the "trusted" middleman sees. They prove the curator only needs to access $O(K^{1/3} |D_s|)$ points, where $K$ is the number of owners.
  • Noiseless Winner Notification: Usually, telling someone they won an auction leaks information about the other bidders. Their novel auction mechanism provides a way to notify winners while maintaining DP guarantees for everyone else.

Key Results

  • Accuracy vs. Privacy: The "Private Greedy" protocol closely tracked the performance of the "Non-Private Greedy" baseline.
  • Outperforming Uniform Sampling: On the Allstate dataset, the private summary led to a 6-10% improvement in classification accuracy compared to simple uniform sampling (a proxy for standard Federated Learning).
  • MNIST Performance: On the digit task, the protocol showed a 10-15% performance gain over uniform sampling, proving it successfully navigated the covariate shift to pick the most relevant digits.

Limitations and Future Work

  • Submodularity Constraints: The theoretical guarantees rely on the objective function being submodular. The authors show this holds under certain conditions (Theorem 1), but these conditions (like diagonal dominance in the kernel matrix) might not always be met in every real-world scenario.
  • Trusted Curator: While the model is "parsimonious," it still requires a curator that is trusted to follow the protocol. The authors briefly discuss an extension for a "less trusted" curator, but full decentralization remains a future challenge.
  • Computational Overhead: Maintaining the distribution over the quantized grid in the $h_2$ step can be memory-intensive, though the authors provide a lemma showing it can be done in linear time relative to the dimensions.

Summary updated

Abstract

We envision Artificial Intelligence marketplaces to be platforms where consumers, with very less data for a target task, can obtain a relevant model by accessing many private data sources with vast number of data samples. One of the key challenges is to construct a training dataset that matches a target task without compromising on privacy of the data sources. To this end, we consider the following distributed data summarizataion problem. Given K private source datasets denoted by $[D_i]_{i\in [K]}$ and a small target validation set $D_v$, which may involve a considerable covariate shift with respect to the sources, compute a summary dataset $D_s\subseteq \bigcup_{i\in [K]} D_i$ such that its statistical distance from the validation dataset $D_v$ is minimized. We use the popular Maximum Mean Discrepancy as the measure of statistical distance. The non-private problem has received considerable attention in prior art, for example in prototype selection (Kim et al., NIPS 2016). Our work is the first to obtain strong differential privacy guarantees while ensuring the quality guarantees of the non-private version. We study this problem in a Parsimonious Curator Privacy Model, where a trusted curator coordinates the summarization process while minimizing the amount of private information accessed. Our central result is a novel protocol that (a) ensures the curator does not access more than $O(K^{\frac{1}{3}}|D_s| + |D_v|)$ points (b) has formal privacy guarantees on the leakage of information between the data owners and (c) closely matches the best known non-private greedy algorithm. Our protocol uses two hash functions, one inspired by the Rahimi-Recht random features method and the second leverages state of the art differential privacy mechanisms. We introduce a novel ``noiseless'' differentially private auctioning protocol, which may be of independent interest. Apart from theoretical guarantees, we demonstrate the efficacy of our protocol using real-world datasets.
BibTeX
@inproceedings{sarpatwar2019differentially,
  author = {Kanthi K. Sarpatwar and Karthikeyan Shanmugam and Venkata Sitaramagiridharganesh Ganapavarapu and Ashish Jagmohan and Roman Vaculín},
  title = {{Differentially Private Distributed Data Summarization under Covariate Shift}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure