本文探讨了在差分隐私约束下学习阈值函数的样本复杂度问题，并提出了一种新的算法来减少样本复杂度。该算法基于选择输入相关哈希函数和将数据库嵌入到大小对数减小的域中，从而在不泄露个体信息的情况下生成内部点。

Nov, 2019

通过对未知对称一维对数凹分布的 d 维空间的 d 倍积的未知仿射变换的环境分布内带有一定间距的高维半空间的多项式时间学习算法，从一个组分分布的数据中删除至少一个 ε 分数的数据引入了半空间。值得注意的是，我们的算法不需要标签，并在这种分布假设下确立了隐藏半空间的独特性（以及高效性）。该算法的样本和时间复杂度在维度和 1/ε 上是多项式的。该算法只使用经验分布的适当重新加权的前两个矩，我们称之为对比矩；其分析使用了关于广义狄利克雷多项式的经典事实，并且关键地依赖于对对数凹分布截断的矩比的新的单调性属性。此前的研究处理了当底层分布是通过非高斯成分分析来进行的非高斯分布的特殊情况。我们通过提供基于总变分距离而不是现有的可以是超多项式的矩边界保证，改进了这一点。我们的工作也是在这个设置中首次超越高斯分布。

Nov, 2023

构建差分隐私估计量，可通过低样本复杂度估计在满足非常温和的矩条件下的任意分布的中位数。

May, 2023

该研究提出了不同 ially private 算法（DP 算法）在发布阈值函数的近似答案时的样本复杂度的新上限和下限结果，还展示了实现此任务在无限域 X 上是不可能的，并需要样本复杂度 n≥Ω（log * |X| ），同时对于使用 DP 合理地学习概念类与无隐私信息学习之间的差异也给出了首个下限结果。

Apr, 2015

该研究通过将真正的差分隐私和近似（ε，Δ）- 差分隐私应用于优化问题中，研究比较了私有学习和消毒的样本复杂性，同时构建了用于高维中的点函数，阈值函数和轴对齐矩形的私有学习器以及标签私有学习，证明了 VC 维完全刻画了学习带标签隐私的样本复杂性。

Jul, 2014

通过差分隐私机制，我们研究了离散优化问题如 $k$-median 问题、顶点集覆盖、最小割、设施选址、Steiner 树和组合公开项目等，在保证客户隐私的前提下仍能获得较好的近似解，并展示了密码学定义无法做到这点的例子。

Mar, 2009

提出并分析了一系列算法来解决在用户级差分隐私约束下的学习任务，包括高维均值估计、平滑损失函数的经验风险最小化、随机凸优化以及具有有限度量熵的学习假设类。

Feb, 2021

通过使用关联的高斯噪声和线性回归步骤，我们基于差分隐私机制的多项式对数组进行了矩阵突触连接和遗传差异，从而在线性查询的上下文中研究了准确性和隐私之间的权衡。

Dec, 2012

本文研究了差分隐私算法在计算数据集的几何中位数方面的应用，提出了一对多项式时间的差分隐私算法，并证明其在样本复杂性方面的最优性。

Jun, 2024

本文提出了一个以多项式回归和定位技术相结合的算法， 用于在 d - 球上均匀分布的情况下，实现对零时最佳半空间分类器的确定性多项式近似方案（PTAS），误差保证为 opt 的 (1+μ)+ε 倍， 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。

Oct, 2014