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

Oct 5, 2026

Differentially Private Mixing of Public Datasets Improves Private Learning

Many machine learning applications involve sensitive data and therefore require training under differential privacy (DP). However, DP training often degrades model utility. In some cases, first pre-training the model on "public" data before finetuning with DP on the sensitive data can reduce the drop in utility. However, the success of this depends on how relevant the selected public dataset is to the sensitive data. We introduce the first pipeline that privately learns the mixture of several public datasets to pretrain on for a given sensitive downstream task. Our key insight is that we can privately find the best mixture of multiple public datasets by privately learning a low-dimensional linear model. We tested our method on the NIH dataset for X-ray classification and the ENRON email dataset for language modeling. Applying our method to find tailored mixtures of X-ray datasets to pretrain on for diseases in the NIH ChestX-ray14 dataset, we improved macro AUC by up to 0.037 across privacy budgets compared to the baselines, with gains as large as +22.8% relative AUC on Cardiomegaly at ε=1ε=1. For DP training on the ENRON dataset, pre-training on our mixture of The Common Pile (a collection of public-domain text datasets) decreased test perplexity by 16% relative to the baseline mixtures.
Oct 4, 2026

Private Component-by-Component Learning

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by kk components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy ε\varepsilon, pays only O~(k/ε)\widetilde O(\sqrt{k}/\varepsilon) overhead relative to the active sample requirement of a single component learning step at target accuracy Θ(α/k)Θ(α/k). For learning dd-dimensional halfspaces over a finite coordinate grid of size LL, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of O~(1εα⋅min⁡{d2.5log⁡∗L,  d2.5+d1.52log⁡∗L}),\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right), which improves on the previously known bound of O~(1εα⋅min⁡{1α⋅d5.5log⁡∗L,  d2.52log⁡∗L}).\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot\min\{\frac{1}α\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right). We also apply the framework to Boolean compositions: given proper private learners for classes H1,…,HkH_1,\ldots,H_k, we obtain a proper private learner for G(H1,…,Hk)G(H_1,\ldots,H_k) for any fixed Boolean function G:{0,1}k→{0,1}G:\{0,1\}^k\to\{0,1\}. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from O~(k/ε)\widetilde O(k/\varepsilon) to O~(k/ε)\widetilde O(\sqrt{k}/\varepsilon).
Nov 3, 2026

Privacy for Free in Efficient Agnostic Halfspace Learning

We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.