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

Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba ZianiarXiv 2026 · arXiv

TL;DR

This paper introduces a learning-theoretic framework for two parties to privately assess if their datasets are "compatible" (i.e., can be fit by a single model) before actually sharing them. The authors establish tight bounds on the minimum error resolution required for this assessment, revealing that for some models, testing compatibility is exponentially more efficient than learning the model itself.

What Problem Does This Paper Address?

Organizations often face a "circular dilemma" when considering data collaboration. To know if pooling datasets will improve a machine learning model, they need to evaluate joint properties of their data. However, evaluating these properties typically requires sharing the data—the very step they are hesitant to take due to privacy concerns, legal hurdles, or competitive risks.

The authors formalize this as a private dataset valuation problem. Two agents, Alice and Bob, want to distinguish between two cases:

  1. Match: Their combined data is perfectly realizable by a hypothesis class $\mathcal{H}$ (e.g., a simple threshold or a linear separator).
  2. Far: Every hypothesis in $\mathcal{H}$ makes at least $t$ mistakes on the combined data.

The goal is to design an interactive protocol that solves this "promise problem" while satisfying two-party differential privacy (DP). This means Alice learns nothing about Bob's individual records (and vice versa) beyond what is revealed by the final "Match" or "Far" verdict. The technical challenge is finding the smallest possible "resolution" $t$ that can be guaranteed under these privacy constraints.

Methods

The paper focuses on two fundamental hypothesis classes: thresholds on the real line and halfspaces in $\mathbb{R}^d$.

Algorithms

  • For Thresholds: The authors propose a protocol based on a private binary search over a binary trie. Instead of Alice just picking a point and Bob counting how many of his points fall on either side (which is privacy-expensive), they search for the "depth" in a trie where their datasets begin to diverge. This allows them to achieve a resolution $t$ that depends only on $\log \log m$ (where $m$ is the domain size), rather than $\log m$.
  • For Halfspaces: The algorithm uses a private elimination procedure in the "dual space" (the space of all possible classifiers). They maintain a set of candidate classifiers and iteratively use "halfspace containers" to prune candidates that are inconsistent with their local data. Alice and Bob use the exponential mechanism to privately select these pruning "cuts."

Lower Bounds

To prove that their algorithms are near-optimal, the authors use a clever connection between DP and information complexity. They construct hard instances using error-correcting codes (specifically expander codes for halfspaces). They show that if a private tester could achieve a resolution smaller than their lower bound, it would imply a communication protocol with an impossibly low information cost for certain hard functions.

Datasets

This is a theoretical paper and does not use standard empirical datasets. Instead, it defines formal data spaces:

  • One-dimensional domains: A finite set of $m$ points on the real line.
  • High-dimensional domains: Finite subsets of $\mathbb{R}^d$ of size $m$.

The authors use synthetic "worst-case" dataset constructions to prove their lower bounds, demonstrating that these limits hold regardless of the actual data distribution.

Key Insights and Ideas

  • Testing vs. Learning: A major "aha moment" is that testing compatibility is strictly easier than learning. For thresholds, learning requires $\Theta(\log m / \varepsilon)$ samples, but testing only requires $\tilde{\Theta}(\log \log m / \varepsilon)$. This exponential gap means organizations can verify if they should collaborate much more easily than they can actually perform the collaboration.
  • The Power of Interaction: Interaction is essential. The authors prove that any non-interactive protocol for thresholds would require a resolution of $\Omega(\log m / \varepsilon)$, losing the exponential benefit found in their interactive trie-search.
  • The Privacy Cost of Decentralization: In a centralized setting with a trusted curator, the resolution $t$ would be a constant $O(1/\varepsilon)$. In the two-party setting, we pay a "decentralization tax" that scales with the domain size or dimension. For halfspaces, this cost scales linearly with the dimension $d$.

Key Results

The main findings are summarized in the table below, showing the upper and lower bounds for the resolution $t$ (the minimum gap needed to distinguish compatible from conflicting data).

Summary of upper and lower bounds for private testing resolution $t$.

For halfspaces, the relationship between the dataset size $n$ and the achievable resolution $t$ is complex. As shown in Figure 1, different algorithms dominate depending on how much data is available.

Resolution $t$ vs. dataset size $n$ for halfspaces. The blue line represents the best known upper bounds across different regimes.
  • Thresholds: The optimal resolution is $\tilde{\Theta}(\log \log m / \varepsilon)$.
  • Halfspaces: The resolution jumps to $\tilde{O}(d^3 \log m / \varepsilon)$, with a lower bound of $\Omega(d \log(m/d) / \varepsilon)$. This jump from $\log \log m$ to $\log m$ represents a fundamental "curse of dimensionality" for private compatibility testing.

Limitations and Future Work

  • Pure vs. Approximate DP: The paper focuses on "pure" $\varepsilon$-DP. Exploring "approximate" $(\varepsilon, \delta)$-DP might lead to even smaller resolutions $t$.
  • Hypothesis Complexity: The results are for simple geometric classes. Extending this to more complex models (like neural networks) remains an open challenge.
  • Multi-party Scaling: The current work is limited to two parties. Real-world collaborations often involve many institutions, and the privacy/communication trade-offs likely change as the number of parties grows.
  • Computational Efficiency: While the threshold algorithm is very efficient, the halfspace algorithm involves searching over "containers," which may be computationally demanding in very high dimensions.

Summary updated

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)$.
BibTeX
@misc{haghifam2026should,
  author = {Mahdi Haghifam and Kumar Kshitij Patel and Avrim Blum and Giulia Fanti and Juba Ziani},
  title = {{Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing}},
  year = {2026},
  eprint = {2611.03599},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03599},
}
Figure