When two parties can safely combine data without privacy loss
Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing
Machine LearningData Structures and AlgorithmsInformation Theory
Summary
Sometimes two people each have their own private data and want to see if they can combine it to train a shared machine learning model. But their data might not agree perfectly, so they want to know if one single model can fit both datasets before sharing anything sensitive. The authors study how Alice and Bob can test this privately without revealing their data, and how accurately they can detect disagreements depending on the problem type. They find it is possible to detect incompatibility with surprisingly small error, even under strong privacy rules.
What this means in practice
- •For data privacy engineers: Decide if datasets from different sources can be combined for private model training without sharing raw data.
- •For federated learning system designers: Determine compatibility of local user datasets in privacy-preserving distributed learning before aggregating models.
A theory result. No direct application yet.
Authors
Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani
Abstract
In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class $\mathcal{H}$. Even when each party's dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in $\mathcal{H}$ fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in $\mathcal{H}$ can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via $\operatorname{opt}_\mathcal{H}$, the minimum \emph{number of mistakes} made by any hypothesis in $\mathcal{H}$ on their pooled data. Through interactive communication, the agents must distinguish $\operatorname{opt}_\mathcal{H}=0$ (compatible datasets) from $\operatorname{opt}_\mathcal{H}\geq t$ (conflicting datasets) under pure $\varepsilon$-two-party differential privacy. A trusted curator could do this with $t=O(1/\varepsilon)$, and we ask how small $t$ can be without one. For thresholds on the real line over a domain of size $m$, we show that the optimal $t$ is $\tildeΘ(\log\log m/\varepsilon)$, exponentially smaller than the $Θ(\log m/\varepsilon)$ samples needed to privately learn thresholds, even with a curator. For halfspaces in $\mathbb{R}^d$, the dependence on $m$ jumps to $\log(m)$: we give a protocol with $t=\tilde{O}(d^3\log m/\varepsilon)$ and show that some domains require $t=Ω(d\log(m/d)/\varepsilon)$.