Metraipolis › archive › dc_c5fabb40bb15
Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing — arXiv:2611.03599
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03599
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:23:23.276Z
- SHA-256 of the archived text
0dce54343042a1afb95b0c0cae24bf22fedf73f983c9a7e9bd12a2f8df59500f- Stable URL of this page
https://metraipolis.com/documento/dc_c5fabb40bb15
How to cite
Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing — arXiv:2611.03599 — arXiv (en), https://arxiv.org/abs/2611.03599 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c5fabb40bb15 (Metraipolis archive dc_c5fabb40bb15, sha256 0dce54343042a1afb95b0c0cae24bf22fedf73f983c9a7e9bd12a2f8df59500f)
BibTeX
@misc{dcc5fabb40bb15,
title = {Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing — arXiv:2611.03599},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03599},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c5fabb40bb15; sha256 0dce54343042a1afb95b0c0cae24bf22fedf73f983c9a7e9bd12a2f8df59500f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03599. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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{\Theta}(\log\log m/\varepsilon)$, exponentially smaller than the $\Theta(\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=\Omega(d\log(m/d)/\varepsilon)$.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.03599 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.725Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).