Nov, 2023

满足 KL 条件的差分私有非凸优化及最优速率

PDF
TL;DR我们研究基于差分隐私的私有经验风险最小化问题，其中损失函数满足（γ，κ）-Kurdyka-Lojasiewicz 条件。当损失函数是利普希茨且光滑的时候，我们提出了一种基于方差减少梯度下降的新算法，并在超过经验风险的速率达到了几乎最优。当 KL 参数未知时，我们对噪声梯度下降算法进行了修改和分析，并证明了该算法在适应性上的性能几乎最优。同时，我们还展示了在不假设 KL 条件的情况下，同样的梯度下降算法可以以快速的收敛速度逼近利普希茨、光滑（甚至非凸）目标的驻点。
private empirical risk minimizationkurdyka-lojasiewicz conditiondifferential privacyvariance reduced gradient descentnoisy gradient descent algorithm
发现论文，激发创造
  • 重新审视差分隐私的经验风险最小化问题：更快且更广泛

    本文研究不同设置下差分隐私经验风险最小化问题，提出了比以前更少的梯度复杂度的算法，并从凸损失函数推广到满足 Polyak-Lojasiewicz 条件的非凸函数，给出比传统算法更紧的上界。

    Feb, 2018

  • 隐私保护随机优化：凸和非凸设置下的新结果

    本文研究隐私保护随机优化问题在凸性和非凸性情况下的解决方案，并给出了针对不同损失函数的最优算法，其中包括 non-smooth generalized linear losses（GLLs）和多种约束条件以及多种平滑系数的情况。

    Jul, 2021

  • 差分隐私经验风险最小化：高效算法和严格误差界

    本文为凸经验风险最小化问题提供了一系列不同的差分隐私算法，并同时给出了相应的下界，且不同的隐私模型需要使用完全不同的算法，这些算法在多项式时间内运行，并且适用于很多简单光滑的函数家族。

    May, 2014

  • 平滑目标高效的私有 ERM

    本文综述了不同凸且光滑目标函数的梯度下降算法与输出扰动方法，不仅能达到近乎最优的效用，而且也提高了以前的隐私优化算法的运行时间。同时，对于非凸光滑目标函数，还提出了 RRPSGD 算法，并附上了隐私保障的收敛性证明。实验表明，我们的算法在效益和运行时间方面始终优于现有方法。

    Mar, 2017

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

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

    May, 2020

  • 如何私下减小梯度：改进的差分隐私非凸优化速率

    我们提供了一个简单灵活的框架，用于设计差分隐私算法以找到非凸损失函数的近似稳定点。我们的框架基于使用私有近似风险最小化器来 “预热” 另一个用于寻找稳定点的私有算法。我们将这一框架应用于多个类别的非凸损失函数中，获得了改进的且有时是最优的速率。

    Feb, 2024

  • 差分隐私的非交互式局部模型中的经验风险最小化

    本文研究了在非交互式局部差分隐私（LDP）模型下经验风险最小化（ERM）问题，利用 Bernstein 多项式逼近方法和内积多项式逼近技术提出了两种解决高维数据下样本复杂度指数级上升的方法，最终提出了用于学习 k 维边际查询和平滑查询的（高效的）非交互式局部差分隐私算法。

    Nov, 2020

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

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

    Aug, 2019

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

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

    Jun, 2021

  • 指数机制下的私有凸优化

    本文介绍了一个基于指数机制和加正则化项的方法，用于解决凸函数私人优化问题，并证明了其满足 Differential Privacy 和 Gaussian Differential Privacy，同时提出了实现这种机制的方法及其采样器

    Mar, 2022