本文给出了一个样本大小的组合特征,是私有概念类学习足够和必需的。我们介绍了概念类的概率表示概念,并证明了私有学习算法对于概念类 C 的样本复杂度意味着 RepDim(C)=O (m),并且存在一个样本复杂度 m = O(RepDim(C))的私有学习算法。
Feb, 2014
讨论私人和公共学习示例的差异隐私问题,证明可通过公共样本数为 $d/\alpha$ 和私有标记样本数为 $d/\alpha^2$ 实现平均误差为 $\alpha$ 的 VC-dimension $d$ 假设类别的免疫性学习,提出与之相匹配的下界。
Oct, 2019
通过利用公共数据来提高私人学习算法的性能,本研究提出了第一种具有计算有效性的算法,以确保在满足与私人样本相关的差分隐私的同时,当私人数据分布足够接近公共数据时也能保证学习效果,并且在函数类可非私密学习时可进行私人学习的证明。
Feb, 2024
根据合理的密码学假设,我们展示了一个概念类别,该类别允许在多项式时间内以多项式错误边界运行的在线学习器,但不存在计算效率高的差异隐私 PAC 学习器。
研究了具有公共数据访问的私人分布学习问题,通过使用公共和私有样本来输出一个对分布 p 的估计,同时满足纯差分隐私的隐私约束。结果显示,Q 类的公共 - 私有可学习性与 Q 类的样本压缩方案以及中间概念列表学习的存在有关,并且将这种连接利用起来恢复了以前关于 Gaussians 和新的结果,包括关于高斯 $k$ 混合物的样本复杂性上界、关于自适应和分布转移抵抗学习的结果,以及在承担混合和分布乘积时广义公共 - 私有学习的闭合特性。最后,利用与列表学习的联系,结果显示对于 Gaussians 在 R^d 中,至少需要 d 个公共样本进行私人可学习性,这接近已知的 d+1 个公共样本的上界。
Aug, 2023
论文证明,私人发布用于大量查询的合成数据库是可能的,但仅针对离散领域,并提供了一种新的数据隐私概念:分布隐私。
Sep, 2011
讨论分布式数据的 PAC 学习问题,分析了涉及的基本通信复杂性问题,包括教学维度和错误绑定。针对特定概念类别,如合取、奇偶函数和决策列表等,给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信,以及如何在不确定环境下实现低通信回归。同时,还考虑了隐私性,包括差分隐私和分布式隐私。
Apr, 2012
该研究通过将真正的差分隐私和近似(ε,Δ)- 差分隐私应用于优化问题中,研究比较了私有学习和消毒的样本复杂性,同时构建了用于高维中的点函数,阈值函数和轴对齐矩形的私有学习器以及标签私有学习,证明了 VC 维完全刻画了学习带标签隐私的样本复杂性。
Jul, 2014
提出一种基于统计学习框架的主动学习算法,能够高效地处理随机分类噪声和差分隐私,且可将其转换为能容忍分类噪声的主动学习算法,同时也实现了用指数级别的误差提高标签节约的差分隐私主动学习算法.
Jul, 2013
本文研究了在差分隐私约束下的学习能力,揭示了隐私、稳定性和学习能力之间的一些复杂关系,并且提出了一个通用算法,可以在普遍条件下私下学习广泛的学习问题。
Feb, 2015