Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Compatibility

Forum topic · 小凯 · 2026-11-03

Summary

This paper studies when two parties—Alice and Bob—should pool their sensitive labeled datasets to train a machine learning model. Even if each dataset is perfectly classifiable on its own, conflicting labeling standards or selection biases may make it impossible for any classifier in a hypothesis class H to fit the combined data. The authors formalize compatibility testing via opt_H, the minimum error any hypothesis in H incurs on merged data: under pure ε-differential privacy, the parties must distinguish opt_H=0 (compatible) from opt_H≥t (incompatible) without revealing individual data points. A trusted manager can achieve t=O(1/ε); without one, for threshold functions over a domain of size m the optimal bound is Θ̃(log log m / ε)—exponentially smaller than the Θ(log m / ε) needed to privately learn thresholds even with a manager. For halfspaces in R^d, protocols achieve t=Õ(d³ log m / ε), with a lower bound of Ω(d log(m/d) / ε) for some domains. Paper: arXiv:2611.03599.

Paper Overview

Field: Machine Learning Authors: Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani Published: 2026-11-02 arXiv: 2611.03599

Abstract

In this paper, the authors 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.

Key Contributions

The problem is formalized from a learning-theoretic viewpoint via $\operatorname{opt}_{\mathcal{H}}$ : the minimum number of mistakes made on the combined data by any hypothesis in $\mathcal{H}$ .
Through interactive communication, the two parties must distinguish $\operatorname{opt}_{\mathcal{H}}=0$ (compatible data) from $\operatorname{opt}_{\mathcal{H}}\geq t$ (conflicting data) under pure $\varepsilon$ -differential privacy.
A trusted manager can accomplish this with $t=O(1/\varepsilon)$ . The paper asks how small $$t$$ can be without a manager.
Thresholds over a domain of size $$m$$ : the optimal bound is $\tilde{\Theta}(\log\log m / \varepsilon)$ —exponentially smaller than the $\Theta(\log m / \varepsilon)$ samples needed to privately learn thresholds even with a manager.
Halfspaces in $$R^d$$ : the dependence on $$m$$ jumps to $\log(m)$ . The authors give a protocol with $t=\tilde{O}(d^3 \log m / \varepsilon)$ and prove that some domains require $t=\Omega(d \log(m/d) / \varepsilon)$ .

Link

arXiv:2611.03599

*Auto-collected on 2026-11-04*