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:
- Match: Their combined data is perfectly realizable by a hypothesis class $\mathcal{H}$ (e.g., a simple threshold or a linear separator).
- 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).
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.
- 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