Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing
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 ℋ. 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 ℋ fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in ℋ can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via optH, the minimum \emph{number of mistakes} made by any hypothesis in ℋ on their pooled data. Through interactive communication, the agents must distinguish optH=0 (compatible datasets) from optH≥ t (conflicting datasets) under pure ε-two-party differential privacy. A trusted curator could do this with t=O(1/ε), 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 Θ̃(loglog m/ε), exponentially smaller than the Θ(log m/ε) samples needed to privately learn thresholds, even with a curator. For halfspaces in ℝd, the dependence on m jumps to log(m): we give a protocol with t=Õ(d3log m/ε) and show that some domains require t=Ω(dlog(m/d)/ε).
Related
- Actually, All Learnable Distribution Classes Are Privately Learnable
- Where should we look for the deviation from quantum mechanics?
- Combinatorics of pre-Lie products sharing the same Lie bracket
- Should the pharmaceutical industry consider using high-order autoregressive models when modelling panel data?
- Fluid and Diffusion Approximation of a Multiclass Proportional Processor Sharing Queue with Reneging and General Distributions
BibTeX
@misc{haghifam2026should,
title = {{Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing}},
author = {Mahdi Haghifam and Kumar Kshitij Patel and Avrim Blum and Giulia Fanti and Juba Ziani},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03599},
eprint = {2611.03599},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03599},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing
AU - Mahdi Haghifam
AU - Kumar Kshitij Patel
AU - Avrim Blum
AU - Giulia Fanti
AU - Juba Ziani
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03599
UR - https://arxiv.org/abs/2611.03599
AB - 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 ℋ. 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 ℋ fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in ℋ can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via opt_H, the minimum \emph{number of mistakes} made by any hypothesis in ℋ on their pooled data. Through interactive communication, the agents must distinguish opt_H=0 (compatible datasets) from opt_H≥ t (conflicting datasets) under pure ε-two-party differential privacy. A trusted curator could do this with t=O(1/ε), 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 Θ̃(loglog m/ε), exponentially smaller than the Θ(log m/ε) samples needed to privately learn thresholds, even with a curator. For halfspaces in ℝ^d, the dependence on m jumps to log(m): we give a protocol with t=Õ(d^3log m/ε) and show that some domains require t=Ω(dlog(m/d)/ε).
ER -