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:
- Selection: How do we pick the specific data points from the sources that best match the consumer's target distribution?
- Privacy: How do we ensure that Hospital A doesn't learn anything about Hospital B's data during the process?
- 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.
- 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.
Datasets
The researchers evaluated their protocol on two real-world benchmarks:
- 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.
- 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