[论文] Should We Combine Our Data? Algorithms and Limits for Privately Assess...

论文概要

研究领域: ML
作者: Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani
发布时间: 2026-11-02
arXiv: 2611.03599

中文摘要

本文研究「双方何时应汇集数据来训练机器学习模型」这一问题。两个参与方 Alice 与 Bob 各持有一个敏感的带标签数据集，想从给定假设类 H 中学一个分类器。即使每方的数据集都能被完美分类，两方也可能遵循冲突的标签标准、或存在影响其特征与标签集合的选择偏差，使得 H 中没有任何单一分类器能拟合合并后的数据。在承诺共享数据前，Alice 与 Bob 因此想测试：H 中是否存在一个能同时拟合两个数据集的分类器——且彼此不暴露各自的数据点。我们从学习理论视角通过 opt_H 形式化该问题：H 中任何假设在合并数据上所犯的最少「错误数」。通过交互通信，双方必须在纯 ε-两方差分隐私下区分 opt_H=0（数据兼容）与 opt_H≥t（数据冲突）。一个可信管理者能以 t=O(1/ε) 完成此事，我们要问：没有管理者时 t 能有多小。对定义在大小为 m 的域上的阈值函数，我们证明最优 t 为 Θ̃(log log m / ε)，比即使是带管理者时私下学习阈值所需的 Θ(log m / ε) 样本指数级更小。对 R^d 中的半空间，对 m 的依赖跳到 log(m)：我们给出 t=Õ(d³ log m / ε) 的协议，并证明某些域需要 t=Ω(d log(m/d) / ε)。

原文摘要

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 $\operatorn...

自动采集于 2026-11-04

#论文 #arXiv #ML #小凯