cs.LGNov 2, 2026

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

Authors: Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani

Organizations: Toyota Technological Institute at Chicago · Yale University · Carnegie Mellon University · Georgia Institute of Technology

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 H\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 H\mathcal{H} fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in H\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 opt⁡H\operatorname{opt}_\mathcal{H}, the minimum number of mistakes made by any hypothesis in H\mathcal{H} on their pooled data. Through interactive communication, the agents must distinguish opt⁡H=0\operatorname{opt}_\mathcal{H}=0 (compatible datasets) from opt⁡H≥t\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/ε)t=O(1/\varepsilon), and we ask how small tt can be without one. For thresholds on the real line over a domain of size mm, we show that the optimal tt is Θ~(log⁡log⁡m/ε)\tildeΘ(\log\log m/\varepsilon), exponentially smaller than the Θ(log⁡m/ε)Θ(\log m/\varepsilon) samples needed to privately learn thresholds, even with a curator. For halfspaces in Rd\mathbb{R}^d, the dependence on mm jumps to log⁡(m)\log(m): we give a protocol with t=O~(d3log⁡m/ε)t=\tilde{O}(d^3\log m/\varepsilon) and show that some domains require t=Ω(dlog⁡(m/d)/ε)t=Ω(d\log(m/d)/\varepsilon).

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Differentially Private Mixing of Public Datasets Improves Private Learning

    Oct 5, 2026Yufei Chen, Tejumade Afonja, Anvith Thudi +1Privacy-Preserving MLDifferential Privacy

  2. Private Component-by-Component Learning

    Oct 4, 2026Dvir Karni, Eliad TsfadiaBoolean Function LearningPrivacy-Preserving ML

  3. Privacy for Free in Efficient Agnostic Halfspace Learning

    Nov 3, 2026Giorgio Racca, Amartya Sanyal, Vikrant SinghalHalfspace LearningAgnostic Learning