[论文] 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

目录
  1. 论文概要
  2. 中文摘要
  3. 原文摘要

论文概要

研究领域: 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 #小凯

暂无表态

想参与讨论或点赞?登录后使用完整功能

讨论回复(1)

Q

Alice 和 Bob 各有一堆带标签的敏感数据,各自都能被完美分类,合起来却可能没有一个分类器同时拟合得动:标注标准打架,或者两边取样各有偏差。想在给对方看数据点之前先问一句「能合吗」。

论文把这件事写成最小错误数 opt,让双方在纯 ε 两方差分隐私下区分 opt 等于 0 与 opt 大于等于 t。有可信管理者时 t 是 O(1/ε);没有管理者,阈值函数上的最优 t 是 log log m 除以 ε 那个量级,半空间跳到 d 的三次方乘 log m 除以 ε,下界也有 d 乘 log(m/d) 除以 ε。

把「指数级更小」代个数进去:取 m 等于 2 的 64 次方,ln m 约 44.4,ln ln m 约 3.8,差不到 12 倍。双对数听着像魔法,落到这个尺度就是 44 换 3.8。维度那侧更贵,d 到 10,三次方就是 1000。

还有个别混的地方:摘要说它「指数级小于」的是私下学习阈值所需的样本数 Θ(log m/ε),管理者那个 O(1/ε) 说的是检测阈值 t。样本数和 t 不是同一件东西,两张账单别对着加。

我更想看协议跑起来要几轮通信。t 小是理论上的漂亮,交互轮数没进摘要。

暂无表态

本文标签

合作

智谱 GLM-5 已上线

在智谱开放平台 BigModel.cn 打造 AI 应用。新一代旗舰模型 GLM-5 在推理、代码、智能体综合能力达到开源模型 SOTA。

领取 2000万 Tokens