Nov, 2023

用户级差分隐私随机凸优化：具有最优收敛速率的高效算法

PDF
TL;DR我们研究了具有用户级隐私的差分隐私随机凸优化（DP-SCO），其中每个用户可能拥有多个数据项。我们开发了新算法用于用户级 DP-SCO，在多项式时间内获得凸和强凸函数的最优速率，并且在维度上只要求用户数量呈对数增长。此外，我们的算法是第一个在多项式时间内获得非平滑函数最优速率的算法。这些算法基于多遍 DP-SGD，结合了一种集中数据的新颖私有均值估计过程，在估计梯度的平均值之前应用了一个异常值移除步骤。
differentially privatestochastic convex optimizationuser-level privacyalgorithmsprivate mean estimation
发现论文，激发创造
  • 用户级私有凸优化

    该研究介绍了一种新的具有用户级差分隐私保证的随机凸优化机制，收敛速度类似于 Levy 等人（2021）；Narayanan 等人（2022）的先前工作，但有两个重要改进。该机制不需要对损失进行任何平滑性假设，同时也是第一个其用户级隐私所需最小用户数不依赖于维度，仅对所需超额误差有对数依赖的界限。其主要思想是表明强凸损失的最优化器具有低局部删除敏感性，以及一种具有低局部删除敏感性函数的输出扰动方法，这可以独立地被广泛关注。

    May, 2023

  • 非欧几里得差分隐私随机凸优化：线性时间内的最优收敛率

    本文系统研究了在不同的 normed space 下，拥有标准平滑性假设的 Differentially private stochastic convex optimization 问题，提出了新的算法并证明了其优于之前已知的算法

    Mar, 2021

  • 具有最佳速率的隐私随机凸优化

    本研究针对随机凸优化问题的不同隐私算法进行了研究，通过分析算法的稳定性以确保泛化，得出了当参数的情况在实践中最为普遍时，隐私 SCO 的渐近收敛率与非隐私的 SCO 相同，即都为 1/√n.

    Aug, 2019

  • 关于私人在线凸优化：在 $l_p$ 几何和高维情境赌徒中的最优算法

    研究了使用差分隐私保护的在线随机凸优化问题，提出了一种具有递归梯度的私有在线 Frank-Wolfe 算法，可在线性时间内实现最优超额风险，并证明递归梯度的方差缩减结果在非平稳场景下也有理论保证。同时，该算法也被扩展到 p=1 的情况，可实现几乎与维度无关的超额风险。

    Jun, 2022

  • 带重尾数据的差分隐私随机凸优化

    本文提出了一种基于采样和聚合框架的方法和基于梯度平滑和剪枝的方案，可有效应对重尾型数据下的不规则性挑战，实现了强凸和一般凸损失函数的差分隐私，且在高概率下应达到预期的超额群体风险水平。

    Oct, 2020

  • 高维差分隐私随机优化及重尾数据

    本文中，我们首次对 DP-SCO 问题的高维重尾数据进行了研究，提出了在约束为多面体的情况下的误差频率及其限制，进一步在 LASSO 和稀疏学习问题中讨论了误差限制。

    Jul, 2021

  • 单个时期和大批量下的 DP-SCO 的最优速率

    我们提出了一种新的差分隐私算法，叫做加速差分隐私随机递归梯度下降（Accelerated-DP-SRGD），它能够在只对当前步骤的新信息进行隐私代价计算的情况下实现最优 DP - 随机凸优化（DP-SCO）错误，通过仅使用数据集上的单个时期并以 Nesterov 的加速速率收敛，解决了从 DP 持续计数中生成相关噪声的问题，最后还展示了我们的算法在 MNIST 和 CIFAR-10 上对多类逻辑回归的优越性。

    Jun, 2024

  • 隐私随机凸优化：在线性时间的最优收敛率

    本文提出两种新的不同 ially private 的方法，实现了凸优化的最优解，使用较少的梯度计算，同时需要对数据有轻度平滑性的假设。

    May, 2020

  • 重尾数据的差分隐私随机凸优化的改进速率

    本文研究带有重尾数据的随机凸优化问题，并在差分隐私（DP）约束条件下进行研究。该文提出了一种新的算法用于估计重尾数据的均值，并针对凸损失函数提供了改进的上界。同时，证明了私密随机凸优化的几乎匹配下界，这表明了纯 DP 和集中 DP 之间的新分离。

    Jun, 2021

  • 用户隐私学习

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

    Feb, 2021