Jul, 2021

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

PDF
TL;DR本文中，我们首次对 DP-SCO 问题的高维重尾数据进行了研究，提出了在约束为多面体的情况下的误差频率及其限制，进一步在 LASSO 和稀疏学习问题中讨论了误差限制。
differentially privateconvex optimizationheavy-tailed datahigh-dimensional spacesparse learning
发现论文，激发创造
  • 带重尾数据的差分隐私随机凸优化

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

    Oct, 2020

  • 简化的简单降维的大尾部私密随机凸优化近乎最优解

    我们研究了具有重尾梯度的差分隐私随机凸优化（DP-SCO）问题，在这里我们假设样本函数的 Lipschitz 常数具有 k 次矩界而不是统一界。我们提出了一种新的基于约束的方法，使我们能够在重尾设置中获得首个最优速率（达到对数因子），在（ε，δ）- 近似差分隐私下，实现误差 G2⋅1/√n+Gk⋅(√d/nε)^(1-1/k)，几乎匹配于 [Lowy and Razaviyayn 2023] 的下界。在额外假设下，我们进一步给出了一套重尾设置的私有算法，包括在已知 Lipschitz 常数假设下的最优算法，平滑函数的近线性时间算法以及平滑广义线性模型的最优线性时间算法。

    Jun, 2024

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

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

    Jun, 2021

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

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

    Mar, 2021

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

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

    Jun, 2022

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

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

    Nov, 2023

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

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

    Aug, 2019

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

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

    May, 2020

  • 重尾扰动下的噪声 (S) GD 的差分隐私

    通过向随机梯度下降算法的迭代中注入重尾噪声，可以实现隐私保护，并且与高斯分布相比，重尾噪声具有相似的差分隐私保证，为一种可行的选择。

    Mar, 2024

  • 用户级私有凸优化

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

    May, 2023