Apr, 2024

不完全统计扰动：私有最小二乘的稳定估计器

PDF
TL;DR我们提出了一个针对普通最小二乘问题的样本和时间高效的差分隐私算法，误差线性依赖于维度并且与 $X^ op X$ 的条件数无关，其中 $X$ 是设计矩阵。我们的算法具有接近最优的准确性保证，适用于具有有限统计杠杆率和有界残差的任何数据集。
differentially private algorithmordinary least squaresdimensioncondition numberdesign matrix
发现论文，激发创造
  • 线性回归的私有梯度下降：更紧凑的误差界限和特定实例的不确定性估计

    我们对标准差分隐私梯度下降方法在线性回归中的分析进行了改进，得出基于输入的合理假设，在每个时间步骤上迭代的分布特征。我们的分析结果揭示了算法的准确性新的发现：对于适当选择的超参数，样本复杂度仅与数据维度呈线性关系。这与（非私有）普通最小二乘估计器以及依赖于复杂的自适应梯度裁剪方案的最新私有算法（Varshney 等，2022 年；Liu 等，2023 年）的维度相关性一致。我们对迭代分布的分析还允许我们构建适应特定数据集算法的方差的置信区间。我们通过对合成数据进行实验证实了我们的定理。

    Feb, 2024

  • 半参数最小二乘学习线性动态系统

    通过分析最小二乘估计器的变体，，提出了一种半参数噪声估计算法，可以解决具有偏差，半参数噪声的估计问题，同时可以应用于部分观测线性系统参数的估计，且对于长期依赖问题的方差引入具有可减少的能力.

    Feb, 2019

  • 不需要私有协方差估计的协方差感知私有均值估计

    提出两种样本有效的差分隐私均值估计器，可用于具有未知协方差的 $d$ 维（子）高斯分布。这些估计器是基于一种简单通用的设计差分隐私机制的方法实现的，但需要新颖的技术步骤使其保持隐私和有效性。

    Jun, 2021

  • 近线性时间内的最优鲁棒线性回归

    研究了高维稳健线性回归问题，在受到对抗性破坏的情况下提出了估计方法，包括样本复杂度，恢复保证，运行时间等关键指标，并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。

    Jul, 2020

  • 稳定凸松弛法私有鲁棒估计

    提出了一种新的框架，以将鲁棒性的凸松弛算法修改为满足适当参数规范的强最坏情况稳定性保证。通过这一框架，提出了一个可以在存在恶意数据干扰下实现微分隐私的高阶矩的鲁棒估计的算法，包括均值和协方差的估计。该算法成功地应用于成族分布，并在适当参数范数下提供恢复和维度参数的从容保证。

    Dec, 2021

  • 鲁棒线性最小二乘回归

    针对在普通最小二乘法回归中预测的偏差问题，我们提出了一个更好的估算方法 —— 基于截断误差差值的极小 - 极大框架，其期望和差距都为 d/n。

    Oct, 2010

  • 基于数据相关充分统计扰动的私有回归

    采用后处理方法以私密发布边际导数为基础的数据依赖 SSP，在线性回归和逻辑回归中优于现有的数据无关 SSP，同时与合成数据的训练有关，机制的整体效用取决于对线性查询的回答情况。

    May, 2024

  • 差分隐私简单线性回归

    通过使用差分隐私，我们在小型数据集的情况下训练针对经济研究的简单线性回归的算法，在不牺牲数据隐私的情况下获得较高的性能。

    Jul, 2020

  • 高维度差分隐私估计器设计

    本研究在高维度背景下研究差分隐私的均值估计问题，通过将高维度鲁棒统计的结果应用到差分隐私中，提出了一种计算可行的算法，能够在高维度下完成差分隐私的均值估计，并且在人工合成数据集上表现出了优异的性能。

    Jun, 2020

  • 一种能处理无界高斯分布、隐私安全且计算高效的估算器

    本文提出了一种多项式时间、多项式采样、差分隐私的算法，用于估计任意高斯分布的均值和协方差，且不需要先验参数范围。该算法的主要技术工具是一种新的差分隐私的预处理器，可以从任意的高斯分布中取样并返回一个矩阵 A，使得 A × Σ × A^T 具有固定的条件数字。

    Nov, 2021